Pith. sign in

REVIEW 2 major objections 5 minor 2 cited by

Interpolating chromatic and homomorphism thresholds

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Odd cycles have blowup threshold 1/(2k−1), and clique thresholds interpolate smoothly via VC-dimension.

desk verdict A substantial paper that resolves the blowup threshold for all odd cycles and gives a genuinely new interpolation between chromatic and homomorphism thresholds, conditional only on one unpublished result used in Theorem 1.1. read the letter →

arxiv 2502.09576 v1 pith:XT3DSGXU submitted 2025-02-13 math.CO

Xinqi Huang , Hong Liu , Mingyuan Rong , Zixiang Xu This is my paper · ORCID
classification math.CO MSC 05C1505C35
keywords chromaticthresholdhomomorphismblowupVC-dimensionoddcyclesclique-freegraphsAndrásfaiextremalgraphtheory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper introduces a generalized threshold that interpolates chromatic and homomorphism thresholds for graphs with bounded VC-dimension, and it determines this threshold exactly for all pairs of cliques. In the same framework, it introduces the blowup threshold δ_B(H), which asks for the minimum degree fraction that forces a maximal H-free graph to be a blowup of a bounded-size graph. The paper's central result is that for odd cycles, δ_B(C_{2k−1}) = 1/(2k−1) for every integer k ≥ 2. This means every maximal C_{2k−1}-free graph on n vertices with minimum degree at least (1/(2k−1)+ε)n is a blowup of a graph of constant size, while at the exact threshold there are twin-free examples that are not. The results answer a question of Schacht and show that blowup thresholds, unlike chromatic thresholds, have 0 as an accumulation point.

What carries the argument

The arguments run on two engines. The first is the theory of VC-dimension: a Haussler packing lemma (Lemma 3.1) partitions the vertex set into classes with nearly identical neighborhoods, and an iterative refinement (Definition 4.13) sharpens this partition until each class is either complete or anti-complete to every other class, yielding the blowup structure. The second is a code-on-graphs theorem (Theorem 1.4), which bounds the total ℓ1-weight of binary vectors assigned to vertices of a dense graph under a constraint on common 1-coordinates of any K_{s−2}; this theorem supplies the clique-number bound on the homomorphic image in Theorem 1.1. For the odd-cycle results, Bollobás's set-pair inequality bounds the VC-dimension of dense maximal C_{2k−1}-free graphs (Theorem 1.5), and Andrásfai graphs provide the sharp lower-bound constructions.

What would settle it

For k = 2, search for a maximal C_5-free graph with minimum degree at least (1/5 + ε)n for some ε > 0 that is not a blowup of any bounded-size graph; Theorem 1.3 predicts none exists, so a single example would refute it. Independently, verify the value δVC_χ(K_4) = 2/3; a different value would break the upper-bound argument of Theorem 1.1.

Watch

Extended reading notes

Core claim

The paper proves two main structural claims. First, for integers t ≥ s ≥ 3, the bounded-VC homomorphism threshold for mapping K_s-free graphs to K_t-free images is δVC_hom(K_s;K_t) = ((s−3)(t−s+2)+1)/((s−2)(t−s+2)+1), with matching constructions showing optimality. As t grows this value descends smoothly from δVC_hom(K_s) = (2s−5)/(2s−3) to δVC_χ(K_s) = (s−3)/(s−2), showing that the coincidence of chromatic and homomorphism thresholds for cliques is governed by VC-dimension. Second, the paper defines the blowup threshold δ_B(H) and proves δ_B(C_{2k−1}) = 1/(2k−1) for all k ≥ 2: any maximal C_{2k−1}-free graph with minimum degree above (1/(2k−1)+ε)n is a blowup of a graph whose size is bounded in terms of k and ε, and the Andrásfai graphs show the threshold cannot be lowered. Along the way the paper proves that such graphs have bounded VC-dimension and that removing O_{ε,k}(1) vertices destroys all short odd cycles.

Load-bearing premise

The upper bound for the clique interpolation theorem assumes the still-unpublished result δVC_χ(K_s) = (s−3)/(s−2); if that result were false, the bounded-coloring step in Section 3 would collapse, though Theorems 1.2 and 1.3 do not depend on it.

Editorial extensions

