Combinatorial Theory Seminar

I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on odd and even cycles. Erdős and Hajnal asked in 1981 whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases, while, in 1984, Erdős asked whether there is a constant $C$ such that every graph with average degree at least $C$ contains a cycle whose length is a power of 2.

We generalize the fact that all graphs omitting a fixed finite bipartite graph can be uniformly approximated by rectangles (Alon-Fischer-Newman, Lovász-Szegedy), showing that hypergraphs omitting a fixed finite $(k+1)$-partite $(k+1)$-uniform hypergraph can be approximated by $k$-ary cylinder sets. In particular, in the decomposition given by hypergraph regularity one only needs the first $k$ levels: such hypergraphs can be approximated using sets of vertices, sets of pairs, and so on up to sets of $k$-tuples, and on most of the resulting $k$-ary cylinder sets, the density is either close to 0 or close to 1. Moreover, existence of such approximations uniformly under all measures on the vertices is a characterization. Our proof uses a combination of analytic, combinatorial and model-theoretic methods, and involves a certain higher arity generalization of the epsilon-net theorem from VC-theory.  Joint work with Henry Towsner.

The Schmidt subspace theorem is a far-reaching generalization of the Thue-Siegel-Roth theorem in diophantine approximation. In this talk I will give an interpretation of Schmidt's subspace theorem in terms of the dynamics of diagonal flows on homogeneous spaces and describe how the exceptional subspaces arise from certain rational Schubert varieties associated to the family of linear forms through the notion of Harder-Narasimhan filtration and an associated slope formalism. This geometric understanding opens the way to a natural generalization of Schmidt's theorem to the setting of diophantine approximation on submanifolds of $GL_d$, which is our main result. In turn this allows us to recover and generalize the main results of Kleinbock and Margulis regarding diophantine exponents of submanifolds. I will also mention an application to diophantine approximation on Lie groups. Joint work with Nicolas de Saxcé.

This talk will focus on the following two related problems:
    (1) What is the minimum number of edges in a graph containing all $n$-vertex planar graphs as subgraphs? A simple construction of Babai, Erdos, Chung, Graham, and Spencer (1982) has $O(n^{3/2})$ edges, which is the best known upper bound.
    (2) What is the minimum number of *vertices* in a graph containing all $n$-vertex planar graphs as *induced* subgraphs? Here steady progress has been achieved over the years, culminating in a $O(n^{4/3})$ bound due to Bonamy, Gavoille, and Pilipczuk (2019).
    As it turns out, a bound of $n^{1+o(1)}$ can be achieved for each of these two problems. The two constructions are somewhat different but are based on a common technique. In this talk I will first give a gentle introduction to the area and then sketch these constructions. The talk is based on joint works with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.

What is fairness, and to what extent is it practically achievable? I'll talk about a simple mathematical model under which one might hope to understand such questions. Red and blue points occur as independent homogeneous Poisson processes of equal intensity in Euclidean space, and we try to match them to each other. We would like to minimize the sum of a some function (say, a power, $\gamma$) of the distances between matched pairs. This does not make sense, because the sum is infinite, so instead we satisfy ourselves with minimizing *locally*. If the points are interpreted as agents who would like to be matched as close as possible, the parameter $\gamma$ encodes a measure of fairness - large $\gamma$ means that we try to avoid occasional very bad outcomes (long edges), even if that means inconvenience to others - small $\gamma$ means everyone is in it for themselves.
    In dimension 1 we have a reasonably complete picture, with a phase transition at $\gamma=1$. For $\gamma<1$ there is a unique minimal matching, while for $\gamma>1$ there are multiple matchings but no stationary solution. In higher dimensions, even existence is not clear in all cases.

A spanning tree of $G$ is a subgraph of $G$ with the same vertex set as $G$ that is a tree. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in random $k$-regular graphs, showing that the number of spanning trees $\kappa_1(G_n)$ in a random $k$-regular graph on $n$ vertices satisfies $\lim_{n \to \infty} (\kappa_1(G_n))^{1/n} = c_{1,k}$ in probability, where $c_{1,k} = (k-1)^{k-1} (k^2-2k)^{-(k-2)/2}$.

In this talk we will discuss a high-dimensional of the matching model for simplicial complexes, known as random Steiner complexes. In particular, we will prove a high-dimensional counterpart of McKay's result and discuss the local limit of such random complexes. 
Based on a joint work with Lior Tenenbaum. 

We study the minimum total weight of a disk triangulation using any number of vertices out of $\{1,..,n\}$ where the boundary is fixed and the $n \choose 3$ triangles have independent rate-1 exponential weights. We show that, with high probability, the minimum weight is equal to $(c+o(1))n-1/2\log n$ for an explicit constant $c$. Further, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle $(123)$ are both attained by the minimum weight disk triangulation. We will discuss a related open problem concerning simple-connectivity of random simplicial complexes, where a similar phenomenon is conjectured to hold. Based on joint works with Itai Benjamini, Eyal Lubetzky, and Zur Luria.

In long-range percolation on $\mathbb{Z}^d$, each potential edge $\{x,y\}$ is included independently at random with probability roughly $\beta\|x-y\|-d-\alpha$, where $\alpha > 0$ controls how long-range the model is and $\beta > 0$ is an intensity parameter. The smaller $\alpha$ is, the easier it is for very long edges to appear. We are normally interested in fixing $\alpha$ and studying the phase transition that occurs as $\beta$ is increased and an infinite cluster emerges. Perhaps surprisingly, the phase transition for long-range percolation is much better understood than that of nearest neighbour percolation, at least when $\alpha$ is small: It is a theorem of Noam Berger that if $\alpha < d$ then the phase transition is continuous, meaning that there are no infinite clusters at the critical value of $\beta$. (Proving the analogous result for nearest neighbour percolation is a notorious open problem!) In my talk I will describe a new, quantitative proof of Berger's theorem that yields power-law upper bounds on the distribution of the cluster of the origin at criticality.
    As a part of this proof, I will describe a new universal inequality stating that on any graph, the maximum size of a percolation cluster is of the same order as its median with high probability. This inequality can also be used to give streamlined new proofs of various classical results on e.g. Erdős-Rényi random graphs, which I will hopefully have time to talk a little bit about also.

I will present work in progress with D. Gayet and F. Pouran (Grenoble) to establish Russo-Seymour-Welsh (RSW) estimates for 2d statistical mechanics models that do not satisfy the FKG inequality. RSW states that critical percolation has no characteristic length, in the sense that large rectangles are crossed by an open path with a probability that is bounded below by a function of their shape, but uniformly in their size; this ensures the polynomial decay of many relevant quantities and opens the way to deeper understanding of the critical features of the model. All the standard proofs of RSW rely on the FKG inequality, i.e. on the positive correlation between increasing events; we establish the stability of RSW under small perturbations that do not preserve FKG, which extends it for instance to the high-temperature anti-ferromagnetic Ising model.

A connected matching is a matching contained in a connected component. A well-known method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs.
    
I will describe Łuczak's reduction, introduce the new reduction, and mention potential applications of the improved method.