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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-16 Page: https://delphi.science/r/arxiv/2611.20539 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…