Georgia Institute of Technology College of Sciences

How likely is $G(n;p)$ to have a less-than-typical number of triangles? This is a foundational question in non-linear large deviation theory. When $p >> n^{-1/2}$ or $p >> n^{-1/2}$ the answer is fairly well-understood, with Janson's inequality applying in the former case and regularity- or container-based methods applying in the latter. We study the regime $p = c n^{-1/2}$, with $c>0$ fixed, with the large deviation event having at most $E$ times the expected number of triangles, for a fixed $0 <= E < 1$.

We prove explicit formula for the log-asymptotics of the event in question, for a wide range of pairs $(c,E)$. In particular, we show that for sufficiently small $E$ (including the triangle-free case $E = 0$) there is a phase transition as $c$ increases, in the sense of a non-analytic point in the rate function. On the other hand, if $E > 1/2$, then there is no phase transition.

As corollaries, we obtain analogous results for the $G(n;m)$ model, when $m = C n^{3/2}$. In contrast to the $G(n;p)$ case, we show that a phase transition occurs as $C$ increases for all $E$.

Finally, we show that the probability of $G(n;m)$ being triangle free, where $m = C n^{3/2}$ for a sufficiently small constant $C$, conforms to a Poisson heuristic.

Joint with Matthew Jenssen, Will Perkins, and Aditya Potukuchi.

The Ramsey number R(3,k) is the smallest n so that every triangle free graph on n vertices has an independent set of size k.  Upper bounds to R(3,k) consist of finding independent sets in triangle free graphs, while lower bounds consist of constructing triangle free graphs with no large independent set.  The previous best-known lower bound was independently due to works of Bohman-Keevash and Fiz Pontiveros-Griffiths-Morris, both of which analyzed the triangle-free process.  The analysis of the triangle-free process is a delicate dance of demonstrating self-correction and requires tracking a large family of graph statistics simultaneously.  We will discuss a new lower bound to R(3,k) and provide a gentle introduction to the concept of "the Rodl nibble," with an emphasis on which ideas simplify our analysis.  This is based on joint work with Marcelo Campos, Matthew Jenssen and Julian Sahasrabudhe.

We prove that graphs that do not contain a totally odd immersion of $K_t$ are $\mathcal{O}(t)$-colorable. In particular, we show that any graph with no totally odd immersion of $K_t$ is the union of a bipartite graph and a graph which forbids an immersion of $K_{\mathcal{O}(t)}$. Our results are algorithmic, and we give a fixed-parameter tractable algorithm (in $t$) to find such a decomposition.

Dirac’s classical theorem asserts that, for $n\ge 3$, any $n$-vertex graph with minimum degree at least $n/2$ is Hamiltonian.  Furthermore, if we additionally assume that such graphs are regular, then, by the breakthrough work of Csaba, Kühn, Lo, Osthus, and Treglown, they admit a decomposition into Hamilton cycles and at most one perfect matching, solving the well-known Nash‑Williams conjecture. In the pseudorandom setting, it has long been conjectured that similar results hold in much sparser graphs.

We prove two overarching theorems for graphs that exclude excessively dense subgraphs, which yield nearly optimal resilience and Hamilton‑decomposition results in sparse pseudorandom graphs. In particular, we show that for every fixed $\gamma>0$, there exists a constant $C>0$ such that if $G$ is a spanning subgraph of an $(n,d,\lambda)$-graph satisfying $\delta(G)\ge\bigl(\tfrac12+\gamma\bigr)d$ and $ d/\lambda\ge C,$ then $G$ must contain a Hamilton cycle.

Secondly, we show that for every $\varepsilon>0$, there is $C>0$ so that any $(n,d,\lambda)$-graph with $d/\lambda\ge C$ contains at least $\bigl(\tfrac12-\varepsilon\bigr)d$ edge‑disjoint Hamilton cycles, and, finally, we prove that the entire edge set of $G$ can be covered by no more than $\bigl(\tfrac12+\varepsilon\bigr)d$ such cycles.

All bounds are asymptotically optimal and significantly improve earlier results on Hamiltonian resilience, packing, and covering in sparse pseudorandom graphs.

This is joint work with Nemanja Draganić, Jaehoon Kim, David Munhá Correia, Matías Pavez-Signé, and Benny Sudakov.