Pith. sign in

REVIEW 1 major objections 5 minor 25 references

Relative discrepancy of hypergraphs

T0 review · 1 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper determines the exact number of moderately dense $k$-uniform hypergraphs that force a pair with large relative discrepancy for $k\le 13$, and bounds that number by $O(k^{0.525})$ in general.

desk verdict Genuine advance on bs(k) with a solid main theorem, but the O(k^{0.525}) corollary rests on an invalid appendix proof that needs repair. read the letter →

arxiv 2506.23264 v1 pith:DV7ORHV6 submitted 2025-06-29 math.CO

Diep Luong-Le , Tuan Tran , Dilong Yang This is my paper · ORCID
classification math.CO MSC 05C6505D4011N05
keywords relativediscrepancyhypergraphk-uniformhypergraphsW-vectorunavoidablepatternsblockdesignsprimegapsharmonicmultilinearpolynomials
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

Two $k$-uniform hypergraphs on the same $n$ vertices have relative discrepancy equal to the largest possible deviation of their edge-intersection size from the expected value $pq\binom{n}{k}$, where $p$ and $q$ are the two densities. The paper asks for the smallest number $\mathrm{bs}(k)$ of moderately dense $k$-uniform hypergraphs that guarantees some pair has the maximal possible discrepancy, of order $n^{(k+1)/2}$. The main theorem proves that $\min\{k,3\} \le \mathrm{bs}(k) \le g(k)+2$ for a small number-theoretic constant $g(k)$, which yields the exact value $\mathrm{bs}(k)=3$ for every $3 \le k \le 13$ and the general bound $\mathrm{bs}(k)=O(k^{0.525})$, improving the previous $\mathrm{bs}(k)\le k+1$. The upper bound rests on a new method: any moderately dense $k$-uniform hypergraph must have a large W-vector component in its top $k-g(k)$ levels unless it carries a very special algebraic structure that is then ruled out using unavoidable patterns. The lower bound $\mathrm{bs}(k)\ge 3$ for $k\ge 3$ is obtained by explicit pairs of moderately dense hypergraphs with zero relative discrepancy, built from block designs, which disproves the Bollobás–Scott conjecture in the unweighted case.

What carries the argument

The engine of the proof is the W-vector. For a $k$-uniform hypergraph $G$, the component $W_r(G)$ is the $L^2$-normalized alternating sum of edge indicators over $r$ paired vertices; Bollobás and Scott had shown that $\mathrm{disc}(G,H)\ge c\,n^{(k+1)/2}\max_{1\le r\le k} W_r(G)W_r(H)$, so forcing some top-level $W_r$ to be large in every moderately dense hypergraph produces a high-discrepancy pair by a pigeonhole argument. The paper proves an algebraic criterion (Proposition 2.4): $\max_{\ell\le r\le k} W_r(f)=0$ if and only if $f$ is a sum over subsets of a fixed function on $(\ell-1)$-sets; the proof uses the rank of inclusion matrices (Gottlieb) for uniqueness and a ballot-theorem argument for the dimension. A stability version (Proposition 2.6) shows that if all $W_r(f)$ are at most $\varepsilon$, then $f$ is within $O(\varepsilon^{1/2})$ of such a structured function on all but $O(\varepsilon^{1/2}\binom{n}{k})$ sets, proved by expansion in Filmus's orthogonal basis of harmonic multilinear polynomials on the Boolean slice. These criteria are married to a robust Fox–Sudakov theorem (Proposition 3.2) that locates a large non-homogeneous $(k,k,k)$-pattern inside any moderately dense hypergraph while avoiding a sparse set of exceptional $k$-sets, and an induction on the pattern's number of parts (Lemma 4.3) shows that any pattern with the relevant W-components zero must be homogeneous, because such a pattern forces a binary vector solving exactly the equation system that defines $g(k)$.

What would settle it

