Combinatorial Theory Seminar

What is the connection between phase transitions in statistical physics and the computational tractability of approximate counting and sampling? There are many fascinating answers to this question but many mysteries remain. I will discuss one particular type of a phase transition: the first-order phase in the Potts model on $\mathbb{Z}^d$ for large $q$, and show how tools used to analyze the phase transition can be turned into efficient algorithms at the critical temperature. In the other direction, I'll discuss how the algorithmic perspective can help us understand phase transitions.

Active matter describes ensembles of self-organizing agents, or particles, interacting with their local environments so that their micro-scale behavior determines macro-scale characteristics of the ensemble. While there has been a surge of activity exploring the physics underlying such systems, less attention has been paid to questions of how to program them to achieve desired outcomes. We will present some recent results designing programmable active matter for specific tasks, including aggregation, dispersion, speciation, and locomotion, building on insights from stochastic algorithms and statistical physics.

Let $X_1, \ldots$ be i.i.d. copies of some real random variable $X$. For any $\varepsilon_2, \varepsilon_3, \ldots$ in $\{0,1\}$, a basic algorithm introduced by H.A. Simon yields a reinforced sequence $\hat{X}_1, \hat{X}_2, \ldots$ as follows. If $\varepsilon_n=0$, then $\hat{X}_n$ is a uniform random sample from $\hat{X}_1, …, \hat{X}_{n-1}$; otherwise $\hat{X}_n$ is a new independent copy of $X$. The purpose of this talk is to compare the scaling exponent of the usual random walk $S(n)=X_1 +\ldots + X_n$ with that of its step reinforced version $\hat{S}(n)=\hat{X}_1+\ldots + \hat{X}_n$. Depending on the tail of $X$ and on asymptotic behavior of the sequence $\varepsilon_j$, we show that step reinforcement may speed up the walk, or at the contrary slow it down, or also does not affect the scaling exponent at all. Our motivation partly stems from the study of random walks with memory, notably the so-called elephant random walk and its variations.

We say that a graph $G$ is $H$-free if $G$ does not contain $H$ as a (not necessarily induced) subgraph. For a positive integer $n$, denote by $\text{ex}(n,H)$ the largest number of edges in an $H$-free graph with $n$ vertices (the Turán number of $H$). The classical theorem of Erdős, Kleitman, and Rothschild states that, for every $r\geq3$, there are $2^{\text{ex}(n,H)+o(n2)}$ many $K_r$-free graphs with vertex set $\{1,…, n\}$. There exist (at least) three different derivations of this estimate in the literature: an inductive argument based on the Kővári-Sós-Turán theorem (and its generalisation to hypergraphs due to Erdős), a proof based on Szemerédi's regularity lemma, and an argument based on the hypergraph container theorems. In this talk, we present yet another proof of this bound that exploits connections between entropy and independence. This argument is an adaptation of a method developed in a joint work with Gady Kozma, Tom Meyerovitch, and Ron Peled that studied random metric spaces.

We study the following question at the intersection of extremal and structural graph theory. Given a fixed graph $H$ that embeds in a fixed surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph that embeds in $\Sigma$? Exact answers to this question are known for specific graphs $H$ when $\Sigma$ is the sphere. We aim for more general, albeit less precise, results. We show that the answer to the above question is $\Theta(nf(H))$, where $f(H)$ is a graph invariant called the `flap-number' of $H$, which is independent of $\Sigma$. This simultaneously answers two open problems posed by Eppstein (1993). When $H$ is a complete graph we give more precise answers. This is joint work with Tony Huynh and Gwenaël Joret [https://arxiv.org/abs/2003.13777]

The small subgraph conditioning method is an analysis of variance technique which was introduced by Robinson and Wormald in 1992, in their proof that almost all cubic graphs are Hamiltonian. The method has been used to prove many structural results about random regular graphs, mostly to show that a certain substructure is present with high probability. I will discuss some applications of the small subgraph conditioning method to hypergraphs, and describe a subtle issue which is absent in the graph setting.

How long does it take for a pandemic to stop spreading? When modelling an infection process, especially these days, this is one of the main questions that comes to mind. In this talk, we consider this question in the bootstrap percolation setting.

Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges $E_0$, and we infect new edges according to a predetermined rule. Given a graph $H$ and a set of previously infected edges $E_t \subseteq E(Kn)$, we infect a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n] , E_t \cup \{e\})$. A question raised by Bollobás asks for the maximum time the process can run before it stabilizes. Bollobás, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where $H=K_r$. They answered the question for $r \leq 4$ and gave a non-trivial lower bound for every $r \geq 5$. They also conjectured that the maximal running time is $o(n^2)$ for every integer $r$. We disprove their conjecture for every $r \geq 6$ and we give a better lower bound for the case $r=5$; in the proof we use the Behrend construction. This is a joint work with József Balogh, Alexey Pokrovskiy, and Tibor Szabó.

This is joint with Gabe Conant. We give a structure theorem for finite subsets A of arbitrary groups G such that A has "small tripling" and "bounded VC dimension". Roughly, A will be a union of a bounded number of translates of a coset nilprogession of bounded rank and step (up to a small error).

I will describe some recent work with D. Kazhdan where we obtain results in algebraic geometry, inspired by questions in additive combinatorics, via analysis over finite fields. Specifically we are interested in quantitative properties of polynomial rings that are independent of the number of variables. A sample application is the following theorem : Let $V$ be a complex vector space, $P$ a high rank polynomial of degree $d$, and $X$ the null set of $P$, $X=\{v \mid P(v)=0\}$. Any function $f:X\to C$ which is polynomial of degree $d$ on lines in $X$ is the restriction of a degree $d$ polynomial on $V$.

The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of $(n-1)^2+1$ distinct real numbers contains a monotone subsequence of length $n$. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They raise the problem of how large should a $d$-dimesional array be in order to guarantee a "monotone" subarray of size $n \times n \times \ldots \times n$. In this talk we discuss this problem and show how to improve their original Ackerman-type bounds to at most a triple exponential. (Joint work with M. Bucic and T. Tran)