Uniformly at Random

Posts Tagged ‘graph theory

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

with 2 comments

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}.


\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

leave a comment »

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

leave a comment »

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, dregular 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 ,