Compute, for each $k$ in the range 14 to 128 and each $m\le k$, using the known values of $g(k)$ from the cited table, whether any prime $p$ satisfies $m-g(k)\le p-1\le m$. A single $m$ with no such prime would disprove the appendix's assertion and remove the support for $\mathrm{bs}(k)=O(k^{0.525})$; conversely, if the assertion holds throughout, the number-theoretic step of the proof is vindicated.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for every $k\ge 2$, $\min\{k,3\} \le \mathrm{bs}(k) \le g(k)+2$, where $g(k)$ is the smallest integer $g$ such that for every $m\in[2,k]$ the binary system of alternating-sum equations $\sum_{i=0}^r (-1)^i \binom{r}{i}\alpha_i=0$ for $r=m-g,\ldots,m$ has only the all-zero and all-one solutions. Plugging in the known values $g(2)=0$, $g(k)=1$ for $3\le k\le 13$, and $g(k)\le G(k)$, the paper obtains $\mathrm{bs}(2)=2$, $\mathrm{bs}(k)=3$ for all $k\in[3,13]$, and, from the prime-gap estimate $G(k)=O(k^{0.525})$, the general bound $\mathrm{bs}(k)=O(k^{0.525})$. The lower bound is proved by constructing, for every $k\ge 3$, two moderately dense $k$-uniform hypergraphs with zero relative discrepancy: one is an $(n,k,k-1,\lambda)$-block design and the other contains exactly the $k$-sets that meet each part of a fixed $(k-1)$-partition, so every placement of the two has the same intersection size, namely $pq\binom{n}{k}$.

Load-bearing premise

The paper's improved bound hinges on an appendix step that asserts, without proof, that for every $m\le k$ there is a prime $p$ with $m-g(k)\le p-1\le m$; if this prime-existence claim fails for some $m$, the corollary $\mathrm{bs}(k)=O(k^{0.525})$ does not follow.

Editorial extensions

If this is right

  • For every $k$ between 3 and 13, any three moderately dense $k$-uniform hypergraphs on $n$ vertices contain a pair with relative discrepancy $\Omega(n^{(k+1)/2})$, and two never suffice.
  • For all $k$, $\mathrm{bs}(k)=O(k^{0.525})$, improving the previously best bound $k+1$ by a polynomial factor.
  • The Bollobás–Scott conjecture that one pair always suffices is false for every $k\ge 3$, since the paper constructs zero-discrepancy pairs of moderately dense hypergraphs.
  • For $14\le k\le 128$, the threshold lies between 3 and 5 inclusive, directly from the theorem and the known values of $g(k)$.
  • If von zur Gathen and Roche's conjecture $g(k)=O(1)$ is true, then $\mathrm{bs}(k)=O(1)$ as well, so the number of hypergraphs needed would be bounded independent of the uniformity $k$.

Reading between the lines

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

  • The algebraic criterion and its stability version are likely portable: any discrepancy-type statement that can be lower-bounded by products of W-type norms and that admits a similar algebraic vanishing characterization could be attacked with the same local-to-global pattern argument.
  • The zero-discrepancy construction suggests a recipe: pair any hypergraph whose edge indicator is constant on all $k$-sets meeting every part of a fixed low-complexity partition with a design whose block-intersection counts match that constant; other design families may yield zero-discrepancy pairs for related discrepancy notions.
  • Because the constant $g(k)$ depends only on finite binary alternating-sum systems, the exact threshold for $\mathrm{bs}(k)$ in the unknown range $k\ge 14$ can be settled by a finite computation for each $k$, making the remaining part of the problem effectively algorithmic rather than purely asymptotic.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 5 minor

