Structural matching conjecture for dense random graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.