Pith. sign in

REVIEW 5 minor 24 references

Dense maximal H-free graphs become exact blowups of a bounded template once the minimum degree clears a positive threshold that never vanishes for non-bipartite H.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-12 05:17 UTC pith:CTHA536C

load-bearing objection Solid separation of blowup thresholds from chromatic ones: positivity, non-monotonicity, and a clean exact value 1/4.

arxiv 2607.03035 v1 pith:CTHA536C submitted 2026-07-03 math.CO

On the spectrum and structure of blowup thresholds

Xinqi Huang , Hong Liu , Mingyuan Rong This is my paper
classification math.CO MSC 05C3505C1505C75
keywords blowup thresholdchromatic thresholdhomomorphism thresholdmaximal H-free graphspseudo-blowupsodd-cycle blowupsminimum degreetwin quotient
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper studies the blowup threshold δ_B(H): the minimum-degree density above which every maximal H-free graph must be an exact blowup of some bounded template graph. This is stricter than the classical chromatic and homomorphism thresholds, which only guarantee bounded colouring or a bounded H-free quotient. The authors prove three structural facts that separate δ_B from those weaker parameters. First, δ_B(H) is always strictly positive whenever H is non-bipartite; the threshold therefore never collapses to zero outside the bipartite world. Second, the parameter is not monotone under induced subgraphs, so global features of H matter and the usual reduction to minimal forbidden subgraphs fails. Third, for a natural family of 3-chromatic constrained blowups of odd cycles one obtains the exact value δ_B(H)=1/4, a density that is impossible for the chromatic threshold. Taken together, the results show that upgrading approximate or quotient structure to genuine homogeneous blowups produces a richer and more delicate spectrum.

Core claim

For every non-bipartite graph H the blowup threshold satisfies δ_B(H)>0; the same threshold is not monotone under induced subgraphs; and there exists a natural family of 3-chromatic constrained odd-cycle blowups for which δ_B(H) equals exactly 1/4.

What carries the argument

The pseudo-blowup construction: replace vertices of a model graph by large and small blocks, keep most adjacent pairs complete bipartite, but replace selected small-block pairs by sparse ordered patterns (matchings or strict inequalities). Sparse pairs force the twin quotient to be unbounded, while the minimum-degree condition still yields a concrete lower bound on δ_B.

Load-bearing premise

The exact upper bound of 1/4 rests on an external stability theorem that every sufficiently dense graph forbidding the relevant odd-cycle blowups becomes almost bipartite after deleting a negligible number of edges.

What would settle it

Exhibit a single 3-chromatic constrained blowup H of an odd cycle, together with an infinite family of maximal H-free graphs of minimum degree strictly larger than n/4 whose twin quotients remain unbounded.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies the blowup threshold δ_B(H), which asks for the minimum-degree density forcing every maximal H-free graph to be an exact blowup of a bounded template graph (a rigid strengthening of the chromatic and homomorphism thresholds). It proves three main results: δ_B(H) > 0 for every non-bipartite H (Theorem 1.1), that δ_B is not monotone under induced subgraphs (Theorem 1.2, via an explicit H with δ_B(H) ≥ 1/2 > δ_B(H ∪ K_3)), and that δ_B(H) = 1/4 exactly for the natural family of 3-chromatic constrained odd-cycle blowups C^4_{2s-1} (Theorem 1.3, obtained by matching the lower-bound pseudo-blowup construction of Theorem 1.5 with the upper bound of Theorem 1.4).

Significance. If correct, the results cleanly separate the blowup threshold from the chromatic-threshold spectrum: positivity never vanishes outside the bipartite world (in contrast to δ_χ(C_{2k-1}) = 0), non-monotonicity under induced subgraphs blocks any direct transfer of the Allen–Böttcher–Griffiths–Kohayakawa–Morris classification strategy, and the exact value 1/4 lies outside {0, 1/3, 1/2}. The pseudo-blowup framework (Definition 2.1 + Lemma 2.2/Corollary 2.3) supplies a reusable, concrete lower-bound engine, while the upper-bound arguments upgrade standard almost-bipartite stability (via maximality and elementary thickening) to exact blowups. These are solid, self-contained contributions that enlarge the structural landscape of dense H-free graphs.

