Schedule for: 19w5009 - Workshop on Probabilistic and Extremal Combinatorics

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

In this talk, we solve a longstanding open problem of Erdős and Hajnal on off-diagonal hypergraph Ramsey numbers, and discuss a variety of related problems. Joint work with Xiaoyu He.

After a brief introduction to classical hypergraph Ramsey numbers, I will focus on the following problem. What is the minimum $t$ such that there exist arbitrarily large $k$-uniform hypergraphs whose independence number is at most polylogarithmic in the number of vertices and every $s$ vertices span at most $t$ edges? Erdos and Hajnal conjectured (1972) that this minimum can be calculated precisely using a recursive formula and Erdos offered a {$}500 prize for a proof. For $k = 3$, this has been settled for many values of $s$, but it was not known for larger $k$. We solve this problem for all $s>k>3$. This is joint work with Alexander Razborov.

We find Dirac-type sharp sufficient conditions for a hypergraph with few edges to have a hamiltonian Berge cycle. To do this, we exploit the language of bipartite graphs. In particular, we extend some results of Jackson on the existence of long cycles in bipartite graphs where the vertices in one part have high degrees, and prove his conjecture from 1981 on the topic. This is joint work with Ruth Luo and Dara Zirlin.

There has been substantial recent interest in extremal problems for ordered graphs, with the recent breakthrough of Marcus and Tardos on excluded permutations and the Stanley-Wilf and Furedi-Hajnal conjectures. We give a survey of selected results, techniques and applications, as well as new results and techniques for ordered hypergraphs, with applications to ordered trees in graphs, tight paths in hypergraphs, and directed paths in eulerian digraphs, amongst others. Joint work with Z. Furedi, T.Jiang, A. Kostochka, D. Mubayi

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle. Fix $0 < \alpha < 1$. Let $N_\alpha(d)$ denote the maximum number of lines in $\mathbb{R}^d$ with pairwise common angle $\arccos \alpha$. Let $k$ denote the minimum number (if it exists) of vertices of a graph whose adjacency matrix has spectral radius exactly $(1-\alpha)/(2\alpha)$. If $k < \infty$, then $N_\alpha(d) = \lfloor k(d-1)/(k-1) \rfloor$ for all sufficiently large $d$, and otherwise $N_\alpha(d) = d + o(d)$. In particular, $N_{1/(2k-1)}(d) = \lfloor k(d-1)/(k-1) \rfloor$ for every integer $k\geq 2$ and all sufficiently large $d$. A key ingredient is a new result in spectral graph theory: the adjacency matrix of a connected bounded degree graph has sublinear second eigenvalue multiplicity. (Joint with with Zilin Jiang, Jonathan Tidor, Yuan Yao, and Shengtong Zhang)

Let us fix a prime $p$. The Erdos-Ginzburg-Ziv problem asks for the minimum integer $s$ such that any collection of $s$ points in the lattice $Z^n$ contains $p$ points whose centroid is also a lattice point in $Z^n$. For large $n$, this is essentially equivalent to asking for the maximum size of a subset of $F_p^n$ without $p$ distinct elements summing to zero. In this talk, we discuss a new upper bound for this problem for any fixed prime $p \geq 5$ and large $n$. Our proof uses the so-called multi-colored sum-free theorem which is a consequence of the Croot-Lev-Pach polynomial method. However, these tools cannot be applied directly in our setting, and there has been work by several authors to apply these tools to the problem discussed here. Using some key new ideas, we significantly improve the previous bounds.

Let $m_d(k,n)$ be the minimal $m$ such that every $k$-uniform hypergraph on $n$ vertices and with minimum $d$-degree at least $m$ contains a perfect matching (of course, assuming that $n$ is divisible by $k$). The problem of determining $m_{d}(k,n)$ has attracted a lot of attention in the last few decades, and unfortunately is still far from being completely understood. For example, already the cases $d=1$ and $k\geq 6$ are unknown. In this talk we show that random hypergraphs typically behave as expected. Specifically, we prove (without knowing $m_d(k,n)$) that for a typical $H^k_{n,p}$ with $p\geq n^{-c(d,k)}$, every spanning subgraph with minimum $d$-degree at least $(1+o(1))m_d(k,n)p$ contains a perfect matching. This is clearly (asymptotically) best possible. Joint work with Matthew Kwan.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

What is the largest number of distinct projections onto $k$ coordinates guaranteed in every family of $m$ binary vectors of length $n$ ? This fundamental combinatorial question has applications in theoretical computer science, geometry, machine learning, probability and more, and is wide open for most settings of the parameters. I will briefly mention some of the history, motivation and known results, focusing on a recent asymptotic solution of the question, in joint work with Moshkovitz and Solomon, for linear $k$ and sub-exponential $m$.