Summary. The paper studies the relative discrepancy disc(G,H) of two k-uniform hypergraphs with prescribed densities, and defines bs(k) as the smallest number of moderate-density k-uniform hypergraphs that forces a pair with discrepancy Ω(n^{(k+1)/2}). The main theorem states min{k,3} ≤ bs(k) ≤ g(k)+2, where g(k) is a number-theoretic function defined via binary linear systems. This yields bs(k)=3 for 3≤k≤13 and bs(k)≤5 for 14≤k≤128. The paper also claims bs(k)=O(k^{0.525}) by combining g(k)≤G(k) (maximal prime gaps) with Baker–Harman–Pintz. The proof introduces a new algebraic criterion for vanishing W-vectors, a stability result via harmonic polynomials, a robust version of the Fox–Sudakov unavoidable-pattern theorem, and uses block designs for the lower bound.

Significance. The paper makes a substantial advance on a question of Bollobás and Scott: it gives the first exact values for bs(k) beyond the graph case, disproves the conjecture that any pair of moderate-density hypergraphs must have large relative discrepancy, and improves the general upper bound from k+1 to a sublinear function. The lower-bound construction via Keevash-style designs is elegant, and the upper-bound machinery (W-vector criterion, harmonic-polynomial stability, robust Fox–Sudakov patterns) is a coherent new toolkit that may find further uses. If the number-theoretic corollary is repaired, the paper delivers a quantitative improvement that goes well beyond the previous state of the art. However, as it stands, the advertised O(k^{0.525}) bound rests on an unproved implication in Appendix A.

major comments (1)
  1. [Appendix A, proof of Theorem 1.3(ii)] The first line of the proof asserts 'From Definition 1.1, there exists a prime p such that m−g ≤ p−1 ≤ m'. This is not a consequence of Definition 1.1, which concerns only the solution set of a binary linear system and contains no prime information. The subsequent modular argument proves the forward direction (if such a prime exists, then the system has only two solutions), but proving g(k)≤G(k) requires the converse for each m. As written, Corollary 1.4(ii) and the abstract's claimed O(k^{0.525}) bound are unsupported. The defect is repairable: take p to be the largest prime with p≤m+1; then p−1≥m−G(k) by the definition of G(k), and applying the modular argument with g=G(k) shows the system for that m has only two solutions, yielding g_m≤G(k).
minor comments (5)
  1. [Proof of Lemma 4.3] The step from the induction hypothesis to 'the F[V\Vi] are either all empty or all complete' needs an explicit justification: for t≥3, any k-subset contained in (V\Vi)∩(V\Vj) has the same edge status in both induced subhypergraphs, so all these subhypergraphs coincide.
  2. [Proof of Proposition 2.4] When ℓ=k, the descent from W^k(f)=0 to W^{k-1}(h1) is unnecessary and would require k-1 ≥ ℓ, which is false; the base case stops at h1. Please clarify the induction or state the case ℓ=k separately.
  3. [Statement of Lemma 2.13] The factor '4r' should be '4^r' (the proof uses 4^r).
  4. [Proof of Proposition 3.2] The bound X ≤ m^2 C(m,k-1) < 2^{-k+2} m^{k+1} is not strict for k=2 (and only just for k=3); use ≤ or adjust the constants.
  5. [Section 4.2] The phrase 'Proof Lemma 4.2.' should read 'Proof of Lemma 4.2.'

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the W-vector proof is self-contained, and the Appendix A prime-gap assertion is a proof gap rather than a circular step.

full rationale

