Pith. sign in

REVIEW 5 minor 16 references

The homomorphism threshold of every clique-bundle T^s_{r,k} equals the clique value (2r-5)/(2r-3).

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-31 13:34 UTC pith:3RD32UAQ

load-bearing objection First exact homomorphism thresholds past cliques, via a clean family and a usable clique-amplification lemma; the long s=1 case is intricate but holds together.

arxiv 2607.28241 v1 pith:3RD32UAQ submitted 2026-07-30 math.CO

Exact Homomorphism Thresholds Beyond Cliques

Xinqi Huang , Mingyuan Rong , Chong Shangguan This is my paper
classification math.CO MSC 05C3505C1505C60
keywords homomorphism thresholdchromatic thresholdminimum degreeclique blow-upsheavy edgesextremal graph theoryT^s_{r,k}
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 settles the exact homomorphism threshold for an infinite family of non-complete graphs. For each r ≥ 3, k ≥ 1 and 1 ≤ s ≤ r, the graph T^s_{r,k} is formed by gluing k copies of the complete graph K_r along a common clique of size s. The authors prove that any T^s_{r,k}-free graph whose minimum degree is at least a little more than (2r-5)/(2r-3) of its order admits a homomorphism into some T^s_{r,k}-free graph of bounded size. That constant is already known to be the chromatic threshold of these graphs, so the two thresholds coincide. Until now the only graphs with a fully determined homomorphism threshold were the cliques themselves; the result therefore gives the first infinite non-clique family for which the stronger homomorphism question is answered exactly.

Core claim

For every r ≥ 3, k ≥ 1 and 1 ≤ s ≤ r one has δ_hom(T^s_{r,k}) = (2r-5)/(2r-3). The lower bound is inherited from the known chromatic threshold; the matching upper bound is obtained by showing that every sufficiently dense maximal T^s_{r,k}-free graph is a blow-up of a bounded T^s_{r,k}-free graph.

What carries the argument

A common-neighbourhood clique-counting lemma that amplifies many small cliques in the joint neighbourhood of a tuple into many larger cliques after one vertex of the tuple is dropped. Iterating the lemma produces a bounded set of “heavy” edges whose deletion leaves a K_r-free graph to which the known clique homomorphism theorem applies.

Load-bearing premise

The argument for the hardest case relies on an external quantitative theorem that every dense maximal clique-free graph is already a blow-up of a bounded clique-free graph; if that black-box bound fails, the final bounded quotient is not guaranteed.

What would settle it

Exhibit a single T^s_{r,k}-free graph on n vertices with minimum degree strictly larger than ((2r-5)/(2r-3)+ε)n that admits no homomorphism into any T^s_{r,k}-free graph whose order is bounded solely in terms of r, k, s and ε.

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

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Gluing any number of K_r’s along a common clique of any size does not raise the homomorphism threshold above the pure-clique value.
  • Every graph in the family has identical chromatic and homomorphism thresholds.
  • The same heavy-edge and blow-up method yields an explicit structural description: dense maximal T^s_{r,k}-free graphs are blow-ups of bounded T^s_{r,k}-free quotients.
  • The result supplies the first infinite non-complete family whose exact homomorphism thresholds are known.

Where Pith is reading between the lines

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

  • The same amplification lemma may decide the homomorphism threshold for other graphs whose chromatic threshold equals (2r-5)/(2r-3).
  • The open problem posed in the paper—characterising all H with δ_hom(H)=(2r-5)/(2r-3)—is now the natural next target.
  • For odd cycles the gap between chromatic threshold 0 and positive homomorphism threshold remains; the new method does not immediately close it.

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 determines the homomorphism threshold exactly for the infinite family T^s_{r,k} (k copies of K_r glued along a common K_s): δ_hom(T^s_{r,k}) = (2r−5)/(2r−3) for all r≥3, k≥1, 1≤s≤r. The lower bound is immediate from the known chromatic-threshold classification. For s≥2 the upper bound reduces to the clique case via a short clique-counting argument showing that dense T^s_{r,k}-free graphs are already K_r-free. For s=1 the authors prove a stronger blow-up statement for maximal dense T_{r,k}-free graphs, via a heavy-edge vertex cover of bounded size, a refined independent-set partition obtained from the clique homomorphism theorem, and a matching/König argument that produces a bounded T_{r,k}-free quotient; the longest step is an induction on blade overlap inside Lemma 3.4.

