Uniformly at Random

Hoffman’s eigenvalue bound on the size of an independent set

We present here Hoffman’s eigenvalue bound on the size of an independent set in a regular graph. We follow the presentation of Ellis, Friedgut, and Pilpel. Recall that a graph is $d$-regular if every vertex has degree $d$.

Theorem. Let $G = (V,E)$ be a $d$-regular graph with adjacency matrix $A$. Let $d = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n = \lambda_{\min}$ be the eigenvalues of $A$. Let $I$ be an independent set in $G$. Then

$|I|/|V| \leq -\lambda_{\min}/(\lambda_1 - \lambda_{\min})$.

Proof. Let us suppose that $V = \{1,2,\ldots,n\}$. Let $\langle\cdot,\cdot\rangle$ be the inner product on $\mathbb{R}^n$ defined by $\langle x,y \rangle = (1/n)(x \cdot y)$, where the $\cdot$ denotes the usual dot product. Let $\|x\| = \sqrt{\langle x,x \rangle}$ be the corresponding norm on $\mathbb{R}^n$.

The adjacency matrix $A$ is a real symmetric matrix, so we may suppose that the eigenvectors $v_1,v_2,\ldots,v_n$ (corresponding to the eigenvalues $\lambda_1,\lambda_2,\ldots,\lambda_n$) form an orthonormal basis of $\mathbb{R}^n$ with respect to the inner product $\langle\cdot,\cdot\rangle$. Note that since $G$ is $d$-regular, $v_1$ is the vector with all entries equal to $1$. Let $u$ be the characteristic vector of the independent set $I$ and define $\alpha = |I|/|V|$.

Observe that $u^TAu$ counts the number of edges among the vertices of $I$. Since $I$ is an independent set, we have $u^TAu = 0$. We write $u$ as a linear combination of the eigenvectors; i.e.,

$u = a_1v_1 + a_2v_2 + \cdots + a_nv_n$.

Since the $v_i$‘s form an orthonormal set, we have $\alpha = \langle u,v_1 \rangle = a_1$. By Parseval’s identity we also have

$a_1^2 + a_2^2 + \cdots + a_n^2 = \|u\|^2 = \langle u,u \rangle = \alpha$.

We therefore have

$0 = u^TAu = \sum_{i=1}^n a_i^2 \lambda_i \geq a_1^2\lambda_1 + \sum_{i=2}^n a_i^2\lambda_{\min} = \alpha^2\lambda_1 + (\alpha - \alpha^2)\lambda_{\min}$.

Thus,

$\alpha\lambda_1 + (1 - \alpha) \lambda_{\min} \leq 0$,

whence we obtain

$\alpha = |I|/|V| \leq -\lambda_{\min}/(\lambda_1 - \lambda_{\min})$,

as required.

Written by uncudh

March 21, 2009 at 5:02 pm

Posted in math

Tagged with ,

Even cycles in directed graphs

Here is a nice application of the Lovasz Local Lemma, due to Alon and Linial, whereby it is proved that for sufficiently large $k$, a $k$-diregular directed graph has an directed even cycle.

Theorem [Lovasz Local Lemma (symmetric version)] Let $G = (V,E)$ be a dependency graph for events $A_1,\ldots,A_n$. Suppose that the maximum degree of $G$ is $d$ and that there is a real number $p$ for which $\Pr[A_i] \leq p$ for all $i=1,\ldots,n$. If $4pd \leq 1$, then $\Pr[\cap\overline{A_i}] > 0$.

In the statement above, the vertices of $G$ consist of $V = {1,\ldots,n}$ and $A_i$ is mutually independent of all the $A_j$‘s for which there is no edge ${i,j}$ in $E$.

Theorem [Alon and Linial] Let $k \geq 8$ and let $G$ be a directed graph where every vertex has indegree and outdegree $k$. Then $G$ has a directed even cycle.

Proof. Consider a random 2-colouring of the vertices of $G$. For each vertex $v$ of $G$, let $A_v$ denote the event that $v$ and all of its outneighbours have the same colour. Then $p = \Pr[A_v] = 2^{-k}$. Moreover, $A_v$ is independent of all $A_u$ for which neither $u$ nor any outneighbour of $u$ is an outneighbour of $v$. However, each of the $k$ outneighbours of $v$ has indegree $k$, so we may apply the local lemma with $d = k^2$. For $k \geq 8$, we have $4\cdot 2^{-k}k^2 \leq 1$, so with positive probability, every vertex of $G$ has an outneighbour of the opposite colour.

