equivalence of random hypergraph models

49 Views Asked by At

On Wikipedia it says that for any monotone graph property $P$, the two statements

"$G(n,p)$ has property $P$ with high probability" and "$G(n, p\binom{n}{2})$ has Property $P$ with high probability" are equivalent. (Where we let $n$ go to infinity and $p=p(n)$ satisfy $pn^2 \to \infty$, I suppose). Is there any analogous statement for uniform hypergraphs?

Thanks in advance.

[Edit: uniform, not regular. My bad]

1

There are 1 best solutions below

0
On BEST ANSWER

Wikipedia is wrong about the two-way equivalence, even for graphs. Consider, for example, the monotone property $P$: "$G$ has at least $\lfloor \frac12 \binom n2\rfloor$ edges". Then $G(n,\frac12)$ will have property $P$ with probability tending to $\frac12$, but $G(n, \frac12\binom n2)$ will have property $P$ with high probability (actually, with probability exactly $1$).

So the strong statement about equivalence can only go one way. However, for that statement, the proof for graphs generalizes to uniform hypergraphs without any additional work.

For example, from the argument here it immediately follows for random $r$-uniform hypergraphs, if $m = \binom nr p$ satisfies $1 < m < \binom nr - 1$ and $P$ is a monotone property, then $$ \frac14 \Pr[G(n,m) \text{ has }P] \le \Pr[G(n,p) \text{ has }P] \le \frac34 + \frac14 \Pr[G(n,m) \text{ has }P]. $$ Therefore if $G(n,p)$ has $P$ with high probability, then $G(n,m)$ also has $P$ with high probability.

Going the other way, the inequality only tells us that if $G(n,m)$ has $P$ with high probability, then $G(n,p)$ has $P$ with probability at least $\frac14$. This is not the equivalence you'd hope for, but as my example above shows, this is the only equivalence we deserve.

However, monotone graph properties are known to have thresholds, and this extends for hypergraphs. In particular, suppose $G(n,p)$ has $P$ with probability at least $\frac14$. Then the union of $k$ (hyper)graphs sampled from $G(n,p)$ has the $G(n, 1 - (1-p)^k)$ distribution, and by monotonicity it has $P$ with probability at least $1 - (\frac34)^k$. Again by monotonicity, $G(n,pk)$ also has $P$ with probability at least $1 - (\frac34)^k$, because $1 - (1-p)^k \le pk$. We can conclude that if $G(n,p)$ does not yet have $P$ with high probability, then $p$ is an edge probability threshold for $P$.

Therefore it is true that the statements "$p$ is an edge probability threshold for $P$" and "$p\binom nr$ is an edge count threshold for $P$" are equivalent, provided that $1 < p \binom nr < \binom nr - 1$.