Let G be a random d-regular triangle-free graph on n vertices, with n→∞. The claimed sharp transition is at d=frac√32√nlog n: if d=(c+o(1))√nlog n with c frac√32, then G is asymptotically almost surely bipartite.

Bipartiteness threshold for random regular triangle-free graphs

Let $G$ be a random $d$ -regular triangle-free graph on $n$ vertices, with $n\to\infty$ . The claimed sharp transition is at $d=\frac{\sqrt{3}}{2}\sqrt{n\log n}$ : if $d=(c+o(1))\sqrt{n\log n}$ with $c<\frac{\sqrt{3}}{2}$ , then $G$ is asymptotically almost surely non-bipartite, while if $c>\frac{\sqrt{3}}{2}$ , then $G$ is asymptotically almost surely bipartite.

References

Primary source

arXiv

Additional references

When are random regular triangle-free graphs bipartite? — arXiv — Gregory DeCamillis, Pu Gao

Posted 2 weeks ago · edited 2 weeks ago

Progress summary

Refreshed 2 weeks ago

Claimed solved

A new paper claims to identify exactly when these constrained random graphs become bipartite, but the result has not been independently verified.

The problem asks for the sharp transition between non-bipartite and bipartite behavior in random regular graphs with no triangles. No proposer or earlier date is given in the retrieved material.

September 16, 2026 claimed threshold

DeCamillis and Gao claim a sharp bipartiteness threshold for random regular triangle-free graphs, with extensions to near-regular degree sequences and other clique-free models. The principal threshold is presented as a theorem, while the further extensions are conjectural; independent verification was not found.

Current status (as of September 2026): The principal threshold is claimed in a new paper but remains unverified; the stated extensions remain conjectural.

Sources

No solutions have been posted yet.