Georgia Institute of Technology College of Sciences

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.

We consider the strong parity edge coloring problem, which aims to color the edges of a graph G so that in each open walk on G, some color appears an odd number of times.  We show that this problem is equivalent to the problem of embedding a graph in a vector space over F2 so that the number of difference vectors attained at the edges is minimized. Using this equivalence, we achieve the following:

1. We characterize graphs on n vertices that can be embedded with ceil(log_2 n) difference vectors, answering a question of Bunde, Milans, West, and Wu.

2. We show that the number of colors needed for a strong parity edge coloring of K_{s,t} is given by the Hopf-Stiefel function, confirming a conjecture of Bunde, Milans, West, and Wu.

3. We find an asymptotically optimal embedding for the power of a path.

This talk is based on joint work with Sergey Norin and Doug West.

What is the minimum/maximum size of a set $A$ of integers that has the property that every integer in $\{1,2,\cdots, n\}$ can be written in at least/at most $g$ ways as a difference of elements of $A$? For the first question, we show that the limit of this minimum size divided by $\sqrt{n}$ exists and is nonzero, answering a question of Kravitz. For the second question, we give an asymptotic formula for the maximum size. We also consider the same problems but in the setting of a vector space over a finite field. During the talk we will discuss open problems and connections to coding theory and graph theory. This is joint work with Eric Schmutz.

We discuss the sphere dimension of a graph. This is the smallest integer $d$ such that the graph can be represented as the intersection graph of a collection of spheres in $\mathbb{R}^d$. We show that graphs with small sphere dimension have small balanced separators, as long as they exclude a complete bipartite graph $K_{t,t}$. This property is connected to forbidding shallow minors and can be used to develop divide-and-conquer algorithms. This is joint work with James Davies, Agelos Georgakopoulos, and Meike Hatzel.