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

Improve this question
$\endgroup$
2
  • 2
    $\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
    Commented Dec 7, 2015 at 21:17
  • 1
    $\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
    Commented Dec 8, 2015 at 6:16

2 Answers 2

Reset to default
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.

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .