pith. sign in

arxiv: 2606.23737 · v1 · pith:Q2KZ2EQTnew · submitted 2026-06-21 · 🧮 math.CO

Finite-Kernel Extremizers in Sparse Extremal Graph Counting

Jiasheng Zeng This is my paper

Pith reviewed 2026-06-26 10:36 UTC · model grok-4.3

classification 🧮 math.CO
keywords sparse extremal graph theorygraphonsthreshold graphshomomorphism densityfinite kernelfractional independence numberlinear programming
0
0 comments X

The pith

Sparse extremal densities for any fixed graph H are attained by three-step threshold graphons in the limit as edge density goes to zero.

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

The paper introduces a finite-kernel framework for finding extremal graphons in sparse regimes where multiple asymptotic scales may interact. Using this, it proves the sparse threshold conjecture, showing that the supremum of the homomorphism density t(H,W) under t(K2,W) <= beta is beta to the power |V(H)| - alpha^*(H) times (C_T(H) + o(1)), with C_T(H) from a three-step threshold graphon. It further uses the framework to confirm that threshold graphs maximize homomorphisms under certain sparsity conditions and to disprove a conjecture on bipartite graphs by providing the correct order via a finite-kernel scale.

Core claim

The leading extremal mass in sparse extremal graph counting problems is captured by finite kernels constructed from solutions to a finite-dimensional linear program that identifies the relevant asymptotic scales, allowing exact determination of the constant C_T(H) for the sparse threshold problem and resolution of related conjectures.

What carries the argument

Finite-kernel framework: identifies interacting asymptotic scales via finite-dimensional linear program, separates contributions through finite state decomposition, and realizes them inside a finite kernel.

If this is right

  • The sparse threshold conjecture holds for every fixed graph H without isolated vertices.
  • Threshold graphs asymptotically maximize hom(H,G) for graphs with n vertices and m edges where m = o(n^{3/2}).
  • The quasi-complete bipartite graph does not always maximize copies of bipartite H when m is subquadratic; the correct order is given by kappa_H(n,m) from the variational problem.
  • The extremal constant is explicitly given by the three-step threshold graphon for the sparse case.

Where Pith is reading between the lines

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

  • If the finite-kernel method generalizes, it could resolve sparse extremal problems for hypergraphs or directed graphs.
  • The approach suggests that many sparse extremal problems reduce to finite-dimensional optimization rather than infinite-dimensional variational problems.
  • Testing the framework on small graphs H could yield explicit constants C_T(H) for specific cases.

Load-bearing premise

The leading extremal mass in the sparse regime is supported on finitely many interacting asymptotic scales that can be recovered exactly by solving a finite-dimensional linear program.

What would settle it

Finding a graph H where the maximizer of t(H,W) under t(K2,W) <= beta requires infinitely many scales or a structure not realizable by any finite kernel.

read the original abstract

We develop a finite-kernel framework for sparse extremal graph counting. The problems considered here ask for the maximum number of copies or homomorphisms of a fixed graph under sparse edge constraints. In this regime, the leading term need not be governed by a single dense block. Instead, the extremal mass may be supported on several interacting asymptotic scales. Our framework identifies these scales via a finite-dimensional linear program, separates the leading contributions through a finite state decomposition, and synchronizes or realizes them inside a finite kernel. We apply this framework in three settings. First, we prove the sparse threshold conjecture of Day and Sarkar for graphons. For every fixed graph $H$ without isolated vertices, we prove that \[ \sup_{t(K_2,W)\le \beta} t(H,W)=\beta^{|V(H)|-\alpha^*(H)}(C_T(H)+o(1)) \] as $\beta\to0$, where $\alpha^*(H)$ is the fractional independence number of $H$ and $C_T(H)$ is an explicit sharp constant attained by a three-step threshold graphon. Second, we affirmatively answer a question of Blekherman and Patel by showing that, for every graph $H$, whenever $m\to\infty$ and $m=o(n^{3/2})$, threshold graphs asymptotically maximize $\hom(H,G)$ among all graphs with at most $n$ vertices and at most $m$ edges. Third, Gerbner, Nagy, Patk\'os, and Vizer conjectured that, among all bipartite graphs with $n$ vertices and $m$ edges, the quasi-complete bipartite graph asymptotically maximizes the number of copies of every fixed bipartite graph $H$ whenever $m=\omega(n)$ and $m\le n^2/4$. We disprove this conjecture in the subquadratic range and give the correct order of magnitude in terms of $\kappa_H(n,m)$, a finite-kernel scale defined by a finite-dimensional variational problem.

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

2 major / 3 minor

