pith. sign in

arxiv: 2606.31967 · v1 · pith:YZD2HQF3new · submitted 2026-06-30 · 🧮 math.CO

On clique-to-clique densities

Jie Ma , Tianhen Wang , Tianming Zhu This is my paper

Pith reviewed 2026-07-01 04:18 UTC · model grok-4.3

classification 🧮 math.CO
keywords clique densityextremal graph theoryLovász–Simonovits functionsgeneralized inverseasymptotic boundsclique counting
0
0 comments X

The pith

For any s less than t the t-clique density is at least the Lovász–Simonovits t-function applied to the inverse of the s-function of the given s-clique density.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a lower bound relating the number of larger cliques to the number of smaller cliques in any graph. It shows that the t-clique count divided by n to the t is bounded below by composing the Lovász–Simonovits density function for t with the generalized inverse of the same function for s. The bound holds for every pair of integers 2 ≤ s < t and is asymptotically tight as the number of vertices grows. It improves on an earlier piecewise-linear bound and supplies a new inductive argument that recovers a known theorem when s equals 2. A reader would care because the result pins down the precise minimal relationship between densities of cliques of different sizes.

Core claim

For any integers 2 ≤ s < t the inequality k_t(G)/n^t ≥ F_t(F_s^{-1}(k_s(G)/n^s)) holds in every n-vertex graph G, where F_r denotes the Lovász–Simonovits r-clique density function and F_s^{-1} its generalized inverse; the bound is asymptotically sharp.

What carries the argument

The composition F_t ∘ F_s^{-1} of the Lovász–Simonovits r-clique density functions with the generalized inverse of the s-function, which produces the minimal possible t-clique density consistent with a prescribed s-clique density.

If this is right

  • The bound is asymptotically sharp.
  • It strengthens Bollobás's piecewise-linear interpolation bound.
  • When s equals 2 the inequality recovers Reiher's clique density theorem.
  • The proof for the s=2 case is inductive.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same composition technique might produce bounds that relate densities of three or more different clique sizes at once.
  • The inductive argument could be adapted to obtain similar relations for other uniform hypergraph densities.
  • Explicit computation of the functions F_r for small r would turn the bound into concrete numerical inequalities for concrete pairs s and t.

Load-bearing premise

The Lovász–Simonovits functions admit generalized inverses whose composition yields exactly the smallest t-clique density that can occur with a given s-clique density in the large-n limit.

What would settle it

A sequence of graphs on n vertices whose t-clique count divided by n^t falls below F_t(F_s^{-1}(k_s(G)/n^s)) by a positive fraction that does not tend to zero.

read the original abstract

Let $k_r(G)$ denote the number of $r$-cliques in a graph $G$ and let $F_r(\cdot)$ be the Lov\'asz--Simonovits $r$-clique density function. For any integers $2\le s<t$, we determine the asymptotically sharp lower bound on $k_t(G)$ in an $n$-vertex graph $G$ with a prescribed number $k_s(G)$, by showing that \[ \frac{k_t(G)}{n^t}\ge F_t\!\left(F_s^{-1}\!\left(\frac{k_s(G)}{n^s}\right)\right), \] where $F_s^{-1}$ denotes the generalized inverse. This strengthens Bollob\'as's piecewise-linear interpolation bound and, in the case $s=2$, recovers Reiher's clique density theorem via a new inductive proof.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The manuscript proves that for integers 2 ≤ s < t, any n-vertex graph G satisfies k_t(G)/n^t ≥ F_t(F_s^{-1}(k_s(G)/n^s)), where F_r is the Lovász–Simonovits r-clique density function and F_s^{-1} its generalized inverse. The bound is asymptotically sharp, strengthens Bollobás's piecewise-linear interpolation, and recovers Reiher's theorem for s=2 via a new inductive proof that reduces the general case to the known s=2 result while verifying the required monotonicity and continuity properties of the F_r.

Significance. If the inductive argument holds, the result determines the exact asymptotic extremal function for t-clique densities given s-clique densities by direct composition of established Lovász–Simonovits functions, with no free parameters or ad-hoc constructions. The reduction to Reiher's theorem together with the explicit verification that the generalized inverses are well-defined and attain the infimum constitutes a clean advance in extremal graph theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance. No major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The central inequality is obtained by composing the externally established Lovász–Simonovits functions F_r (defined independently of this paper) with their generalized inverses. The manuscript supplies an inductive argument that reduces the (s,t) case to the known s=2 case of Reiher and verifies the required monotonicity and continuity properties of F_r needed for the inverse to be well-defined. These steps rely on prior external results rather than self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the existence and properties of the Lovász–Simonovits clique density functions and their inverses, which are drawn from prior literature in extremal graph theory.

axioms (1)
  • domain assumption The Lovász–Simonovits r-clique density functions F_r are continuous, non-decreasing, and admit generalized inverses that correctly capture the extremal densities.
    Invoked implicitly when applying F_s^{-1} and composing with F_t to obtain the lower bound.

pith-pipeline@v0.9.1-grok · 5669 in / 1326 out tokens · 34084 ms · 2026-07-01T04:18:04.799072+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. An edge-spectral supersaturation of Mubayi's theorem for color-critical graphs

    math.CO 2026-07 unverdicted novelty 8.0

    For color-critical F with χ(F)=r+1≥4, λ²(G) ≥ 2(1-1/r)m + q implies N_F(G) ≥ (B_F - o(1)) q m^{(f-2)/2} for small q, with sharp B_F = α_F/4 ⋅ (2r/(r-1))^{f/2}.

