The triangle-maximisation conjecture for total clique counts on surfaces

From papers

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.

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.