nach oben

2008 | Buch

Kapitel lesen Erstes Kapitel lesen

Building Bridges

Between Mathematics and Computer Science

herausgegeben von: Martin Grötschel, Gyula O. H. Katona, Gábor Sági

Verlag: Springer Berlin Heidelberg

Buchreihe : Bolyai Society Mathematical Studies

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Discrete mathematics and theoretical computer science are closely linked research areas with strong impacts on applications and various other scientific disciplines. Both fields deeply cross fertilize each other. One of the persons who particularly contributed to building bridges between these and many other areas is László Lovász, a scholar whose outstanding scientific work has defined and shaped many research directions in the last 40 years. A number of friends and colleagues, all top authorities in their fields of expertise and all invited plenary speakers at one of two conferences in August 2008 in Hungary, both celebrating Lovász’s 60th birthday, have contributed their latest research papers to this volume. This collection of articles offers an excellent view on the state of combinatorics and related topics and will be of interest for experienced specialists as well as young researchers.

Inhaltsverzeichnis

Frontmatter

On the Power of Linear Dependencies

Abstract

Simple as they may be, linear dependencies have proved very useful in many ways. In this survey several geometric applications of linear dependencies are discussed, focusing on rearrangements of sums and on sums with ±1 signs.

Imre Bárány

Surplus of Graphs and the Lovász Local Lemma

Abstract

The Surplus is a game-theoretic graph parameter. To illustrate it in a special case, suppose that two players, called Maker and Breaker, are playing on an n×n chessboard, and alternately mark previously unmarked little squares. Maker uses (say) mark X and Breaker uses (say) O, exactly like in Tic-Tac-Toe; Maker’s goal is to achieve a large lead in some line, where a “line” means either a row or a column. Let $ \frac{n} {2} + \Delta $ denote the maximum number of Xs (“Maker’s mark”) in some line at the end of a play; then the difference $ \left( {\frac{n} {2} + \Delta } \right) - \left( {\frac{n} {2} - \Delta } \right) = 2\Delta $ is Maker’s lead; Maker wants to maximize Δ = Δ(n). Since Δ = Δ = Δ(n) can be a half-integer (it happens when n is odd), and it is customary to work with integral graph parameters (like chromatic number), I prefer to call 2Δ = 2Δ(n) the Surplus of the n×n board (and refer to Δ = Δ(n) as the half-surplus). That is, the Surplus is the maximum terminal lead that Maker can always achieve against a perfect opponent. (In other words, Surplus is a game-theoretic one-sided discrepancy concept.)

József Beck

Deformable Polygon Representation and Near-Mincuts

Abstract

We derive a necessary and sufficient condition for a symmetric family of sets to have a geometric representation involving a convex polygon and some of its diagonals. We show that cuts of value less than 6/5 times the edge-connectivity of a graph admit such a representation, thereby extending the cactus representation of all mincuts.

András A. Benczúr, Michel X. Goemans

Variations for Lovász’ Submodular Ideas

Abstract

In [18], L. Lovász provided simple and short proofs for two classic min-max theorems of graph theory by inventing basic techniques to handle sub- or supermodular functions. In this paper, we want to demonstrate that these ideas are alive after thirty years of their birth.

Kristóf Bérczi, András Frank

Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries

Abstract

The starting point is the known fact that some much-studied random walks on permutations, such as the Tsetlin library, arise from walks on real hyperplane arrangements. This paper explores similar walks on complex hyperplane arrangements. This is achieved by involving certain cell complexes naturally associated with the arrangement. In a particular case this leads to walks on libraries with several shelves.

We also show that interval greedoids give rise to random walks belonging to the same general family. Members of this family of Markow chains, based on certain semigroups, have the property that all eigenvalues of the transition matrices are non-negative real and given by a simple combinatorial formula.

Background material needed for understanding the walks is reviewed in rather great detail.

Anders Björner

The Finite Field Kakeya Problem

Abstract

