Pith. sign in

REVIEW 3 major objections 7 minor 1 cited by

Sunflowers and Ramsey problems for restricted intersections

T0 review · 3 major / 7 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read Forbidden L-sunflowers force large intersection-free subfamilies, with matching bounds

desk verdict A genuinely strong paper: tight sunflower-Ramsey bounds for all L, a surprising double-exponential lower bound for Furedi's delta-system lemma, and a clean single-exponential variant; just check the technical Appendix A carefully. read the letter →

arxiv 2504.15264 v2 pith:R6IZS62H submitted 2025-04-21 math.CO cs.DMquant-ph

Barnabás Janzer , Zhihan Jin , Benny Sudakov , Kewen Wu This is my paper · ORCID
classification math.COcs.DMquant-ph MSC 05D0505D1005C6505D40
keywords restrictedintersectionssunflowersdelta-systemsRamseyproblemscolourcertificatesshadowtomographymodularsetsystems
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

The paper resolves, for every uniformity k and every forbidden-intersection set L, the exact dependence on the petal number m in a Ramsey-type question: if a family of k-element sets contains no sunflower with m petals whose kernel size lies in L, then it must contain a subfamily of size Ω_k($m^{{-k+b-a}}$|F|) in which no two sets meet in a size belonging to L. The bound is shown to be best possible for L-sunflowers for every L, so the answer is complete in terms of the exponent of m. The same techniques yield a variant of the classical delta-system lemma with only single-exponential dependence on k, together with a construction showing that the full classical version cannot have such a dependence. As a further consequence, the paper improves the sample-complexity exponent in a shadow-tomography problem for local fermionic observables from exponential in k to 2(k+1).

What carries the argument

The lower bounds are driven by a technique the paper calls colour certificates. For every set A that is not the kernel of an m-petal sunflower, the collection of sets containing A has a small vertex cover ψ(A); the ground set is coloured with few colours so that each such ψ(A) is rainbow, and then the colour palettes are grouped into classes in which any two palettes intersect in fewer than ℓ elements. This lets the paper select a subfamily in which every forbidden intersection A is certified by one special element φ(A) contained in every member that contains A, forcing any two surviving sets to avoid intersection size A. The matching upper bound rests on a separate explicit construction, Lemma A.2, of a layered graph whose k-partite path families have sunflower kernels exactly outside L. For the modular and quantum results, the key structural object is an atomic decomposition: the ground set is partitioned into disjoint d-element atoms and the surviving subfamily consists only of sets that are unions of atoms.

What would settle it

For a concrete small case, take k = 3 and L = {1}, build the graph and family prescribed in the proof of Lemma A.2 for fixed m and n ≥ m, and search by computer for an (m+1)-petal sunflower with a one-element kernel inside that family. Theorem 3.1 asserts that no such sunflower exists; finding one would refute the tightness construction and hence the matching upper bound.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: writing a for the smallest non-negative integer not in L and b for the first integer at least a that lies in L or equals k, any finite family F of k-element sets with no L-sunflower of m petals contains a subfamily F' with |F'| = Ω_k($m^{{-k+b-a}}$|F|) that avoids all intersection sizes in L, and this m-dependence is tight for L-sunflowers for every L. The paper also proves that the classical delta-system lemma cannot be improved beyond a double-exponential constant in k, but provides an alternative single-exponential version, β_{k,m} = (25·2^k k m)^{-k}, that keeps enough structure for many standard applications. In the modular setting, when L is all residues modulo p except one, the paper determines the exponent up to an additive O(1), and when L is the odd integers and k is even, it bounds the fractional chromatic number of the intersection graph by O_k($m^{{k/2}}$), which yields the shadow-tomography improvement.

Load-bearing premise

The matching upper bound rests on the existence, for every L containing 1, of a layered graph satisfying the eight technical properties of Lemma A.2; if that explicit construction fails in any one property, the claimed tightness for L-sunflowers has no proof.

Editorial extensions

