pith. sign in

arxiv: 2606.22661 · v1 · pith:JLJAMX23new · submitted 2026-06-21 · 🧮 math.CO

Excluding an induced star in dense random graphs

Sam van der Poel This is my paper

Pith reviewed 2026-06-26 09:52 UTC · model grok-4.3

classification 🧮 math.CO
keywords induced starsgraphonsentropy densitylarge deviationsrandom graphsphase transitionsextremal graph theoryTurán-type problems
0
0 comments X

The pith

Dense graphs without an induced star K_{1,k} have explicit entropy densities and large-deviation rates solved by graphon optimization, with phase transitions at critical densities.

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

The paper determines the asymptotic number and typical structure of graphs on n vertices with no induced copy of the star K_{1,k} when the graphs are dense. It solves the associated graphon variational problems both for a fixed edge density γ and for the conditioned Erdős–Rényi model G(n,p) at constant p. The solutions produce closed-form expressions for the entropy density of such graphs and for the large-deviation rate function of the induced-star-free event. These expressions display a second-order phase transition at an explicit critical density γ_k and a first-order transition at a critical p_k. The optimizers are fully characterized, and the typical graphs are described structurally in both regimes.

Core claim

The entropy density of induced-K_{1,k}-free graphs with Θ(n²) edges is given by an explicit formula exhibiting a second-order phase transition at γ_k, while the large-deviation rate function for G(n,p) being induced-K_{1,k}-free exhibits a first-order phase transition at p_k; the optimizers of both variational problems are completely characterized, with infinitely many optimal graphons possible yet a unique one in the cut metric, and the typical structures are the complement of a (k-1)-partite graph (supercritical) or that complement plus a sparse remainder (subcritical fixed-density case).

What carries the argument

The graphon variational problem maximizing entropy (or minimizing rate) subject to the induced-K_{1,k}-free constraint, solved at fixed edge density γ and for conditioned G(n,p).

If this is right

  • For parameters above the critical values the typical structure is exactly the complement of a (k-1)-partite graph with high probability.
  • Below the critical density in the fixed-edge model the typical graph is the complement of a (k-1)-partite graph plus an o(n²)-edge remainder.
  • In the subcritical conditioned random-graph model a typical sample has only o(n²) edges.
  • There exist parameter regimes with infinitely many optimal graphons, yet the cut-metric limit of the typical structure remains unique.

Where Pith is reading between the lines

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

  • The same variational approach could be applied to other forbidden induced bipartite graphs to obtain analogous entropy formulas.
  • The explicit location of γ_k supplies a concrete threshold that could be tested in algorithmic sampling of induced-star-free graphs.
  • The distinction between second-order and first-order transitions may indicate different stability behaviors under small perturbations of the edge density or p.

Load-bearing premise

The graphon variational problems for induced-K_{1,k}-free graphs admit explicit closed-form solutions together with a complete characterization of their optimizers, including the locations of the critical densities γ_k and p_k.

What would settle it

Direct numerical enumeration or Monte-Carlo sampling of the number of induced-K_{1,k}-free graphs on moderate n at several densities straddling the predicted γ_k, compared against the explicit entropy formula.

Figures

Figures reproduced from arXiv: 2606.22661 by Sam van der Poel.

Figure 1
Figure 1. Figure 1: The entropy density Ek (left) and rate function Rk (right) for k = 3, 4, 5. The curves R3, R4, and R5 coincide on the interval [0, p5]. The most important feature of both Theorems 1.1 and 1.2 is that the entropy density and rate function are given by piecewise formulas, reflecting that there are competing struc￾tural mechanisms that determine the exponential rates. These competing structures were heuristic… view at source ↗
Figure 2
Figure 2. Figure 2: Optimal graphons for induced-K1,8-free graphs of fixed edge density. The top row shows the unique optimal graphons of edge densities γ8 ≈ 0.317, 1 2 , 2 3 , and 5 6 . The bottom row shows examples of optimal graphons of edge density 1 10 . The white areas represent density 0, gray areas density pγ ∈ (0, 1), and black areas density 1. To understand heuristically why the all-zero graphon is the subcritical o… view at source ↗
read the original abstract

