ProV Logo
0
How unproportional must a graph be?
Naves, Humberto...

Free

How unproportional must a graph be? by Naves, Humberto ( Author )
Lemonjar Open Access
Australian National University
01-09-2023
Let $u_k(G,p)$ be the maximum over all $k$-vertex graphs $F$ of by how much the number of induced copies of $F$ in $G$ differs from its expectation in the binomial random graph with the same number of vertices as $G$ and with edge probability $p$. This may be viewed as a measure of how close $G$ is to being $p$-quasirandom. For a positive integer $n$ and $0<p<1$, let $D(n,p)$ be the distance from $p\binom{n}{2}$ to the nearest integer. Our main result is that, for fixed $k\ge 4$ and for $n$ large, the minimum of $u_k(G,p)$ over $n$-vertex graphs has order of magnitude $\Theta\big(\max\{D(n,p), p(1-p)\} n^{k-2}\big)$ provided that $p(1-p)n^{1/2} \to \infty$.
-
Article
pdf
29.34 KB
English
-
MYR 0.01
-
http://arxiv.org/abs/1404.1206
Share this eBook