Partitioning and Connectivity

Abstract: The most famous and useful characterization of k-connected graphs is Menger's Theorem, but there is another, very nice but little-known characterization of a wholly different nature.

An n-vertex graph G is k-connected if and only if for any positive integers n1,...nk that sum to n and any distinct vertices v1,...,vk, there is a partition of the vertices of G into sets V1,...,Vk such that for all i,

1. Vi induces a connected subgraph of G,
2. Vi contains vi, and
3. |Vi|=ni.

This was conjectured by A. Frank in 1975, and proved independently by Lovasz and Gyori. The first proof is nonconstructive and involves homology of simplicial complexes, and the second proof involves an extremal choice over a huge number of sets. I will sketch a relatively straightforward version of Gyori's proof that is more algorithmic. I will also mention other results that relate partitioning to connectivity. I feel that these results are fundamental and that there ought to be applications, yet I only know of one (which I will sketch).

Event Topic

Discrete Applied Math Seminar