For fixed $k\geq3$, we study the asymptotic number and typical structure of dense graphs with no induced copy of the star $K_{1,k}$. We solve the associated graphon variational problems both at fixed constant edge density $\gamma$ and for the conditioned Erd\H{o}s--R\'enyi random graph $G(n,p)$ for constant $p$. As consequences, we obtain explicit formulas for the entropy density of induced-$K_{1,k}$-free graphs with $\Theta(n^2)$ edges and for the large deviation rate function for the event that $G(n,p)$ is induced-$K_{1,k}$-free. The entropy density exhibits a second-order phase transition at an explicit critical density $\gamma_k$, while the rate function exhibits a first-order phase transition at a critical parameter $p_k$. We completely characterize the optimizers of both variational problems. Both models have parameter values for which there are infinitely many optimal graphons, but there is always a unique graphon that represents the typical structure in cut metric. We refine the graphon-level results by giving a detailed structural description of both models. For supercritical parameters, each random graph model is the complement of a $(k-1)$-partite graph with high probability. In the subcritical regime of the fixed-density model, the typical structure is the disjoint union of the complement of a $(k-1)$-partite graph, and a sparse remainder. In the subcritical regime of the conditioned Erd\H{o}s--R\'enyi random graph, a typical sample has $o(n^2)$ edges.

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

Summary. The paper studies the asymptotic number and typical structure of dense graphs without an induced copy of the star K_{1,k} for fixed k≥3. It solves the associated graphon variational problems both at fixed constant edge density γ and for the conditioned Erdős–Rényi random graph G(n,p) for constant p. As consequences, explicit formulas are obtained for the entropy density of induced-K_{1,k}-free graphs with Θ(n²) edges and for the large deviation rate function for the event that G(n,p) is induced-K_{1,k}-free. The entropy density exhibits a second-order phase transition at an explicit critical density γ_k, while the rate function exhibits a first-order phase transition at a critical parameter p_k. The optimizers of both variational problems are completely characterized; both models have parameter values with infinitely many optimal graphons, but there is always a unique graphon representing the typical structure in the cut metric. Structural descriptions are refined: supercritical samples are complements of (k-1)-partite graphs w.h.p.; subcritical fixed-density samples are the disjoint union of such a complement and a sparse remainder; subcritical conditioned G(n,p) samples have o(n²) edges.

Significance. If the results hold, the manuscript delivers explicit closed-form solutions to the graphon variational problems for induced-K_{1,k}-free graphs together with complete optimizer characterization and explicit critical densities γ_k, p_k. This constitutes a substantial advance in the theory of induced-forbidden subgraphs for dense graphs and random-graph large deviations, including the handling of non-unique optimizers while identifying a unique typical structure in the cut metric and providing regime-specific structural descriptions.

minor comments (3)
  1. §1 (Introduction): the definitions of the entropy density and the large-deviation rate function should be stated explicitly before the variational problems are introduced, to make the transition from the abstract claims to the technical development self-contained.
  2. The notation for the critical values γ_k and p_k is introduced in the abstract and §2; a single consolidated statement collecting their explicit formulas (with the dependence on k) would improve readability.
  3. Figure captions (throughout): several figures depicting optimal graphons would benefit from an explicit statement of the cut-metric distance to the claimed unique typical structure, to illustrate the uniqueness claim numerically.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, recognition of its contributions to graphon variational problems for induced-K_{1,k}-free graphs, and recommendation of minor revision. No major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The abstract states that the graphon variational problems are solved to yield explicit formulas for entropy density and large-deviation rate functions, with complete characterization of optimizers and explicit critical densities γ_k, p_k. No derivation steps, equations, or self-citations are exhibited in the provided material that reduce any claimed prediction or result to a fitted input, self-definition, or prior author work by construction. The central claims rest on solving the variational problems rather than renaming or fitting quantities already present in the inputs. This is the normal case of a self-contained mathematical derivation with no load-bearing circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, ad-hoc axioms, or invented entities are named. The work rests on standard graphon theory and variational calculus whose details cannot be audited here.

axioms (1)
  • standard math Existence and well-posedness of graphon variational problems for induced-hereditary properties
    Invoked implicitly when the abstract states that the problems are solved.

