Georgia Institute of Technology College of Sciences

Given a graph G, the clique chromatic number of G is the smallest number of colors needed to color the vertices of G so that no maximal clique containing at least two vertices is monochromatic.
We solve an open question proposed by McDiarmid, the speaker, and Pralat concerning the asymptotic order of the clique chromatic number for binomial random graphs.
More precisely, we find the correct order of the clique chromatic number for most values of the edge-probability p around n^{-1/2}. Furthermore, the gap between upper and lower bounds is at most a logarithmic factor in n in all cases.

Based on joint work in progress with Lyuben Lichev and Lutz Warnke.

(Please note the unusual time from 4-5pm, due to the Virtual Admitted Student Day in the School of Mathematics.)

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.