pith. sign in

arxiv: 2606.18321 · v1 · pith:RDSQ667Knew · submitted 2026-06-16 · 🧮 math.CO

Proofs of Two Conjectures of Alon on Subgraph Counts

Peiru Kuang , Shuang Sun , Yan Wang , Jiasheng Zeng This is my paper

Pith reviewed 2026-06-27 00:05 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C35
keywords extremal subgraph countsAlon conjecturesvariational problemsfinite coresdisjoint unions of starsgraph automorphismsasymptotic densities
0
0 comments X

The pith

The limit of N(m,H) divided by m to the power gamma(H) exists for every fixed graph H and equals Lambda(H) over the order of the automorphism group of H.

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

The paper proves Alon's 1986 conjecture that the maximum number of copies of a fixed graph H in any m-edge graph, denoted N(m,H), satisfies that the normalized quantity N(m,H) over m to the power gamma(H) has a limit as m tends to infinity. It identifies this limit explicitly as lambda(H) equal to Lambda(H) divided by the size of the automorphism group of H, where Lambda(H) comes from a variational problem over finite cores. The authors also prove the second conjecture that when H is a disjoint union of stars, an extremal graph achieving N(m,H) can always be chosen to itself be a disjoint union of stars.

Core claim

For any fixed graph H with no isolated vertices, the limit as m approaches infinity of N(m,H) over m to the power gamma(H) exists and equals lambda(H) which is Lambda(H) over the order of the automorphism group of H, where Lambda(H) is characterized by a variational problem over finite cores. If H is a disjoint union of stars, then for every m an extremal graph attaining N(m,H) may be chosen to be a disjoint union of stars.

What carries the argument

The variational problem over finite cores that defines Lambda(H) and thereby determines the exact asymptotic density lambda(H) of the maximum number of H-subgraphs.

Load-bearing premise

The variational problem over finite cores correctly captures the asymptotic density of the extremal constructions used to identify the limit lambda(H).

What would settle it

A concrete graph H together with numerical computation of N(m,H) for a sequence of large m values showing that the ratio N(m,H) over m to the power gamma(H) fails to approach the value Lambda(H) over the automorphism group order obtained from the variational problem.

read the original abstract

All graphs considered are finite with no isolated vertices. Let $N(m,H)$ be the maximum number of subgraphs of a graph $G$ isomorphic to $H$, taken over all graphs $G$ with $m$ edges. Alon proved that $N(m,H)=\Theta_H(m^{\gamma(H)})$, where $\gamma(H)=(|V(H)|+D(H))/2$ and $D(H)=\max_{S\subseteq V(H)}(|S|-|N_H(S)|)$, and conjectured [Conjecture 1, Isr. J. Math., 1986] that limit of $N(m,H)/m^{\gamma(H)}$ exists as $m\to\infty$. We prove this conjecture and identify the limit as $\lambda(H)=\Lambda(H)/|\operatorname{Aut}(H)|$, where $\Lambda(H)$ is characterized by a variational problem over finite cores. We also resolve another conjecture of Alon [Conjecture 2, Isr. J. Math., 1986], which stated that if $H$ is a disjoint union of stars, then for every $m$ an extremal graph attaining $N(m,H)$ may be chosen to be a disjoint union of stars.

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 / 1 minor

Summary. The paper proves two 1986 conjectures of Alon on subgraph counts. It establishes that the limit λ(H) = lim_{m→∞} N(m,H)/m^{γ(H)} exists and equals Λ(H)/|Aut(H)|, where Λ(H) is given by a variational problem over finite cores; it also shows that when H is a disjoint union of stars, an extremal graph attaining N(m,H) may always be chosen as a disjoint union of stars.

Significance. Resolving these conjectures supplies the precise asymptotic density for the maximum number of copies of a fixed H and gives an explicit variational characterization of the limit. The second result supplies a clean structural description of the extremal graphs for the star-union case. Both strengthen the earlier Θ(m^{γ(H)}) bound of Alon and place the problem in the framework of variational problems on cores.

minor comments (1)
  1. The abstract refers to 'finite cores' and the variational problem defining Λ(H), but no explicit definition or section reference is supplied in the provided material.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their summary of the paper and for acknowledging the resolution of Alon's two conjectures. The report accurately reflects the main results on the existence of the limit λ(H) and the structural characterization for star unions. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No circularity; direct proofs of external conjectures

full rationale

The manuscript supplies explicit proofs of two 1986 conjectures of Alon. The first establishes existence of the limit λ(H) and identifies it with an independently characterized variational quantity Λ(H)/|Aut(H)| over finite cores; the second shows that extremal graphs for star-disjoint-union H may be taken as star-disjoint unions. Neither step reduces to a fitted parameter renamed as prediction, a self-definitional loop, or a load-bearing self-citation. The variational characterization is introduced as part of the proved statement rather than presupposed by it, and all cited prior work is external (Alon 1986). The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard graph-theoretic definitions and the well-posedness of a variational problem over finite cores; no free parameters or new postulated entities are introduced.

