2025/06/29 by Diep Luong-Le, Tuan Tran, Luong-Le, Diep +2
Mathematics · #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2506.23264
openalex publication_date 2025/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given k-uniform hypergraphs G and H on n vertices with densities p and q, their relative discrepancy is defined as \hboxdisc(G,H)=max||E(G')∩ E(H')|-pq\binomnk|, where the maximum ranges over all pairs G',H' with G'≅ G, H'≅ H, and V(G')=V(H'). Let \hboxbs(k) denote the smallest integer m ≥ 2 such that any collection of m k-uniform hypergraphs on n vertices with moderate densities contains a pair G,H for which \hboxdisc(G,H) = Ω(n(k+1)/2). In this paper, we answer several questions raised by Bollobás and Scott, providing both upper and lower bounds for \hboxbs(k). Consequently, we determine the exact value of \hboxbs(k) for 2≤ k≤ 13, and show \hboxbs(k)=O(k0.525), substantially improving the previous bound \hboxbs(k)≤ k+1 due to Bollobás-Scott. The case k=2 recovers a result of Bollobás-Scott, which generalises classical theorems of Erdős-Spencer, and Erdős-Goldberg-Pach-Spencer. The case k=3 also follows from the results of Bollobás-Scott and Kwan-Sudakov-Tran. Our proof combines linear algebra, Fourier analysis, and extremal hypergraph theory.