7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$? $\endgroup$ – Andrew Uzzell Dec 7 '15 at 21:17
  • $\begingroup$ no..I mean non-empty $k$-core, I mean the graph has at least one non-empty $k$-core with any arbitrary vertices. $\endgroup$ – user3070752 Dec 8 '15 at 6:16
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – user36212 Dec 20 '16 at 16:09
  • $\begingroup$ You're quite right, of course. Thank you: I'll make an appropriate edit. $\endgroup$ – Ben Barber Dec 20 '16 at 16:25
2
$\begingroup$

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.

$\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.