A Besicovitch set in AG(n, q) is a set of points containing a line in every direction. The Kakeya problem is to determine the minimal size of such a set. We solve the Kakeya problem in the plane, and substantially improve the known bounds for n>4.

Aart Blokhuis, Francesco Mazzocca

An Abstract Szemerédi Regularity Lemma

Abstract

We extend Szemerédi’sRegularity Lemma to abstract measure spaces.

Béla Bollobás, Vladimir Nikiforov

Isotropic PCA and Affine-Invariant Clustering

Abstract

We present an extension of Principal Component Analysis (PCA) and a new algorithm for clustering points in Rⁿ based on it. The key property of the algorithm is that it is affine-invariant. When the input is a sample from a mixture of two arbitrary Gaussians, the algorithm correctly classifies the sample assuming only that the two components are separable by a hyperplane, i.e., there exists a halfspace that contains most of one Gaussian and almost none of the other in probability mass. This is nearly the best possible, improving known results substantially [15, 10, 1]. For k>2 components, the algorithm requires only that there be some (k−1)-dimensional subspace in which the overlap in every direction is small. Here we define overlap to be the ratio of the following two quantities: 1) the average squared distance between a point and the mean of its component, and 2) the average squared distance between a point and the mean of the mixture. The main result may also be stated in the language of linear discriminant analysis: if the standard Fisher discriminant [9] is small enough, labels are not needed to estimate the optimal subspace for projection. Our main tools are isotropic transformation, spectral projection and a simple reweighting technique. We call this combination isotropic PCA.

S.Charles Brubaker, Santosh S. Vempala

Small Linear Dependencies for Binary Vectors of Low Weight

Abstract

We show that every set of $ m \simeq cn \sqrt {n log log n} $ vectors in {0, 1}ⁿ in which every vector has Hamming weight 3 contains a subset of {tiO(log n) vectors that form a linear dependency. Our proof is based on showing that in every graph of average degree at least c log log n, every legal edge coloring produces a cycle in which one of the colors appears either once or twice.} (In both results, c is some constant.) The results proved are used (in a companion work) in refutation algorithms for semirandom 3CNF formulas.

Uriel Feige

Plünnecke’s Inequality for Different Summands

Abstract

The aim of this paper is to prove a general version of Plünnecke’s inequality. Namely, assume that for finite sets A, B ₁,…,B _k we have information on the size of the sumsets A+Bi ₁+…+Bi _l for all choices of indices i ₁,…,i _l. Then we prove the existence of a non-empty subset X of A such that we have good control’ over the size of the sumset X+B ₁+…+B _k. As an application of this result we generalize an inequality of [1] concerning the submultiplicativity of cardinalities of sumsets.

Katalin Gyarmati, Máté Matolcsi, Imre Z. Ruzsa

Decoupling and Partial Independence

Abstract

The initial motivation of this note was the question: How many samples are needed to approximate the inertia matrix (variance-covariance matrix) of a density on R ⁿ? It first arose in a joint paper with L. Lovász and M. Simonovits on an algorithm for computing volumes of convex sets. Rudelson proved a very interesting result (answering the question) based on a classical theorem from Functional Analysis (see Square Form Theorem below) due to Lust-Piquard, which is proved using the beautiful technique of Decoupling. This note gives a self-contained proof of the theorem and its application to this problem as well as a different question dealing with extending the basic result of Random Matrix Theory to partially random matrices (see Theorem 3) below.

Ravi Kannan

Combinatorial Problems in Chip Design

Abstract

The design of very large scale integrated (VLSI) chips is an exciting area of applying mathematics, posing constantly new challenges.

We present some important and challenging open problems in various areas of chip design. Although the problems are motivated by chip design, they are formulated mathematically; understanding and solving them does not require any knowledge of chip design. We give some partial results and argue why a full resolution of one of the problems could result in an advance of the state of the art in algorithms for chip design.

Bernhard Korte, Jens Vygen

Structural Properties of Sparse Graphs

Abstract

In this chapter we briefly outline the main motivation of our work and we relate it to other research. We do not include any definition here.

