Structural matching conjecture for dense random graphs
Fix , and let , where
For each , let be the set of vertices in a largest -matching of , with an arbitrary deterministic choice in case of ties.
Structural matching conjecture. With high probability as , the graph contains a -matching that covers all but vertices of .
This conjecture would provide the structural theorem needed to extend the paper's results to larger values of . The source notes that the analogous case follows from an earlier structural result, while the cases remain open.
References
Primary source
Zhifei Yan, “The chromatic number of very dense random graphs”, arXiv:2405.13914 (2024).
Progress summary
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.