Penny Haxell: Extremal graphs for connectedness

It is known that the topological connectedness of the independence complex of the line graph of G is bounded below by the matching number of G (minus 2). This parameter turns out to be important for some old conjectures about hypergraphs, in particular Ryser's conjecture on r-partite r-uniform hypergraphs. We study the bipartite graphs G that are extremal for this parameter, and as one consequence characterise the 3-partite 3-uniform hypergraphs that are extremal for Ryser's conjecture.

Joint work with Lothar Narins and Tibor Szabo.