Jaroslav NeŠetřil, Patrice Ossona De Mendez

Recent Progress in Matching Extension

Abstract

Let G be a graph with at least 2n+2 vertices, where n is a non-negative integer. The graph G is said to be n-extendable if every matching of size n in G extends to (i.e., is a subset of) a perfect matching. The study of this concept began in earnest in the 1980’s, although it was born out of the study of canonical matching decompositions carried out in the 1970’s and before. As is often the case, in retrospect it is apparent that there are roots of this topic to be found even earlier.

In the present paper, we will begin with a brief history of the subject and then concentrate on reviewing results on n-extendability and closely related areas obtained in the last ten-fifteen years, as there already exist two surveys of the subject in 1994 and 1996, respectively.

Michael D. Plummer

The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) × n

Abstract

The complex of maximal lattice free bodies associated with a well behaved matrix A of size (n+1)×n is generated by a finite set of simplicies, K ⁰(A), of the form 0, h¹, …, h ^k∼, with k≤n, and their lattice translates. The simplicies in K ⁰(A) are selected so that the plane a ⁰ x=0, with a ⁰ the first row of A, passes through the vertex 0. The collection of simplicies h ¹, …, h ^k is denoted by Top. Various properties of Top are demonstrated, including the fact that no two interior faces of Top are lattice translates of each other. Moreover, if g is a generator of the cone generated by the set of neighbors h with a ⁰ h>0, then the set of simplicies of Top which contain g is the union of linear intervals of simplicies with special features. These features lead to an algorithm for calculating the simplicies in K ₀(A) as a ⁰ varies and the plane a ⁰ x=0 passes through the generator g.

Herbert E. Scarf

Graph Invariants in the Edge Model

Abstract

We sharpen the characterization of Szegedy of graph invariants

$$ f_b (G) = \sum\limits_{\varphi : EG \to [n]} { \prod\limits_{\upsilon \in V G} {b(\varphi (\delta (\upsilon )))} } , $$

where b is a real-valued function defined on the collection of all multisubsets of [n]:= {1,… n}.

Alexander Schrijver

Incidences and the Spectra of Graphs

Abstract

In this paper we give incidence bounds for arrangements of curves in $ \mathbb{F}_q^2 $. As an application, we prove a new result that if (x, f(x)) is a Sidon set then either A+A or f(A) + f(A) should be large. The main goal of the paper is to illustrate the use of graph spectral techniques in additive combinatorics.

József Solymos

The Maturation of the Probabilistic Method

Abstract

In this historical review we discuss probability results of László Lovász and Svante Janson. These results have, we feel, played a central role in the development of the Probabilistic Method.

Joel Spencer

A Structural Approach to Subset-Sum Problems

Abstract

We discuss a structural approach to subset-sum problems in additive combinatorics. The core of this approach are Freiman-type structural theorems, many of which will be presented through the paper. These results have applications in various areas, such as number theory, combinatorics and mathematical physics.

Van Vu

Titel: Building Bridges
herausgegeben von: Martin Grötschel
Gyula O. H. Katona
Gábor Sági
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-85221-6
Print ISBN: 978-3-540-85218-6
DOI: https://doi.org/10.1007/978-3-540-85221-6

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

On the Power of Linear Dependencies

Surplus of Graphs and the Lovász Local Lemma

Deformable Polygon Representation and Near-Mincuts

Variations for Lovász’ Submodular Ideas

Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries

The Finite Field Kakeya Problem

An Abstract Szemerédi Regularity Lemma

Isotropic PCA and Affine-Invariant Clustering

Small Linear Dependencies for Binary Vectors of Low Weight

Plünnecke’s Inequality for Different Summands

Decoupling and Partial Independence

Combinatorial Problems in Chip Design

Structural Properties of Sparse Graphs

Recent Progress in Matching Extension

The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) × n

Graph Invariants in the Edge Model

Incidences and the Spectra of Graphs

The Maturation of the Probabilistic Method

A Structural Approach to Subset-Sum Problems

Premium Partner