Advanced Topics in Graph Theory

Department of Computer Science | Ariel University

1. König-Egerváry theorem

The cardinalities of a maximum matching and that of a minimum vertex-cover coincide for bipartite graphs; this is the so called König-Egerváry theorem. We provide a linear programming (LP) based proof where the main tool borrowed from LP is the so called Duality Theorem used to establish the duality of the (integer) linear programs associated with the problems of maximum matching and minimum vertex-cover. Understanding of the latter requires some prelimenary meditation regarding convex sets.

Students are kindly requested to reinforce their knowledge through this piece of material here.

2. The adjacency matrix of a graph

We consider the spectrum of the adjacency matrix of some classical families of graphs.

Students are kindly requested to review the material using this note.

3. Classical graph properties determined by the spectrum of the adjacency matrix

On its own the spectrum of the adjacency matrix does not determine a graph uniquely (it needs some help sort of speak). Nevertheless, the spectrum alone can determine certain graph invariants and even (rough) structure of all graphs with that spectrum. We review some classical properties determined by the spectrum alone.

In this exposition we do make use of the so called spectral decomposition theorem and the so called Rayleigh principle. Students who would like to be reminded as to the definition of the angle between a vector and a subspace can find support here

Students are kindly requested to reinforce their knowledge using this note.

4. The Perron-Frobenius Theorem

We have seen here that properties like degree regularity and bipartiteness of graphs admit stronger characterisations in terms of the spectrum of the graph once the graph is assumed to be connected. To establish those we in fact relied on the so called Perron-Frobenius thereom fragments of which we relied on without proof. In this note we prove parts of the Perron-Frobenius theorem.

Students are kindly requested to reinforce their knowledge using this note.

5. The expander mixing lemma

We start with a result of Alon providing a lower bound on the number of edges crossing a cut (i.e., a vertex bipartition) in a degree-regular graph. The main message of this resylt is that the smaller is the 2nd larget eigenvalue of the graph the more edges cross the cut.

We then consider a strong generalisation of this result commonly referred to as the expander mixing lemma proved by Alon and Chung. This latter result provides both lower and upper bounds on the number of edges crossing between any two (large enough) sets of vertices.

We conclude with a result by Tanner which can be viewed as a spectral variant of the famous Hall-condition.

A key tool used in this exposition is the Courant-Fischer theorem.

6. Expansion in bipartite graphs

We start with a probabilistic argument showing that bipartite expanders exist. By that we mean that bipartite graphs with certain enhanced Hall-type conditions exist.

We then use such bipartite expanders to construct fairly robust error correcting codes.