A family $F$ of subsets of $[n]$ is called $s$-saturated if it contains no $s$ pairwise disjoint sets, and moreover, no set can be added to $F$ while preserving this property. Over 40 years ago, Erdos and Kleitman conjectured that an $s$-saturated family of subsets of $[n]$ has size at least $(1 - 2/(s-1))2n$. We show that every $s$-saturated family has size at least $(1 - 1/s)2n$, thus providing the first non-trivial progress on the conjecture.

In 1989, Rota made the following conjecture. Given $n$ bases $B_1,\ldots, B_n$ in an $n$-dimensional vector space $V$, one can always find $n$ disjoint bases of $V$, each containing exactly one element from each $B_i$ (we call such bases transversal bases). Rota’s basis conjecture remains open despite its apparent simplicity and the efforts of many researchers (for example, the conjecture was recently the subject of the collaborative “Polymath” project). In this talk, I will discuss how to find $(0.5 - o(1))n$ disjoint transversal bases, improving the previously best known bound of $n/\log n$. This is joint work with Bucic, Kwan, and Sudakov.

Consider a quadratic polynomial $f\left(\xi_{1},\dots,\xi_{n}\right)$ of independent Bernoulli random variables. What can be said about the concentration of $f$ on any single value? This generalises the classical Littlewood--Offord problem, which asks the same question for linear polynomials. As in the linear case, it is known that the point probabilities of $f$ can be as large as about $1/\sqrt{n}$, but still poorly understood is the ``inverse'' question of characterising the algebraic and arithmetic features $f$ must have if it has point probabilities comparable to this bound. In this talk we present some results of an algebraic flavour, showing that if $f$ has point probabilities much larger than $1/n$ then it must be close to a quadratic form with low rank. We also give an application to Ramsey graphs, asymptotically answering a question of Kwan, Sudakov and Tran. Joint work with Lisa Sauermann.

Understanding approximate minimisers for isoperimetric problems is of fundamental importance in Combinatorics, Analysis and Geometry. We will discuss recent progress on these problems in the combinatorial setting of the discrete cube (joint with Eoin Long) and the analytic setting of boolean functions with small influence, with applications to sharp thresholds and Extremal Combinatorics via the Junta Method (joint with Noam Lifshitz, Eoin Long and Dor Minzer).

Note that the vertices of the $n$-dimensional cube $\{0, 1\}^n$ can be covered by two affine hyperplanes $x_1=1$ and $x_1=0$. However if we leave one vertex uncovered, then suddenly at least $n$ affine hyperplanes are needed. This was a classical result of Alon and F\"uredi, followed from the Combinatorial Nullstellensatz. In this talk, we consider the following natural generalization of the Alon-F\"uredi theorem: what is the minimum number of affine hyperplanes such that the vertices in $\{0, 1\}^n \setminus \{\vec{0}\}$ are covered at least $k$ times, and $\vec{0}$ is uncovered? We answer the problem for $k \le 3$ and show that a minimum of $n+3$ affine hyperplanes is needed for $k=3$, using a punctured version of the Combinatorial Nullstellensatz. We also develop an analogue of the Lubell-Yamamoto-Meshalkin inequality for subset sums, and solve the problem asymptotically for fixed $n$ and $k \rightarrow \infty$, and pose a conjecture for fixed $k$ and large $n$. Joint work with Alexander Clifton (Emory University).

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)}$. We almost close 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 Matthew Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan Tran and Adam Wagner.

