Skip to main content

2019 | Buch

Building Bridges II

Mathematics of László Lovász

herausgegeben von: Prof. Imre Bárány, Prof. Gyula O. H. Katona, Dr. Attila Sali

Verlag: Springer Berlin Heidelberg

Buchreihe : Bolyai Society Mathematical Studies

insite
SUCHEN

Über dieses Buch

This volume collects together research and survey papers written by invited speakers of the conference celebrating the 70th birthday of László Lovász.

The topics covered include classical subjects such as extremal graph theory, coding theory, design theory, applications of linear algebra and combinatorial optimization, as well as recent trends such as extensions of graph limits, online or statistical versions of classical combinatorial problems, and new methods of derandomization.

László Lovász is one of the pioneers in the interplay between discrete and continuous mathematics, and is a master at establishing unexpected connections, “building bridges” between seemingly distant fields. His invariably elegant and powerful ideas have produced new subfields in many areas, and his outstanding scientific work has defined and shaped many research directions in the last 50 years.

The 14 contributions presented in this volume, all of which are connected to László Lovász's areas of research, offer an excellent overview of the state of the art of combinatorics and related topics and will be of interest to experienced specialists as well as young researchers.

Inhaltsverzeichnis

Frontmatter
Lovász, Vectors, Graphs and Codes
Abstract
A family of high-degree triangle-free pseudo-random Cayley graphs has been constructed in (Alon, Electro J Combin 1(R12):8, 1994 [2]), motivated by a geometric question of Lovász. These graphs turned out to be useful in tackling a variety of additional extremal problems in Graph Theory and Coding Theory. Here we describe the graphs and their applications, and mention several intriguing related open problems. This is mainly a survey, but it contains several new results as well. One of these is a construction showing that the Lovász \(\theta \)-function of a graph cannot be bounded by any function of its Shannon capacity.
Noga Alon
Continuous Matroids Revisited
Abstract
Here we look back at some work done in the mid-1980s in collaboration with László Lovász. Our main concern at that time was to provide conditions that make it possible to pass to the limit of a class of finite matroids. With the current flurry of interest in limits of combinatorial objects, a review of such matroid limits seems timely. The characteristic property of a continuous matroid is the existence of a rank function taking as values the full real unit interval. Known examples of such rank functions include Lebesgue measure on the unit interval and the dimension function of certain von Neumann algebras. In both these cases the lattice property of modularity plays a crucial role. A more general concept, pseudomodularity, makes possible the construction of e.g. continuous field extensions (algebraic matroids) and continuous partition lattices (graphic matroids).
Anders Björner
Identifiability for Graphexes and the Weak Kernel Metric
Abstract
In two recent papers by Veitch and Roy and by Borgs, Chayes, Cohn, and Holden, a new class of sparse random graph processes based on the concept of graphexes over \(\sigma \)-finite measure spaces has been introduced. In this paper, we introduce a metric for graphexes that generalizes the cut metric for the graphons of the dense theory of graph convergence. We show that a sequence of graphexes converges in this metric if and only if the sequence of graph processes generated by the graphexes converges in distribution. In the course of the proof, we establish a regularity lemma and determine which sets of graphexes are precompact under our metric. Finally, we establish an identifiability theorem, characterizing when two graphexes are equivalent in the sense that they lead to the same process of random graphs.
Christian Borgs, Jennifer T. Chayes, Henry Cohn, László Miklós Lovász
Online Ramsey Numbers and the Subgraph Query Problem
Abstract
The (mn)-online Ramsey game is a combinatorial game between two players, Builder and Painter. Starting from an infinite set of isolated vertices, Builder draws an edge on each turn and Painter immediately paints it red or blue. Builder’s goal is to force Painter to create either a red \(K_m\) or a blue \(K_n\) using as few turns as possible. The online Ramsey number \(\tilde{r}(m,n)\) is the minimum number of edges Builder needs to guarantee a win in the (mn)-online Ramsey game. By analyzing the special case where Painter plays randomly, we obtain an exponential improvement \(\tilde{r}(n,n) \ge 2^{(2-\sqrt{2})n + O(1)}\) for the lower bound on the diagonal online Ramsey number, as well as a corresponding improvement \(\tilde{r}(m,n) \ge n^{(2-\sqrt{2})m + O(1)}\) for the off-diagonal case, where \(m\ge 3\) is fixed and \(n\rightarrow \infty \). Using a different randomized Painter strategy, we prove that \(\tilde{r}(3,n)=\tilde{\Theta }(n^3)\), determining this function up to a polylogarithmic factor. We also improve the upper bound in the off-diagonal case for \(m \ge 4\). In connection with the online Ramsey game with a random Painter, we study the problem of finding a copy of a target graph H in a sufficiently large unknown Erdős–Rényi random graph G(Np) using as few queries as possible, where each query reveals whether or not a particular pair of vertices are adjacent. We call this problem the Subgraph Query Problem. We determine the order of the number of queries needed for complete graphs up to five vertices and prove general bounds for this problem.
David Conlon, Jacob Fox, Andrey Grinshpun, Xiaoyu He
Statistical Matching Theory
Abstract
In this paper, we survey some recent developments on statistical properties of matchings of very large and infinite graphs. We discuss extremal graph theoretic results like Schrijver’s theorem on the number of perfect matchings of regular bipartite graphs and its variants from the point of view of graph limit theory. We also study the number of matchings of finite and infinite vertex-transitive graphs.
Péter Csikvári
Sequential Importance Sampling for Estimating the Number of Perfect Matchings in Bipartite Graphs: An Ongoing Conversation with Laci
Abstract
Sequential importance sampling offers an alternative way to approximately evaluate the permanent. It is a stochastic algorithm which seems to work in practice but has eluded analysis. This paper offers examples where the analysis can be carried out and the first general bounds for the sample size required. This uses a novel importance sampling proof of Brégman’s inequality due to Lovász.
Persi Diaconis
Tighter Bounds for Online Bipartite Matching
Abstract
We study the online bipartite matching problem, introduced by Karp, Vazirani and Vazirani [1990]. For bipartite graphs with matchings of size n, it is known that the Ranking randomized algorithm matches at least \((1 - \frac{1}{e})n\) edges in expectation. It is also known that no online algorithm matches more than \((1 - \frac{1}{e})n + O(1)\) edges in expectation, when the input is chosen from a certain distribution that we refer to as \(D_n\). This upper bound also applies to fractional matchings. We review the known proofs for this last statement. In passing we observe that the O(1) additive term (in the upper bound for fractional matching) is \(\frac{1}{2} - \frac{1}{2e} + O(\frac{1}{n})\), and that this term is tight: the online algorithm known as Balance indeed produces a fractional matching of this size. We provide a new proof that exactly characterizes the expected cardinality of the (integral) matching produced by Ranking when the input graph comes from the support of \(D_n\). This expectation turns out to be \((1 - \frac{1}{e})n + 1 - \frac{2}{e} + O(\frac{1}{n!})\), and serves as an upper bound on the performance ratio of any online (integral) matching algorithm.
Uriel Feige
Minimum Cost Globally Rigid Subgraphs
Abstract
A d-dimensional framework is a pair (Gp), where \(G=(V,E)\) is a graph and p is a map from V to \(\mathbb {R}^d\). The length of an edge of G is equal to the distance between the points corresponding to its end-vertices. The framework is said to be globally rigid if its edge lengths uniquely determine all pairwise distances in the framework. A graph G is called globally rigid in \(\mathbb {R}^d\) if every generic d-dimensional framework (Gp) is globally rigid. Global rigidity has applications in wireless sensor network localization, molecular conformation, formation control, CAD, and elsewhere. Motivated by these applications we consider the following optimization problem: given a graph \(G=(V,E)\), a non-negative cost function \(c:E\rightarrow \mathbb {R}_{+}\) on the edge set of G, and a positive integer d. Find a subgraph \(H=(V,E')\) of G, on the same vertex set, which is globally rigid in \(\mathbb {R}^d\) and for which the total cost \(c(E'):=\sum _{e\in E'} c(e)\) of the edges is as small as possible. This problem is NP-hard for all \(d\ge 1\), even if c is uniform or G is complete and c is metric. We focus on the two-dimensional case, where we give \(\frac{3}{2}\)-approximation (resp. 2-approximation) algorithms for the uniform cost and metric versions. We also develop a constant factor approximation algorithm for the metric version of the d-dimensional problem, for every \(d\ge 3\).
Tibor Jordán, András Mihálykó
Coloured and Directed Designs
Abstract
We give some illustrative applications of our recent result on decompositions of labelled complexes, including some new results on decompositions of hypergraphs with coloured or directed edges. For example, we give fairly general conditions for decomposing an edge-coloured graph into rainbow triangles, and for decomposing an r-digraph into tight q-cycles.
Peter Keevash
Efficient Convex Optimization with Oracles
Abstract
Minimizing a convex function over a convex set is a basic algorithmic problem. We give a simple algorithm for the general setting in which the function is given by an evaluation oracle and the set by a membership oracle. The algorithm takes \(\widetilde{O}(n^{2})\) oracle calls and \(\widetilde{O}(n^{3})\) additional arithmetic operations. This results in more efficient reductions among the five basic oracles for convex sets and functions defined by Grötschel, Lovász and Schrijver (Algorithms Comb 2, (1988), [5]).
Yin Tat Lee, Aaron Sidford, Santosh S. Vempala
Approximations of Mappings
Abstract
We consider mappings, which are structure consisting of a single function (and possibly some number of unary relations) and address the problem of approximating a continuous mapping by a finite mapping. This problem is the inverse problem of the construction of a continuous limit for first-order convergent sequences of finite mappings. We solve the approximation problem and, consequently, the full characterization of limit objects for mappings for first-order (i.e. \(\mathrm{FO}\)) convergence and local (i.e. \(\mathrm{FO}^\mathrm{local}\)) convergence. This work can be seen both as a first step in the resolution of inverse problems (like Aldous–Lyons conjecture) and a strengthening of the classical decidability result for finite satisfiability in Rabin class (which consists of first-order logic with equality, one unary function, and an arbitrary number of monadic predicates). The proof involves model theory and analytic techniques.
Jaroslav Nešetřil, Patrice Ossona de Mendez
Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization
Abstract
This paper presents a deterministic, strongly polynomial time algorithm for computing the matrix rank for a class of symbolic matrices (whose entries are polynomials over a field). This class was introduced, in a different language, by Lovász [16] in his study of flats in matroids, and proved a duality theorem putting this problem in \(NP \cap coNP\). As such, our result is another demonstration where “good characterization” in the sense of Edmonds leads to an efficient algorithm. In a different paper Lovász [17] proved that all such symbolic rank problems have efficient probabilistic algorithms, namely are in BPP. As such, our algorithm may be interpreted as a derandomization result, in the long sequence special cases of the PIT (Polynomial Identity Testing) problem. Finally, Lovász and Yemini [20] showed how the same problem generalizes the graph rigidity problem in two dimensions. As such, our algorithm may be seen as a generalization of the well-known deterministic algorithm for the latter problem. There are two somewhat unusual technical features in this paper. The first is the translation of Lovász’ flats problem into a symbolic rank one. The second is the use of submodular optimization for derandomization. We hope that the tools developed for both will be useful for related problems, in particular for better understanding of graph rigidity in higher dimensions.
Orit E. Raz, Avi Wigderson
Finding k Partially Disjoint Paths in a Directed Planar Graph
Abstract
The partially disjoint paths problem is: given: a directed graph, vertices \(r_1,s_1,\ldots ,r_k,s_k\), and a set F of pairs \(\{i,j\}\) from \(\{1,\ldots ,k\}\), find: for each \(i=1,\ldots ,k\) a directed \(r_i-s_i\) path \(P_i\) such that if \(\{i,j\}\in F\) then \(P_i\) and \(P_j\) are disjoint. We show that for fixed k, this problem is solvable in polynomial time if the directed graph is planar. More generally, the problem is solvable in polynomial time for directed graphs embedded on a fixed compact surface. Moreover, one may specify for each edge a subset of \(\{1,\ldots ,k\}\) prescribing which of the \(r_i-s_i\) paths are allowed to traverse this edge.
Alexander Schrijver
Embedding Graphs into Larger Graphs: Results, Methods, and Problems
Abstract
Extremal Graph Theory is a very deep and wide area of modern combinatorics. It is very fast developing, and in this long but relatively short survey we select some of those results which either we feel very important in this field or which are new breakthrough results, or which—for some other reasons—are very close to us. Some results discussed here got stronger emphasis, since they are connected to Lovász (and sometimes to us).
Miklós Simonovits, Endre Szemerédi
Backmatter
Metadaten
Titel
Building Bridges II
herausgegeben von
Prof. Imre Bárány
Prof. Gyula O. H. Katona
Dr. Attila Sali
Copyright-Jahr
2019
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-59204-5
Print ISBN
978-3-662-59203-8
DOI
https://doi.org/10.1007/978-3-662-59204-5