The simultaneous clique-maximisation conjecture for graphs on surfaces

From papers

Let GG be an nn-vertex graph embeddable in a surface Σ\Sigma. Let C(G)C(G) denote its total number of complete subgraphs, let C(Σ,n)C(\Sigma,n) be the maximum of C(G)C(G) over all such graphs, and let C(Ks,Σ,n)C(K_s,\Sigma,n) be the maximum number of copies of KsK_s in an nn-vertex graph embeddable in Σ\Sigma.

Simultaneous clique-maximisation conjecture. If C(G)=C(Σ,n)C(G)=C(\Sigma,n), then for every s0s\geqslant 0,

C(Ks,G)=C(Ks,Σ,n).C(K_s,G) = C(K_s,\Sigma,n).

This is the equality-case counterpart of the clique-count decomposition conjecture: every graph attaining the maximum total clique count should also attain each individual clique-count maximum. It has been verified for the surfaces listed in the paper, while the assertion for arbitrary surfaces remains open.

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

Tony Huynh, Gwenaël Joret and David R. Wood, “Subgraph densities in a surface”, arXiv:2003.13777 (2021).

Solutions 0

No solutions have been posted yet.