Georgia Institute of Technology College of Sciences

Combinatorics was conceived, and then developed over centuries as a discipline about finite structures. In the modern world, however, its applications increasingly pertain to structures that, although finite, are extremely large: the Internet network, social networks, statistical physics, to name just a few. This makes it very natural to try to think of the "limit theory" of such objects by pretending that "very large" actually means "infinite". This mathematical abstraction turns out to be very useful and instructive.

After briefly reviewing the basics of the theory (graphons and flag algebras), I will report on some more recent developments. Time permitting, we will discuss the most general form of the theory suitable for arbitrary combinatorial structures (peons and theons), its applications to the theory of quasi-randomness and its applications to machine learning.

The first two topics are based on joint work with L. Coregliano, and the third one on a recent paper by Coregliano and Malliaris.

A classic problem in probability theory and combinatorics is to estimate the probability that the random graph G(n,p) contains no triangles.  This problem can be viewed as a question in "non-linear large deviations".   The asymptotics of the logarithm of this probability (and related lower tail probabilities) are known in two distinct regimes.  When p>> 1/\sqrt{n}, at this level of accuracy the probability matches that of G(n,p) being bipartite; and when p<< 1/\sqrt{n}, Janson's Inequality gives the asymptotics of the log.  I will discuss a new approach to estimating this probability in the "critical regime": when p = \Theta(1/\sqrt{n}).  The approach uses ideas from statistical physics and algorithms and gives information about the typical structure of graphs drawn from the corresponding conditional distribution.  Based on joint work with Matthew Jenssen, Aditya Potukuchi, and Michael Simkin.

A graph is $H$-Ramsey if every two-coloring of its edges contains a monochromatic copy of $H$. Define the $F$-Ramsey number of $H$, denoted by $r_F(H)$, to be the minimum number of copies of $F$ in a graph which is $H$-Ramsey. This generalizes the Ramsey number and size Ramsey number of a graph. Addressing a question of Spiro, we prove that \[r_{K_3}(K_t)=\binom{r(K_t)}3\] for all sufficiently large $t$. 

Our proof employs many recent results on the chromatic number of locally sparse graphs. In particular, I will highlight a new result on the chromatic number of degenerate graphs, which leads to several intriguing open problems.

The geometry of non-arithmetic hyperbolic manifolds is mysterious in spite of how plentiful they are. McMullen and Reid independently conjectured that such manifolds have only finitely many totally geodesic hyperplanes and their conjecture was recently settled by Bader-Fisher-Miller-Stover in dimensions larger than 3. Their works rely on superrigidity theorems and are not constructive. In this talk, we strengthen their result by proving a quantitative finiteness theorem for non-arithmetic hyperbolic manifolds that arise from a gluing construction of Gromov and Piatetski-Shapiro. Perhaps surprisingly, the proof relies on an effective density theorem for certain periodic orbits. The effective density theorem uses a number of ideas including Margulis functions, a restricted projection theorem, and an effective equidistribution result for measures that are nearly full dimensional. This is joint work with K. W. Ohm.