If this is right

  • For every k ≥ 2, every maximal C_{2k−1}-free graph with minimum degree at least (1/(2k−1)+ε)n is a blowup of a graph of size bounded by a tower function in k and 1/ε.
  • The Andrásfai graphs show the threshold is sharp: at minimum degree n/(2k−1) there are maximal C_{2k−1}-free graphs that are twin-free and hence not blowups of any smaller graph.
  • Since 1/(2k−1) → 0 as k → ∞, blowup thresholds have 0 as an accumulation point, in contrast to chromatic thresholds, which are all jumps.
  • The interpolation formula for cliques, δVC_hom(K_s;K_t) = ((s−3)(t−s+2)+1)/((s−2)(t−s+2)+1), is exact and decreases to δVC_χ(K_s) as t → ∞.
  • For mixed odd-cycle families, δVC_hom(C_{2k+1}; C_{2k−1}) = 0, extending the VC-dimension transition for homomorphism thresholds from 1/(2k+1) to 0.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper does not compute δ_B for other graphs; testing Conjecture 5.1 (δ_hom = δ_B) on even cycles or on K_{s,t} would be a natural next step, and Theorem 1.4's code bound may be the right tool.
  • The iterative refinement that forces blowup structure suggests a general sufficient condition: any H-free graph whose VC-dimension is bounded and whose minimum degree is a positive fraction of n should be near a blowup, potentially extending beyond odd cycles.
  • Theorem 1.2's zero threshold for {C_{2k+1}, C_{2k−1}}-free graphs suggests the blowup threshold of the family {C_{2k+1}, C_{2k−1}} might also be 0; verifying or refuting this would be a concrete test of the framework.
  • The paper leaves open whether δVC(C_{2k−1}) equals 1/(2k−1); resolving this would pin down when bounded VC-dimension alone, rather than maximality, forces blowup structure.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. This paper introduces two new threshold parameters for H-free graphs: the bounded-VC homomorphism threshold δVC_hom(G1;G2), which interpolates between chromatic and homomorphism thresholds, and the blowup threshold δ_B(H). The main results are Theorem 1.1, computing δVC_hom(K_s;K_t)=((s-3)(t-s+2)+1)/((s-2)(t-s+2)+1); Theorem 1.2, giving two zero thresholds for families of odd cycles; Theorem 1.3, proving δ_B(C_{2k-1})=1/(2k-1); and Theorem 1.5, bounding the VC-dimension of dense maximal C_{2k-1}-free graphs. The proofs combine Haussler's packing lemma, an iterative partition-refinement process, a new inequality for codes on graphs (Theorem 1.4), and Andrásfai-graph lower-bound constructions.

Significance. If the results are correct, this is a substantial contribution: Theorem 1.1 gives the first smooth interpolation between chromatic and homomorphism thresholds, and Theorem 1.3 resolves the blowup threshold for all odd cycles while answering a question of Schacht. The odd-cycle arguments appear largely self-contained and introduce a useful framework for refining VC-based partitions. Theorem 1.4 is a clean statement of independent interest. The main caveat is that the upper bound of Theorem 1.1 rests on an unpublished result, and one proof in Section 4 appears to misapply a stated lemma; these issues must be resolved before the full significance can be assessed.

major comments (2)
  1. [Section 3, first paragraph] The proof of the upper bound of Theorem 1.1 invokes the equality δVC_χ(K_s)=(s-3)/(s-2), cited from [34] (Liu, Shangguan, Xue, 'In preparation'), to conclude that G has a bounded coloring before applying Lemma 3.1. This step is load-bearing: it is what makes the refined partition have O_{ε,d,r}(1) parts, and hence what makes the auxiliary graph H have bounded size. Because no proof or published reference is supplied, the upper bound of Theorem 1.1 is conditional on [34]. The authors should include a proof of this equality in an appendix or state Theorem 1.1 as conditional on the unpublished result.
  2. [Section 4.3, proof of Theorem 1.2] The first assertion of Theorem 1.2 states δVC_hom(C_{2k+1}; C_{2k-1})=0, so the input graph G is assumed only to be C_{2k+1}-free. The proof, however, applies Lemma 4.16(2), whose stated hypothesis is that G is {C_{2k+1}, C_{2k-1}}-free. Moreover, the proof of Lemma 4.16 explicitly uses C_{2k-1}-freeness of G to rule out singular C_{2k-1} cycles in H_k(G,ε/3). Thus the proof as written does not establish the stronger first assertion of Theorem 1.2. Please correct the statement of Lemma 4.16, add the missing argument, or restrict the theorem accordingly.
