When are random regular triangle-free graphs bipartite?

Abstract

We study the structure of random $d$-regular triangle-free graphs and show that a sharp phase transition occurs at $d=\frac{\sqrt{3}}{2}\sqrt{n\log n}$. For smaller $d$, asymptotically almost surely the graph is non-bipartite, whereas for greater $d$, asymptotically almost surely the graph is bipartite.

arXiv comment72 pages, results originally appeared in master thesis of first author. Figures are not rendered correctly in HTML version