If this is right

  • For L = {ℓ}, the main theorem connects the sunflower problem with fixed kernel size ℓ to the forbidden-intersection problem, showing the former exceeds the latter by at most a factor of O_k(m^{k-ℓ}); in the balanced range ℓ ≥ (k-1)/2 this recovers the known Duke–Erdős bound.
  • The new delta-system lemma with single-exponential constant (25·2^k k m)^{-k} can replace the classical version in several standard applications, including forbidden-intersection problems and Chvátal's simplex problem, while improving the dependence on k.
  • The classical delta-system lemma, in its full form with all three structural properties, necessarily has constant at most k!·2^{-C(k,⌈k/2⌉)}, so no single-exponential strengthening of that exact statement is possible.
  • In the modular setting with L = (Z/pZ) \ {a}, the Ramsey number r(k,L,m) is m^{-⌊k/p⌋+O(1)}, and when k is even and L is the odd integers, the intersection graph has fractional chromatic number O_k(m^{k/2}).
  • For k-local fermionic shadow tomography, the exponent in the total copy count improves from O((2k)^{k+1}) to 2(k+1), giving a triply efficient algorithm with O_k((1/ε)^{2k+2} log n) copies.

Reading between the lines

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

  • The atomic-structure technique is likely to extend to families with other divisibility conditions on intersections, since the core induction does not use primality; this could give modular Ramsey bounds for composite moduli.
  • The colour-certificate mechanism suggests a general recipe: whenever a forbidden configuration has a small vertex cover, a rainbow colouring plus a palette-class selection can certify a large cleaner subfamily, so similar bounds may hold for hypergraphs and graph families beyond set systems.
  • The modular singleton bound O_k(m^{-(p-1)k/p+p^2}) hints that the true exponent is close to (p-1)k/p; a matching construction would probably require designs with tightly controlled intersection residues.
  • The double-exponential obstruction is tied to the projection-invariance property of the classical delta-system lemma, so applications that need only intersection-closed kernels can safely use the single-exponential variant.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 7 minor

Summary. The paper studies a Ramsey-type version of restricted-intersection problems for k-uniform set families. Given a forbidden intersection set L and a family F of k-element sets with no L-sunflower having m petals, it asks for the largest guaranteed subfamily F' in which no pairwise intersection has size in L. The main result, Theorem 1.2, determines the m-dependence of this quantity for every k and every L, giving a lower bound of order m^{-k+b-a}|F| and a matching upper bound. The proof introduces a colour-certificate technique (Lemma 2.1), reduces the upper bound to a technical tree-like construction (Theorem 3.1 and Lemma A.2), and also obtains a modular version for L-cliques (Theorem 1.4), a new single-exponential delta-system lemma (Theorem 1.7), a double-exponential lower bound for Furedi's delta-system lemma (Theorem 1.6), and an application to shadow tomography for fermionic observables (Theorem 1.9).

Significance. If the results are correct, the paper fully settles the dependence on m for sunflower Ramsey problems with restricted intersections, which is a natural and previously open question. The modular result Theorem 1.4 reveals a genuine difference between forbidden sunflowers and forbidden cliques, and the improved delta-system lemma with matching lower bound for Furedi's original constant is a notable contribution to a widely used method. The quantum computing application is a clean, one-way consequence and improves the sample-complexity exponent from exponential to 2(k+1). The paper is also well structured: the colour-certificate argument is elegant, the reduction steps are carefully organized, and the main claims are accompanied by explicit constructions. The strongest part of the paper, the matching upper bound for all L, rests on a substantial algebraic construction in Appendix A; I did not find a demonstrated error in it, but it is the part that needs the most careful checking.

