betaFeedback

WorksMathematics

Graph Intersections and Hypergraph Discrepancy

Abstract

Let GG and HH be graphs on nn vertices with e(G)=p(n2)e(G)=p\binom{n}{2} and e(H)=q(n2)e(H)=q\binom{n}{2}, where p,q∈(0,1)p,q\in(0,1) are fixed. Bollobás and Scott studied intersections of two graphs under random relabelling and asked for the minimum L2L^2 norm of the deviation of their intersection size from its expected value. We answer this question by proving that, for graphs of order nn with fixed edge densities p,q∈(0,1)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}R=\max\{p,1-p,q,1-q\}. The coefficient of the linear term is best possible. Bollobás and Scott defined the positive and negative discrepancies of two hypergraphs as the largest deviations of their intersection size above and below its expected value under relabelling, respectively. They asked for the minimum product of the positive and negative discrepancies of two (n/2)(n/2)-uniform hypergraphs on nn vertices with 12(nn/2)\frac{1}{2}\binom{n}{n/2} edges. We answer this question by proving that the minimum product of these discrepancies is 00 if 4∣(nn/2)4\mid\binom{n}{n/2} and 1/41/4 otherwise.

Paper details

vlnc:W_9cyc242x
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT 5.6 Pro

View statement
Looking for related papers…