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