minor comments (5)
  1. [Section 2] Definition 2.1: the three admissible sparse rules (i = j, i < j, i > j) are clear, but a one-sentence remark that the rule is fixed once and for all for each small-block pair would prevent any ambiguity when the same model is reused for different H.
  2. [Section 2.1] Lemma 2.5 / Claim 2.6: the argument that a non-singular vertex forces a second neighbour inside a matching pair is correct, yet the subsequent distance calculation on the projected cycle (gaps of length at least 2 except one) could be illustrated with a short diagram or an explicit listing of the 4k-3 lower bound for the singleton interval.
  3. [Section 3.2] Section 3.2: the constant 58 arising from the dense-matching number is harmless for the existence proof, but a parenthetical remark that any fixed bound works (and that the precise value is irrelevant) would reassure the reader that no optimisation is claimed.
  4. [Section 4] Figure 4.1 and the surrounding text: the distinction between C^ℓ_ℓ and C^≥ℓ_ℓ is visually clear, yet a single sentence defining “singleton interval of length exactly ℓ with all other parts size ≥ 2” in the caption itself would make the figure self-contained.
  5. Throughout: the notation Fr·s for an arbitrary blowup appears with varying typography (Fr·s, F[r], etc.); a uniform choice (e.g., F[r]) would improve readability.

Circularity Check

0 steps flagged

No circularity: positivity, non-monotonicity and exact 1/4 rest on self-contained pseudo-blowup constructions and an external stability lemma, not on self-referential definitions or load-bearing self-citations.

full rationale

The paper is a pure combinatorial extremal-graph-theory work. The three main theorems are proved by explicit constructions (pseudo-blowups of carefully chosen model graphs M for lower bounds; case analysis of dense maximal (H∪K3)-free graphs for non-monotonicity) together with an external stability result of Łuczak–Simonovits (Lemma 4.1) that supplies an almost-bipartite starting point for the upper bound δB(H)≤1/4. The subsequent promotion from almost-bipartite to exact complete bipartite (Claim 4.3 and the thickening argument) is elementary and does not recycle the target numerical value. Self-citations to the authors’ earlier introduction of the blowup threshold ([9]) and related work ([12]) appear only as background comparisons (e.g., known values for cliques and odd cycles); none of them is invoked as a uniqueness theorem or as a premise that forces the new statements. There is no data fitting, no parameter estimated from a subset of instances and then re-used as a “prediction,” and no definition of δB that already encodes the claimed positivity or the value 1/4. Consequently the derivation chain is independent of its own conclusions.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 1 invented entities

The paper is pure extremal combinatorics. It relies on standard graph-theoretic notions (blow-ups, chromatic number, maximality) and one external stability theorem; no free parameters are fitted and no new physical or algebraic entities are postulated.

axioms (3)
  • domain assumption Łuczak–Simonovits stability: every sufficiently dense H-free graph with H homomorphic to an odd cycle becomes bipartite after deleting o(n^{2}) edges (Lemma 4.1).
    Invoked as the starting point of the upper-bound argument for δ_B≤1/4; the paper does not reprove it.
  • standard math Andrásfai–Erdős–Sós theorem: a triangle-free graph with minimum degree > (3/5)n is bipartite.
    Used in the non-monotonicity proof to conclude that G-S is bipartite once dense edges are removed.
  • standard math Standard definitions of blow-up, homomorphism, chromatic number and maximality of H-free graphs.
    Background language of the whole paper.
invented entities (1)
  • pn1,n2q-pseudo-blowup of a model graph M no independent evidence
    purpose: Provides dense maximal H-free graphs whose twin quotient is forced to be unbounded, yielding lower bounds on δ_B.
    A technical construction introduced in Definition 2.1; it is a combinatorial gadget rather than a new mathematical object with independent existence.

pith-pipeline@v1.1.0-grok45 · 28813 in / 2439 out tokens · 17294 ms · 2026-07-12T05:17:53.651536+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of On the spectrum and structure of blowup thresholds." pith.science (2026). https://pith.science/paper/CTHA536C

