Liu–Montgomery's crux conjecture for clique subdivisions

From papers

Let GG be a graph and let calpha=1100calpha=\tfrac{1}{100}. For a subgraph HGH\subset G, write d(H)d(H) for its average degree, and let Cα(G)C_{\alpha}(G) be the minimum order of a subgraph HGH\subset G with d(H)αd(G)d(H)\geq \alpha d(G). A subdivision of a clique is obtained by replacing each edge of the clique by internally vertex-disjoint paths.

Liu–Montgomery's crux conjecture. There exists some constant c>0c>0 such that every graph GG contains a subdivision of a clique with at least

cmin{d(G),Cα(G)logCα(G)}c\min \Big\{d(G), \sqrt{\tfrac{C_{\alpha}(G)}{\log C_{\alpha}(G)}}\Big\}

vertices.

The conjecture formalizes the idea that graphs without a small subgraph almost as dense as the whole graph should contain a large clique subdivision. The parameter Cα(G)C_{\alpha}(G) is the crux, measuring the order of the smallest dense patch; the source states that Liu and Montgomery raised this conjecture with α=1100\alpha=\tfrac{1}{100}, but gives no resolution here.

Progress summary

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

Sources & referencesView supporting material

Primary source

Donglei Yang and Fan Yang, “Embedding clique subdivisions via crux”, arXiv:2405.15409 (2024).

Solutions 0

No solutions have been posted yet.