Triangle factors in pseudorandom graphs

Abstract:

An $(n,d,\lambda)$-graph is an $n$ vertex, $d$-regular graph with second eigenvalue in absolute value $\lambda$. When $\lambda$ is small compared to $d$, such graphs have \emph{pseudorandom} properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free $(n,d,\lambda)$-graph with $d=\Theta(n^{2/3})$ and $\lambda=\Theta(d^2/n)$. This construction is optimal as having $\lambda=o(d^2/n)$ guarantees the existence of a triangle in an $(n,d,\lambda)$-graph. Krivelevich, Sudakov and Szab\'o (2004) conjectured that if $n\in 3\mathbb{N}$ and $\lambda=o(d^2/n)$ then an $(n,d,\lambda)$-graph $G$ in fact contains a \emph{triangle factor}: vertex disjoint triangles covering the whole vertex set.

In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab\'o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph $G$ contains every graph on $n$ vertices with maximum degree at most 2.

An (n,d,λ)(n,d,λ)-graph is an nn vertex, dd-regular graph with second eigenvalue in absolute value λλ. When λλ is small compared to dd, such graphs have \emph{pseudorandom} properties. A fundamental question in the study of pseudorandom graphs is to find conditions on the parameters that guarantee the existence of a certain subgraph. A celebrated construction due to Alon gives a triangle-free (n,d,λ)(n,d,λ)-graph with d=Θ(n2/3)d=Θ(n2/3) and λ=Θ(d2/n)λ=Θ(d2/n). This construction is optimal as having λ=o(d2/n)λ=o(d2/n) guarantees the existence of a triangle in an (n,d,λ)(n,d,λ)-graph. Krivelevich, Sudakov and Szab\'o (2004) conjectured that if n∈3Nn∈3N and λ=o(d2/n)λ=o(d2/n) then an (n,d,λ)(n,d,λ)-graph GG in fact contains a \emph{triangle factor}: vertex disjoint triangles covering the whole vertex set.

In this talk, we discuss a solution to the conjecture of Krivelevich, Sudakov and Szab\'o. The result can be seen as a clear distinction between pseudorandom graphs and random graphs, showing that essentially the same pseudorandom condition that ensures a triangle in a graph actually guarantees a triangle factor. In fact, even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition actually guarantees that such a graph GG contains every graph on nn vertices with maximum degree at most 2.

 This is a seminar of the Combinatorial Mathematics Society of Australasia.

To attend email cmsa-webinar@monash.edu with the subject 'subscribe' to receive zoom details. [You only need to subscribe once, not for future talks.]