@misc{pith2026260703035,
  author       = {Pith},
  title        = {Pith review of: On the spectrum and structure of blowup thresholds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CTHA536C}},
  note         = {Machine review of arXiv:2607.03035}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The chromatic threshold of Erd\H{o}s and Simonovits asks when a minimum-degree condition forces every \(H\)-free graph to have bounded chromatic number. Thomassen's homomorphism threshold strengthens this by requiring a bounded \(H\)-free homomorphic image. The recently introduced blowup threshold \(\delta_{\mathrm B}(H)\) asks for a still more rigid conclusion: when must every sufficiently dense maximal \(H\)-free graph be an actual blowup of a bounded graph? Thus the blowup threshold measures when quotient-level structure can be upgraded to exact bounded-template structure. We show that, although chromatic and homomorphism thresholds are often hard to separate, the stronger blowup threshold diverges from the chromatic threshold in several fundamental ways. First, we prove that \(\delta_{\mathrm B}(H)>0\) for every non-bipartite graph \(H\). Hence, unlike the chromatic threshold, the blowup threshold never vanishes outside the bipartite world. Second, we prove that $\delta_{\mathrm B}$ is not monotone under taking induced subgraphs. This shows that the blowup threshold is sensitive to global features of the forbidden graph and cannot be classified by a direct analogue of the monotonicity-based strategy used for chromatic thresholds. Third, we prove that $\delta_{\mathrm B}(H)=\frac{1}{4}$ for a natural family of \(3\)-chromatic constrained blowups of odd cycles. This gives a new exact blowup-threshold value beyond the chromatic-threshold spectrum.

Figures

Figures reproduced from arXiv: 2607.03035 by Hong Liu, Mingyuan Rong, Xinqi Huang.

