The triangle-maximisation conjecture for total clique counts on surfaces

About 6 years old · traced to

Let GG be an nn-vertex graph embeddable in a surface Σ\Sigma. Let C(K3,G)C(K_3,G) be the number of copies of K3K_3 in GG, let C(G)C(G) be the total number of complete subgraphs of GG, and let C(K3,Σ,n)C(K_3,\Sigma,n) and C(Σ,n)C(\Sigma,n) be the respective maxima over all nn-vertex graphs embeddable in Σ\Sigma.

Triangle-maximisation conjecture. If

C(K3,G)=C(K3,Σ,n),C(K_3,G)=C(K_3,\Sigma,n),

then

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

The claim formalises the proposed equivalence between maximising the number of triangles and maximising the total number of complete subgraphs. It has been verified for the surfaces listed in the paper, but is open for general surfaces.

References

Primary source

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

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.