major comments (3)
  1. [Section 3, lower-bound proof of Theorem 1.2] The proof of the lower bound in Theorem 1.2 does not cover the case L = ∅. In that case one has a = 0 and b = k, but the first paragraph applies Lemma 2.1 with ℓ = b = k, whereas Lemma 2.1 is stated only for ℓ ∈ [0, k-1]. The theorem is easily repaired: if L = ∅, taking F' = F gives |F'| = |F| = m^{0}|F| and F' trivially avoids intersections of size in L. Please add this case explicitly or extend Lemma 2.1.
  2. [Appendix A, Lemma A.2 and proof of Theorem 3.1] The tightness half of Theorem 1.2 depends entirely on Theorem 3.1, whose proof in turn depends on Lemma A.2 and its eight technical properties. The verification of Lemma A.2 is compressed into a short paragraph: Property 0 is asserted with a count that is not shown, Property 1 is justified in one sentence, and Properties 2-8 are each dismissed in a sentence. I checked the construction and did not find a flaw, but the current level of detail makes the main upper-bound proof hard to verify independently. The proof should spell out the counting yielding |V(1,1)| = n^{t-2}m^{k-t+1} and |F| = n^{t-2}m^{2k-t}, and should give a fuller argument for the connectedness claim in Property 1.
  3. [Section 4.3, proof of Theorem 4.3] In the proof of the upper bound in Theorem 4.3, the statement that the number of indices i with δ_i ≥ p is at most ⌊(k-1)/p⌋ = k/p - 1 is valid only when p divides k. The theorem statement, however, allows arbitrary positive k. The preceding paragraph says the proof is only written for k a multiple of p and that the general case is similar, so the exposition is misleading. Either restrict Theorem 4.3's upper-bound claim accordingly or give the short extra argument for general k; the application in Theorem 5.4 absorbs a constant additive change, so this does not affect the main conclusions.
minor comments (7)
  1. [Abstract] The phrase "70 year" should read "70 years".
  2. [Footnote 1] The footnote contains a duplicated phrase: "stands for the stands for the set ...".
  3. [Theorem 1.2 statement] The parenthetical "this holds F it has no L-clique of size m" should read "this holds if F has no L-clique of size m".
  4. [Lemma A.1 statement] In the statement of Lemma A.1, "h1,...,t t" should be "h_1,...,h_t".
  5. [Theorem 5.1, Eq. (4)] The definition of w'(F) in Eq. (4) is ambiguous in the rendered text: the position of d relative to the binomial coefficient should be clarified. The proof is consistent with w'(F) = (1/(d * binom(k,d-1) * m))^{|F|/d} w(F), and the formula should be typeset unambiguously.
  6. [Appendix B, proof of Lemma 5.10] The sentence "we iteratively shrink the ground set by two each time" should say "by d each time" or "by p each time" in the application, since the general theorem uses a parameter d.
  7. [Section 5.1, application to quantum computing] In the discussion after Theorem 5.9, the classical running time is described as poly(nk, 1/ε), but Theorem 5.9 states poly(nk, T, 1/ε); this is harmless but should be made consistent.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the main theorems are proved from explicit first-principles constructions with no fitted input renamed as a prediction.

full rationale

The paper's central claims (Theorems 1.2, 1.4, 1.6, 1.7, and the quantum application) are derived through self-contained arguments. The lower bound in Theorem 1.2 follows from the colour-certificate Lemma 2.1, whose proof is a direct probabilistic construction; the upper bound is built from the explicit graph construction in Lemma A.2 and Appendix A, with every property (0–8) checked against the defined vertex sets and families. There is no parameter fitted to a data subset that is later renamed as a prediction, and no definition of a central quantity in terms of the quantity it is supposed to determine. The paper does cite prior work by overlapping authors (e.g., [6] and [2]), but these citations are contextual comparisons or tools, not load-bearing premises: the lower bound in Theorem 1.2 does not invoke [6], the upper bound does not invoke [2], and Theorem 3.1 is proved by an explicit construction rather than imported as an external uniqueness theorem. The only technical blemish is an edge case in the lower-bound proof when L is empty: the argument invokes Lemma 2.1 with ℓ=b=k, while Lemma 2.1 states ℓ≤k−1; however, this is immediately repairable by taking F′=F and gives the same claimed exponent, and it is a correctness gap, not circularity. The quantum application is a one-way use of the graph-theoretic bounds on the fractional chromatic number together with the external reduction in [28], so it does not feed back into the combinatorial derivation. Overall, the derivation chain is independent and no step reduces to its own input by construction.

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