A finite number of people want to cut up a piece of cake amongst themselves `fairly'. How efficiently can they do this? Almost everything is known in the case where each of the $N$ people want $1/N$ of the cake. On the other hand, the more general problem where each person wants an arbitrary real fraction of the cake is rather poorly understood. In this talk, we shall improve considerably on classical, decades-old arguments from algebraic topology and report on an efficient, combinatorial procedure for the general problem that yields nearly optimal bounds. Joint work with Logan Crew and Sophie Spirkl.

Let $f_r(n, v, e)$ be the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices which contains no induced subgraph with $v$ vertices and at least $e$ edges. The Brown--Erd\H{o}s--S\'os problem of determining $f_r(n, v, e)$ is a central question in extremal combinatorics, with surprising connections to a number of seemingly unrelated areas. For example, the result of Ruzsa and Szemer\'edi that $f_3(n, 6, 3) = o(n^2)$ implies Roth's theorem on the existence of $3$-term arithmetic progressions in dense subsets of the integers. As a generalisation of this result, it is conjectured that $$f_r(n, e(r-k) + k + 1, e) = o(n^k)$$ for any fixed $r > k \geq 2$ and $e \geq 3$. The best progress towards this conjecture, due to S\'ark\"ozy and Selkow, says that $$f_r(n, e(r-k) + k + \lfloor \log e\rfloor, e) = o(n^k),$$ where the $\log$ is taken base two. In this talk, we will discuss a recent improvement to this bound.

An $r$-uniform hypergraph ($r$-graph for short) is simple if every pair of vertices belongs to at most one edge. A simple $r$-graph is complete if every pair of vertices is covered exactly once. The famous Brown-Erdos-Sos Conjecture states that for every fixed $k$ and $r$, every simple $r$-graph with $\Omega(n^2)$ edges contains $k$ edges spanned by at most $(r-2)k+3$ vertices. Addressing a question asked among others by D.Conlon and by R. Nenadov, we prove the following Ramsey variant of the Brown-Erdos-Sos Conjecture: For every $c$ and large enough $r$, in every $c$-coloring of a complete simple $r$-graph one can find a monochromatic collection of $k$ edges spanned by at most $(r-2)k+3$ vertices. Joint work with Asaf Shapira

Given a partial Steiner triple system (STS) of order n, what is the order of the smallest complete STS it can be embedded into? The study of this question goes back more than 40 years. In this talk we answer it for relatively sparse STSs, showing that given a partial STS of order n with at most $r \leq \epsilon n^2$ triples, it can always be embedded into a complete STS of order $n+O(\sqrt{r})$, which is asymptotically optimal. We also obtain similar results for completions of Latin squares and other designs. This suggests a new, natural class of questions, called deficiency problems. Given a global spanning property P and a graph G, we define the deficiency of the graph G with respect to the property P to be the smallest positive integer $t$ such that the join $G\ast K_t$ has property P. To illustrate this concept we consider deficiency versions of some well-studied properties, such as having a $K_k$-decomposition, Hamiltonicity, having a triangle-factor and having a perfect matching in hypergraphs. This is joint work with Rajko Nenadov and Benny Sudakov

Several problems in extremal combinatorics arise from a new generalization of the optimal coupling theorem to multiple random variables: Given a collection of random variables, it is possible to couple all of them so that any two differ with probability comparable to the total-variation distance between them. A typical problem is to maximize various functionals over a selection of an element from each subset of $[n]$ of size $k$.

If $v$ is a vertex in a graph $G$ we denote by $G_v$ the subgraph of $G$ induced on $v$’s neighbors. An $(a,b)$ graph is an $a$-regular graph where every $G_v$ is $b$-regular. Q1: For which $a>b>0$ integers do there exist arbitrarily large, connected $(a,b)$-graphs? Q2: Can such graphs be very good expanders? Q3: What if you require in addition that every $G_v$ be connected? Q4: Can you even make every $G_v$ a very good expander? In this talk I will provide some answers to these and related questions and still leave much to be considered on this domain. Joint work with Michael Chapman and Yuval Peled

The projective norm graphs $NG(q,t)$ provide tight constructions in the Tur\'an problem for complete bipartite graphs $K_{t,s}$ when $s>(t-1)!$. The $K_{t,s}$-freeness of $NG(q,t)$ is a very much atypical property: in a random graph with the same edge density a positive fraction of $t$-tuples are involved in a copy of $K_{t,s}$. Yet, projective normgraphs are random-like in various other senses. Most notably their second eigenvalue is of the order of the square root of the degree, which, through the Expander Mixing Lemma, implies further quasirandom properties concerning small subgraph densities. In the talk we will explore how far the quasirandomness of projective norm graphs goes. In particular we make progress, beyond the eigenvalue methods of the Expander Mixing Lemma, about what subgraphs it must contain. While doing so we encounter interesting phenomena concerning solutions of norm equation systems and uncover an unexpected connection to Singer difference sets. Joint work with Tomas Bayer, Tamas Meszaros and Lajos Ronyai.

One of the all-time combinatorial classics, Mantel's Theorem asserts that if one forbids an $n$-vertex graph $G$ from containing any triangle, then $G$ can have at most $\frac{n^2}{4}$ edges. In this talk, we explore an extension of this theorem suggested by Gil Kalai. Suppose, for some $0 \le m \le \binom{n}{3}$, we can only forbid $m$ of the triangles from appearing in $G$. What choice of the forbidden triangles then minimises the maximum number of edges $G$ can have? We determine the threshold at which Mantel's bound still holds, and bound how many extra edges appear when fewer triangles are forbidden. These results also generalise to larger cliques, thereby extending Turán's Theorem along the same lines. This is joint work with Ander Lamaison and Tuan Tran.

The conjecture of Linial and Morgenstern asserts that, among all tournaments with a given density $d$ of cycles of length three, the density of cycles of length four is minimized by a random blow-up of a transitive tournament with all but one parts of equal sizes, i.e., a tournament with the structure similar to graphs appearing in the Erdos-Rademacher problem on triangles in graphs with a given edge density. We prove this conjecture for $d\geq 1/36$ using methods from spectral graph theory, and demonstrate that the structure of extremal examples is more complex than expected and give its full description for $d\geq 1/16$. At the end of the talk, we will discuss the maximum number of cycles of a given length in a tournament and report on some recent results that we have obtained. The talk is based on results joint with Timothy Chan, Andrzej Grzesik, Laszlo Miklos Lovasz, Jonathan Noel and Jan Volec.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.