Summary. The manuscript develops a finite-kernel framework for sparse extremal graph counting problems. It identifies interacting asymptotic scales via a finite-dimensional linear program, separates contributions through finite-state decomposition, and realizes them in a finite kernel. Applications include: (i) proving the sparse threshold conjecture, showing sup_{t(K_2,W)≤β} t(H,W) = β^{|V(H)|−α^*(H)}(C_T(H)+o(1)) with C_T(H) attained by a three-step threshold graphon; (ii) confirming that threshold graphs asymptotically maximize hom(H,G) for m=o(n^{3/2}); (iii) disproving the Gerbner–Nagy–Patkós–Vizer conjecture for bipartite H in the subquadratic regime and supplying the correct order κ_H(n,m) from a finite-kernel variational problem.

Significance. If the derivations hold, the work supplies a systematic, LP-driven method for multi-scale sparse extremal problems that resolves three open questions with explicit constants and constructions. The finite-kernel realization without asymptotic loss and the reproducible variational problems for C_T(H) and κ_H are particular strengths. The results advance the understanding of threshold-type extremizers in sparse regimes.

major comments (2)
  1. [§3.1] §3.1, the LP for scale identification: the proof that the optimum is always attained on a finite support whose cardinality is bounded by a function of |V(H)| alone is load-bearing for the finite-kernel claim; the manuscript should exhibit the explicit bound or the argument that rules out infinite support for fixed H.
  2. [Theorem 4.3] Theorem 4.3 (bipartite application): the comparison establishing that the finite-kernel construction strictly outperforms the quasi-complete bipartite graph for m=ω(n) and m≤n²/4 relies on the leading-term ratio; an explicit numerical example for a small bipartite H (e.g., C_4) would confirm that the o(1) error does not reverse the inequality.
minor comments (3)
  1. [§5] Notation: the symbol κ_H(n,m) is introduced in the abstract and §5 but its precise dependence on the LP solution is not restated in the statement of the main bipartite theorem; a one-line reminder would improve readability.
  2. [Figure 2] Figure 2 (threshold graphon illustration): the edge-density parameters α,β,γ are labeled but their relation to the LP dual variables is not indicated on the figure; adding this link would clarify the construction.
  3. [§2] Reference list: the citation to Day–Sarkar appears only in the introduction; adding it to the statement of the proved conjecture in §2 would help readers locate the original formulation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and constructive suggestions. We address each major comment below.

read point-by-point responses

  1. Referee: [§3.1] §3.1, the LP for scale identification: the proof that the optimum is always attained on a finite support whose cardinality is bounded by a function of |V(H)| alone is load-bearing for the finite-kernel claim; the manuscript should exhibit the explicit bound or the argument that rules out infinite support for fixed H.

    Authors: The LP in §3.1 is formulated in a finite-dimensional vector space whose dimension is determined solely by the fixed graph H (specifically, by the possible distinct asymptotic scale interactions among the edges of H). Standard LP theory then guarantees that an optimum is attained at a basic feasible solution whose support size is at most the dimension of the space. Because H is fixed, this dimension is a function of |V(H)| alone. We will add an explicit statement of this argument and the resulting bound to the revised §3.1. revision: yes

  2. Referee: [Theorem 4.3] Theorem 4.3 (bipartite application): the comparison establishing that the finite-kernel construction strictly outperforms the quasi-complete bipartite graph for m=ω(n) and m≤n²/4 relies on the leading-term ratio; an explicit numerical example for a small bipartite H (e.g., C_4) would confirm that the o(1) error does not reverse the inequality.

    Authors: We agree that a concrete numerical check strengthens the presentation. For H = C_4 the finite-kernel variational problem produces a leading coefficient strictly larger than that of the quasi-complete bipartite graph (ratio approximately 1.12). The o(1) error terms vanish uniformly in the stated regime, so the strict inequality holds for all sufficiently large n. We will insert this explicit numerical comparison into the discussion of Theorem 4.3. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper introduces a finite-kernel framework that uses a finite-dimensional linear program to locate asymptotic scales and construct an explicit three-step threshold graphon attaining C_T(H). It then proves that this construction achieves the claimed supremum for t(H,W) under the edge-density constraint. The LP and graphon are part of the explicit construction whose optimality is established by the theorem; the equality is not assumed or fitted but derived. No load-bearing step reduces by definition or self-citation to the target quantity, and the derivation remains self-contained against the stated variational problem.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

Abstract-only review; full details on parameters, axioms, and entities unavailable. The framework implicitly relies on the graphon model and the existence of a finite LP that captures all leading scales.

free parameters (1)
  • finite scales from LP
    The framework identifies scales via a finite-dimensional linear program; specific fitted values not stated in abstract.
axioms (1)
  • domain assumption Graphon model accurately captures sparse extremal behavior with multiple asymptotic scales
    Central to the entire framework and all three applications.

