Structural matching conjecture for dense random graphs

Fix r4r\geqslant 4, and let GG(n,q)G\sim G(n,q), where

n2/(r1)(logn)1/(r12)q=q(n)n2/r.n^{-2/(r-1)}(\log n)^{1/{r-1 \choose 2}}\ll q=q(n)\ll n^{-2/r}.

For each rNr\in\mathbb{N}, let Sr(G)S_r(G) be the set of vertices in a largest KrK_r-matching of GG, with an arbitrary deterministic choice in case of ties.

Structural matching conjecture. With high probability as nn\rightarrow\infty, the graph GSr(G)G-S_r(G) contains a Kr1K_{r-1}-matching that covers all but o(μr)o(\sqrt{\mu_r}) vertices of V(G)Sr(G)V(G)\setminus S_r(G).

This conjecture would provide the structural theorem needed to extend the paper's results to larger values of rr. The source notes that the analogous case r=3r=3 follows from an earlier structural result, while the cases r4r\geqslant4 remain open.

Sources & referencesView supporting material

Primary source

Zhifei Yan, “The chromatic number of very dense random graphs”, arXiv:2405.13914 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.