pith-pipeline@v0.9.1-grok · 5811 in / 1156 out tokens · 28520 ms · 2026-06-26T09:52:15.658913+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

49 extracted references · 1 canonical work pages

  1. [1]

    V. E. Alekseev. On the entropy values of hereditary classes of graphs. Discrete Mathematics and Applications 3.2 (1993), pp. 191–200

    1993

  2. [2]

    N. Alon, J. Balogh, B. Bollob´ as, and R. Morris. The structure of almost all graphs in a hereditary property. Journal of Combinatorial Theory, Series B 101.2 (2011), pp. 85–110

    2011

  3. [3]

    Balogh, B

    J. Balogh, B. Bollob´ as, and M. Simonovits. The typical structure of graphs without given excluded subgraphs. Random Structures & Algorithms 34.3 (2009), pp. 305–318

    2009

  4. [4]

    Balogh and J

    J. Balogh and J. Butterfield. Excluding induced subgraphs: critical graphs. Random Structures & Algorithms 38.1-2 (2011), pp. 100–120

    2011

  5. [5]

    Balogh, R

    J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. Journal of the American Mathematical Society 28.3 (2015), pp. 669–709

    2015

  6. [6]

    Balogh, R

    J. Balogh, R. Morris, W. Samotij, and L. Warnke. The typical structure of sparse Kr+1-free graphs. Trans. Amer. Math. Soc. 368.9 (2016), pp. 6439–6485. 82 REFERENCES

    2016

  7. [7]

    Balogh and W

    J. Balogh and W. Samotij. An efficient container lemma. Discrete Analysis (Dec. 10, 2020)

    2020

  8. [8]

    Bollob´ as and A

    B. Bollob´ as and A. Thomason. Hereditary and monotone properties of graphs. The mathematics of Paul Erd˝ os, II. Vol. 14. Algorithms Combin. Springer, Berlin, 1997, pp. 70–78

    1997

  9. [9]

    Borgs, J

    C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing. Adv. Math. 219.6 (2008), pp. 1801–1851

    2008

  10. [10]

    B¨ ottcher, A

    J. B¨ ottcher, A. Taraz, and A. W¨ urfl. Perfect graphs of fixed density: Counting and homogeneous sets. Combinatorics, Probability and Computing 21.5 (2012), pp. 661–682

    2012

  11. [11]

    Chatterjee and S

    S. Chatterjee and S. R. S. Varadhan. The large deviation principle for the Erd˝ os-R´ enyi random graph. European Journal of Combinatorics 32.7 (2011), pp. 1000–1017

    2011

  12. [12]

    P. Erd˝ os. Some recent results on extremal problems in graph theory. Results. Theory of Graphs (In- ternat. Sympos., Rome, 1966) . Gordon & Breach, New York, 1967, 117–123 (English), pp. 124–130 (French)

    1966

  13. [13]

    Erd˝ os, D

    P. Erd˝ os, D. J. Kleitman, and B. L. Rothschild. Asymptotic enumeration of Kn-free graphs. Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II . Accad. Naz. Lincei, Rome, 1976, pp. 19–27

    1973

  14. [14]

    Hatami, S

    H. Hatami, S. Janson, and B. Szegedy. Graph properties, graph limits, and entropy. Journal of Graph Theory 87.2 (2018), pp. 208–229

    2018

  15. [15]

    G. Jaeger. The Ehrenfest classification of phase transitions: introduction and evolution. Arch. Hist. Exact Sci. 53.1 (1998), pp. 51–81

    1998

  16. [16]

    Jenssen, W

    M. Jenssen, W. Perkins, and A. Potukuchi. On the evolution of structure in triangle-free graphs. Adv. Math. 480.part B (2025), Paper No. 110499, 127

    2025

  17. [17]

    Keevash and W

    P. Keevash and W. Lochet. The structure of typical eye-free graphs and a Tur´ an-type result for two weighted colours. Combin. Probab. Comput. 26.6 (2017), pp. 886–910

    2017

  18. [18]

    J. Kim, D. K¨ uhn, D. Osthus, and T. Townsend. Forbidding induced even cycles in a graph: typical structure and counting. J. Combin. Theory Ser. B 131 (2018), pp. 170–219

    2018

  19. [19]

    Kozma and W

    G. Kozma and W. Samotij. Lower tails via relative entropy. The Annals of Probability 51.2 (2023), pp. 665–698

    2023

  20. [20]

    Lov´ asz

    L. Lov´ asz. Large Networks and Graph Limits . Vol. 60. American Mathematical Soc., 2012

    2012

  21. [21]

    Lov´ asz and B

    L. Lov´ asz and B. Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B 96.6 (2006), pp. 933–957

    2006

  22. [22]

    T. Luczak. On triangle-free random graphs. Random Structures & Algorithms 16.3 (2000), pp. 260– 276

    2000

  23. [23]

    W. Mantel. Vraagstuk xxviii. Wiskundige Opgaven met de Oplossingen 10.2 (1907), pp. 60–61

    1907

  24. [24]

    Marchant and A

    E. Marchant and A. Thomason. Extremal graphs and multigraphs with two weighted colours. Fete of combinatorics and computer science (2010), pp. 239–286

    2010

  25. [25]

    Marchant and A

    E. Marchant and A. Thomason. The structure of hereditary properties and 2-coloured multigraphs. Combinatorica 31 (2011), pp. 85–93

    2011

  26. [26]

    R. R. Martin. The Edit Distance Function and Symmetrization. The Electronic Journal of Combina- torics (2013), P26–P26

    2013

  27. [27]

    Morris, W

    R. Morris, W. Samotij, and D. Saxton. An asymmetric container lemma and the structure of graphs with no induced 4-cycle. J. Eur. Math. Soc. (JEMS) 26.5 (2024), pp. 1655–1711

    2024

  28. [28]

    Norin and Y

    S. Norin and Y. Yuditsky. Typical structure of hereditary graph families. I. Apex-free families. Random Structures Algorithms 66.1 (2025)

    2025

  29. [29]

    Norin and Y

    S. Norin and Y. Yuditsky. Typical structure of hereditary graph families. II. Exotic examples. Random Structures Algorithms 66.1 (2025)

    2025

  30. [30]

    Osthus, H

    D. Osthus, H. J. Pr¨ omel, and A. Taraz. For which densities are random triangle-free graphs almost surely bipartite? Combinatorica 23 (2003), pp. 105–150

    2003

  31. [31]

    Perkins and S

    W. Perkins and S. van der Poel. The typical structure of dense claw-free graphs. arXiv preprint arXiv:2501.17816 (2025)

    work page arXiv 2025

  32. [32]

    H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs. III. A general asymptotic. Random Struc- tures Algorithms 3.1 (1992), pp. 19–31

    1992

  33. [33]

    H. J. Pr¨ omel and A. Steger. Excluding induced subgraphs: quadrilaterals. Random Structures Algo- rithms 2.1 (1991), pp. 55–71

    1991

  34. [34]

    H. J. Pr¨ omel and A. Steger. Almost all Berge graphs are perfect. Combin. Probab. Comput. 1.1 (1992), pp. 53–79. APPENDIX 83

    1992

  35. [35]

    H. J. Pr¨ omel and A. Steger. The asymptotic number of graphs not containing a fixed color-critical subgraph. Combinatorica 12 (1992), pp. 463–473

    1992

  36. [36]

    H. J. Pr¨ omel and A. Steger. On the asymptotic structure of sparse triangle free graphs. J. Graph Theory 21.2 (1996), pp. 137–151

    1996

  37. [37]

    Radin, K

    C. Radin, K. Ren, and L. Sadun. The asymptotics of large constrained graphs. Journal of Physics A: Mathematical and Theoretical 47.17 (2014), p. 175001

    2014

  38. [38]

    Radin and L

    C. Radin and L. Sadun. Phase transitions in a complex network. Journal of Physics A: Mathematical and Theoretical 46.30 (2013), p. 305002

    2013

  39. [39]

    Radin and L

    C. Radin and L. Sadun. Singularities in the entropy of asymptotically large simple graphs. Journal of Statistical Physics 158 (2015), pp. 853–865

    2015

  40. [40]

    Riordan and L

    O. Riordan and L. Warnke. The Janson inequalities for general up-sets. Random Structures & Algo- rithms 46.2 (2015), pp. 391–395

    2015

  41. [41]

    Simonovits

    M. Simonovits. A method for solving extremal problems in graph theory, stability problems. Theory of Graphs (Proc. Colloq., Tihany, 1966) . Academic Press, New York-London, 1968, pp. 279–319

    1966

  42. [42]

    Stark and N

    D. Stark and N. Wormald. The probability of non-existence of a subgraph in a moderately sparse random graph. Combin. Probab. Comput. 27.4 (2018), pp. 672–715

    2018

  43. [43]

    A. Steger. On the evolution of triangle-free graphs. Combin. Probab. Comput. 14.1-2 (2005), pp. 211– 224

    2005

  44. [44]

    Thomason

    A. Thomason. Graphs, colours, weights and hereditary properties. Surveys in combinatorics 2011 . Vol. 392. London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 2011, pp. 333– 364

    2011

  45. [45]

    defect graphs

    Y. Zhao. On the lower tail variational problem for random graphs. Combinatorics, Probability and Computing 26.2 (2017), pp. 301–320. Appendix A. Deferred Results Lemma A.1. For all δ > 0 and integers ℓ, L, t ⩾ 1 there exists ϵ∗ = ϵ∗(δ, ℓ) > 0 such that for all η ∈ (0, ϵ∗) there exist integers U = U(δ, ℓ, L, t, η) and n0 = n0(δ, ℓ, L, t, η) with the follow...

    2017

  46. [46]

    Let Fγ(R, B) := R · H γ(n 2)−B R

    there exists δ > 0 such that the following holds for all large enough n. Let Fγ(R, B) := R · H γ(n 2)−B R . If α ⩽ γ n 2 − B R ⩽ 1 − α , R ⩾ αn2 , D r ⩾ αn2 , and |Db| ⩽ n , then Fγ(R + Dr, B + Db) ⩾ Fγ(R, B) + δn2 . Proof. Since ∂ ∂B Fγ(R, B) = −H ′ γ(n 2)−B R , there is a constant L = L(α) > 0 such that |Fγ(R, B + Db) − Fγ(R, B)| ⩽ L|Db| ⩽ Ln . Now let ...

  47. [47]

    Now let p := m−eb(J ∗) er(J ∗)

    such that q ∈ [α, 1 − α] for all large enough n. Now let p := m−eb(J ∗) er(J ∗) . Since m = γ n 2 + o(n2), we have |p − q| = o(1), and therefore p ∈ [0, 1] for all large enough n. Consider the family P(J ∗, m) of (simple, uncolored) graphs G on n vertices and m edges obtained as follows: include every blue edge of J ∗, exclude every green edge of J ∗, and...

  48. [48]

    Apply Lemma A.1 with parameters τ, ℓ := 4, L := ⌈1/τ ⌉, t := 1, and the trivial initial partition {V (G)}, and let η > 0, u ∈ N, and n1 be the resulting constants

    so that 4 τ < ϵ/ 2 and C · H(τ) + 3τ ⩽ δ0/4. Apply Lemma A.1 with parameters τ, ℓ := 4, L := ⌈1/τ ⌉, t := 1, and the trivial initial partition {V (G)}, and let η > 0, u ∈ N, and n1 be the resulting constants. By reducing η if necessary, we may assume η ⩽ min{τ, η0/10}. Hence every graph on at least n1 vertices has an ( η, τ, 4)-type (P, R) with ⌈1/τ ⌉ ⩽ v...

  49. [49]

    The following lemma quantifies how the number of graphs in FΠ,T is constrained if the defect graph T contains a matching of a given size

    such that for all large enough n, if Π = (A, B) ∈ P, |t| ⩽ ϵn2 + n, and 0 ⩽ z ⩽ n then (112) β ⩽ m − |B| 2 − t |A| · |B| − z ⩽ 1 − β , and the same bound also holds if one subtracts z from the numerator (by decreasing β). The following lemma quantifies how the number of graphs in FΠ,T is constrained if the defect graph T contains a matching of a given siz...