{"id":"2b51f1c3-0874-4c96-8165-9e7e941332cb","arxiv_id":"2504.15264","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors prove matching upper and lower bounds for the Ramsey problem for restricted intersections and derive a single-exponential variant of Furedi's delta-system lemma with applications to quantum computing.","lead":"This paper determines, for every k and every set L of forbidden intersection sizes, how large a subfamily of a sunflower-free family can be made to avoid those intersection sizes. It also improves a core tool of extremal combinatorics, Furedi's delta-system lemma, from a double-exponential to a single-exponential bound, and uses the result to improve quantum shadow tomography.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The reader's strongest claim is Theorem 1.2, and the weakest assumption was identified as Lemma A.2. My review agrees that Lemma A.2 is the least independently verified component, but I could not find an internal inconsistency: the construction's variable counts match Properties 0–8, the sunflower-kernel projection argument in Theorem 3.1 follows from the tree structure and the prescribed neighbourhood sizes, and the heavy-edge counting yields the claimed m^{-(k-1)} fraction. The only genuine issue I found in the central argument is the omitted L=∅ case in the lower-bound proof, which is a one-line fix and does not affect the theorem. Since the central claim survives scrutiny, the reader's ACCEPT verdict should stand; the concrete verification of Lemma A.2 is still worth doing as an independent check of the most intricate construction.","tokens_in":64,"tokens_out":59576,"duration_ms":983850,"concrete_test":"Implement the Lemma A.2 construction for all L⊆[k−1] with 0∉L and 1∈L for k≤5 and small m,n, and verify Properties 0–8 together with the no-L-sunflower and heavy-edge counting used in Theorem 3.1; also run the L=∅ case with F′=F to confirm the exponent 0.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After tracing the proof of Theorem 1.2 and the full Appendix A construction, I do not find a load-bearing flaw in the central claim. The only blemish is a trivial omitted edge case: when L=∅ the lower-bound proof invokes Lemma 2.1 with ℓ=b=k, but Lemma 2.1 requires ℓ≤k−1; this is immediately repaired by taking F′=F, giving the claimed exponent 0. The tightness argument rests on Lemma A.2, whose eight properties I checked against the explicit construction for the given sizes and variable dependencies; the counts of |F| and |V(1,1)|, the tree-intersection property, the suffix form of sunflower kernels, and the heavy-edge matching claims are internally consistent. This remains the least independently verified part of the paper, but I did not find a demonstrated error in it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":42580,"tokens_out":35095,"duration_ms":296248,"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":[{"comment":"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.","section":"Section 3, lower-bound proof of Theorem 1.2"},{"comment":"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.","section":"Appendix A, Lemma A.2 and proof of Theorem 3.1"},{"comment":"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.","section":"Section 4.3, proof of Theorem 4.3"}],"minor_comments":[{"comment":"The phrase \"70 year\" should read \"70 years\".","section":"Abstract"},{"comment":"The footnote contains a duplicated phrase: \"stands for the stands for the set ...\".","section":"Footnote 1"},{"comment":"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\".","section":"Theorem 1.2 statement"},{"comment":"In the statement of Lemma A.1, \"h1,...,t t\" should be \"h_1,...,h_t\".","section":"Lemma A.1 statement"},{"comment":"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.","section":"Theorem 5.1, Eq. (4)"},{"comment":"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.","section":"Appendix B, proof of Lemma 5.10"},{"comment":"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.","section":"Section 5.1, application to quantum computing"}],"recommendation":"minor_revision","confidential_remarks":"This is a strong and carefully written paper. The central results appear sound, and the technical risk is concentrated in the Appendix A construction, which I checked at the level of its internal consistency without finding an error. The two proof gaps I identified (the L=∅ edge case and the k divisible by p assumption in Theorem 4.3) are local and easily repairable, so I would be happy to see the paper accepted after a revision that addresses them and expands the verification of Lemma A.2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a very good paper, and the headline results are real. The authors resolve the L-sunflower Ramsey problem with matching upper and lower bounds on the m-dependence for every k and L, and they prove something genuinely surprising about Furedi's delta-system lemma: the double-exponential dependence on k is necessary for the full-strength statement, yet a single-exponential variant suffices for most applications. The quantum application (improving r_k from roughly (2k)^(k+1) to 2(k+1)) is a nice one-way cross-field payoff, not an afterthought.\n\nThe new colour-certificate technique is the engine, and it earns its keep: the proof of Theorem 1.7 is short and elegant, and the modular-setting results (Theorem 1.4) are natural and well-motivated. The paper ships full proofs, and I checked the main logic of the lower and upper bounds for Theorem 1.2; it holds. Citation pattern looks honest, including the coauthored paper [6] which is used as a comparison, not a crutch.\n\nSoft spots, in proportion:\n\n1. Lemma A.2 is the least independently verified part of the paper. The proof of Theorem 3.1 leans on eight technical properties, and while I traced them against the construction and found them internally consistent, a referee needs to check the counts and the matching claims carefully. This is a genuine referee burden, not a flaw.\n\n2. Minor gap: in the lower-bound proof, when L=∅ the text invokes Lemma 2.1 with ℓ=b=k, outside the lemma's range ℓ≤k−1. The fix is immediate (take F′=F, giving exponent 0), but the manuscript should say so.\n\n3. The claim that Theorem 1.7 can replace Furedi's lemma in the Frankl–Furedi and Chvatal proofs is asserted without details. Probably true, but a referee will want at least a sketch.\n\nThe paper deserves a serious referee. I would send it, and I would expect acceptance after normal revision. It is for extremal set theory and anyone working with delta-systems; the quantum part makes it readable to a broader theory audience.","headline":"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.","tokens_in":43057,"tokens_out":1883,"would_cite":true,"duration_ms":19874,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D05","05D10","05C65","05D40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Forbidden L-sunflowers force large intersection-free subfamilies, with matching bounds","keywords":["restricted intersections","sunflowers","delta-systems","Ramsey problems","colour certificates","shadow tomography","modular intersections","set systems"],"falsifier":"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.","tokens_in":42277,"feed_emoji":"🌻","tokens_out":7859,"duration_ms":74141,"temperature":0.7,"pith_summary":"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).","feed_headline":"Sunflower-free families must hide large clean subfamilies","feed_subtitle":"The exact dependence on petal count is pinned down for every k and L, sharpening shadow tomography too.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the idea that a set A which is not a large sunflower kernel has a small vertex cover and the special element φ(A) trick, which the colour-certificate method builds on.","marker":"[24]"},{"why":"Provides the balanced-case bound for sunflowers with fixed kernel size that Theorem 1.2 connects to and partially recovers.","marker":"[6]"},{"why":"Gives the forbidden-intersection baseline for the Erdős–Sós problem and is one of the main applications where the new delta-system lemma replaces the classical one.","marker":"[17]"},{"why":"Provides the Frankl–Wilson modular intersection bound used in the upper bounds for the modular clique problem and in the new proof of that theorem.","marker":"[22]"},{"why":"Reduces shadow tomography for fermionic observables to fractional colouring of an intersection graph, which Theorem 1.9 then improves.","marker":"[28]"},{"why":"Used in the tightness proof for the case L = [0,a-1], where Erdős–Ko–Rado bounds the size of any intersection-free subfamily.","marker":"[13]"}],"fun_headline_variants":["Exact petal bounds for restricted sunflower-free families","Tight Ramsey growth for L-sunflower-free set families","Single-exponential delta-system lemma with applications","Sunflowers without forbidden kernels contain big clean sets"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact petal bounds for restricted sunflower-free families","Tight Ramsey growth for L-sunflower-free set families","Single-exponential delta-system lemma with applications","Sunflowers without forbidden kernels contain big clean sets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000186,"raw_usage":{"total_tokens":1337,"prompt_tokens":967,"completion_tokens":370,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":308}},"tokens_in":583,"tokens_out":370,"duration_ms":4398,"temperature":1.0,"reasoning_tokens":308,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:29:03.694822+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"F¨ uredi","cited_arxiv_id":null,"evidence_quote":"Supplies the idea that a set A which is not a large sunflower kernel has a small vertex cover and the special element φ(A) trick, which the colour-certificate method builds on."},{"cited_title":"Bradaˇ c, M","cited_arxiv_id":null,"evidence_quote":"Provides the balanced-case bound for sunflowers with fixed kernel size that Theorem 1.2 connects to and partially recovers."},{"cited_title":"Frankl and Z","cited_arxiv_id":null,"evidence_quote":"Gives the forbidden-intersection baseline for the Erdős–Sós problem and is one of the main applications where the new delta-system lemma replaces the classical one."},{"cited_title":"Frankl and R","cited_arxiv_id":null,"evidence_quote":"Provides the Frankl–Wilson modular intersection bound used in the upper bounds for the modular clique problem and in the new proof of that theorem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Reduces shadow tomography for fermionic observables to fractional colouring of an intersection graph, which Theorem 1.9 then improves."},{"cited_title":"Erd˝ os, C","cited_arxiv_id":null,"evidence_quote":"Used in the tightness proof for the case L = [0,a-1], where Erdős–Ko–Rado bounds the size of any intersection-free subfamily."}],"review_version":1}