Topological methods in discrete mathematics
Organizer and Chair: Ron Aharoni (Technion - Israel Institute of Technology, Israel)
[PDF]

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.

ANDREAS HOLMSEN, KAIST
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.

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.