Significance. Prior to this work the only graphs with exactly known homomorphism thresholds were cliques. The paper supplies the first infinite family of non-complete forbidden graphs for which δ_hom is determined exactly, and shows that the clique value is stable under gluing several K_r’s along a common clique. The common-neighborhood clique-counting lemmas (especially the inductive amplification Lemma 2.2) are of independent technical interest and cleanly extend the dense-edge phenomenon of Fox–Wigderson. The argument is fully combinatorial and self-contained once the external clique blow-up theorem is granted as a black box.

minor comments (5)
  1. [§3.2, Lemma 3.4] The induction on the overlap parameter a inside Lemma 3.4 (pp. 14–16) is correct but dense; a short roadmap paragraph at the start of §3.2 listing the cases (a=0; a≥1 with core outside W; a≥2 with core in W; a=1 with core in W) would help the reader track the reductions.
  2. [§3.1, Choice of the heavy-edge constant] The quantitative dependence of α_h and the λ_j sequence on ε is only sketched via successive applications of Lemmas 2.1–2.3. A one-line remark that all constants remain positive and depend only on r,ε (so that the tower-type bound of Theorem 2.5 is absorbed into the ε-dependent order permitted by δ_hom) would make the bookkeeping fully explicit.
  3. [§2, Theorem 2.5] Theorem 2.5 is cited as an arXiv preprint. If a published version exists, update the reference; otherwise a brief parenthetical note that only the homomorphism-direction bound (not the maximality-to-blow-up clause) is used would clarify the logical dependence.
  4. [Appendix A] In the appendix (r=3) the constant 6k²/ε for |V(F)| is slightly looser than the main-text 4k²/α_h pattern; aligning the two presentations would improve uniformity.
  5. Minor typos: “Erd˝ os” spacing inconsistencies; “K¨ onig” accent; “hom− − →” rendering; “therparts” (p. 12) and “Sincetis” (p. 6) missing spaces. A global proof-reading pass is recommended.

Circularity Check

0 steps flagged

No significant circularity: threshold equality is derived from independent chromatic-threshold lower bound plus new counting lemmas and a standard external clique black box.

full rationale

The claimed equality δ_hom(T^s_{r,k}) = (2r-5)/(2r-3) is not assumed or fitted. The lower bound is imported from the external chromatic-threshold classification of Allen–Böttcher–Griffiths–Kohayakawa–Morris, which already gives δ_χ(T^s_{r,k}) = (2r-5)/(2r-3) and hence δ_hom ≥ δ_χ. The upper bound is proved by a genuine case split: for s ≥ 2 a new common-neighborhood clique-counting lemma forces the graph to be K_r-free, after which the known clique homomorphism theorem applies; for s = 1 the paper builds heavy-edge constants existentially from Lemmas 2.1–2.3, deletes a bounded vertex cover, refines a bounded partition, and runs an internal induction on blade overlap inside Lemma 3.4 that either produces a forbidden T_{r,k} or reduces the overlap parameter. Constants α_h, λ_j are never fitted to data. The only external structural input is Theorem 2.5 (quantitative clique blow-up/homomorphism), used as a black box for K_r-free and K_{r-1}-free dense graphs; even though one coauthor overlaps with that citation, the clique case itself was already classical (Łuczak; Goddard–Lyle) and the present novelty is the extension beyond cliques. No equation reduces the target threshold to a quantity defined in terms of itself, and no uniqueness or ansatz is smuggled in. The derivation is therefore self-contained against its stated external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 2 invented entities

The result is a pure extremal-graph-theory theorem. It rests on standard graph-theoretic language, two major external theorems (chromatic thresholds of all graphs; homomorphism/blow-up theorem for cliques), König’s theorem, and the authors’ new counting lemmas. No empirical free parameters appear. The only “invented” objects are proof devices (heavy edges, the auxiliary graphs Γ and Γ_v) and the family T^s_{r,k} itself, which is a standard gluing construction.