minor comments (5)
  1. [Section 1.1] The name is misspelled as 'Obsen and Schacht'; it should be 'Ebsen and Schacht'.
  2. [Section 4.2, heading] The heading 'Proof of Lemma 1.5' should refer to Theorem 1.5.
  3. [Section 3.2 and Claim 3.2] In the proof of Theorem 1.4, the symbols V(H), N_H, and H are used where the graph under discussion is G; for example, the maximum in equation (5) should be over V(G) and the neighborhoods should be in G.
  4. [Throughout] Several LaTeX control sequences appear literally in the text, such as '/suppress Luczak' and '/suppress' before Thomassé; these should be typeset properly.
  5. [Figure 1.1] Figure 1.1 is difficult to read and is not needed for the proofs; consider simplifying or removing it.

Circularity Check

1 steps flagged · score 4.0 of 10

Theorem 1.1's upper bound relies on an unpublished co-authored threshold result; the rest of the derivation chain is self-contained.

  1. self citation load bearing [Section 3, first paragraph (upper bound of Theorem 1.1)]
    "As δpGq ě p s´3 s´2 ` εqn and δVC χ pKsq “ s´3 s´2, G can be colored by a bounded number of colors, say C colors. Then, apply Lemma 3.1 to refine the color classes of th is coloring to obtain a partition V pGq “ U1 \ ¨ ¨ ¨ \UK"

    The upper-bound proof of Theorem 1.1 needs the partition U1,...,UK to have K = O(1) so that the auxiliary graph H = H(U1,...,UK) is a bounded-size homomorphic image. The boundedness of K comes entirely from the bounded coloring step, which invokes the equality δVC_χ(K_s) = (s−3)/(s−2). This equality is cited to [34] (Liu, Shangguan, Xue, 'In preparation'), whose author list overlaps with the present paper (Hong Liu). No proof or published version is supplied, so the step is not independently verifiable. If the cited equality is false or unavailable, K is not O(1), and the upper bound for δVC_hom(K_s;K_t) is not established.

full rationale

The derivation chain for the odd-cycle results (Theorems 1.2, 1.3, 1.5) is self-contained: Theorem 1.5 is proved in Section 4.2 from Bollobás's set-pair inequality and a Ramsey argument; Lemma 4.16 is proved by internal claims; the lower bound for δB(C_{2k−1}) uses an explicit Andrásfai construction verified in Proposition 4.21. The lower-bound construction for Theorem 1.1 is an explicit family of K_s-free graphs whose VC-dimension is bounded and whose homomorphic images are forced to contain K_t; it does not rely on any fitted parameter or cited threshold. The only load-bearing step that reduces to a non-independent input is the bounded-coloring step in the upper bound of Theorem 1.1, which invokes δVC_χ(K_s) = (s−3)/(s−2) from reference [34], an unpublished manuscript co-authored by one of the present authors. Since the rest of the upper-bound proof (Haussler partition, Theorem 1.4, the code-on-graphs argument) is a genuine derivation from that coloring, the overall result is not equivalent to its inputs by construction; but the first main theorem's upper bound is not self-contained and rests on a self-citation whose correctness is not independently established. Citations to [33] for the Haussler partition lemma and the clique homomorphism-threshold observation are also self-citations, but those statements are either directly derivable from Haussler's lemma or not needed for the final conclusions. This warrants a score of 4 rather than 0–2.

Assumptions & free parameters 0 free parameters · 6 assumptions · 2 invented entities

The central claims rely on standard results (Haussler packing, Bollobás set-pair, Ramsey) and on two cited results from the same research group, notably δVC_χ(K_s) = (s-3)/(s-2) which is still 'In preparation' ([34]). No numbers are fitted to data.

assumptions (6)
  • standard math Haussler packing lemma based partition lemma (Lemma 3.1) providing a partition with small neighborhood symmetric differences for graphs with bounded VC-dimension.
    Used to define P0(G, γ) in Definition 4.13 and to construct the auxiliary graph H in Section 3.
  • domain assumption δVC_χ(K_s) = (s-3)/(s-2) (reference [34], 'In preparation').
    Used in Section 3 to obtain a bounded coloring of a K_s-free graph with δ ≥ (s-3)/(s-2)+ε n; essential for the upper bound of Theorem 1.1.
  • standard math Bollobás set-pair inequality (Theorem 4.6).
    Used in the proof of Theorem 1.5 to bound the number of paths intersecting a given path.
  • standard math Ramsey number upper bound R(s,t) ≤ binom(s+t-2, s-1).
    Used in Claim 4.8 to find a subset with many common neighbors.
  • standard math Lemma 4.1 from Ebsen and Schacht [14]: a C_{2k-1}-free graph with δ ≥ (1/(2k-1)+ε)n is C_ℓ-free for every odd ℓ with k ≤ ℓ ≤ 2k-1.
    Used in the proof of Theorem 1.5 and Lemma 4.16 to rule out shorter odd cycles.
  • standard math Basic properties of VC-dimension (shattering, packing), treated as standard.
    Foundational to the paper's framework.