Figure 2.1
Figure 2.1. Figure 2.1: The model graph M and its pseudo-blowup M with rule i “ j, for k “ 2. Proof. Since 2s´1 ě 4k´1 are odd, C2s´1 admits a homomorphism to C4k´1: take a closed walk with p2s ´ 1 ` 4k ´ 1q{2 forward steps and p2s ´ 1 ´ p4k ´ 1qq{2 backward steps. Hence C2s´1 Ď C4k´1r2ss, and therefore H Ď C2s´1r|V pHq|s Ď Mr2s|V pHq|s “ Mrts. Choose n2 ą tC4k and then choose n1 ą n2 so that n1 2kpn1`n2q ě 1 2k ´ 1 C . Every v… view at source ↗
Figure 3.1
Figure 3.1. Figure 3.1: Illustration of the construction for the lower bound. [PITH_FULL_IMAGE:figures/full_fig_p010_3_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: c) [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 3.2
Figure 3.2. Figure 3.2: Illustration of why M is H-free. Theorem 3.4. Let H be the graph defined in Definition 3.1. Then δBpHq ě 1 2 . Proof. Suppose that δBpHq ă 1{2. Choose α ă 1{2 and a graph F witnessing the defining property of the blowup threshold at α. Put C :“ |V pFq| and ε :“ 1 2 ´ α. Choose M as in Lemma 3.2. By Lemma 3.3, M is H-free. Add edges to M, without changing its vertex set, until obtaining a maximal H-free g… view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: Two special blowups of C7. 4.1 A stability starting point We start from the following stability theorem: if H is homomorphic to an odd cycle of length at least 2s ´ 1, then every sufficiently dense H-free graph is almost bipartite. Recall that C ě0 s is simply the family of all blowups of Cs. Lemma 4.1 ([23]). For any integer s ě 2, let H P C ě0 2s´1 . Then for every γ, η ą 0, there exists n0 such that f… view at source ↗
Figure 4.2
Figure 4.2. Figure 4.2: The subgraph Grtzu Y P1 Y P 2 2 Y Q1 Y Ls contains a blowup of C5. Therefore, G is bipartite. Since G is maximal H-free, it follows that G is a complete bipartite graph. This completes the proof. 5 Concluding remarks The results of this paper suggest that the blowup-threshold spectrum ∆B “ tδBpHq : χpHq ě 3u is more subtle than the chromatic-threshold spectrum. The positivity theorem shows that the blowu… view at source ↗

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

24 extracted references · 7 linked inside Pith

  1. [1]

    Allen, J

    P. Allen, J. B¨ ottcher, S. Griffiths, Y. Kohayakawa, and R. Morris. The chromatic thresholds of graphs.Adv. Math., 235:261–295, 2013

    2013

  2. [2]

    N. Alon, E. Fischer, and I. Newman. Efficient testing of bipartite graphs for forbidden induced subgraphs.SIAM Journal on Computing, 37(3):959–976, 2007

    2007

  3. [3]

    B¨ ottcher, N

    J. B¨ ottcher, N. Frankl, D. M. Cecchelli, O. Parczyk, and J. Skokan. Graphs with large minimum degree and no small odd cycles are 3-colourable, 2023. arXiv preprint: 2302.01875

    Pith/arXiv arXiv 2023

  4. [4]

    Brandt and S

    S. Brandt and S. Thomass´ e. Dense triangle-free graphs are four-colorable: A solution to the Erd˝ os-Simonovits problem. preprint, 2011

    2011

  5. [5]

    Ebsen and M

    O. Ebsen and M. Schacht. Homomorphism thresholds for odd cycles.Combinatorica, 40(1):39–62, 2020

    2020

  6. [6]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits. On a valence problem in extremal graph theory.Discrete Math., 5:323–334, 1973

    1973

  7. [7]

    Goddard and J

    W. Goddard and J. Lyle. Dense graphs with small clique number.J. Graph Theory, 66(4):319–331, 2011

    2011

  8. [8]

    H¨ aggkvist

    R. H¨ aggkvist. Odd cycles of specified length in nonbipartite graphs. InGraph theory (Cambridge, 1981), North-Holland Math. Stud., 62, pages 89–99. 1982

    1981

  9. [9]

    Huang, H

    X. Huang, H. Liu, M. Rong, and Z. Xu. Interpolating chromatic and homomorphism thresholds,

  10. [10]

    arXiv preprint: 2502.09576

    Pith/arXiv arXiv

  11. [11]

    G. P. Jin. Triangle-free four-chromatic graphs.Discrete Math., 145(1-3):151–170, 1995

    1995

  12. [12]

    Letzter and R

    S. Letzter and R. Snyder. The homomorphism threshold of C3, C5-free graphs.J. Graph Theory, 90(1):83–106, 2019

    2019

  13. [13]

    H. Liu, C. Shangguan, J. Skokan, and Z. Xu. Beyond the chromatic threshold via pp, qq-theorem, and a sharp blow-up phenomenon, 2024. arXiv preprint: 2403.17910

    Pith/arXiv arXiv 2024

  14. [14]

    Lov´ asz and B

    L. Lov´ asz and B. Szegedy. Regularity partitions and the topology of graphons. InAn Irregular Mind: Szemer´ edi is 70, pages 415–446. Springer, 2010

    2010

  15. [15]

    T. Luczak. On the structure of triangle-free graphs of large minimum degree.Combinatorica, 26(4):489–493, 2006

    2006

  16. [16]

    Luczak and S

    T. Luczak and S. Thomass´ e. Coloring dense graphs via VC-dimension, 2010. arXiv preprint: 1007.1670

    Pith/arXiv arXiv 2010

  17. [17]

    Nikiforov

    V. Nikiforov. Chromatic number and minimum degree ofK r-free graphs, 2010. arXiv preprint: 1001.2070

    Pith/arXiv arXiv 2010

  18. [18]

    B. Ning, J. Wang, and Y. Xue. On the chromatic profile for tripartite graphs and beyond, 2026. arXiv preprint: 2604.09394

    Pith/arXiv arXiv 2026

  19. [19]

    Oberkampf and M

    H. Oberkampf and M. Schacht. On the structure of dense graphs with bounded clique number. Comb. Probab. Comput., 29(5):641–649, 2020

    2020

  20. [20]

    M. Sankar. Homotopy and the homomorphism threshold of odd cycles, 2022. arXiv preprint: 2206.07525. 21

    Pith/arXiv arXiv 2022

  21. [21]

    Szemer´ edi

    E. Szemer´ edi. Regular partitions of graphs. InProbl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 ofColloq. Internat. CNRS, pages 399–401. CNRS, Paris, 1978

    1976

  22. [22]

    Thomassen

    C. Thomassen. On the chromatic number of triangle-free graphs of large minimum degree. Combinatorica, 22(4):591–596, 2002

    2002

  23. [23]

    Thomassen

    C. Thomassen. On the chromatic number of pentagon-free graphs of large minimum degree. Combinatorica, 27(2):241–243, 2007

    2007

  24. [24]

    Luczak and M

    T. Luczak and M. Simonovits. On the minimum degree forcing F -free graphs to be (nearly) bipartite.Discrete Mathematics, 308(17):3998–4002, 2008. 22

    2008