Reference graph

Works this paper leans on

20 extracted references · cited by 1 Pith paper

  1. [1]

    Many T copies in H-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016

    Noga Alon and Clara Shikhelman. Many T copies in H-free graphs.Journal of Combinatorial Theory, Series B, 121:146–172, 2016

    2016

  2. [2]

    On complete subgraphs of different orders.Mathematical Proceedings of the Cambridge Philosophical Society, 79(1):19–24, 1976

    Béla Bollobás. On complete subgraphs of different orders.Mathematical Proceedings of the Cambridge Philosophical Society, 79(1):19–24, 1976

    1976

  3. [3]

    On the number of complete subgraphs contained in certain graphs.Magyar Tud

    Paul Erdős. On the number of complete subgraphs contained in certain graphs.Magyar Tud. Akad. Mat. Kutató Int. Közl., 7(3):459–464, 1962

    1962

  4. [4]

    The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent.Graphs and Combinatorics, 2:113–121, 1986

    Paul Erdős, Péter Frankl, and Vojtěch Rödl. The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent.Graphs and Combinatorics, 2:113–121, 1986

    1986

  5. [5]

    Lower bounds on the number of triangles in a graph.Journal of Graph Theory, 13(4):505–512, 1989

    David Charles Fisher. Lower bounds on the number of triangles in a graph.Journal of Graph Theory, 13(4):505–512, 1989

    1989

  6. [6]

    On sets of acquaintances and strangers at any party.The American Mathematical Monthly, 66(9):778–783, 1959

    Adolph Winkler Goodman. On sets of acquaintances and strangers at any party.The American Mathematical Monthly, 66(9):778–783, 1959

    1959

  7. [7]

    Khadžiivanov and Vladimir S

    Nikolai G. Khadžiivanov and Vladimir S. Nikiforov. The Nordhaus–Stewart–Moon–Moser inequality.Serdica, 4(4):344–350, 1978. In Russian

    1978

  8. [8]

    Asymptotic structure for the clique density theorem.Discrete Analysis, pages Paper No

    Jaehoon Kim, Hong Liu, Oleg Pikhurko, and Maryam Sharifzadeh. Asymptotic structure for the clique density theorem.Discrete Analysis, pages Paper No. 19, 26 pp., 2020

    2020

  9. [9]

    The exact minimum number of triangles in graphs with given order and size.Forum of Mathematics, Pi, 8:e8, 2020

    Hong Liu, Oleg Pikhurko, and Katherine Staden. The exact minimum number of triangles in graphs with given order and size.Forum of Mathematics, Pi, 8:e8, 2020

    2020

  10. [10]

    American Mathematical Society, Providence, RI, 2012

    László Lovász.Large Networks and Graph Limits, volume 60 ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012

    2012

  11. [11]

    On the number of complete subgraphs of a graph

    László Lovász and Miklós Simonovits. On the number of complete subgraphs of a graph. II. InStudies in Pure Mathematics, pages 459–495. Birkhäuser, Basel, 1983

    1983

  12. [12]

    Moon and Leo Moser

    John W. Moon and Leo Moser. On a problem of Turán.Magyar Tud. Akad. Mat. Kutató Int. Közl., 7:283–286, 1962

    1962

  13. [13]

    The number of cliques in graphs of given order and size.Transactions of the American Mathematical Society, 363(3):1599–1618, 2011

    Vladimir Nikiforov. The number of cliques in graphs of given order and size.Transactions of the American Mathematical Society, 363(3):1599–1618, 2011

    2011

  14. [14]

    Nordhaus and Bonnie Madison Stewart

    Edward A. Nordhaus and Bonnie Madison Stewart. Triangles in an ordinary graph.Canadian Journal of Mathematics, 15:33–41, 1963

    1963

  15. [15]

    Razborov

    Oleg Pikhurko and Alexander A. Razborov. Asymptotic structure of graphs with the minimum number of triangles.Combinatorics, Probability and Computing, 26(1):138–160, 2017

    2017

  16. [16]

    Razborov

    Alexander A. Razborov. Flag algebras.Journal of Symbolic Logic, 72(4):1239–1282, 2007. 11

    2007

  17. [17]

    Razborov

    Alexander A. Razborov. On the minimal density of triangles in graphs.Combinatorics, Probability and Computing, 17(4):603–618, 2008

    2008

  18. [18]

    The clique density theorem.Annals of Mathematics, 184(3):683–707, 2016

    Christian Reiher. The clique density theorem.Annals of Mathematics, 184(3):683–707, 2016

    2016

  19. [19]

    Eine extremalaufgabe aus der graphentheorie.Matematikai és Fizikai Lapok, 48:436–452, 1941

    Pál Turán. Eine extremalaufgabe aus der graphentheorie.Matematikai és Fizikai Lapok, 48:436–452, 1941

    1941

  20. [20]

    Aleksandr A. Zykov. On some properties of linear complexes.Matematicheskii Sbornik. Novaya Seriya, 24(66)(2):163–188, 1949. A Proof of Lemma 4.3 We include a short proof of Lemma 4.3, adapted from the proof of Proposition 3.1 in Reiher [18]. The argument may be viewed as a weighted double-counting of the pairs(L,{u, v} ), where L⊆V (G)has size r− 1and u, ...

    1949