invented entities (2)
  • Bounded-VC homomorphism threshold δVC_hom(G1; G2) independent evidence
    purpose: Interpolates between chromatic and homomorphism thresholds under a VC-dimension bound on the host graph.
    Defined in Section 1.2. Theorem 1.1 computes it for cliques, providing a concrete, checkable value.
  • Blowup threshold δ_B(H) independent evidence
    purpose: Minimum degree fraction that forces maximal H-free graphs to be blowups of a bounded-size graph.
    Defined in Section 1.3. Theorem 1.3 determines it for odd cycles, giving an exact checkable value.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Interpolating chromatic and homomorphism thresholds." pith.science (2026). https://pith.science/paper/XT3DSGXU

@misc{pith2026250209576,
  author       = {Pith},
  title        = {Pith review of: Interpolating chromatic and homomorphism thresholds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XT3DSGXU}},
  note         = {Machine review of arXiv:2502.09576}
}
abstract

The problem of chromatic thresholds seeks for minimum degree conditions that ensure $H$-free graphs to have a bounded chromatic number, or equivalently a bounded size homomorphic image. The strengthened homomorphism thresholds problem further requires that the homomorphic image itself is $H$-free. The purpose of this paper is two-fold. First, we define a generalized notion of threshold which encapsulates and interpolates chromatic and homomorphism thresholds via the theory of VC-dimension. Our first result shows a smooth transition between these two thresholds when varying the restrictions on homomorphic images. In particular, we proved that for $t \ge s \ge 3$ and $\epsilon>0$, if $G$ is an $n$-vertex $K_s$-free graph with VC-dimension $d$ and $\delta(G) \ge (\frac{(s-3)(t-s+2)+1}{(s-2)(t-s+2)+1} + \epsilon)n$, then $G$ is homomorphic to a $K_t$-free graph $H$ with $|H| = O(1)$. Moreover, we construct graphs showing that this minimum degree condition is optimal. This extends and unifies the results of Thomassen, {\L}uczak and Thomass\'e, and Goddard, Lyle and Nikiforov, and provides a deeper insight into the cause of existences of homomorphic images with various properties. Second, we introduce the blowup threshold $\delta_B(H)$ as the infimum $\alpha$ such that every $n$-vertex maximal $H$-free graph $G$ with $\delta(G)\ge\alpha n$ is a blowup of some $F$ with $|F|=O(1)$. This notion strengthens homomorphism threshold. While the homomorphism thresholds for odd cycles remain unknown, we prove that $\delta_B(C_{2k-1})=1/(2k-1)$ for any integer $k\ge 2$. This strengthens the result of Ebsen and Schacht and answers a question of Schacht and shows that, in sharp contrast to the chromatic thresholds, 0 is an accumulation point for blowup thresholds. Our proofs mix tools from VC-dimension theory and an iterative refining process, and draw connection to a problem concerning codes on graphs.

Figures

Figures reproduced from arXiv: 2502.09576 by the authors.

