{"id":"arxiv/2611.20539","url":"https://arxiv.org/abs/2611.20539","tags":["math.CO"],"score":0,"title":"Graph Intersections and Hypergraph Discrepancy","domain":"math.CO","source":"arxiv","authors":["Zhanping Yang"],"reviews":0,"subject":"math.CO","summary":"Let $G$ and $H$ be graphs on $n$ vertices with $e(G)=p\\binom{n}{2}$ and $e(H)=q\\binom{n}{2}$, where $p,q\\in(0,1)$ are fixed. Bollobás and Scott studied intersections of two graphs under random relabelling and asked for the minimum $L^2$ norm of the deviation of their intersection size from its expected value. We answer this question by proving that, for graphs of order $n$ with fixed edge densities $p,q\\in(0,1)$, the minimum is \\begin{equation*} \\left(\\sqrt{\\frac{p(1-p)q(1-q)}{2}\\cdot\\frac{1-\\sqrt R}{1+\\sqrt R}}\\right)n+o(n), \\end{equation*} where $R=\\max\\{p,1-p,q,1-q\\}$. The coefficient of…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-16","reactions":{}}