The paper's central derivation is not circular. Definition 1.1 defines g(k) purely in terms of a binary linear system, independently of bs(k); Theorem 1.2 is then proved by translating W-vector vanishings into that system (Lemma 4.3 and Lemma 4.4), with g(k) entering only as a precomputed number-theoretic parameter. The lower bound uses external design theorems (Keevash; Glock-Kühn-Lo-Osthus), and the stability machinery rests on external results (Gottlieb, Filmus, Filmus-Mossel, Fox-Sudakov). No quantity is fitted to data and then renamed as a prediction, and no target result is assumed in its own proof. The self-citations to Kwan-Sudakov-Tran [20] (Tran is a co-author) are used as published lemmas with independent statements, e.g., Lemma 3.4, rather than as authorities defining the target quantities, so they do not make the argument circular. Flagged limitation, not circularity: Appendix A's proof of Theorem 1.3(ii) contains the assertion 'From Definition 1.1, there exists a prime p such that m−g ≤ p−1 ≤ m'. Definition 1.1 concerns a binary linear system and does not imply prime existence; the existence of such a prime would follow instead from the definition of G(k) or from the prime-gap bound for the intended choice g = G(k). As written, that appendix does not prove g(k) ≤ G(k), so Corollary 1.4(ii) is unsupported by the supplied proof. This is a correctness gap in a peripheral number-theoretic lemma, not an instance of a conclusion reducing to its inputs.

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

The central claim rests on standard external theorems in design theory, discrepancy, Fourier analysis, and number theory. The only non-standard, unproved input is the prime-existence implication in Appendix A, which is flagged as a red flag. No free parameters are fitted to data.

assumptions (10)
  • domain assumption Existence of (n,k,k−1,λ)-block designs for all sufficiently large n and suitable λ (Glock-Kühn-Lo-Osthus [16, Theorem 1.1 and Corollary 4.14])
    Used in Proposition 4.1 to build hypergraph G with disc(G,H)=0, proving bs(k)≥3.
  • domain assumption Bollobás-Scott [4, Theorem 3] lower bound on relative discrepancy in terms of W-vectors
    Basis of Lemma 2.3, connecting W-vectors to disc(G,H).
  • domain assumption Fox-Sudakov unavoidable patterns theorem [14, Theorem 4.2]
    Used to find non-homogeneous patterns in Proposition 3.2.
  • domain assumption Kwan-Sudakov-Tran [20, Lemma A.3] two-colouring lemma
    Used in Proposition 3.2 to find many intersecting edge/non-edge pairs.
  • standard math Gottlieb's rank theorem for inclusion matrices
    Ensures uniqueness of h in Proposition 2.4.
  • standard math Filmus orthogonal basis of harmonic multilinear polynomials on slices [12]
    Used in the stability proof, Proposition 2.6.
  • standard math Filmus-Mossel extension theorem: functions on the slice extend to harmonic multilinear polynomials of degree at most k [13, Thm 3.6]
    Used at the start of the proof of Proposition 2.6.
  • domain assumption von zur Gathen-Roche values of g(k): g(2)=0, g(k)=1 for 3≤k≤13, g(k)≤3 for 14≤k≤128
    Supplies the numerical g(k) values used in Corollary 1.4(i).
  • domain assumption Baker-Harman-Pintz bound G(k)=O(k^{0.525}) on maximal prime gaps
    Combined with g(k)≤G(k) to yield bs(k)=O(k^{0.525}).
  • ad hoc to paper Prime-existence implication: if the binary system in Definition 1.1 has only two solutions for m,g, then the interval [m−g,m] contains p−1 for a prime p
    Asserted without proof in Appendix A; needed to prove g(k)≤G(k).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Relative discrepancy of hypergraphs." pith.science (2026). https://pith.science/paper/DV7ORHV6

@misc{pith2026250623264,
  author       = {Pith},
  title        = {Pith review of: Relative discrepancy of hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DV7ORHV6}},
  note         = {Machine review of arXiv:2506.23264}
}
abstract

