# In a random graph which one is more probable, $k$-clique or $k$-core?

Recall that the $k$-core of a graph $G$ is the unique maximal subgraph of $G$ with minimum degree at least $k$.

In an Erdos-Renyi random graph, where the edge selection is independent with probability is $p$, we have the following inequalities: $$P(\text{G contains at least one k-clique}) \leq \dbinom{n}{k} p^\dbinom{k}{2}$$ and $$P(\text{G has a nonempty k-core}) \leq \dbinom{n}{m} \prod_{i=1}^m \sqrt Q,$$ where $$Q = \sum_{i=k}^{m-1} \dbinom{m-1}{i} p^i (1-p)^{m-1-i}$$ and $m$ is the size of the $k$-core.

I can't understand how I should compare these two probabilities to conclude which one is more probable.

• Are you asking for a non-empty $k$-core, or for a $k$-core with at least $m$ vertices? If the latter, what is $m$? Does it depend on $n$? Dec 7, 2015 at 21:17
• no..I mean non-empty $k$-core, I mean the graph has at least one non-empty $k$-core with any arbitrary vertices. Dec 8, 2015 at 6:16

Every graph of average degree $2k$ contains a subgraph of minimum degree $k$, so the threshold for the appearance of a non-empty $k$-core is at most $2k/n$. Since the threshold for the appearance of a $k$-clique is $n^{-2/(k-1)}$, $k$-cores typically appear before $k$-cliques.
The exact threshold for the appearance of a non-empty $k$-core was found by Pittel, Spencer and Wormald.
• The content of Pittel-Spencer-Wormald is to find the $c_k$, not to show that $p=cn$ for some $c$ guarantees a non-empty $k$-core. That's trivial - as soon as you have $kn$ edges, you have average degree $2k$ and hence there is a subgraph with minimum degree $k$, which is contained in the $k$-core; the only probabilistic part here is to say it's likely there are $kn$ edges. Also, nitpicking, the $3$-clique shows up with probability bounded away from zero before the $3$-core for any $k\ge 3$ (but if you want high probability, that comes after all $k$-cores). Dec 20, 2016 at 16:09
Every $k$-clique is a $k-1$-core. Thus, for events $A_k = \{\text{graph contains a$k$-clique}\}$ and $B_k = \{\text{graph contains a$k$-core}\}$ we have the relation $A_k \subset B_{k-1}$, and $P(A_k) \leq P(B_{k-1})$.
Probably, if you have $k$-clique and $k$-core, probabilities might be incomparable, e.g. what if $k=|V|$ where $G=(V,E)$ is complete graph, then probability of having a clique is not 0 (apparently 1) when $p=1$ while probability having a $k$-core is always 0. On the other hand, $k$-core should be more probable intuitively in not extreme cases.