pith. sign in

arxiv: 2606.18048 · v1 · pith:QUUYMFKUnew · submitted 2026-06-16 · 🧮 math.CO · cs.DM· cs.DS

The independence number of uncrowded hypergraphs: bounds matching the shattering threshold

Abhishek Dhawan , Abhishek Methuku , Minh-Quan Vo This is my paper

Pith reviewed 2026-06-26 23:49 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.DS
keywords uncrowded hypergraphsindependence numbershattering thresholdlinear hypergraphsindependent setsrandomized algorithmsLOCAL algorithmsconstraint satisfaction
0
0 comments X

The pith

Uncrowded k-uniform hypergraphs contain independent sets reaching the shattering threshold up to a (1-ε) factor.

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

The paper proves that for every ε>0 and k≥2, every n-vertex k-uniform uncrowded hypergraph with large enough maximum degree Δ has an independent set of size at least (1-ε)n ((1/(k-1))(log Δ/Δ))^{1/(k-1)}. This matches the shattering-threshold constant that appears in the solution-space geometry of random constraint satisfaction problems. The result improves the leading constant from the Ajtai-Komlós-Pintz-Spencer-Szemerédi theorem and gives the first pseudorandom class of hypergraphs attaining the threshold. It also yields efficient static and distributed algorithms.

Core claim

For every ε>0 and k≥2, every n-vertex k-uniform uncrowded hypergraph of sufficiently large maximum degree Δ contains an independent set of size at least (1-ε)n ((1/(k-1))(log Δ/Δ))^{1/(k-1)}. This attains the shattering-threshold constant, resolves a folklore conjecture by providing the first pseudorandom class matching the threshold, and resolves the Verstraëte-Wilson conjecture by showing linear hypergraphs have independence number at least c_k n (log Δ/Δ)^{1/(k-1)} with c_k=1-o_k(1). The proofs are constructive and give Õ(nΔ)-time randomized static algorithms and Õ(1)-round randomized LOCAL algorithms.

What carries the argument

The uncrowded condition, a quantitative restriction on edge intersections, which allows the independence number bound to reach the shattering threshold via a constructive probabilistic argument.

If this is right

  • Uncrowded hypergraphs form the first pseudorandom class whose independence number matches the shattering threshold.
  • Linear hypergraphs satisfy the independence number lower bound with leading constant 1-o_k(1).
  • There is an Õ(nΔ)-time randomized algorithm to find an independent set of the stated size in uncrowded hypergraphs.
  • There is an Õ(1)-round randomized LOCAL algorithm to find such an independent set.

Where Pith is reading between the lines

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

  • The constructive algorithms may adapt to produce large independent sets in other restricted hypergraph families that are close to uncrowded.
  • The matching of the shattering threshold supplies a deterministic combinatorial analog to the geometry observed in random constraint satisfaction instances.
  • The result suggests checking whether the (1-ε) factor can be removed entirely for sufficiently structured subclasses of uncrowded hypergraphs.

Load-bearing premise

The input hypergraph must be uncrowded and have sufficiently large maximum degree Δ.

What would settle it

An explicit construction of a k-uniform uncrowded hypergraph with large Δ whose largest independent set is smaller than (1-ε)n ((1/(k-1))(log Δ/Δ))^{1/(k-1)} for some fixed ε>0.

Figures

Figures reproduced from arXiv: 2606.18048 by Abhishek Dhawan, Abhishek Methuku, Minh-Quan Vo.

