[Discrete-math-seminar] Location of Thursday __1:15pm__ seminar, M. Pelsmajer "Partitioning and Connectivity"

[Robert Ellis]

Hi all,

The location of the Michael's talk today will probably be E1 124. 
However, the room reservation has not been confirmed, so if it is not 124 
I will post a note outside that door where it will actually be.

Thanks,
Robert Ellis

E1 105C, IL Inst. Tech.
Chicago, IL 60616
(312) 567-5336 --- rellis at math.iit.edu
http://math.iit.edu/~rellis/


On Tue, 12 Sep 2006, Robert Ellis wrote:

> After considering the options, we have moved the seminar up to 1:15pm 
> Thursday (from 2pm).  I am working on the new room reservation now and will 
> try to make it near E1 122 (on the same hall) -- to be announced.
>
> Thursday Sept. 14 Talk
> ======================
> Speaker: Michael Pelsmajer
> Title: Partitioning and Connectivity
> Time: 2:15pm
> Location: TBA (probably near E1 122)
>
> 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).
>