We continue the study by Melo and Winter [arXiv:1712.01763, 2017] on the possible intersection sizes of a $k$-dimensional subspace with the vertices of the $n$-dimensional hypercube in Euclidean space. Melo and Winter conjectured that all intersection sizes larger than $2^{k-1}$ (the “large” sizes) are of the form $2^{k-1} + 2^i$. We show that this is almost true: the large intersection sizes are either of this form or of the form $35\cdot2^{k-6}$ . We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing.

# Past Combinatorial Theory Seminar

The classical theory of Erdős–Rényi random graphs is concerned primarily with random subgraphs of $K_n$ or $K_{n,n}$. Lately, there has been much interest in understanding random subgraphs of other graph families, such as regular graphs.

We study the following problem: Let $G$ be a $k$-regular bipartite graph with $2n$ vertices. Consider the random process where, beginning with $2n$ isolated vertices, $G$ is reconstructed by adding its edges one by one in a uniformly random order. An early result in the theory of random graphs states that if $G=K_{n,n}$, then with high probability a perfect matching appears at the same moment that the last isolated vertex disappears. We show that if $k = Ω(n)$, then this holds for any $k$-regular bipartite graph $G$. This improves on a result of Goel, Kapralov, and Khanna, who showed that with high probability a perfect matching appears after $O(n \log(n))$ edges have been added to the graph. On the other hand, if $k = o(n / (\log(n) \log (\log(n)))$, we construct a family of $k$-regular bipartite graphs in which isolated vertices disappear long before the appearance of perfect matchings.

Joint work with Roman Glebov and Zur Luria.

How long a monotone path can one always find in any edge-ordering of the complete graph $K_n$? This appealing question was first asked by Chvatal and Komlos in 1971, and has since attracted the attention of many researchers, inspiring a variety of related problems. The prevailing conjecture is that one can always find a monotone path of linear length, but until now the best known lower bound was $n^{2/3−o(1)}$, which was proved by Milans. This talk will be

about nearly closing this gap, proving that any edge-ordering of the complete graph contains a monotone path of length $n^{1−o(1)}$. This is joint work with Bucic, Kwan, Sudakov, Tran, and Wagner.

Let $G$ be a regular graph of degree $d$ and let $A\subset V(G)$. Say that $A$ is $\eta$-closed if the average degree of the subgraph induced by $A$ is at least $\eta d$. This says that if we choose a random vertex $x\in A$ and a random neighbour $y$ of $x$, then the probability that $y\in A$ is at least $\eta$. In recent joint work with Tim Gowers, we were aiming to obtain a qualitative description of closed subsets of the Cayley graph $\Gamma$ whose vertex set is $\mathbb{F}_2^{n_1}\otimes \dots \otimes \mathbb{F}_2^{n_d}$ with two vertices joined by an edge if their difference is of the form $u_1\otimes \cdots \otimes u_d$. For the matrix case (that is, when $d=2$), such a description was obtained by Khot, Minzer and Safra, a breakthrough that completed the proof of the 2-to-2 conjecture. We have formulated a conjecture for higher dimensions, and proved it in an important special case. In this talk, I will sketch this proof. Also, we have identified a statement about $\eta$-closed sets in Cayley graphs on arbitrary finite Abelian groups that implies the conjecture and can be considered as a "highly asymmetric Balog-Szemerédi-Gowers theorem" when it holds. I will present an example to show that this statement is not true for an arbitrary Cayley graph. It remains to decide whether the statement can be proved for the Cayley graph $\Gamma$.

The last remaining open problem from Erdős and Rényi's original paper on random graphs is the following: for q at least 3, what is the largest d so that the random graph G(n,d/n) is q-colorable with high probability? A lot of interesting work in probabilistic combinatorics has gone into proving better and better bounds on this q-coloring threshold, but the full answer remains elusive. However, a non-rigorous method from the statistical physics of glasses - the cavity method - gives a precise prediction for the threshold. I will give an introduction to the cavity method, with random graph coloring as the running example, and describe recent progress in making parts of the method rigorous, emphasizing the role played by tools from extremal combinatorics. Based on joint work with Amin Coja-Oghlan, Florent Krzakala, and Lenka Zdeborová.

It is difficult to determine when a graph G can be edge-covered by edge-disjoint copies of a fixed graph F. That is, when it has an F-decomposition. However, if G is large and has a high minimum degree then it has an F-decomposition, as long as some simple divisibility conditions hold. Recent research allows us to prove bounds on the necessary minimum degree by studying a relaxation of this problem, where a fractional decomposition is sought.

I will show how a relatively simple random process can give a good approximation to a fractional decomposition of a dense graph, and how it can then be made exact. This improves the best known bounds for this problem.

Consider a family of k-element subsets of an n-element set, and assume that the family does not contain s pairwise disjoint sets. The well-known Erdos Matching Conjecture suggests the maximum size of such a family. Finding the maximum is trivial for n<(s+1)k and is relatively easy for n large in comparison to s,k. There was a splash of activity around the conjecture in the recent years, and, as far as the original question is concerned, the best result is due to Peter Frankl, who verified the conjecture for all n>2sk. In this work, we improve the bound of Frankl for any k and large enough s. We also discuss the connection of the problem to an old question on deviations of sums of random variables going back to the work of Hoeffding and Shrikhande.

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a k-uniform hypergraph on n vertices that does not contain an 'enlarged' copy H^+ of a fixed hypergraph H. These include well-known problems such as the Erdős-Sós 'forbidding one intersection' problem and the Frankl-Füredi 'special simplex' problem.

In this talk we present a general approach to such problems, using a 'junta approximation method' that originates from analysis of Boolean functions. We prove that any (H^+)-free hypergraph is essentially contained in a 'junta' -- a hypergraph determined by a small number of vertices -- that is also (H^+)-free, which effectively reduces the extremal problem to an easier problem on juntas. Using this approach, we obtain, for all C<k<n/C, a complete solution of the extremal problem for a large class of H's, which includes the aforementioned problems, and solves them for a large new set of parameters.

Based on joint works with David Ellis and Nathan Keller

We prove that the dimension of every poset whose comparability graph has maximum degree $\Delta$ is at most $\Delta\log^{1+o(1)} \Delta$. This result improves on a 30-year old bound of F\"uredi and Kahn, and is within a $\log^{o(1)}\Delta$ factor of optimal. We prove this result via the notion of boxicity. The boxicity of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $\Delta$ has boxicity at most $\Delta\log^{1+o(1)} \Delta$, which is also within a $\log^{o(1)}\Delta$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $\Theta(\sqrt{g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a $O(1)$ factor. This is joint work with Alex Scott (arXiv:1804.03271).