Figure 1.1
Figure 1.1. The x, y, z-axes correspond to the values of t ´ s, s and δ VC hompKs; Ktq, respectively. The curve on the plane x “ 0 corresponds to δ VC hompKsq; the curves on the planes y “ s correspond to δ VC hompKs; Ktq respectively and their limits when t Ñ 8 form the curve δ VC χ pKsq on the plane x “ `8. 1.3 Blowup thresholds In the second part of our work, we introduce blowup thresholds, a notion that we believe is more n… view at source ↗
Figure 2.1
Figure 2.1. Structure of the 6-partite graph G with t “ 6, m “ 2 We then show some desired properties of the graph G defined in Definition 2.4. Proposition 2.5. The following properties of G holds: (1). The minimum degree satisfies δpGq ě pm ´ 1qmk´2 “ m´1 2km ¨ |V pGq| ě p 1 2k ´ εq ¨ |V pGq|. (2). G is triangle free. (3). VCpGq ď 4k 2 . (4). If there exists a graph H such that G hom ÝÝÑ H with |H| ď f, then H contains a copy … view at source ↗
Figure 2.2
Figure 2.2. Structure of the 5-partite graph G with t “ 5, m “ 4 Proposition 2.7. The following properties of G holds: (1) The minimum degree δpGq ě pm ´ 1qmk´2 “ m´1 p2k`1qm ¨ |V pGq| ě p 1 2k`1 ´ εq ¨ |V pGq|. (2) G is triangle free. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_2_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Regularity for hypergraphs with bounded VC$_2$ dimension

    math.CO 2025-08 accept novelty 8.0 of 10

    For 3-graphs of bounded VC2 dimension, an (ε,ψ)-regular partition exists with twr(twr(poly(1/ε))) vertex parts, improving the generic wowzer bound to tower type.

  2. On the spectrum and structure of blowup thresholds

    math.CO 2026-07 accept novelty 7.0 of 10

    Blowup thresholds are always positive for non-bipartite H, fail monotonicity under induced subgraphs, and equal 1/4 for certain constrained odd-cycle blowups.

Reference graph

Works this paper leans on

49 extracted references · 38 canonical work pages · cited by 2 Pith papers

  1. [34]

    H. Liu, C. Shangguan, and Y. Xue. Stability for chromati c thresholds. In preparation

    work page

  2. [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. 26

    work page 2013

  3. [2]

    N. Alon, J. Pach, R. Pinchasi, R. Radoiˇ ci´ c, and M. Sharir. Crossing patterns of semi-algebraic sets. J. Combin. Theory Ser. A , 111(2):310–326, 2005

    work page 2005

  4. [3]

    Andr´ asfai, P

    B. Andr´ asfai, P. Erd˝ os, and V. T. S´ os. On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math., 8:205–218, 1974

    work page 1974

  5. [4]

    Balister, B

    P. Balister, B. Bollob´ as, O. Riordan, and R. H. Schelp. G raphs with large maximum degree containing no odd cycles of a given length. J. Combin. Theory Ser. B , 87(2):366–373, 2003

    work page 2003

  6. [5]

    Balogh, A

    J. Balogh, A. Bernshteyn, M. Delcourt, A. Ferber, and H. T . Pham. Sunflowers in set systems with small VC-dimension. arXiv preprint, arXiv: 2408.04165, 2024

    arXiv 2024

  7. [6]

    Beke and O

    C. Beke and O. Janzer. On the generalized Tur´ an problem f or odd cycles. SIAM J. Discrete Math., 38(3):2416–2428, 2024

    work page 2024

  8. [7]

    Bollob´ as

    B. Bollob´ as. On generalized graphs. Acta Math. Acad. Sci. Hungar. , 16:447–452, 1965

    work page 1965

Show all 49 references
  1. [8]

    B¨ ottcher, N

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

    2023 arXiv

  2. [9]

    Bradaˇ c, H

    D. Bradaˇ c, H. Liu, Z. Wu, and Z. Xu. Clique density vs blow ups. arXiv preprint , arXiv: 2410.07098, 2024

    2024 arXiv

  3. [10]

    Brandt, R

    S. Brandt, R. Faudree, and W. Goddard. Weakly pancyclic graphs. J. Graph Theory, 27(3):141– 176, 1998

    1998

  4. [11]

    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. [12]

    T.-W. Chao, Z. Xu, C. H. Yip, and S. Zhang. Uniform set sys tems with small VC-dimension. arXiv preprint, arXiv: 2501.13850, 2025

    2025 arXiv

  6. [13]

    Z. Chen, J. Hou, C. Hu, and X. Liu. Generalized Andr´ asfai–Erd˝ os–S´ os theorems for odd cycles. arXiv preprint, arXiv: 2409.11950, 2024

    2024 arXiv

  7. [14]

    Ebsen and M

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

    2020

  8. [15]

    P. Erd˝ os. Graph theory and probability. Canadian J. Math. , 11:34–38, 1959

    1959

  9. [16]

    P. Erd˝ os. Problems and results on set systems and hypergraphs. In Extremal problems for finite sets (Visegr´ ad, 1991), volume 3 of Bolyai Soc. Math. Stud. , pages 217–227. J´ anos Bolyai Math. Soc., Budapest, 1994

    1991

  10. [17]

    Erd˝ os and L

    P. Erd˝ os and L. P´ osa. On independent circuits contain ed in a graph. Canadian J. Math. , 17:347–352, 1965

    1965

  11. [18]

    Erd˝ os and M

    P. Erd˝ os and M. Simonovits. A limit theorem in graph the ory. Studia Sci. Math. Hungar. , 1:51–57, 1966

    1966

  12. [19]

    Erd˝ os and M

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

    1973

  13. [20]

    Erd˝ os and A

    P. Erd˝ os and A. H. Stone. On the structure of linear graphs. Bull. Amer. Math. Soc. , 52:1087– 1091, 1946. 27

    1946

  14. [21]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres. A combinatorial problem in geometry. Compositio Math., 2:463–470, 1935

    1935

  15. [22]

    J. Fox, M. Gromov, V. Lafforgue, A. Naor, and J. Pach. Overl ap properties of geometric expanders. J. Reine Angew. Math. , 671:49–83, 2012

    2012

  16. [23]

    J. Fox, J. Pach, and A. Suk. Erd˝ os-Hajnal conjecture fo r graphs with bounded VC-dimension. Discrete Comput. Geom. , 61(4):809–829, 2019

    2019

  17. [24]

    J. Fox, J. Pach, and A. Suk. Bounded VC-dimension implie s the Schur-Erd˝ os conjecture.Com- binatorica, 41(6):803–813, 2021

    2021

  18. [25]

    J. Fox, J. Pach, and A. Suk. Sunflowers in set systems of bo unded dimension. Combinatorica, 43(1):187–202, 2023

    2023

  19. [26]

    G. Ge, Z. Xu, C. H. Yip, S. Zhang, and X. Zhao. The Frankl-P ach upper bound is not tight for any uniformity. arXiv preprint, arXiv: 2412.11901, 2024

    2024 arXiv

  20. [27]

    Goddard and J

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

    2011

  21. [28]

    H¨ aggkvist

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

    1981

  22. [29]

    Haussler

    D. Haussler. Sphere packing numbers for subsets of the B oolean n-cube with bounded Vapnik- Chervonenkis dimension. J. Combin. Theory Ser. A , 69(2):217–232, 1995

    1995

  23. [30]

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

    1995

  24. [31]

    Letzter and R

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

    2019

  25. [32]

    H. Lin, G. Wang, and W. Zhou. A strengthening on consecut ive odd cycles in graphs of given minimum degree. arXiv preprint, arXiv: 2410.00648, 2024

    2024 arXiv

  26. [33]

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

    2024 arXiv

  27. [35]

    /suppress Luczak

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

    2006

  28. [36]

    /suppress Luczak and S

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

    2010 arXiv

  29. [37]

    Mubayi and Y

    D. Mubayi and Y. Zhao. On the VC-dimension of uniform hyp ergraphs. J. Algebraic Combin. , 25(1):101–110, 2007

    2007

  30. [38]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph de nsity. VI. Bounded VC-dimension. arXiv preprint, arXiv: 2312.15572, 2023

    2023 arXiv

  31. [39]

    Nikiforov

    V. Nikiforov. Chromatic number and minimum degree of Kr-free graphs, 2010. arXiv preprint: 1001.2070. 28

    2010 arXiv

  32. [40]

    Nikiforov and R

    V. Nikiforov and R. H. Schelp. Cycles and paths in graphs with large minimal degree. J. Graph Theory, 47(1):39–52, 2004

    2004

  33. [41]

    Oberkampf and M

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

    2020

  34. [42]

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

    2022 arXiv

  35. [43]

    M. Schacht. Personal communication

  36. [44]

    A. Suk. On short edges in complete topological graphs. arXiv preprint, arXiv: 2307.08165, 2023

    2023 arXiv

  37. [45]

    Szemer´ edi

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

    1976

  38. [46]

    Thomassen

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

    2002

  39. [47]

    Thomassen

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

    2007

  40. [48]

    Z. Yan, Y. Peng, and X. Yuan. Tight minimum degree condit ion to guarantee C2k`1-free graphs to be r-partite. arXiv preprint, arXiv: 2409.03407, 2024

    2024 arXiv

  41. [49]

    Yuan and Y

    X. Yuan and Y. Peng. Minimum degree stability of C2k`1-free graphs. J. Graph Theory , 106(2):307–321, 2024. 29

    2024

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.