Graph Intersections and Hypergraph Discrepancy
Source: arxiv.org/abs/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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.20539
curl -X POST /api/v1/records/arxiv/2611.20539/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.20539/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'