Clique-counting conjecture for bounded-degree graphs with a fixed number of edges

Let t3t\geq 3, let GG be a graph with mm edges and maximum degree at most rr, and write

m=a(r+12)+b,0b<(r+12).m=a\binom{r+1}{2}+b,\qquad 0\leq b<\binom{r+1}{2}.

Here kt(G)k_t(G) denotes the number of copies of KtK_t in GG, Kr+1K_{r+1} is the complete graph on r+1r+1 vertices, and C(b)\mathcal{C}(b) is the colex graph with bb edges. Bounded-degree edge-resource clique-counting conjecture. One has

kt(G)kt(aKr+1C(b)).k_t(G)\leq k_t\bigl(aK_{r+1}\cup\mathcal{C}(b)\bigr).

The conjecture refines the paper's main theorem, which proves the analogous assertion for the total number of cliques. The source attributes this refinement to the authors' earlier work, but gives no resolution status, so it remains open here.

Sources & referencesView supporting material

Primary source

Rachel Kirsch and A. J. Radcliffe, “Many cliques with few edges”, arXiv:1912.09872 (2021).

Additional references

2 papers in this index state this conjecture (2017–2019). The statement above is taken from the most recent of them; the others are arXiv:1709.06163.

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.