axioms (1)
  • standard math Standard axioms and definitions of finite simple graphs, subgraph isomorphism, and automorphism groups.
    Invoked throughout the statements of N(m,H), gamma(H), Aut(H), and the variational problem.

pith-pipeline@v0.9.1-grok · 5754 in / 1272 out tokens · 34552 ms · 2026-06-27T00:05:03.127009+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. Finite-Kernel Extremizers in Sparse Extremal Graph Counting

    math.CO 2026-06 unverdicted novelty 7.0

    Introduces finite-kernel framework for sparse extremal graph counting that proves the Day-Sarkar sparse threshold conjecture, affirms threshold graphs as maximizers for homomorphisms when m=o(n^{3/2}), and disproves a...

Reference graph

Works this paper leans on

23 extracted references · cited by 1 Pith paper

  1. [1]

    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

  2. [2]

    On the number of certain subgraphs contained in graphs with a given number of edges.Israel Journal of Mathematics, 53: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:97–120, 1986

    1986

  3. [3]

    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

  4. [4]

    Paths in graphs.Studia Scientiarum Mathematicarum Hungarica, 38(1–4):115–137, 2001

    Béla Bollobás and Amites Sarkar. Paths in graphs.Studia Scientiarum Mathematicarum Hungarica, 38(1–4):115–137, 2001. 15

    2001

  5. [5]

    Paths of length four.Discrete Mathematics, 265:357–363, 2003

    Béla Bollobás and Amites Sarkar. Paths of length four.Discrete Mathematics, 265:357–363, 2003

    2003

  6. [6]

    Brown and Alexander Sidorenko

    Jason I. Brown and Alexander Sidorenko. The inducibility of complete bipartite graphs.Journal of Graph Theory, 18(6):629–645, 1994

    1994

  7. [7]

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

    1986

  8. [8]

    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

  9. [9]

    Springer, Berlin, 5 edition, 2017

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

    2017

  10. [10]

    Subhypergraph counts in extremal and random hypergraphs and the fractionalq-independence.Journal of Combinatorial Optimization, 19:184–199, 2010

    Andrzej Dudek, Joanna Polcyn, and Andrzej Ruciński. Subhypergraph counts in extremal and random hypergraphs and the fractionalq-independence.Journal of Combinatorial Optimization, 19:184–199, 2010

    2010

  11. [11]

    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

  12. [12]

    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

  13. [13]

    Graphs with maximum number of star-forests.Studia Scientiarum Mathematicarum Hungarica, 27:403–407, 1992

    Zoltán Füredi. Graphs with maximum number of star-forests.Studia Scientiarum Mathematicarum Hungarica, 27:403–407, 1992

    1992

  14. [14]

    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 ofHin graphs with given size and order.Journal of Graph Theory, 96(1):34–43, 2021

    2021

  15. [15]

    Upper tails for subgraph counts in random graphs.Israel Journal of Mathematics, 142:61–92, 2004

    Svante Janson, Krzysztof Oleszkiewicz, and Andrzej Ruciński. Upper tails for subgraph counts in random graphs.Israel Journal of Mathematics, 142:61–92, 2004

    2004

  16. [16]

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

    1907

  17. [17]

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

    2017

  18. [18]

    Nemhauser and Leslie E

    George L. Nemhauser and Leslie E. Trotter, Jr. Properties of vertex packing and independence system polyhedra.Mathematical Programming, 6:48–61, 1974

    1974

  19. [19]

    Nemhauser and Leslie E

    George L. Nemhauser and Leslie E. Trotter, Jr. Vertex packings: Structural properties and algorithms.Mathematical Programming, 8:232–248, 1975

    1975

  20. [20]

    John Wiley & Sons, Chichester, 1986

    Alexander Schrijver.Theory of Linear and Integer Programming. John Wiley & Sons, Chichester, 1986

    1986

  21. [21]

    A method for solving extremal problems in graph theory, stability problems

    Miklós Simonovits. A method for solving extremal problems in graph theory, stability problems. In Paul Erdős and Gábor Katona, editors,Theory of Graphs, pages 279–319. Academic Press, New York, 1968

    1968

  22. [22]

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

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

    1941

  23. [23]

    Generalized Turán number with given size.arXiv preprint arXiv:2508.00483, 2025

    Yan Wang, Yue Xu, Jiasheng Zeng, and Xiao-Dong Zhang. Generalized Turán number with given size.arXiv preprint arXiv:2508.00483, 2025. 16

    arXiv 2025