Relative discrepancy of hypergraphs

Abstract

Given $k$-uniform hypergraphs $G$ and $H$ on $n$ vertices with densities $p$ and $q$, their relative discrepancy is defined as $disc(G,H)=\max ||E(G^{\prime })\cap E(H^{\prime })|-pq(\genfrac{}{}{0ex}{}{n}{k}\left)\right|$, where the maximum ranges over all pairs $G^{\prime },H^{\prime }$ with $G^{\prime }\cong G$, $H^{\prime }\cong H$, and $V(G^{\prime })=V(H^{\prime })$. Let $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 $disc(G,H)=\hat{I}\text{c◯}(n^{(k+1)/2})$. In this paper, we answer several questions raised by Bollobás and Scott, providing both upper and lower bounds for $bs(k)$. Consequently, we determine the exact value of $bs(k)$ for $2\le k\le 13$, and show $bs(k)=O(k^{0.525})$, substantially improving the previous bound $bs(k)\le 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.