2
$\begingroup$

Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ that are pairwise non-adjacent. So Caro-Wei says that $\alpha(G) \geq \sum_{d_i \in V(G)}{\frac{1}{1+d_i}}$. The standard probabilistic proof goes as follow, here we let $V(G)=\{1,2,...,n\}$:

Consider the set $S_n$ of permutations of the vertices in $G$ and $\sigma \in S_n$ be a permutation in $S_n$. Let $A_i$ be the event that $\sigma(i)<\sigma(j), \forall j \in N(i)$ namely all neighbours $j$ of the vertex $i$ gets maps to by $\sigma$ to some number greater than $\sigma(i)$. There are $\binom{n}{1+d_i}$ places that $\sigma$ can map the vertex $i$ and its neighbors to. Futhermore, $\sigma(i)$ is the smallest, so there are $d_i!$ ways for the neighbours of $i$ to be map to and $(n-d_i-1)!$ ways for the remaining number to be permuted. So $P(A_i)=\frac{\binom{n}{d_i+1} d_i!(n-d_i-1)!}{n!}=\frac{1}{1+d_i}$. Now consider the subset of the vertex set of $G$, $U=\{i \mid A_i = \text{true}\}$. Notice that two vertices in $U$ does not share an edge. The expected value $E[|U|]=\sum_{i\in \{1,...,n\}}{\frac{1}{1+d_i}}$. So done.

But I'm wondering if there is a proof not involving probabilistic method.

$\endgroup$

3 Answers 3

2
$\begingroup$

An algorithmic proof is given by Murphy [1, Section 1], where he attributes the algorithm to Erdös [2].

As a side remark, I don't know what the original proof of Caro or Wei is, but I believe the proof you mention is due to Alon and Spencer [3].


[1] Murphy, Owen. "Lower bounds on the stability number of graphs computed in terms of degrees." Discrete Mathematics 90.2 (1991): 207-211.

[2] Erdös, Paul. "On the graph theorem of Turán." Mat. Lapok 21. (1970): 249-251.

[3] Alon, Noga, and Joel H. Spencer. The Probabilistic Method. John Wiley & Sons, 2004.

$\endgroup$
2
  • $\begingroup$ Sorry also in the turan's theorem , they mentioned $K_{r-1}$free graph.What is a $k_n$free graph ? $\endgroup$
    – user614287
    Commented Nov 28, 2018 at 17:01
  • 1
    $\begingroup$ @mathnoob An $H$-free graph means that it doesn't have a subgraph isomorphic to $H$. $\endgroup$
    – Juho
    Commented Nov 28, 2018 at 17:03
1
$\begingroup$

There are several non-probabilisitc proofs : 1/ using greedy algorithm deleting minimum degree : See : https://www.sciencedirect.com/science/article/pii/S0166218X13001339 https://onlinelibrary.wiley.com/doi/10.1002/jgt.3190150110

2/ deleting vertices of maximum degree : see :https://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p33

There are everal more variations.

My original 1999 proof was via induction and deleting vertex of maximum degree.

$\endgroup$
1
$\begingroup$

Induction on the order of G . True for |G| = 1. Assume for |G| = n let prove it for |G| = n +1. Choose a vertex v of minimum degree . Consider H = G - N[v]. Clearly a(G)> = 1 + a(H) > = 1 + sum { 1/( deg_H(u) +1) :u in V(H)} > = ** sum { 1/(deg_G(w)) +1 ) :w in N[{v] } + sum { 1/( deg_H(u) +1) : u in V(H)} = sum { 1/(deg_G(w)) +1 ) : w in N[{v] } + sum { 1/( deg_G(u) +1 : u in V(G)\N[v]}= sum { 1/(deg(w)+1 ) w in V(G) }. deg_G(w) the degree of w in G , deg_H(u) the degree of u in H. ** observe 1=sum {1/(deg(v)+1 ):w in N[v] } > = sum{ 1/(deg_G(w) +1) : w in N[v] } as v has minimum degree . Best - Yair Caro .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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