2
$\begingroup$

In the Erdös-Rényi model for random graphs,the clique number is seen to go to infinity as the number of vertices grows. Is anyone aware of models for random graphs with bounded clique number?

$\endgroup$
4
$\begingroup$

The Erdös-Rényi model works. One just has to take the associated probability $p$ to scale with the size of the graph $n$. For instance, Theorem 4.13 in Random Graphs by Bollobás shows that for ER graph with $p=p(n)$ such that $np→∞$ with $np=o(n^\frac{1}{3})$ as $n→∞$, the clique number satisfies $\omega(G(n, p))= 3$ with high probability.

$\endgroup$
2
  • $\begingroup$ Slightly more generally, seems like Erdös-Rényi model works if one takes $p=o(n^{-\varepsilon})$ for some fixed $\varepsilon>0$, i.e., in this case, the clique number is bounded with high probability. $\endgroup$ Aug 18 '19 at 6:15
  • $\begingroup$ @DmitryKrachun Yes, this also follows from the result in Bollobás. The above is just an instance of that theorem. $\endgroup$ Aug 18 '19 at 6:21
0
$\begingroup$

Divide the vertex set into a fixed number of parts, in any way you like (such as randomly). Choose two probabilities $p_1,p_2$, where $p_1\le n^{-\varepsilon}$ for some fixed $\varepsilon\gt 0$ and $p_2$ is arbitrary. Now insert edges within the parts independently with probability $p_1$ and between the parts independently with probability $p_2$.

Consider cliques of size $k\ge 1+m+\frac{2m}\varepsilon$. If the number of parts is $m$, then every clique of size $k$ has at least $k/m$ vertices in some part. The probability of that part having a clique of size $k$ is at most its expectation $O(n^{k/m}p_1^{\binom{k/m}{2}})$, which goes to zero as $O(n^{-\eta})$ for some $\eta\gt0$. Multiplying by $m$ to bound the probability that any part has a clique of size $k/m$ makes no difference since $m$ is constant. So with probability $1-O(n^{-\eta})$ there are no cliques of size $k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.