Given $k$-uniform hypergraphs $G$ and $H$ on $n$ vertices with densities $p$ and $q$, their relative discrepancy is defined as $\hbox{disc}(G,H)=\max\big||E(G')\cap E(H')|-pq\binom{n}{k}\big|$, where the maximum ranges over all pairs $G',H'$ with $G'\cong G$, $H'\cong H$, and $V(G')=V(H')$. Let $\hbox{bs}(k)$ denote the smallest integer $m \ge 2$ such that any collection of $m$ $k$-uniform hypergraphs on $n$ vertices with moderate densities contains a pair $G,H$ for which $\hbox{disc}(G,H) = \Omega(n^{(k+1)/2})$. In this paper, we answer several questions raised by Bollob\'as and Scott, providing both upper and lower bounds for $\hbox{bs}(k)$. Consequently, we determine the exact value of $\hbox{bs}(k)$ for $2\le k\le 13$, and show $\hbox{bs}(k)=O(k^{0.525})$, substantially improving the previous bound $\hbox{bs}(k)\le k+1$ due to Bollob\'as-Scott. The case $k=2$ recovers a result of Bollob\'as-Scott, which generalises classical theorems of Erd\H{o}s-Spencer, and Erd\H{o}s-Goldberg-Pach-Spencer. The case $k=3$ also follows from the results of Bollob\'as-Scott and Kwan-Sudakov-Tran. Our proof combines linear algebra, Fourier analysis, and extremal hypergraph theory.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 22 canonical work pages

  1. [25]

    von zur Gathen and J

    J. von zur Gathen and J. R. Roche. Polynomials with two values.Combinatorica, 17(3):345–362, 1997. Appendix A. A number-theoretic result Proof of part (ii) of Theorem 1.3.Let g = g(k). Fix m ∈ [2, k], and consider the following system of linear equations X 0≤i≤r (−1)i r i αi = 0 for all r = m − g, . . . , m, where ⃗ α= (α0, . . . , αm) ∈ {0, 1}m+1. From D...

    work page 1997

  2. [1]

    R. C. Baker, G. Harman, and J. Pintz. The difference between consecutive primes. II.Proceedings of the London Mathe- matical Society, 83(3):532–562, 2001

    work page 2001

  3. [2]

    Discrepancy in graphs and hypergraphs

    Béla Bollobás and Alex Scott. Discrepancy in graphs and hypergraphs. In Ervin Győri, Gyula O.H. Katona, László Lovász, and Tamás Fleiner, editors,More Sets, Graphs and Numbers , volume 15 ofBolyai Society Mathematical Studies , pages 33–56. Springer, 2006

    work page 2006

  4. [3]

    Intersections of graphs.Journal of Graph Theory , 66(4):261–282, 2011

    Béla Bollobás and Alex Scott. Intersections of graphs.Journal of Graph Theory , 66(4):261–282, 2011

    work page 2011

  5. [4]

    Intersections of hypergraphs.Journal of Combinatorial Theory, Series B , 110:180–208, 2015

    Béla Bollobás and Alex Scott. Intersections of hypergraphs.Journal of Combinatorial Theory, Series B , 110:180–208, 2015

    work page 2015

  6. [5]

    Intersections of random hypergraphs and tournaments.European Journal of Combinatorics, 44:125–139, 2015

    Béla Bollobás and Alex Scott. Intersections of random hypergraphs and tournaments.European Journal of Combinatorics, 44:125–139, 2015. 11

    work page 2015

  7. [6]

    The Discrepancy Method: Randomness and Complexity

    Bernard Chazelle. The Discrepancy Method: Randomness and Complexity . Cambridge University Press, Cambridge, UK, 2000

    work page 2000

  8. [7]

    H. Cramér. On the order of magnitude of the difference between consecutive prime numbers.Acta Arithmetica, 2:23–46, 1936

    work page 1936