The central claims are proved from these standard theorems plus new techniques. There are no fitted parameters or invented physical entities. The main new concept, colour certificates, is a proof technique rather than a postulated object.

assumptions (6)
  • standard math Ray-Chaudhuri-Wilson theorem
    Used in the upper bound proof of Theorem 1.4 to bound the size of families with restricted pairwise intersection sizes.
  • standard math Frankl-Wilson theorem
    Used in Theorem 4.6 and in the upper bound of Theorem 1.4 to control L-cliques modulo a prime.
  • standard math Erdős-Ko-Rado theorem
    Used in the tightness proof of Theorem 1.2 to bound the maximum size of a subfamily avoiding small intersections.
  • standard math Tuza's theorem
    Used in Theorem 5.7 to bound the size of L-cliques in the constructed family.
  • standard math Inclusion-exclusion principle
    Used in Proposition 4.5 to derive a polynomial identity for intersection-closed families.
  • domain assumption Primality of p for modular bounds
    Theorems 1.4 and 4.3 require p prime to apply Frankl-Wilson and related tools; the lower bounds in Theorem 1.4 actually hold for any integer d.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sunflowers and Ramsey problems for restricted intersections." pith.science (2026). https://pith.science/paper/R6IZS62H

@misc{pith2026250415264,
  author       = {Pith},
  title        = {Pith review of: Sunflowers and Ramsey problems for restricted intersections},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R6IZS62H}},
  note         = {Machine review of arXiv:2504.15264}
}
abstract

Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 years. In this paper, we study the following Ramsey version of these problems. Given a set $L\subseteq \{0,\dots,k-1\}$ and a family $\mathcal{F}$ of $k$-element sets which does not contain a sunflower with $m$ petals whose kernel size is in $L$, how large a subfamily of $\mathcal{F}$ can we find in which no pair has intersection size in $L$? We give matching upper and lower bounds, determining the dependence on $m$ for all $k$ and $L$. This problem also finds applications in quantum computing. As an application of our techniques, we also obtain a variant of F\"uredi's celebrated semilattice lemma, which is a key tool in the powerful delta-system method. We prove that one cannot remove the double-exponential dependency on the uniformity in F\"uredi's result, however, we provide an alternative with significantly better, single-exponential dependency on the parameters, which is still strong enough for most applications of the delta-system method.

Figures

Figures reproduced from arXiv: 2504.15264 by the authors.

