Induced-Count Discrepancy in Uniform Hypergraphs

Abstract

Let $u_k^{(r)}(H,p)$ be the maximum, over all $k$-vertex $r$-uniform hypergraphs $F$, of the absolute difference between the number of induced copies of $F$ in $H$ and its expectation in the binomial random $r$-graph with the same number of vertices as $H$ and edge probability $p$. Let $u_k^{(r)}(n,p)$ be the minimum of $u_k^{(r)}(H,p)$ over all $n$-vertex $r$-uniform hypergraphs, and let $D_r(n,p)$ be the distance from $p\binom nr$ to the nearest integer. For fixed $r\ge3$, $k\ge2r$ and $\varepsilon>0$, the quantity $u_k^{(r)}(n,p)$ has order $\max\!\left\{D_r(n,p),p(1-p)\right\}n^{k-r}$ whenever $p(1-p)n^{\lfloor r/2\rfloor/(\binom{2r-2}{r}-1)}\ge\varepsilon$. Using local moment estimates and switchings in a sparse reservoir, we construct one hypergraph with the nearest-integer edge count that controls all induced orders simultaneously.