Georgia Institute of Technology College of Sciences

In 1973, Brown, Erdős and Sós proved that if H is a 3-uniform hypergraph on n vertices which contains no triangulation of the sphere, then H has at most O(n^{5/2}) edges, and this bound is the best possible up to a constant factor. Resolving a conjecture of Linial, also reiterated by Keevash, Long, Narayanan, and Scott, we show that the same result holds for triangulations of the torus. Furthermore, we extend our result to every closed orientable surface S.

Joint work with Alexandr Polyanskii, István Tomon and Dmitriy Zakharov, see https://arxiv.org/abs/2010.07191

In this talk, we will discuss the minimum positive value of the stationary distribution of a random walk on a directed random graph with given degrees. While for undirected graphs the stationary distribution is simply determined by the degrees, the graph geometry plays a major role in the directed case. Understanding typical stationary values is key to determining the mixing time of the walk, as shown by Bordenave, Caputo, and Salez. However, typical results provide no information on the minimum value, which is important for many applications. Recently, Caputo and Quattropani showed that the stationary distribution exhibits logarithmic fluctuations provided that the minimum degree is at least 2. In this talk, we show that dropping the minimum degree condition may yield polynomially smaller stationary values of the form n^{-(1+C+o(1))}, for a constant C determined by the degree distribution. In particular, C is the combination of two factors: (1) the contribution of atypically thin in-neighborhoods, controlled by subcritical branching processes; and (2) the contribution of atypically "light" trajectories, controlled by large deviation rate functions. As a by-product of our proof, we also determine the hitting and cover time in random digraphs. This is joint work with Xing Shi Cai.

Motivated by a new probabilistic interpretation of the Hardy-Littlewood k-tuples conjectures, we introduce a new probabilistic model of the primes and make a new conjecture about the largest gaps between the primes below x.  Our bound depends on a property of the interval sieve which is not well understood.  We also show that any sequence of integers which satisfies a sufficiently uniform version of the Hardy-Littlewood conjectures must have large gaps of a specific size.  This work is joint with Bill Banks and Terry Tao.

We introduce a class of random graph processes, which we call flip processes. Each such process is given by a rule which is just a function $\mathcal{R}:\mathcal{H}_k\rightarrow \mathcal{H}_k$ from all labelled $k$-vertex graphs into itself ($k$ is fixed). Now, the process starts with a given $n$-vertex graph $G_0$. In each step, the graph $G_i$ is obtained by sampling $k$ random vertices $v_1,\ldots,v_k$ of $G_{i-1}$ and replacing the induced graph $G_{i-1}[v_1,\ldots,v_k]$ by $\mathcal{R}(G_{i-1}[v_1,\ldots,v_k])$. This class contains several previously studied processes including the Erdos-Renyi random graph process and the random triangle removal.

Given a flip processes with a rule $\mathcal{R}$ we construct time-indexed trajectories $\Phi:\mathcal{W}\times [0,\infty)\rightarrow\mathcal{W}$ in the space of graphons. We prove that with high probability, starting with a large finite graph $G_0$ which is close to a graphon $W_0$, the flip process will follow the trajectory $(\Phi(W_0,t))_{t=0}^\infty$ (with appropriate rescaling of the time).

These graphon trajectories are then studied from the perspective of dynamical systems. We prove that two trajectories cannot form a confluence, give an example of a process with an oscilatory trajectory, and study stability and instability of fixed points.

Joint work with Frederik Garbe, Matas Sileikis and Fiona Skerman.