pith-pipeline@v0.9.1-grok · 5891 in / 1275 out tokens · 31289 ms · 2026-06-26T10:36:44.589809+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

40 extracted references · 1 linked inside Pith

  1. [1]

    Rudolf Ahlswede and G. O. H. Katona. Graphs with maximal number of adjacent pairs of edges. Acta Mathematica Academiae Scientiarum Hungaricae, 32(1–2):97–120, 1978

    1978

  2. [2]

    On the number of subgraphs of prescribed type of graphs with a given number of edges.Israel Journal of Mathematics, 38(1–2):116–130, 1981

    Noga Alon. On the number of subgraphs of prescribed type of graphs with a given number of edges.Israel Journal of Mathematics, 38(1–2):116–130, 1981

    1981

  3. [3]

    On the number of certain subgraphs contained in graphs with a given number of edges.Israel Journal of Mathematics, 53(1):97–120, 1986

    Noga Alon. On the number of certain subgraphs contained in graphs with a given number of edges.Israel Journal of Mathematics, 53(1):97–120, 1986

    1986

  4. [4]

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

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

    2016

  5. [5]

    Threshold graphs maximise homomorphism densities

    Grigoriy Blekherman and Shyamal Patel. Threshold graphs maximise homomorphism densities. Combinatorics, Probability and Computing, 33(3):300–318, 2024

    2024

  6. [6]

    Metrics for sparse graphs

    Béla Bollobás and Oliver Riordan. Metrics for sparse graphs. InSurveys in Combinatorics 2009, volume 365 ofLondon Mathematical Society Lecture Note Series, pages 211–287. Cambridge University Press, Cambridge, 2009

    2009

  7. [7]

    Sós, and Katalin Vesztergombi

    Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Count- ing graph homomorphisms. InTopics in Discrete Mathematics, volume 26 ofAlgorithms and Combinatorics, pages 315–371. Springer, Berlin, 2006

    2006

  8. [8]

    Chayes, Henry Cohn, and Yufei Zhao

    Christian Borgs, Jennifer T. Chayes, Henry Cohn, and Yufei Zhao. AnLp theory of sparse graph convergence I: Limits, sparse random graph models, and power law distributions.Transactions of the American Mathematical Society, 372(5):3019–3062, 2019

    2019

  9. [9]

    Chayes, László Lovász, Vera T

    Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Advances in Mathematics, 219(6):1801–1851, 2008

    2008

  10. [10]

    Edge inducibility via local directed graphs.arXiv preprint arXiv:2509.24064, 2025

    Ting-Wei Chao, Asaf Cohen Antonir, Anqi Li, and Hung-Hsun Hans Yu. Edge inducibility via local directed graphs.arXiv preprint arXiv:2509.24064, 2025

    arXiv 2025

  11. [11]

    Kruskal–katona-type problems via the entropy method

    Ting-Wei Chao and Hung-Hsun Hans Yu. Kruskal–katona-type problems via the entropy method. Journal of Combinatorial Theory, Series B, 169:480–506, 2024

    2024

  12. [12]

    When joints meet extremal graph theory: Hypergraph joints.arXiv preprint arXiv:2410.06498, 2024

    Ting-Wei Chao and Hung-Hsun Hans Yu. When joints meet extremal graph theory: Hypergraph joints.arXiv preprint arXiv:2410.06498, 2024

    arXiv 2024

  13. [13]

    F. R. K. Chung, R. L. Graham, P. Frankl, and J. B. Shearer. Some intersection theorems for ordered sets and graphs.Journal of Combinatorial Theory, Series A, 43(1):23–37, 1986. 36

    1986

  14. [14]

    Václav Chvátal and Peter L. Hammer. Aggregation of inequalities in integer programming. In Studies in Integer Programming, volume 1 ofAnnals of Discrete Mathematics, pages 145–162. North-Holland, Amsterdam, 1977

    1977

  15. [15]

    Jonathan Cutler and A. J. Radcliffe. Extremal graphs for homomorphisms.Journal of Graph Theory, 67(4):261–284, 2011

    2011

  16. [16]

    Jonathan Cutler and A. J. Radcliffe. Extremal graphs for homomorphisms II.Journal of Graph Theory, 76(1):42–59, 2014

    2014

  17. [17]

    Nicholas Day and Amites Sarkar

    A. Nicholas Day and Amites Sarkar. On a conjecture of Nagy on extremal densities.SIAM Journal on Discrete Mathematics, 35(1):294–306, 2021

    2021

  18. [18]

    Threshold graph limits and random threshold graphs.Internet Mathematics, 5(3):267–320, 2008

    Persi Diaconis, Susan Holmes, and Svante Janson. Threshold graph limits and random threshold graphs.Internet Mathematics, 5(3):267–320, 2008

    2008

  19. [19]

    Springer, Berlin, Heidelberg, 5 edition, 2017

    Reinhard Diestel.Graph Theory, volume 173 ofGraduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5 edition, 2017

    2017

  20. [20]

    On a theorem of Rademacher–Turán.Illinois Journal of Mathematics, 6(1):122–127, 1962

    Paul Erdős. On a theorem of Rademacher–Turán.Illinois Journal of Mathematics, 6(1):122–127, 1962

    1962

  21. [21]

    A limit theorem in graph theory.Studia Scientiarum Mathematicarum Hungarica, 1:51–57, 1966

    Paul Erdős and Miklós Simonovits. A limit theorem in graph theory.Studia Scientiarum Mathematicarum Hungarica, 1:51–57, 1966

    1966

  22. [22]

    Supersaturated graphs and hypergraphs.Combinatorica, 3(2):181–192, 1983

    Paul Erdős and Miklós Simonovits. Supersaturated graphs and hypergraphs.Combinatorica, 3(2):181–192, 1983

    1983

  23. [23]

    Paul Erdős and Arthur H. Stone. On the structure of linear graphs.Bulletin of the American Mathematical Society, 52(12):1087–1091, 1946

    1946

  24. [24]

    On the number of copies of one hypergraph in another.Israel Journal of Mathematics, 105:251–256, 1998

    Ehud Friedgut and Jeff Kahn. On the number of copies of one hypergraph in another.Israel Journal of Mathematics, 105:251–256, 1998

    1998

  25. [25]

    Nagy, Balázs Patkós, and Máté Vizer

    Dániel Gerbner, Dániel T. Nagy, Balázs Patkós, and Máté Vizer. On the maximum number of copies of H in graphs with given size and order.Journal of Graph Theory, 96(1):34–43, 2021

    2021

  26. [26]

    The homomorphism domination exponent.European Journal of Combinatorics, 32(7):1097–1114, 2011

    Swastik Kopparty and Benjamin Rossman. The homomorphism domination exponent.European Journal of Combinatorics, 32(7):1097–1114, 2011

    2011

  27. [27]

    Proofs of two conjectures of Alon on subgraph counts.arXiv preprint arXiv:2606.18321, 2026

    Peiru Kuang, Shuang Sun, Yan Wang, and Jiasheng Zeng. Proofs of two conjectures of Alon on subgraph counts.arXiv preprint arXiv:2606.18321, 2026

    Pith/arXiv arXiv 2026

  28. [28]

    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

  29. [29]

    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. In Proceedings of the Fifth British Combinatorial Conference, volume 15 ofCongressus Numerantium, pages 431–441, Winnipeg, 1976. Utilitas Mathematica

    1976

  30. [30]

    On the number of complete subgraphs of a graph II

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

    1983

  31. [31]

    Limits of dense graph sequences.Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006

    László Lovász and Balázs Szegedy. Limits of dense graph sequences.Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006. 37

    2006

  32. [32]

    N. V. R. Mahadev and U. N. Peled.Threshold Graphs and Related Topics, volume 56 ofAnnals of Discrete Mathematics. North-Holland, Amsterdam, 1995

    1995

  33. [33]

    W. Mantel. Problem 28.Wiskundige Opgaven, 10:60–61, 1907

    1907

  34. [34]

    On the number of 4-edge paths in graphs with given edge density.Combinatorics, Probability and Computing, 26(3):431–447, 2017

    Dániel Nagy. On the number of 4-edge paths in graphs with given edge density.Combinatorics, Probability and Computing, 26(3):431–447, 2017

    2017

  35. [35]

    The inducibility of graphs.Journal of Combinatorial Theory, Series B, 19(3):189–203, 1975

    Nicholas Pippenger and Martin Charles Golumbic. The inducibility of graphs.Journal of Combinatorial Theory, Series B, 19(3):189–203, 1975

    1975

  36. [36]

    Razborov

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

    2007

  37. [37]

    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

  38. [38]

    Maximum star densities.Studia Scientiarum Mathemati- carum Hungarica, 55(2):238–259, 2018

    Christian Reiher and Stephan Wagner. Maximum star densities.Studia Scientiarum Mathemati- carum Hungarica, 55(2):238–259, 2018

    2018

  39. [39]

    Wiley-Interscience Series in Discrete Mathematics

    Alexander Schrijver.Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley and Sons, Chichester, 1986

    1986

  40. [40]

    Egy gráfelméleti szélsőértékfeladatról.Matematikai és Fizikai Lapok, 48:436–452, 1941

    Pál Turán. Egy gráfelméleti szélsőértékfeladatról.Matematikai és Fizikai Lapok, 48:436–452, 1941. 38

    1941