{"id":"arxiv/2609.17958","url":"https://arxiv.org/abs/2609.17958","tags":["math.CO"],"score":0,"title":"When are random regular triangle-free graphs bipartite?","domain":"math.CO","source":"arxiv","authors":["Gregory DeCamillis","Pu Gao"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-16","reactions":{}}