{"id":"a17257d6-64fb-449d-9fab-c2d0ea2280b2","arxiv_id":"2412.06490","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For r-partite intersection hypergraphs of axis-parallel boxes in R^d, the paper proves the sharp bound O_{d,r}(t n^{r-1} (log n / log log n)^{d-1}), and for pseudo-discs, O_r(t n^{r-1} (log n)^{r-2}).","lead":"This paper proves sharp bounds on the maximum number of hyperedges in intersection hypergraphs of axis-parallel boxes and pseudo-discs that avoid a complete r-partite subhypergraph. The results improve on bounds that had stood for decades in some settings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The clipping step in Section 3.2 is load-bearing for Theorem 1.2 but only sketched; it is not established that clipping pseudo-discs to Z preserves the pseudo-disc property after perturbation.","rationale":"The paper's box result (Theorem 1.1) appears to be supported by detailed combinatorial arguments; I did not find a specific flaw there. The pseudo-disc result (Theorem 1.2), however, depends on a nontrivial geometric clipping claim that is only sketched. The reader identified exactly this as the weakest assumption but considered it non-fatal. I believe the concern is more serious: without a rigorous proof that the perturbed clipped family is a family of pseudo-discs, the induction step in Section 3.2 does not go through. The claim is concrete and testable, and the paper itself provides no reference or complete proof. A conditional acceptance requiring a full proof of the clipping lemma (or a counterexample, which would refute Theorem 1.2) is the appropriate verdict.","tokens_in":23571,"tokens_out":27736,"duration_ms":262675,"concrete_test":"Take Z as the intersection of two unit discs whose boundaries cross at two points. Choose two unit discs s1,s2 whose boundaries each cross both arcs of ∂Z (so each has four endpoints on ∂Z). Apply the paper's clipping procedure for every linear extension of the defined partial order, using sufficiently small offset parameters. Compute the number of transverse intersections between ∂(s1∩Z) and ∂(s2∩Z). If any pair exceeds two, the clipping lemma is false. If all pairs have at most two, further test with Z an intersection of three discs and pseudo-discs with more boundary crossings; a formal proof of the perturbation lemma would also settle the concern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 1.2's induction step requires that after clipping every pseudo-disc in A1∪...∪Ar-1 to Z = ∩_{a∈T} a and applying the stated perturbation, the resulting family is still a family of pseudo-discs. This is asserted with a one-paragraph justification: a partial order on the pseudo-discs by inclusion of their intersections with ∂Z, extended linearly, and clipping 'closer to the boundary' for smaller elements supposedly ensures any two boundaries still intersect at most twice. The argument is not formal and the key assertion 'an intersection is added only to pairs ... whose boundaries have only one intersection point inside Z' is not proved. In fact, a pseudo-disc boundary can meet ∂Z in up to 2t points (since ∂Z is composed of t boundary arcs). The perturbation introduces offset level curves near ∂Z; these curves can cross the interior boundary arcs of another pseudo-disc near each of its endpoints on ∂Z, potentially adding O(t) crossings. The claimed bound of two total crossings does not follow from the described ordering. If the clipping lemma fails, the induction step cannot guarantee that the K^{r-1}_{t,...,t} found in the clipped hypergraph is contained in Z, so the construction of K^r_{t,...,t} in H collapses. Since no alternative proof or reference is supplied, Theorem 1.2 is not fully established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the hypergraph Zarankiewicz problem for r-partite intersection hypergraphs of geometric objects. The first main result, Theorem 1.1, gives an O_{r,d}( t n^{r-1} (log n / log log n)^{d-1} ) bound for axis-parallel boxes in R^d, improving the previous bound of Basit et al. by a factor of about (log n)^{d(2^{r-1}-2)} and matching the known lower bound up to the dependence on t. The second main result, Theorem 1.2, gives O_r( t n^{r-1} (log n)^{r-2} ) for y-monotone pseudo-discs, which is sharp up to logarithmic factors. The proofs introduce a lopsided bipartite Zarankiewicz bound for boxes, a modified biclique cover lemma, an induction on a constraints graph, and a lopsided point--pseudo-disc incidence bound; the pseudo-disc case reduces r to r-1 via a clipping step.","tokens_in":23860,"tokens_out":24724,"duration_ms":256827,"significance":"If both theorems are correct, they are substantial: they give the first improvement over Erdős's 60-year-old general bound for these non-algebraic geometric settings, and the box bound is sharp in both n and t. The biclique-cover lemma and the lopsided bipartite bounds are likely to be useful beyond this paper. The proof of Theorem 1.1 is largely self-contained and the underlying divide-and-conquer arguments are carefully structured. The main risks are the delicate clipping step in Theorem 1.2 and the reliance on two unpublished preprints for base cases; both are localized and appear fixable within the manuscript's scope.","major_comments":[{"comment":"The induction step for Theorem 1.2 rests on the assertion, in the paragraph beginning 'Now, we clip each pseudo-disc s ...', that after clipping every s in A_1 ∪ ... ∪ A_{r-1} to s ∩ Z and applying the described perturbation, the family {s'} is again a family of y-monotone pseudo-discs. This is load-bearing: the induction hypothesis is applied to the clipped (r-1)-partite hypergraph H', and the resulting K^{r-1}_{t,...,t} must be contained in Z. The one-paragraph justification does not constitute a proof. A pseudo-disc boundary can meet ∂Z in up to 2t points, the inclusion partial order on s ∩ ∂Z does not by itself control how many crossings the perturbation adds at the endpoints of the arcs of ∂Z, and the text does not show that s ∩ Z is connected or that the perturbed regions remain y-monotone. Without a rigorous clipping lemma (proved in the paper or quoted with full hypotheses from a published source), Theorem 1.2 is not fully established.","section":"Section 3.2"},{"comment":"The proof of Lemma 3.5 states: 'By the last part of Lemma 3.3, the number of cells in Ξ that contain at least one point of depth between m/r and 2m/r is O(r).' The quoted Lemma 3.3 gives a (1/(2r))-cutting with O(r^2) cells and a per-cell boundary-weight bound; the asserted O(r) bound for cells containing points in that depth range is not a consequence of the statement as written. This bound is what makes the recursion in Theorem 3.2 converge, so the gap is in the main line of the pseudo-disc proof. Please either state the full shallow-cutting theorem from [7] that implies the O(r) cell count, or supply a direct proof.","section":"Section 3.1, Lemma 3.5"},{"comment":"Two load-bearing ingredients are outsourced to preprints that are not yet in final published form. Proposition 2.4 is proved only as a sketch adapting [6, Theorem 3], and Theorem 3.7, the r=2 base case of Theorem 1.2, is quoted from [17], an arXiv preprint. Proposition 2.4 feeds Theorem 2.1 and hence Theorem 1.1; Theorem 3.7 is the induction basis of Theorem 1.2. The manuscript should either include complete proofs of these statements, give their exact statements with all hypotheses, or point to final published versions. As it stands, the correctness of both main theorems depends on the correctness of those preprints.","section":"Appendix A and Section 3.2"}],"minor_comments":[{"comment":"In the triangle case, the sentence 'by partitioning each of A_4,...,A_r arbitrarily into b equal parts' appears to be a typo: after the three splits the first three parts have size n/b^2, so to obtain T_G(n/b^2) the remaining r-3 families must be partitioned into b^2 equal parts, not b.","section":"Section 2.2.3, Case B"},{"comment":"In the proof of Proposition 2.3, the phrase 'substituting to (14)' should read 'substituting to (1)'; the displayed equation is numbered (1).","section":"Section 2.1.3"},{"comment":"There is a typo in the abstract: 'Futhermore' should be 'Furthermore'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong contribution if the clipping lemma and the two preprint-dependent ingredients are resolved. I found no circularity: the lopsided theorems are proved from prior bounds used as building blocks, not from the target claims. The editor may wish to confirm the publication status of [6] and [17]; the dependence on them is substantive but localized."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read. The box bound (Theorem 1.1) is the real result; it is sharp, the proof is detailed, and the biclique-cover induction is a genuine technical contribution. The pseudo-disc bound (Theorem 1.2) has a load-bearing gap in the clipping step. The paper as a whole is well above the desk-reject line, but Theorem 1.2 is not fully proved as written.\n\nWhat's new and good: Theorem 1.1 improves the previous box hypergraph bound by a factor of about (log n)^{d(2^{r-1}-2)} and matches the lower bound, a substantial advance. The lopsided graph-Zarankiewicz lemmas (Theorem 2.1 and Proposition 2.2) are useful on their own. The authors are also honest about leaning on the unpublished preprints [6] and [17] for base cases; that dependency is standard and not a red flag.\n\nThe soft spot is Section 3.2. The clipping step is the heart of the induction for Theorem 1.2, and it is justified in a single paragraph. The stress-test concern is not a nitpick. The region Z is an intersection of t pseudo-discs; its boundary is made of t arcs, so a pseudo-disc boundary can cross ∂Z up to 2t times. The ordering by inclusion of intersections with ∂Z, followed by clipping 'closer to the boundary' for smaller elements, is supposed to ensure that only pairs with one intersection point inside Z gain crossings. That does not follow. Two pseudo-discs that were disjoint inside Z can each cross ∂Z several times, and their clipped boundaries can gain many crossings along the added arcs near ∂Z. Nothing in the one-paragraph argument rules out more than two total intersections.\n\nThis matters because the induction needs H' to be a hypergraph of y-monotone pseudo-discs in general position. If the clipping family is not a pseudo-disc family, the induction hypothesis doesn't apply, and the constructed K^{r-1}_{t,...,t} need not lie in Z. The proof of Theorem 1.2 collapses unless the clipping lemma is true for a different reason. I can't say it's false—the ordering idea might be repairable with a more careful choice of the perturbation level curves—but as it stands the claim is unproved.\n\nThe paper deserves a serious referee. Theorem 1.1 alone justifies sending it out. For Theorem 1.2, the referee should insist on a complete proof of the clipping step. I would bring this to reading group and would cite the paper for the box result, but I wouldn't build anything on Theorem 1.2 until the gap is closed.","headline":"Strong, likely-correct bound for boxes; the pseudo-disc theorem has a real gap in the clipping step that needs fixing.","tokens_in":24346,"tokens_out":5674,"would_cite":true,"duration_ms":58712,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C65","05C35","52C45"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves near-optimal Zarankiewicz bounds for intersection hypergraphs of boxes and pseudo-discs; in the box case the logarithmic factor does not grow with r.","keywords":["Zarankiewicz problem","intersection hypergraphs","axis-parallel boxes","pseudo-discs","extremal combinatorics","biclique covers","shallow cuttings","geometric hypergraphs"],"falsifier":"Find two $y$-monotone pseudo-discs $s_1,s_2$ and a set $T$ of pseudo-discs whose common intersection $Z$ forces the clipped boundaries $s_1'$ and $s_2'$ to have at least three crossing points inside $Z$ under every perturbation of the type described in Section 3.2. Such a pair would show the clipping step can destroy the pseudo-disc property, invalidating the induction in the proof of Theorem 1.2.","tokens_in":23413,"feed_emoji":"📦","tokens_out":11143,"duration_ms":102692,"temperature":0.7,"pith_summary":"Zarankiewicz's problem for hypergraphs asks how many intersecting r-tuples can be formed from r families of n objects each, under the condition that the resulting r-partite hypergraph contains no complete t-by-t-by-...-by-t subhypergraph. This paper proves that for axis-parallel boxes in $\\mathbb{R}^d$ the answer is $O_{r,d}(t n^{r-1} (\\log n / \\log \\log n)^{d-1})$, a bound whose logarithmic factor does not grow with $r$ and which is sharp in both $n$ and $t$. For $y$-monotone pseudo-discs it proves the bound $O_r(t n^{r-1} (\\log n)^{r-2})$, sharp up to a factor of $(\\log n)^{r-2}$. These are the first improvements over the 60-year-old general hypergraph bound in geometric settings with no algebraic structure, and the pseudo-disc bound improves the best previous semialgebraic disc bound by a polynomial factor. The proofs reduce the hypergraph problem to lopsided two-family graph Zarankiewicz bounds, then reassemble the $r$ parts using biclique covers and shallow cuttings.","feed_headline":"Log factor stops growing with r in box hypergraph bound","feed_subtitle":"For pseudo-discs, the same method cuts a 60-year-old bound down to within logarithms.","key_machinery":"The argument is carried by four objects. A lopsided graph Zarankiewicz theorem (Theorem 2.1) bounds intersections between two families of boxes with unequal side sizes, splitting vertex-containment intersections from facet intersections. A biclique-cover lemma (Lemma 2.7) partitions the intersection graph of two box families into $O(b\\log^{d-1} b)$ full and partial bicliques, so the proof can split two coordinates at a cost that does not explode with $r$. A constraints graph on the $r$ parts records which pairs of families contain a disjoint pair of boxes; the proof removes its edges inductively, and the Helly number 2 property of boxes (any pairwise intersecting family of boxes has a common point) converts a $K_{t,t}$ into a $K^r_{t,t,\\ldots,t}$. For pseudo-discs, shallow cuttings (a plane decomposition whose cells are crossed by few boundaries) and a lopsided point-versus-pseudo-disc bound supply the induction step, while a clipping-plus-perturbation step cuts every pseudo-disc to the common intersection $Z$ of a chosen set and keeps the clipped family inside the pseudo-disc class.","core_discovery":"On the paper's own terms, the central discovery is that $r$-partite intersection hypergraphs of geometric families inherit near-optimal Zarankiewicz bounds from lopsided two-family intersection graph bounds, with no algebraic assumptions needed. Theorem 1.1 states that for $r,d,t\\ge 2$ and $n$ axis-parallel boxes in general position in $\\mathbb{R}^d$, every $K^r_{t,t,\\ldots,t}$-free intersection hypergraph has at most $O_{r,d}(t n^{r-1} (\\log n/\\log\\log n)^{d-1})$ hyperedges, and matching lower bounds show this is sharp. Theorem 1.2 states that for $r$ families of $n$ $y$-monotone pseudo-discs in general position, the number of hyperedges is $O_r(t n^{r-1}(\\log n)^{r-2})$, sharp up to logarithmic factors. The paper also conjectures that the pseudo-disc truth is $O_r(t n^{r-1})$ and that this would follow from a lopsided version of the linear graph-level bound.","pith_inferences":["If a stronger lopsided graph bound for boxes is ever found, the same biclique-cover and constraints-graph recursion would transplant it verbatim to $r$-partite hypergraphs, because those steps do not depend on the exact graph bound.","The constraints-graph recursion has an algorithmic reading the paper does not state: a $K^r_{t,\\ldots,t}$-free box hypergraph could be enumerated in time proportional to the bound by splitting only along constraints-graph edges.","The pseudo-disc proof hinges on a geometric clipping property; testing whether clipping an arbitrary pseudo-disc family to a convex region $Z$ preserves the at-most-two-crossings condition would show whether Theorem 1.2 extends beyond $y$-monotone pseudo-discs or to other simply connected regions.","The logarithmic gap in the pseudo-disc result could be probed by constructing $K^r_{t,\\ldots,t}$-free $r$-partite intersection hypergraphs with $n^{r-1}$ times a polylogarithmic number of hyperedges, modeled on graph-level lower-bound constructions; the paper does not provide such lower bounds."],"forward_implications":["For axis-parallel boxes, the maximum number of hyperedges is now pinned down up to constant factors, and the power of $\\log n$ in the bound does not depend on $r$.","The box result improves the previous semilinear bound by a factor of about $(\\log n)^{d(2^{r-1}-2)}$.","For pseudo-discs, the bound $O_r(t n^{r-1}(\\log n)^{r-2})$ improves the best previous semialgebraic disc bound by a factor of order $n^{(2r-2)/(3r-2)}$.","In the pseudo-disc case, an optimal lopsided two-family graph bound would upgrade the theorem to the conjectured $O_r(t n^{r-1})$.","The lower-bound construction from the graph setting extends to $r$ families by adding $r-2$ families of large boxes, so the box bound is sharp in both $n$ and $t$."],"supporting_citations":[{"why":"Supplies the graph-level point-versus-box Zarankiewicz bound and the shallow-cutting lemma for points versus pseudo-discs that the hypergraph proofs build on.","marker":"[7]"},{"why":"Supplies the earlier two-family rectangle graph bound that the box proof improves and generalizes.","marker":"[19]"},{"why":"Supplies the linear bound for horizontal and vertical segment intersection graphs used to control facet intersections and to sharpen the dependence on t.","marker":"[6]"},{"why":"Supplies the linear Zarankiewicz bound for two families of pseudo-discs, which is the base case r=2 of Theorem 1.2.","marker":"[17]"},{"why":"Supplies the previous semilinear bound for box intersection hypergraphs that Theorem 1.1 improves.","marker":"[3]"},{"why":"Supplies the biclique-cover theorem from which Lemma 2.7 is adapted.","marker":"[11]"},{"why":"Supplies the lower-bound construction showing the box bound is sharp.","marker":"[9]"},{"why":"Supplies the shallow-cutting construction used in the lopsided point-pseudo-disc bound.","marker":"[21]"},{"why":"Supplies the original hypergraph Zarankiewicz problem and the general $O(n^{r-1/t^{r-1}})$ bound that the geometric results improve.","marker":"[14]"},{"why":"Supplies the fact that the common intersection of a family of pseudo-discs is connected, used when forming the region Z in the pseudo-disc proof.","marker":"[2]"}],"fun_headline_variants":["Sharp Zarankiewicz bounds for geometric intersection hypergraphs","Box and pseudo-disc hypergraphs get sharp Zarankiewicz bounds","Geometric hypergraphs beat 60-year-old Zarankiewicz bound","No algebra needed: sharp bounds for geometric Zarankiewicz","Pseudo-discs and boxes: near-optimal hypergraph bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that clipping every pseudo-disc to the common intersection region $Z$ of a chosen set $T$, then perturbing boundaries slightly, yields a family whose boundaries still cross at most twice; if clipping can create a third crossing between two boundaries, the induction step that builds a forbidden $K^r_{t,t,\\ldots,t}$ fails.","fun_headline_variants_meta":{"raw":{"variants":["Sharp Zarankiewicz bounds for geometric intersection hypergraphs","Box and pseudo-disc hypergraphs get sharp Zarankiewicz bounds","Geometric hypergraphs beat 60-year-old Zarankiewicz bound","No algebra needed: sharp bounds for geometric Zarankiewicz","Pseudo-discs and boxes: near-optimal hypergraph bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000853,"raw_usage":{"total_tokens":3819,"prompt_tokens":1171,"completion_tokens":2648,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":787,"completion_tokens_details":{"reasoning_tokens":2563}},"tokens_in":787,"tokens_out":2648,"duration_ms":18966,"temperature":1.0,"reasoning_tokens":2563,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T19:35:03.121845+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find two $y$-monotone pseudo-discs $s_1,s_2$ and a set $T$ of pseudo-discs whose common intersection $Z$ forces the clipped boundaries $s_1'$ and $s_2'$ to have at least three crossing points inside $Z$ under every perturbation of the type described in Section 3.2. Such a pair would show the clipping step can destroy the pseudo-disc property, invalidating the induction in the proof of Theorem 1.2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the graph-level point-versus-box Zarankiewicz bound and the shallow-cutting lemma for points versus pseudo-discs that the hypergraph proofs build on."},{"cited_title":"Keller and S","cited_arxiv_id":null,"evidence_quote":"Supplies the earlier two-family rectangle graph bound that the box proof improves and generalizes."},{"cited_title":"Chalermsook, L","cited_arxiv_id":null,"evidence_quote":"Supplies the linear bound for horizontal and vertical segment intersection graphs used to control facet intersections and to sharpen the dependence on t."},{"cited_title":"Basit, A","cited_arxiv_id":null,"evidence_quote":"Supplies the previous semilinear bound for box intersection hypergraphs that Theorem 1.1 improves."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the biclique-cover theorem from which Lemma 2.7 is adapted."},{"cited_title":"Chazelle","cited_arxiv_id":null,"evidence_quote":"Supplies the lower-bound construction showing the box bound is sharp."},{"cited_title":"Matouˇ sek","cited_arxiv_id":null,"evidence_quote":"Supplies the shallow-cutting construction used in the lopsided point-pseudo-disc bound."},{"cited_title":"Ackerman, B","cited_arxiv_id":null,"evidence_quote":"Supplies the fact that the common intersection of a family of pseudo-discs is connected, used when forming the region Z in the pseudo-disc proof."}],"review_version":1}