Caro-Wei Theorem Proof

Question

I was reading a proof of the Caro-Wei Theorem using the probabilistic method when I came acroos something that I did not understand.

I learned characteristic functions such that $1_{s\in A}$ equals 1 if s is in A, and 0 otherwise. However, when the proof defines $X$, it says $1_{\sigma\in A_i}$, which does not make sense to me as $A_i$ was defined as an event. Is this a different type of usage of characteristic functions? Could anyone explain it to me?

Thank you!

Answer 1

The characteristic function you’re thinking of is $\mathbb{1}_S$, defined as $\mathbb{1}_S(x)=1$ when $x\in S$ and $\mathbb{1}_S(x)=0$ when $x\notin S$. In the proof you reproduced, don’t think of $1_{\sigma\in A_i}$ as a characteristic function; it’s just a number that depends on $i$. It’s the number $1$ if $\sigma\in A_i$, and it’s $0$ if $\sigma\notin A_i$. So $X(\sigma)$ (defined as $X(\sigma)=\sum_{i=1}^n 1_{\sigma\in A_i}$) is the number of values of $i$ between $1$ and $n$ for which $\sigma\in A_i$, or, using the definition of $A_i$ (and the unmentioned assumption that the vertex set of the graph is $\{1,\dots,n\}$), it’s the number of vertices $i$ in the graph $G$ for which $\sigma(i)<\sigma(j)$ for some vertex $j$ that is a neighbor of of $i$ in $G$.

Answer 2

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 .