Now let $P$ be a maximal properly 2-coloured directed path in $G$, ending at a vertex $v$. Let $w$ be any outneighbour of $v$ coloured differently from $v$. By the maximality of $P$, $w$ must lie on $P$ itself. Thus the cycle obtained by starting at $w$, following $P$ to $v$, and then returning to $w$ via the edge $(v,w)$, is a properly 2-coloured cycle, and hence, even. This completes the proof.

Written by uncudh

January 7, 2009 at 5:57 pm

Posted in math

Tagged with ,

Some assorted graph-theoretic results

Here are a few assorted results concerning paths and cycles in graphs.

Lemma.  Let $\delta(G)$ denote the minimum degree of $G$.  A connected graph $G$ with $n \geq 3$ vertices has a path of length $\min\{2\delta(G),|G|-1\}$.

Proof.  Let $P = (v_0,v_1,\ldots,v_m)$ be a longest path in $G$.  If $P$ is Hamiltonian we are done, so suppose $P$ is not Hamiltonian. We first observe that all the neighbours of $v_0$ and $v_m$ are on the path $P$, since otherwise $P$ would not be a longest path.

We now claim that if $v_i$ is adjacent to $v_0$, then $v_{i-1}$ is not adjacent to $v_m$.  Suppose to the contrary that $v_{i-1}$ is adjacent to $v_m$.  Recall that $P$ is not Hamiltonian, so there exists a vertex $u$ not on $P$ but connected to $P$, say at some vertex $v_j$.  Using $u$, we can find a longer path in $G$ (draw a picture to see this), contradicting the maximality of $P$.

For $i=1,\ldots,m$ call $v_{i-1}$ a predecessor of $v_i$. We see that $v_m$ and all of its neighbours are on $P$.  This contributes at least $\delta(G)+1$ vertices to $P$.  Further, $v_0$ and the predecessors of all the neighbours of $v_0$ are all on $P$. This contributes an additional $\delta(G)$ vertices to $P$.  Thus $P$ has at least $2\delta(G)+1$ vertices and hence has length at least $2\delta(G)$.

Theorem (Erdos-Gallai).  A graph $G$ with $n$ vertices and more than $(k-1)n/2$ edges has a path of length $k$.

Proof.  Suppose $n>k$.  Suppose there exists $v$ with degree $\leq (k-1)/2$. Then $G \setminus \{v\}$ has more than $(k-1)(n-1)/2$ edges and the result holds inductively.  Suppose then that the minimum degree of $G$ is more than $(k-1)/2$; i.e., $\delta(G) \geq k/2$.  By the previous lemma, $G$ has a path of length $k$.

In the following result, $d$regular means that every vertex has degree $d$, and the girth is the length of the shortest cycle in the graph.

Theorem (Erdos-Sachs).  For $d \geq 2$ and $g \geq 2$ there exists a $d$-regular graph with girth $g$.

Proof.  Let $G(d,g)$ denote a $d$-regular graph of girth $g$.  Suppose we have $G_1 = G(d,g)$ and $G_2 = G(d',g-1)$, where $d'=|V(G_1)|$.  We will
construct $G' = G(d+1,g)$.

For each vertex $v$ in $G_2$, split $v$ into $d'$ new vertices and identify these with the vertices of a copy of of $G_1$ to obtain $G'$. The graph $G'$ is $(d+1)$-regular; we will show it has girth $g$. The graph $G_1$ has girth $g$, so $G'$ has girth at most $g$.

Let $C$ be a cycle of length $s$ in $G'$ ($C$ not entirely in a copy of $G_1$).  The cycle $C$ must include an edge from a copy of $G_1$.  Now contract $G'$ to recover $G_2$.  The cycle $C$ has now been contracted to a new cycle $C'$ of length at most $s-1$ in $G_2$.  However, $G_2$ has girth $g-1$, so $s-1 \leq g-1$.  Thus, $s \geq g$, so $G'$ has girth $G$.

This completes the inductive step.  For the base step, note that $G(2,g)$ and $G(d,2)$ exist trivially for all $d,g \geq 2$.

Written by uncudh

November 15, 2008 at 4:03 pm

Posted in math

Tagged with ,