axioms (5)
  • domain assumption Allen–Böttcher–Griffiths–Kohayakawa–Morris classification: δ_χ(H) is completely determined for every H; in particular δ_χ(T^s_{r,k}) = (2r-5)/(2r-3).
    Supplies the matching lower bound δ_hom ≥ δ_χ used in the first paragraph of the proof of Theorem 1.1.
  • domain assumption Liu–Shangguan–Skokan–Xu clique homomorphism/blow-up theorem (Theorem 2.5): every n-vertex K_r-free graph with δ ≥ ((2r-5)/(2r-3)+ε)n is homomorphic to a K_r-free graph of order ≤ 2^{(1/ε)^C}, and maximal such graphs are blow-ups.
    Black-box engine for the upper bound after the graph is reduced to K_r-free (s≥2) or after deletion of F (s=1).
  • standard math König’s theorem: in a bipartite graph, maximum matching size equals minimum vertex-cover size.
    Used in the final refinement step (after Lemma 3.4) to turn bounded matching number of bipartite complements into a bounded vertex cover K.
  • standard math Every T-free graph on a fixed vertex set extends to a maximal T-free graph without decreasing minimum degree.
    Stated in the introduction and again at the start of §3.1; lets the authors prove the stronger blow-up statement only for maximal graphs.
  • ad hoc to paper Common-neighborhood clique-counting lemmas (Lemmas 2.1–2.3) as proved in the paper.
    Load-bearing new analytic engine; if the amplification step in Lemma 2.2 fails, both the s≥2 reduction and the heavy-edge analysis collapse.
invented entities (2)
  • Family T^s_{r,k} (k copies of K_r glued along a common K_s) independent evidence
    purpose: Defines the infinite family whose homomorphism thresholds are determined.
    Standard gluing construction; not a physical postulate. Independent interest is combinatorial only.
  • Heavy edges (edges whose common neighborhood contains ≥ α_h n^{r-2} copies of K_{r-2}) no independent evidence
    purpose: Proof device that isolates a bounded vertex set F whose deletion leaves a K_r-free graph.
    Defined ad hoc in §3.1 from the counting constants; no meaning outside the argument.

pith-pipeline@v1.2.0-daily-grok45 · 23241 in / 3471 out tokens · 67124 ms · 2026-07-31T13:34:41.007026+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Exact Homomorphism Thresholds Beyond Cliques." pith.science (2026). https://pith.science/paper/3RD32UAQ

@misc{pith2026260728241,
  author       = {Pith},
  title        = {Pith review of: Exact Homomorphism Thresholds Beyond Cliques},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3RD32UAQ}},
  note         = {Machine review of arXiv:2607.28241}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The chromatic threshold, originating in a question of Erd\H{o}s and Simonovits, asks when a linear minimum-degree condition forces bounded chromatic number in H-free graphs. Motivated by a question of Thomassen, the homomorphism threshold asks for the stronger conclusion that every such graph admits a homomorphism to an H-free graph of bounded order. Since the work of Goddard and Lyle determined the clique case, exact homomorphism thresholds for individual non-complete forbidden graphs have remained unknown. In this paper, we extend the clique case to a larger family of forbidden graphs, determining the homomorphism threshold exactly for every graph in this family.

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

16 extracted references · 4 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]

    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

  3. [3]

    Ebsen and M

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

    2020

  4. [4]

    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

  5. [5]

    Fox and Y

    J. Fox and Y. Wigderson. Minimum degree and the graph removal lemma.Journal of Graph Theory, 102(4):648–665, 2023

    2023

  6. [6]

    Goddard and J

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

    2011

  7. [7]

    H¨ aggkvist

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

    1981

  8. [8]

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

    1995

  9. [9]

    D. K¨ onig. Graphen und Matrices.Mat. Fiz. Lapok, 38:116–119, 1931

    1931

  10. [10]

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

    Pith/arXiv arXiv 2024

  11. [11]

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

    2006

  12. [12]

    Luczak and S

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

    Pith/arXiv arXiv 2010

  13. [13]

    Nikiforov

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

    Pith/arXiv arXiv 2010

  14. [14]

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

    Pith/arXiv arXiv 2022

  15. [15]

    Thomassen

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

    2002

  16. [16]

    Thomassen

    C. Thomassen. On the chromatic number of pentagon-free graphs of large minimum degree. Combinatorica, 27(2):241–243, 2007. 17 A Proof of Theorem 1.1 whenr= 3ands= 1 Proof.LetGbe a maximalT 3,k-free graph withδ(G)≥(1/3 +ε)nwheren=|V(G)|. We first isolate the edges which are forced by triangles. For every trianglexyzinG, a simple inclusion- exclusion argume...

    2007