Show all 25 references
  1. [8]

    Charles F. Dunkl. A Krawtchouk polynomial addition theorem and wreath products of symmetric groups.Indiana Univ. Math. J., 25:335–358, 1976

    1976

  2. [9]

    Empirical verification of the even Goldbach conjecture and computation of prime gaps up to4 × 1018

    Tomás Oliveira e Silva, Siegfried Herzog, and Silvio Pardi. Empirical verification of the even Goldbach conjecture and computation of prime gaps up to4 × 1018. Mathematics of Computation , 83(288):2033–2060, 2014

    2014

  3. [10]

    Erdős and J

    P. Erdős and J. Spencer. Imbalances ink-colorations. Networks, 1(4):379–385, 1971

    1971

  4. [11]

    Cutting a Graph into Two Dissimilar Halves.Journal of Graph Theory, 12(1):121–131, 1988

    Paul Erdős, Mark Goldberg, János Pach, and Joel Spencer. Cutting a Graph into Two Dissimilar Halves.Journal of Graph Theory, 12(1):121–131, 1988

    1988

  5. [12]

    An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube.Electronic Journal of Combina- torics, 23(1):P1.23, 2016

    Yuval Filmus. An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube.Electronic Journal of Combina- torics, 23(1):P1.23, 2016

    2016

  6. [13]

    Harmonicity and Invariance on Slices of the Boolean Cube.Probability Theory and Related Fields, 175(3-4):721–782, 2019

    Yuval Filmus and Elchanan Mossel. Harmonicity and Invariance on Slices of the Boolean Cube.Probability Theory and Related Fields, 175(3-4):721–782, 2019

    2019

  7. [14]

    Unavoidable patterns.Journal of Combinatorial Theory, Series A , 115(8):1561–1569, 2008

    Jacob Fox and Benny Sudakov. Unavoidable patterns.Journal of Combinatorial Theory, Series A , 115(8):1561–1569, 2008

    2008

  8. [15]

    Péter Frankl and Ron L. Graham. Old and new proofs of the Erdős-Ko-Rado theorem.Journal of Sichuan University, Natural Science Edition , 26:112–122, 1989

    1989

  9. [16]

    Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus.The Existence of Designs via Iterative Absorption: Hypergraph F -Designs for Arbitrary F, volume284of Memoirs of the American Mathematical Society.AmericanMathematicalSociety, 2023

    2023

  10. [17]

    D. H. Gottlieb. A certain class of incidence matrices.Proceedings of the American Mathematical Society , 17(6):1233–1237, 1966

    1966

  11. [18]

    The edge-statistics conjecture for hypergraphs.arXiv preprint arXiv:2505.03954, 2025

    Vishesh Jain, Matthew Kwan, Dhruv Mubayi, and Tuan Tran. The edge-statistics conjecture for hypergraphs.arXiv preprint arXiv:2505.03954, 2025

    2025 arXiv

  12. [19]

    The existence of designs.arXiv preprint arXiv:1401.3665 , 2014

    Peter Keevash. The existence of designs.arXiv preprint arXiv:1401.3665 , 2014

    2014 arXiv

  13. [20]

    Anticoncentration for subgraph statistics.Journal of the London Math- ematical Society, 99(3):757–777, 2019

    Matthew Kwan, Benny Sudakov, and Tuan Tran. Anticoncentration for subgraph statistics.Journal of the London Math- ematical Society, 99(3):757–777, 2019

    2019

  14. [21]

    Discrepancy of random graphs and hypergraphs.Random Structures & Algorithms, 45(2):253–271, 2014

    Jie Ma, Humberto Naves, and Benny Sudakov. Discrepancy of random graphs and hypergraphs.Random Structures & Algorithms, 45(2):253–271, 2014

    2014

  15. [22]

    Positive discrepancy, MaxCut, and eigenvalues of graphs.arXiv preprint arXiv:2311.02070, 2023

    Eero Räty, Benny Sudakov, and István Tomon. Positive discrepancy, MaxCut, and eigenvalues of graphs.arXiv preprint arXiv:2311.02070, 2023

    2023 arXiv

  16. [23]

    Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs

    Eero Räty and István Tomon. Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs. arXiv preprint arXiv:2409.15140, 2024

    2024 arXiv

  17. [24]

    Srinivasan

    Murali K. Srinivasan. Symmetric chains, Gelfand–Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme. Journal of Algebraic Combinatorics , 34(2):301–322, 2011

    2011

Pith tools

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