Combinatorial Theory Seminar

I will discuss various results and conjectures about off-diagonal hypergraph Ramsey numbers, focusing on recent developments.

A set in the Euclidean plane is called an integer distance set if the distance between any pair of its points is an integer.  All so-far-known integer distance sets have all but up to four of their points on a single line or circle; and it had long been suspected, going back to Erdős, that any integer distance set must be of this special form. In a recent work, joint with Marina Iliopoulou and Sarah Peluse, we developed a new approach to the problem, which enabled us to make the first progress towards confirming this suspicion.  In the talk, I will discuss the study of integer distance sets, its connections with other problems, and our new developments.

Paraphrasing the title of Riemann’s famous lecture of 1854 I ask: What is the most rudimentary notion of a geometry? A possible answer is a path system: Consider a finite set of “points” $x_1,…,x_n$ and provide a recipe how to walk between $x_i$ and $x_j$ for all $i\neq j$, namely decide on a path $P_{ij}$, i.e., a sequence of points that starts at $x_i$ and ends at $x_j$, where $P_{ji}$ is $P_{ij}$, in reverse order. The main property that we consider is consistency. A path system is called consistent if it is closed under taking subpaths. What do such systems look like? How to generate all of them? We still do not know. One way to generate a consistent path system is to associate a positive number $w_{ij}>0$ with every pair and let $P_{ij}$ be the corresponding $w$-shortest path between $x_i$ and $x_j$. Such a path system is called metrical. It turns out that the class of consistent path systems is way richer than the metrical ones.

My main emphasis in this lecture is on what we don’t know and wish to know, yet there is already a considerable body of work that we have done on the subject.

The new results that I will present are joint with my student Daniel Cizma as well as with him and with Maria Chudnovsky.

I'll discuss how a certain notion of symmetry captures the computational complexity of approximating homomorphism problems between relational structures, also known as constraint satisfaction problems. I'll present recent results on inapproximability of conflict-free and linearly-ordered hypergraph colourings and solvability of systems of equations.

Upper bounds on the number of incidences between points and lines, tubes, and other geometric objects, have many applications in combinatorics and analysis. On the other hand, much less is known about lower bounds. We prove a general lower bound for the number of incidences between points and tubes in the plane under a natural spacing condition. In particular, if you take $n$ points in the unit square and draw a line through each point, then there is a non-trivial point-line pair with distance at most $n^{-2/3+o(1)}$. This quickly implies that any $n$ points in the unit square define a triangle of area at most $n^{-7/6+o(1)}$, giving a new upper bound for the Heilbronn's triangle problem.

Joint work with Alex Cohen and Cosmin Pohoata.

In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained the first exponential improvement of the upper bound on the classical Ramsey numbers since 1935. I will outline a reinterpretation of their proof, replacing the underlying book algorithm with a simple inductive statement. In particular, I will present a complete proof of an improved upper bound on the off-diagonal Ramsey numbers and describe the main steps involved in improving their upper bound for the diagonal Ramsey numbers to $R(k,k)\le(3.8)^k$ for sufficiently large $k$.

Based on joint work with Parth Gupta, Ndiame Ndiaye, and Louis Wei.

Let $(V(u))$ be a branching random walk and $(\eta(u))$ be i.i.d marks on the vertices. To each path $\xi$ of the tree, we associate the discounted sum $D(\xi)$ which is the sum of the $\exp(V(u))\eta_u$ along the path. We study conditions under which $\sup_\xi D(\xi)$ is finite, answering an open question of Aldous and Bandyopadhyay. We will see that this problem is related to the study of the local time process of the branching random walk along a path. It is a joint work with Yueyun Hu and Zhan Shi.

The celebrated Szemeredi-Trotter theorem states that the maximum number of incidences between $n$ points and $n$ lines in the plane is $\mathcal{O}(n^{4/3})$, which is asymptotically tight.

Solymosi conjectured that this bound drops to $o(n^{4/3})$ if we exclude subconfigurations isomorphic to any fixed point-line configuration. We describe a construction disproving this conjecture. On the other hand, we prove new upper bounds on the number of incidences for configurations that avoid certain subconfigurations. Joint work with Martin Balko.

In 1975, Bollobás, Erdős, and Szemerédi asked the following Zarankiewicz-type problem. What is the smallest $\tau$ such that an $n \times n \times n$ tripartite graph with minimum degree $n + \tau$ must contain $K_{t, t, t}$? They further conjectured that $\tau = O(n^{1/2})$ when $t = 2$.

I will discuss our proof that $\tau = O(n^{1 - 1/t})$ (confirming their conjecture) and an infinite family of extremal examples. The bound $O(n^{1 - 1/t})$ is best possible whenever the Kővári-Sós-Turán bound $\operatorname{ex}(n, K_{t, t}) = O(n^{2 - 1/t})$ is (which is widely-conjectured to be the case).

This is joint work with Francesco Di Braccio (LSE).

A zero-one matrix $M$ is said to contain another zero-one matrix $A$ if we can delete some rows and columns of $M$ and replace some 1-entries with 0-entries such that the resulting matrix is $A$. The extremal number of $A$, denoted $\operatorname{ex}(n,A)$, is the maximum number of 1-entries that an $n\times n$ zero-one matrix can have without containing $A$. The systematic study of this function for various patterns $A$ goes back to the work of Furedi and Hajnal from 1992, and the field has many connections to other areas of mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices, but very little is known about the general case (that is, the case where $A$ is not necessarily acyclic). We prove the first asymptotically tight general result by showing that if $A$ has at most $t$ 1-entries in every row, then $\operatorname{ex}(n,A)\leq n^{2-1/t+o(1)}$. This verifies a conjecture of Methuku and Tomon.

Our result also provides the first tight general bound for the extremal number of vertex-ordered graphs with interval chromatic number two, generalizing a celebrated result of Furedi, and Alon, Krivelevich and Sudakov about the (unordered) extremal number of bipartite graphs with maximum degree $t$ in one of the vertex classes.

Joint work with Barnabas Janzer, Van Magnan and Abhishek Methuku.