Regular bipartite decompositions of pseudorandom graphs

Abstract

In 1972, Kotzig proved that for every even $n$, the complete graph $K_n$ can be decomposed into $\lceil {\log }_{2}n\rceil$ edge-disjoint regular bipartite spanning subgraphs, which is best possible. In this paper, we study regular bipartite decompositions of $(n,d,\hat{I}»)$-graphs, where $n$ is an even integer and $d_0\le d\le n-1$ for some absolute constant $d_0$. With a randomized algorithm, we prove that such an $(n,d,\hat{I}»)$-graph with $\hat{I}»\le d/12$ can be decomposed into at most ${\log }_{2}d+36$ regular bipartite spanning subgraphs. This is best possible up to the additive constant term. As a consequence, we also improve the best known bounds on $\hat{I}»=\hat{I}»(d)$ by Ferber and Jain (2020) to guarantee that an $(n,d,\hat{I}»)$-graph on an even number of vertices admits a $1$-factorization, showing that $\hat{I}»\le cd$ is sufficient for some absolute constant $c>0$.

23 pages, 1 figure