Figure 1
Figure 1. Figure 1: The figure shows how an edge e ∈ E(H) is shrunk to e ∗ = e ∩ K∗ when defining H∗ in Step (5). It also illustrates that any edge of H contained in A must lie entirely within D, confirming that Ii = A \ D is an independent set of H. The orange vertices are neither activated nor discarded, but fail their equalizing coin flips and so do not survive to K∗ . Finally, the vertices in K∗ \ K′ have high degree in H… view at source ↗
Figure 2
Figure 2. Figure 2: The j-edge e shrinks to the ℓ-edge f ∪ {v}, with g = e \ (f ∪ {v}) [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
read the original abstract

A foundational theorem of Ajtai, Koml\'os, Pintz, Spencer, and Szemer\'edi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph with maximum degree $\Delta$ contains an independent set of size $c_k n{\left(\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}}$, for some constant $c_k>0$. Determining the optimal leading constant $c_k$ in this bound is a major open problem. A natural target is the so-called shattering-threshold constant $\left(\frac{1}{k-1}\right)^{\frac{1}{k-1}}$, which appears in the solution-space geometry of random constraint satisfaction problems, in average-case complexity theory, and in statistical physics, among other areas. We prove that uncrowded hypergraphs attain this threshold. More precisely, for every $\epsilon>0$ and $k\geq 2$, every $n$-vertex $k$-uniform uncrowded hypergraph of sufficiently large maximum degree $\Delta$ contains an independent set of size at least $(1-\epsilon) n {\left(\frac{1}{k-1}\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}}$. Consequently, we obtain the first pseudorandom class of hypergraphs whose guaranteed independence number matches the shattering threshold, resolving a folklore conjecture. Moreover, as another direct consequence, we resolve a conjecture of Verstra\"ete and Wilson by proving that there exists a constant $c_k=1-o_k(1)$ such that every $n$-vertex $k$-uniform linear hypergraph of maximum degree $\Delta$ has independence number at least $c_k n\left(\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}$. Our techniques are constructive yielding efficient algorithms for both static and distributed settings. Specifically, we provide an $\tilde O(n\Delta)$-time randomized static algorithm and an $\tilde O(1)$-round randomized $\textsf{LOCAL}$ algorithm to find an independent set in uncrowded hypergraphs at the shattering threshold. These results extend seamlessly to the the setting of linear hypergraphs.

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 manuscript proves that for every ε>0 and k≥2, every n-vertex k-uniform uncrowded hypergraph with sufficiently large maximum degree Δ contains an independent set of size at least (1-ε)n ((1/(k-1))(log Δ/Δ))^{1/(k-1)}. This matches the shattering-threshold constant up to a (1-ε) factor. The result extends immediately to linear hypergraphs (with leading constant 1-o_k(1)) and yields an Õ(nΔ)-time randomized static algorithm together with an Õ(1)-round randomized LOCAL algorithm.

Significance. If the central probabilistic argument holds, the work resolves the folklore conjecture on the optimal leading constant for uncrowded (hence linear) hypergraphs, supplies the first pseudorandom class attaining the shattering threshold, and upgrades the classical Ajtai–Komlós–Pintz–Spencer–Szemerédi theorem with a parameter-free leading constant once Δ is large. The constructive nature of the proofs (refined deletion/LLL tailored to the uncrowded codegree condition) is a notable strength.

minor comments (3)
  1. [§2] §2: the uncrowded condition is invoked from the AKPS-S literature; a one-sentence self-contained definition would aid readers who do not consult the reference.
  2. [Algorithms section] The Õ notation in the algorithmic statements hides polylog(Δ) factors; an explicit statement of the dependence on k and ε would improve precision.
  3. [Introduction] The extension from uncrowded to linear hypergraphs is stated as immediate, but a one-line justification of the inclusion linear ⊂ uncrowded would eliminate any ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of the manuscript, for recognizing its resolution of the folklore conjecture on the shattering threshold for uncrowded hypergraphs, and for recommending acceptance.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The central claim upgrades the leading constant in the AKPS-S theorem for uncrowded hypergraphs from some positive c_k to (1-ε) times the shattering threshold via a self-contained probabilistic argument (refined deletion/LLL exploiting the uncrowded intersection condition to control codegrees). The uncrowded hypothesis and large-Δ assumption are used directly to absorb lower-order terms without any fitted parameter, self-citation chain, or definitional reduction; the extension to linear hypergraphs is immediate by inclusion. No load-bearing step reduces to a prior result by the same authors or renames an input as output.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no explicit free parameters, axioms, or invented entities can be extracted beyond the standard definition of uncrowded hypergraphs and the imported shattering threshold constant.

pith-pipeline@v0.9.1-grok · 5960 in / 1235 out tokens · 34452 ms · 2026-06-26T23:49:01.957593+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

61 extracted references · 4 linked inside Pith

  1. [1]

    Algorithmic barriers from phase transitions

    D. Achlioptas and A. Coja-Oghlan. “Algorithmic barriers from phase transitions”. In:2008 IEEE 49th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2008, pp. 793–802. Full version:https://arxiv.org/abs/0803.2122(cit. on pp. 2, 7)

    Pith/arXiv arXiv 2008

  2. [2]

    On Tur´ an’s theorem for sparse graphs

    M. Ajtai, P. Erd˝ os, J. Koml´ os, and E. Szemer´ edi. “On Tur´ an’s theorem for sparse graphs”. In: Combinatorica1.4 (1981), pp. 313–317 (cit. on p. 3)

    1981

  3. [3]

    Extremal uncrowded hypergraphs

    M. Ajtai, J. Koml´ os, J. Pintz, J. Spencer, and E. Szemer´ edi. “Extremal uncrowded hypergraphs”. In:Journal of Combinatorial Theory, Series A32.3 (1982), pp. 321–335 (cit. on pp. 2, 11)

    1982

  4. [4]

    A note on Ramsey numbers

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. “A note on Ramsey numbers”. In:Journal of Combinatorial Theory, Series A29.3 (1980), pp. 354–360 (cit. on pp. 1, 3)

    1980

  5. [5]

    A dense infinite Sidon sequence

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. “A dense infinite Sidon sequence”. In:European Journal of Combinatorics2.1 (1981), pp. 1–11 (cit. on p. 1)

    1981

  6. [6]

    Coloring graphs with forbidden bipartite subgraphs

    J. Anderson, A. Bernshteyn, and A. Dhawan. “Coloring graphs with forbidden bipartite subgraphs”. In:Combinatorics, Probability and Computing32.1 (2023), pp. 45–67 (cit. on pp. 2, 3)

    2023

  7. [7]

    Coloring graphs with forbidden almost bipartite subgraphs

    J. Anderson, A. Bernshteyn, and A. Dhawan. “Coloring graphs with forbidden almost bipartite subgraphs”. In:Random Structures & Algorithms66.4 (2025), e70012 (cit. on p. 2)

    2025

  8. [8]

    Hypergraph coloring up to condensation

    P. Ayre, A. Coja-Oghlan, and C. Greenhill. “Hypergraph coloring up to condensation”. In:Random Structures & Algorithms54.4 (2019), pp. 615–652 (cit. on p. 2)

    2019

  9. [9]

    Larger matchings and independent sets in regular uniform hypergraphs of high girth

    D. Bal and P. Bennett. “Larger matchings and independent sets in regular uniform hypergraphs of high girth”.https://arxiv.org/abs/2307.15601(preprint). 2023 (cit. on p. 3)

    arXiv 2023

  10. [10]

    On the chromatic number of random regular hypergraphs

    P. Bennett and A. Frieze. “On the chromatic number of random regular hypergraphs”. In:SIAM Journal on Discrete Mathematics38.2 (2024), pp. 1369–1380 (cit. on p. 2)

    2024

  11. [11]

    Online edge coloring algorithms via the nibble method

    S. Bhattacharya, F. Grandoni, and D. Wajc. “Online edge coloring algorithms via the nibble method”. In:Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2021, pp. 2830–2842 (cit. on p. 5)

    2021

  12. [12]

    The average-case complexity of counting cliques in Erd˝ os–R´ enyi hypergraphs

    E. Boix-Adser` a, M. Brennan, and G. Bresler. “The average-case complexity of counting cliques in Erd˝ os–R´ enyi hypergraphs”. In:SIAM Journal on Computing54.4 (2025), FOCS19-39–FOCS19-80 (cit. on p. 3). 28

    2025

  13. [13]

    Boundingχby a fraction of ∆ for graphs without large cliques

    M. Bonamy, T. Kelly, P. Nelson, and L. Postle. “Boundingχby a fraction of ∆ for graphs without large cliques”. In:Journal of Combinatorial Theory, Series B157 (2022), pp. 263–282 (cit. on p. 2)

    2022

  14. [14]

    Toward Vu’s conjecture

    P. Bradshaw, A. Dhawan, A. Methuku, and M. C. Wigal. “Toward Vu’s conjecture”.https : //arxiv.org/abs/2508.16818(preprint). 2025 (cit. on p. 5)

    arXiv 2025

  15. [15]

    A new lower bound for the Ramsey numbersR(3, k)

    M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe. “A new lower bound for the Ramsey numbersR(3, k)”.https://arxiv.org/abs/2505.13371(preprint). 2025 (cit. on p. 2)

    arXiv 2025

  16. [16]

    Pirogov–Sinai Theory for the Hard-Core Model Beyond Lattices

    S. Cannon, T. Helmuth, and W. Perkins. “Pirogov–Sinai Theory for the Hard-Core Model Beyond Lattices”. In:Communications in Mathematical Physics407.6 (2026), p. 129 (cit. on p. 2)

    2026

  17. [17]

    On independent sets in random graphs

    A. Coja-Oghlan and C. Efthymiou. “On independent sets in random graphs”. In:Random Structures & Algorithms47.3 (2015), pp. 436–486 (cit. on p. 2)

    2015

  18. [18]

    List coloring triangle-free hypergraphs

    J. Cooper and D. Mubayi. “List coloring triangle-free hypergraphs”. In:Random Structures & Algorithms47.3 (2015), pp. 487–519 (cit. on p. 6)

    2015

  19. [19]

    On the average size of independent sets in triangle-free graphs

    E. Davies, M. Jenssen, W. Perkins, and B. Roberts. “On the average size of independent sets in triangle-free graphs”. In:Proceedings of the American Mathematical Society146.1 (2018), pp. 111– 124 (cit. on p. 3)

    2018

  20. [20]

    Graph structure via local occupancy

    E. Davies, R. J. Kang, F. Pirot, and J.-S. Sereni. “Graph structure via local occupancy”.https: //arxiv.org/abs/2003.14361(preprint). 2020 (cit. on pp. 2, 3)

    arXiv 2003

  21. [21]

    Balanced independent sets and colorings of hypergraphs

    A. Dhawan. “Balanced independent sets and colorings of hypergraphs”. In:Journal of Graph Theory 109.1 (2025), pp. 43–51 (cit. on p. 2)

    2025

  22. [22]

    Bounds for the independence and chromatic numbers of locally sparse graphs

    A. Dhawan. “Bounds for the independence and chromatic numbers of locally sparse graphs”. In: Annals of Combinatorics(2025), pp. 1–28 (cit. on p. 3)

    2025

  23. [23]

    List colorings ofk-partitek-graphs

    A. Dhawan. “List colorings ofk-partitek-graphs”. In:The Electronic Journal of Combinatorics 32.2 (2025), P2.16 (cit. on p. 2)

    2025

  24. [24]

    Fractional coloring via entropy

    A. Dhawan. “Fractional coloring via entropy”.https://arxiv.org/abs/2603.17730(preprint). 2026 (cit. on p. 2)

    Pith/arXiv arXiv 2026

  25. [25]

    Algorithmic phase transition for large independent sets in dense hypergraphs

    A. Dhawan, N. U. Dinh, E. C. Kızılda˘ g, N. Maitra, and B. A. S ¸ahin. “Algorithmic phase transition for large independent sets in dense hypergraphs”.https://arxiv.org/abs/2605.05618(preprint). 2026 (cit. on pp. 2, 3, 7, 8)

    Pith/arXiv arXiv 2026

  26. [26]

    Independent sets and colorings ofK t,t,t-free graphs

    A. Dhawan, O. Janzer, and A. Methuku. “Independent sets and colorings ofK t,t,t-free graphs”. https://arxiv.org/abs/2511.17191(preprint). 2025 (cit. on pp. 2–4, 6, 8, 9, 12, 13)

    arXiv 2025

  27. [27]

    Improved bounds on the independence number of triangle- free hypergraphs

    A. Dhawan, A. Methuku, and M.-Q. Vo. “Improved bounds on the independence number of triangle- free hypergraphs”. In preparation (cit. on p. 6)

  28. [28]

    The chromatic number of uncrowded hypergraphs: bounds matching the shattering threshold

    A. Dhawan, A. Methuku, and M.-Q. Vo. “The chromatic number of uncrowded hypergraphs: bounds matching the shattering threshold”. In preparation (cit. on p. 6)

  29. [29]

    The low-degree hardness of finding large independent sets in sparse random hypergraphs

    A. Dhawan and Y. Wang. “The low-degree hardness of finding large independent sets in sparse random hypergraphs”. In:SIAM Journal on Discrete Mathematics40.1 (2026), pp. 374–419 (cit. on pp. 2, 3, 7, 8)

    2026

  30. [30]

    On uncrowded hypergraphs

    R. A. Duke, H. Lefmann, and V. R¨ odl. “On uncrowded hypergraphs”. In:Random Structures & Algorithms6.2–3 (1995), pp. 209–212 (cit. on pp. 3–6, 8, 12)

    1995

  31. [31]

    Choosability in graphs

    P. Erd˝ os, A. L. Rubin, and H. Taylor. “Choosability in graphs”. In:Congressus Numerantium26 (1979), pp. 125–157 (cit. on p. 6)

    1979

  32. [32]

    Coloring simple hypergraphs

    A. Frieze and D. Mubayi. “Coloring simple hypergraphs”. In:Journal of Combinatorial Theory, Series B103.6 (2013), pp. 767–794 (cit. on p. 6)

    2013

  33. [33]

    Phase transitions in theq-coloring of random hypergraphs

    M. Gabri´ e, V. Dani, G. Semerjian, and L. Zdeborov´ a. “Phase transitions in theq-coloring of random hypergraphs”. In:Journal of Physics A: Mathematical and Theoretical50.50 (2017), p. 505002 (cit. on p. 2)

    2017

  34. [34]

    The overlap gap property: A topological barrier to optimizing over random struc- tures

    D. Gamarnik. “The overlap gap property: A topological barrier to optimizing over random struc- tures”. In:Proceedings of the National Academy of Sciences118.41 (2021), e2108492118 (cit. on pp. 3, 7)

    2021

  35. [35]

    Optimal hardness of online algorithms for large independent sets

    D. Gamarnik, E. C. Kızılda˘ g, and L. Warnke. “Optimal hardness of online algorithms for large independent sets”.https://arxiv.org/abs/2504.11450(preprint). 2025 (cit. on p. 8)

    arXiv 2025

  36. [36]

    Fast distributed algorithms for Brooks–Vizing colorings

    D. A. Grable and A. Panconesi. “Fast distributed algorithms for Brooks–Vizing colorings”. In: Journal of Algorithms37.1 (2000), pp. 85–120 (cit. on p. 5). 29

    2000

  37. [37]

    ImprovingR(3, k) in just two bites

    Z. Hefty, P. Horn, D. King, and F. Pfender. “ImprovingR(3, k) in just two bites”.https://arxiv. org/abs/2510.19718(preprint). 2025 (cit. on p. 2)

    arXiv 2025

  38. [38]

    Improved bounds for coloring locally sparse hypergraphs

    F. Iliopoulos. “Improved bounds for coloring locally sparse hypergraphs”. In:Approximation, Ran- domization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). 2021 (cit. on pp. 2, 6)

    2021

  39. [39]

    The probabilistic analysis of some combinatorial search algorithms

    R. M. Karp. “The probabilistic analysis of some combinatorial search algorithms”. In:Algorithms and Complexity: New Directions and Recent Results. Ed. by J. F. Traub. New York: Academic Press, 1976, pp. 1–19 (cit. on p. 7)

    1976

  40. [40]

    On Brooks’ theorem for sparse graphs

    J. H. Kim. “On Brooks’ theorem for sparse graphs”. In:Combinatorics, Probability and Computing 4.2 (1995), pp. 97–132 (cit. on p. 3)

    1995

  41. [41]

    A lower bound for Heilbronn’s problem

    J. Koml´ os, J. Pintz, and E. Szemer´ edi. “A lower bound for Heilbronn’s problem”. In:Journal of the London Mathematical Societys2-25.1 (1982), pp. 13–24 (cit. on p. 2)

    1982

  42. [42]

    The chromatic number of triangle-free hypergraphs

    L. Li and L. Postle. “The chromatic number of triangle-free hypergraphs”.https://arxiv.org/ abs/2202.02839(preprint). 2022 (cit. on pp. 6, 7)

    arXiv 2022

  43. [43]

    Locality in distributed graph algorithms

    N. Linial. “Locality in distributed graph algorithms”. In:SIAM Journal on Computing21.1 (1992), pp. 193–201 (cit. on p. 5)

    1992

  44. [44]

    Strong spatial mixing for repulsive point processes

    M. Michelen and W. Perkins. “Strong spatial mixing for repulsive point processes”. In:Journal of Statistical Physics189.1 (2022), p. 9 (cit. on p. 2)

    2022

  45. [45]

    The freezing threshold fork-colourings of a random graph

    M. Molloy. “The freezing threshold fork-colourings of a random graph”. In:Journal of the ACM 65.2 (2018), pp. 1–62 (cit. on pp. 2, 7)

    2018

  46. [46]

    The list chromatic number of graphs with small clique number

    M. Molloy. “The list chromatic number of graphs with small clique number”. In:Journal of Com- binatorial Theory, Series B134 (2019), pp. 264–284 (cit. on p. 2)

    2019

  47. [47]

    Molloy and B

    M. Molloy and B. Reed.Graph Colourings and the Probabilistic Method. Berlin: Springer, 2002 (cit. on p. 9)

    2002

  48. [48]

    Colouring graphs when the number of colours is almost the maximum degree

    M. Molloy and B. Reed. “Colouring graphs when the number of colours is almost the maximum degree”. In:Journal of Combinatorial Theory, Series B109 (2014), pp. 134–195 (cit. on p. 14)

    2014

  49. [49]

    Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth

    J. Nie and J. Verstra¨ ete. “Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth”. In:Random Structures & Algorithms59.1 (2021), pp. 79–95 (cit. on pp. 3, 4)

    2021

  50. [50]

    Distributed coloring algorithms for triangle-free graphs

    S. Pettie and H.-H. Su. “Distributed coloring algorithms for triangle-free graphs”. In:Information and Computation243 (2015), pp. 263–280 (cit. on p. 5)

    2015

  51. [51]

    Local algorithms for independent sets are half-optimal

    M. Rahman and B. Vir´ ag. “Local algorithms for independent sets are half-optimal”. In:The Annals of Probability45.3 (2017), pp. 1543–1577 (cit. on pp. 7, 8)

    2017

  52. [52]

    A note on the independence number of triangle-free graphs

    J. B. Shearer. “A note on the independence number of triangle-free graphs”. In:Discrete Mathe- matics46.1 (1983), pp. 83–87 (cit. on pp. 1, 3, 4)

    1983

  53. [53]

    A note on the independence number of triangle-free graphs, II

    J. B. Shearer. “A note on the independence number of triangle-free graphs, II”. In:Journal of Combinatorial Theory, Series B53.2 (1991), pp. 300–307 (cit. on p. 1)

    1991

  54. [54]

    On the independence number of sparse graphs

    J. B. Shearer. “On the independence number of sparse graphs”. In:Random Structures & Algorithms 7.3 (1995), pp. 269–271 (cit. on p. 3)

    1995

  55. [55]

    Tur´ an’s theorem fork-graphs

    J. Spencer. “Tur´ an’s theorem fork-graphs”. In:Discrete Mathematics2.2 (1972), pp. 183–186 (cit. on p. 2)

    1972

  56. [56]

    On an extremal problem in graph theory

    P. Tur´ an. “On an extremal problem in graph theory”. In:Matematikai ´ es Fizikai Lapok48 (1941). In Hungarian, pp. 436–452 (cit. on p. 2)

    1941

  57. [57]

    Independent sets in hypergraphs

    J. Verstra¨ ete and C. Wilson. “Independent sets in hypergraphs”. In:Random Structures & Algo- rithms68.1 (2026), e70047 (cit. on p. 3)

    2026

  58. [58]

    Coloring the vertices of a graph in prescribed colors

    V. G. Vizing. “Coloring the vertices of a graph in prescribed colors”. In:Diskretnyi Analiz29 (1976). In Russian, pp. 3–10 (cit. on p. 6)

    1976

  59. [59]

    Optimal low-degree hardness of maximum independent set

    A. S. Wein. “Optimal low-degree hardness of maximum independent set”. In:Mathematical Statis- tics and Learning4.3 (2022), pp. 221–251 (cit. on pp. 7, 8)

    2022

  60. [60]

    Hypergraph independence bounds: from maximum degree to average degree

    J. Yu and J. Zhang. “Hypergraph independence bounds: from maximum degree to average degree”. https://arxiv.org/abs/2604.28046(preprint). 2026 (cit. on pp. 4, 5, 8, 13)

    Pith/arXiv arXiv 2026

  61. [61]

    Phase transitions in the coloring of random graphs

    L. Zdeborov´ a and F. Krzakala. “Phase transitions in the coloring of random graphs”. In:Physical Review E76 (2007), p. 031131 (cit. on pp. 2, 7)

    2007