CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Méthodes topologiques en mathématiques discrètes
Responsable et président: Ron Aharoni (Technion - Israel Institute of Technology, Israel)

PENNY HAXELL, University of Waterloo
Tripartite hypergraphs and connectedness  [PDF]

We derive certain structural results about 3-partite 3-uniform hypergraphs by studying the topological connectedness of the independence complex of line graphs. These in turn lead to new bounds for an old conjecture on packing and covering triangles in graphs.

The geometric join and the general position complex  [PDF]

The geometric join and the general position complex are two constructions which give rise to topological spaces (simplicial complexes) and we are interested in bounding their connectivity. I will present the bounds we know and how they relate to some problems in discrete geometry.

LOTHAR NARINS, Freie Universität Berlin
Extremal Hypergraphs for Ryser's Conjecture  [PDF]

Ryser's Conjecture states that in an $r$-partite $r$-uniform hypergraph, the vertex cover number is at most $r - 1$ times the matching number. The case $r = 3$ was proven using topologically-based methods by Aharoni, but the cases $r \geq 4$ remain wide open. Together with Penny Haxell and Tibor Szabó, we characterize the extremal hypergraphs for $r = 3$, also using topological methods. Related to this, we also formulate a conjecture relating the vertex cover number of a hypergraph to the connectedness of the independence complex of its line graph.

MATEJ STEHLIK, Université Joseph Fourier
A graph colouring version of the Borsuk–Ulam theorem  [PDF]

The Borsuk–Ulam theorem plays a key role in obtaining `topological' lower bounds on the chromatic number. The first such bound was found by Lovász in 1978.

We will show that—surprisingly—the Borsuk–Ulam theorem is equivalent to a recent generalisation of Youngs's theorem on the chromatic number of projective quadrangulations. This seems to suggests that all topological lower bounds on the chromatic number ought to follow from the generalisation of Youngs's theorem, and we will show that this is indeed the case for some of them, including Lovász's original bound.

Partly based on joint work with Tomáš Kaiser.

SHIRA ZERBIB, Technion, Israel
Matchings and covers of (weighted) d-intervals  [PDF]

A $d$-interval hypergraph consists of edges that are each the union of $d$ closed intervals on the real line. Kaiser showed that the ratio between the covering number and the matching number in such hypergraphs is bounded by $d^2$. I will present some new results regarding the weighted and fractional versions of this theorem, and examples for their sharpness. I will also discuss an extension of the topological KKM theorem (due to Shapley) and use it to give a straightforward proof to Kaiser's theorem.

Joint work with R. Aharoni and T. Kaiser.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan