Penny Haxell: Extremal graphs for connectedness
Tid: Ti 2014-04-22 kl 14.00 - 15.00
Plats: Institut Mittag-Leffler, Auravägen 17, Djursholm
Medverkande: Penny Haxell, University of Waterloo
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.