Figure 1
Figure 1. An illustration of G when k = 8 and L = {1, 2, 3, 6} (hence t = 5). The eight parts of G are depicted by circles and there are edges between two parts if and only if there is a solid line between the two circles. A Proof of Theorem 3.1 In this section, we prove Theorem 3.1 by extending the construction we used in the case L = {1}. For notational convenience, we will show rsf(k, L, m + 1) ≤ m−(k−1) for all L ⊆ [k − 1… view at source ↗
Figure 2
Figure 2. Continuation of the illustration when k = 8 and L = {1, 2, 3, 6}. The solid black arrows indicate the number of neighbours in the incoming part of any vertex in the outgoing part. The dashed pink arrows indicate the number of options (Wu,v) in the incoming part given any two vertices in the two outgoing parts. 25 [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Delta-system method: a survey

    math.CO 2025-08 conditional novelty 3.0 of 10

    A survey of the Delta-system (sunflower) method in extremal set theory, with proofs of key theorems and a broad literature review.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · cited by 1 Pith paper

  1. [6]

    Bradaˇ c, M

    D. Bradaˇ c, M. Buci´ c, and B. Sudakov. Tur´ an numbers of sunflowers. Proc. Amer. Math. Soc. , 151(3):961– 975, 2023. 1, 4.4, 4.4

    work page 2023

  2. [1]

    Aaronson

    S. Aaronson. Shadow tomography of quantum states. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 325–338, 2018. 1.3

    work page 2018

  3. [2]

    Alweiss, S

    R. Alweiss, S. Lovett, K. Wu, and J. Zhang. Improved bounds fo r the sunflower lemma. Ann. of Math. (2) , 194(3):795–815, 2021. 1, 6

    work page 2021

  4. [3]

    Arora, E

    S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and appli- cations. Theory Comput. , 8(1):121–164, 2012. 5.1, B

    work page 2012

  5. [4]

    Babai and P

    L. Babai and P. Frankl. Linear algebra methods in combinatorics, 2022. 1

    work page 2022

  6. [5]

    B˘ adescu and R

    C. B˘ adescu and R. O’Donnell. Improved quantum data analysis. I n Proc. 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 1398–1411, 2021. 1.3

    work page 2021

  7. [7]

    Conlon, J

    D. Conlon, J. Fox, and B. Sudakov. Recent developments in grap h Ramsey theory. In Surveys in Combi- natorics 2015 , volume 424 of London Math. Soc. Lecture Note Ser. , pages 49–118. Cambridge Univ. Press, Cambridge, 2015. 1

    work page 2015

  8. [8]

    M. Deza. Solution d’un probl` eme de Erd˝ os–Lov´ asz.J. Combin. Theory Ser. B , 16:166–167, 1974. 1, 5.3

    work page 1974

Show all 47 references
  1. [9]

    M. Deza, P. Erd˝ os, and P. Frankl. Intersection properties of systems of finite sets. Proc. London Math. Soc. (3), 36(2):369–384, 1978. 1, 1.2

    1978

  2. [10]

    R. A. Duke and P. Erd˝ os. Systems of finite sets having a commo n intersection. In Proc. 8th S-E Conf. Combinatorics, Graph Theory and Computing , volume 19 of Congress. Numer. , pages 247–252. Utilitas Math., Winnipeg, 1977. 1

    1977

  3. [11]

    Ellis, N

    D. Ellis, N. Keller, and N. Lifshitz. Stability for the complete inters ection theorem, and the forbidden intersection problem of Erd˝ os and S´ os.J. Eur. Math. Soc. (JEMS) , 26(5):1611–1654, 2024. 1, 4.1

    2024

  4. [12]

    P. Erd˝ os. Problems and results in graph theory and combinato rial analysis. In Proc. 5th British Com- binatorial Conf. 1975 , volume 15 of Congress. Numer. , pages 169–192. Utilitas Math., Winnipeg, 1976. 1

    1975

  5. [13]

    Erd˝ os, C

    P. Erd˝ os, C. Ko, and R. Rado. Intersection theorems for sy stems of finite sets. Quart. J. Math. Oxford Ser. (2), 12:313–320, 1961. 3

    1961

  6. [14]

    Erd˝ os and R

    P. Erd˝ os and R. Rado. Intersection theorems for systems o f sets. J. London Math. Soc. , 35:85–90, 1960. 1

    1960

  7. [15]

    Erd˝ os and G

    P. Erd˝ os and G. Szekeres. A combinatorial problem in geometr y. Compos. Math., 2:463–470, 1935. 1

    1935

  8. [16]

    P. Frankl. On intersecting families of finite sets. J. Combin. Theory Ser. A , 24(2):146–161, 1978. 1.2, 1.5, 1.2 22

    1978

  9. [17]

    Frankl and Z

    P. Frankl and Z. F¨ uredi. Forbidding just one intersection. J. Combin. Theory Ser. A , 39(2):160–176, 1985. 1, 1.2, 1.2, 4.1

    1985

  10. [18]

    Frankl and Z

    P. Frankl and Z. F¨ uredi. Exact solution of some Tur´ an-typeproblems. J. Combin. Theory Ser. A , 45(2):226– 262, 1987. 1.2, 1.2, 4.1

    1987

  11. [19]

    Frankl and A

    P. Frankl and A. M. Odlyzko. On subsets with cardinalities of inte rsections divisible by a fixed integer. European J. Combin. , 4(3):215–220, 1983. 5.3

    1983

  12. [20]

    Frankl and N

    P. Frankl and N. Tokushige. Invitation to intersection problem s for finite sets. J. Combin. Theory Ser. A , 144:157–211, 2016. 1

    2016

  13. [21]

    Frankl and N

    P. Frankl and N. Tokushige. Uniform eventown problems. European J. Combin. , 51:280–286, 2016. 4.3

    2016

  14. [22]

    Frankl and R

    P. Frankl and R. M. Wilson. Intersection theorems with geomet ric consequences. Combinatorica, 1:357–368,

  15. [23]

    Frankston, J

    K. Frankston, J. Kahn, B. Narayanan, and J. Park. Thresho lds versus fractional expectation-thresholds. Ann. of Math. (2) , 194(2):475–495, 2021. 1

    2021

  16. [24]

    F¨ uredi

    Z. F¨ uredi. On finite set-systems whose every intersection is a kernel of a star. Discrete Math., 47(1):129–132,

  17. [25]

    F¨ uredi

    Z. F¨ uredi. Tur´ an type problems. InSurveys in combinatorics, 1991 (Guildford, 1991) , volume 166 of London Math. Soc. Lecture Note Ser. , pages 253–300. Cambridge Univ. Press, Cambridge, 1991. 1.2

    1991

  18. [26]

    Gishboliner, B

    L. Gishboliner, B. Sudakov, and I. Tomon. Small doubling, atomic structure and ℓ-divisible set families. Discrete Anal., Paper No. 11, 2022. 5.3

    2022

  19. [27]

    Keller and N

    N. Keller and N. Lifshitz. The junta method for hypergraphs an d the Erd˝ os-Chv´ atal simplex conjecture. Adv. Math. , 392:Paper No. 107991, 2021. 4.1

    2021

  20. [28]

    R. King, D. Gosset, R. Kothari, and R. Babbush. Triply efficient s hadow tomography. PRX Quantum , 6:010336, 2025. 1.3, 1.8, 1.3, 5.1, 5.1, 5.9, 6

    2025

  21. [29]

    Kupavskii and D

    A. Kupavskii and D. Zakharov. Spread approximations for for bidden intersections problems. Adv. Math. , 445:Paper No. 109653, 2024. 1, 1, 4.1

    2024

  22. [30]

    Mubayi and J

    D. Mubayi and J. Verstra¨ ete. A survey of Tur´ an problems for expansions. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl. , pages 117–143. Springer, Cham, 2016. 1.2, 1.2, 6

    2016

  23. [31]

    N¨ agele, B

    M. N¨ agele, B. Sudakov, and R. Zenklusen. Submodular minimizat ion under congruency constraints. Com- binatorica, 39(6):1351–1386, 2019. 4.4

    2019

  24. [32]

    Park and H

    J. Park and H. T. Pham. A proof of the Kahn-Kalai conjecture . J. Amer. Math. Soc. , 37(1):235–243, 2024. 1

    2024

  25. [33]

    A. Rao. Sunflowers: from soil to oil. Bull. Amer. Math. Soc. , 60(1):29–38, 2023. 1

    2023

  26. [34]

    D. K. Ray-Chaudhuri and R. M. Wilson. On t-designs. Osaka Math. J. , 12(3):737–744, 1975. 1

    1975

  27. [35]

    Z. Tuza. Inequalities for two-set systems with prescribed inte rsections. Graphs Combin. , 3(1):75–80, 1987. 5.1 23 V(1,1) V(2,1) V(2,2) V(3,1) V(4,1) V(4,2) V(4,3) V(5,1) h1 = 1 h2 = 2 h3 = 1 h4 = 3 h5 = 1 Figure 1: An illustration of G when k = 8 and L = {1, 2, 3, 6} (hence ...

    1987

  28. [36]

    |V(1,1)| =nt−2mk−t+1 and |F | =nt−2m2k−t

  29. [37]

    Whenever F,F ′ ∈ F , then {p ∈P :F ∩F ′ ∩Vp ⁄= ∅} induces a connected (or empty) subgraph of T

  30. [38]

    For all a ∈ [t − 1], each vertex in V(a,1) has exactly m neighbours in V(a+1,1)

  31. [39]

    Moreover, each vertex in V(t,1) has exactly m neighbours in V(t−1,1)

    For all a ∈ [2,t − 1], each vertex in V(a,1) has exactly n neighbours in V(a−1,1). Moreover, each vertex in V(t,1) has exactly m neighbours in V(t−1,1)

  32. [40]

    Whenever (a,b ) ∈P with b ≥ 2, then each vertex in V(a,b) has exactly m neighbours in V(a,b−1)

  33. [41]

    If a ∈ [t − 1] with ha ≥ 2, u ∈V(a,1), and v ∈V(a+1,1), there exists a set Wu,v ⊆V(a,2) of size m such that every F ∈ F that contains u,v must contain one of the vertices in Wu,v

  34. [42]

    If F,F ′ ∈ F satisfies F ∩V(a,1) =F ′ ∩V(a,1) and F ∩V(a+1,1) ⁄=F ′ ∩V(a+1,1), then F ∩V(a,2) ⁄=F ′ ∩V(a,2)

    Let a ∈ [t − 1] with ha ≥ 2. If F,F ′ ∈ F satisfies F ∩V(a,1) =F ′ ∩V(a,1) and F ∩V(a+1,1) ⁄=F ′ ∩V(a+1,1), then F ∩V(a,2) ⁄=F ′ ∩V(a,2)

  35. [43]

    If a ∈ [t − 1], b ∈ [3,h a], u ∈V(a,b−1), and v ∈V(a,b−2), there exists a set Wu,v ⊆V(a,b) of size m such that every F ∈ F that contains u,v must contain one of the vertices in Wu,v

  36. [44]

    very few

    Let a ∈ [t−1] andb ∈ [3,h a]. If F,F ′ ∈ F satisfies F ∩V(a,b−1) =F ′∩V(a,b−1) andF ∩V(a,b−2) ⁄=F ′∩V(a,b−2), then F ∩V(a,b) ⁄=F ′ ∩V(a,b). We note that Properties 1, 2, and 3 correspond to (1), (2), and (3), respectively; Property 4 is the analogue of Property (2) forV(a,b) wi...

  37. [45]

    For alla ∈ [t − 1] and b ∈ [ha − 1], by Properties 2 and 5 (ifb = 1) or Properties 4 and 7 (ifb> 1), each vertex in V(a,b) has at most m2 G-neighbours in V(a,b+1)

    in the last step. For alla ∈ [t − 1] and b ∈ [ha − 1], by Properties 2 and 5 (ifb = 1) or Properties 4 and 7 (ifb> 1), each vertex in V(a,b) has at most m2 G-neighbours in V(a,b+1). Hence, using Property 4, we have |V(a,b)| ≤ |V(a,1)| ·mb−1 = nt−a−1mk−t+a+b−1 for all a ∈ [t − ...

  38. [46]

    Initialize w(1) ∈ RF ≥0 by setting w(1) F = 1 |F | for all F ∈ F

  39. [47]

    As discussed above, we can find the independent set I (t) in running time poly( nk)

    For each step t = 1,...,T , find an independent set I (t) ⊆ F of GF satisfying ∑ F ∈I (t) w(t)(F ) ≥ 1 χ ∑ F ∈F w(t)(F ), (6) and let w(t+1) ∈ RF ≥0 be the weighting given by w(t+1)(F ) = { w(t)(F ) · ( 1 + 1 4χ2 ) if F /∈ I (t), w(t)(F ) · ( 1 − 1 4χ + 1 4χ2 ) if F ∈ I (t). As...

Pith tools

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