## Posts Tagged ‘**graph theory**’

## 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 -regular if every vertex has degree .

**Theorem**. Let be a -regular graph with adjacency matrix . Let be the eigenvalues of . Let be an independent set in . Then

.

*Proof*. Let us suppose that . Let be the inner product on defined by , where the denotes the usual dot product. Let be the corresponding norm on .

The adjacency matrix is a real symmetric matrix, so we may suppose that the eigenvectors (corresponding to the eigenvalues ) form an orthonormal basis of with respect to the inner product . Note that since is -regular, is the vector with all entries equal to . Let be the characteristic vector of the independent set and define .

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

.

Since the ‘s form an orthonormal set, we have . By Parseval’s identity we also have

.

We therefore have

.

Thus,

,

whence we obtain

,

as required.

## 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 , a -diregular directed graph has an directed even cycle.

** Theorem** [Lovasz Local Lemma (symmetric version)] Let be a dependency graph for events . Suppose that the maximum degree of is and that there is a real number for which for all . If , then .

In the statement above, the vertices of consist of and is mutually independent of all the ‘s for which there is no edge in .

**Theorem** [Alon and Linial] Let and let be a directed graph where every vertex has indegree and outdegree . Then has a directed even cycle.

*Proof*. Consider a random 2-colouring of the vertices of . For each vertex of , let denote the event that and all of its outneighbours have the same colour. Then . Moreover, is independent of all for which neither nor any outneighbour of is an outneighbour of . However, each of the outneighbours of has indegree , so we may apply the local lemma with . For , we have , so with positive probability, every vertex of has an outneighbour of the opposite colour.

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

## Some assorted graph-theoretic results

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

**Lemma**. Let denote the minimum degree of . A connected graph with vertices has a path of length .

*Proof*. Let be a longest path in . If is Hamiltonian we are done, so suppose is not Hamiltonian. We first observe that all the neighbours of and are on the path , since otherwise would not be a longest path.

We now claim that if is adjacent to , then is not adjacent to . Suppose to the contrary that is adjacent to . Recall that is not Hamiltonian, so there exists a vertex not on but connected to , say at some vertex . Using , we can find a longer path in (draw a picture to see this), contradicting the maximality of .

For call a *predecessor* of . We see that and all of its neighbours are on . This contributes at least vertices to . Further, and the predecessors of all the neighbours of are all on . This contributes an additional vertices to . Thus has at least vertices and hence has length at least .

**Theorem** (Erdos-Gallai). A graph with vertices and more than edges has a path of length .

*Proof*. Suppose . Suppose there exists with degree . Then has more than edges and the result holds inductively. Suppose then that the minimum degree of is more than ; i.e., . By the previous lemma, has a path of length .

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

**Theorem** (Erdos-Sachs). For and there exists a -regular graph with girth .

*Proof*. Let denote a -regular graph of girth . Suppose we have and , where . We will

construct .

For each vertex in , split into new vertices and identify these with the vertices of a copy of of to obtain . The graph is -regular; we will show it has girth . The graph has girth , so has girth at most .

Let be a cycle of length in ( not entirely in a copy of ). The cycle must include an edge from a copy of . Now contract to recover . The cycle has now been contracted to a new cycle of length at most in . However, has girth , so . Thus, , so has girth .

This completes the inductive step. For the base step, note that and exist trivially for all .