Candida Bowtell

University of Oxford

[POSTPONED UNTIL FURTHER NOTICE] (Matchings in $k$-partite $k$-graphs)

Combinatorics Seminar

17th March 2020, 11:00 am – 12:00 pm
Fry Building, 2.04

[POSTPONED UNTIL FURTHER NOTICE] Let $H$ be a $k$-partite $k$-graph with parts $V_1, \cdots, V_k$ each of size $n$, such that, for every $i \in [k]$, every $(k-1)$-set in $\prod_{j \in [k]\setminus\{i\}} V_j$ lies in at least $a_i$ edges. Suppose further that $a_1 \geq \cdots \geq a_k$. Hang, Zang and Zhao showed that for every $\epsilon>0$ and sufficiently large $n$, with $a_1, a_2 \geq \epsilon n$, $H$ contains a matching of size at least $\min\{n-1, \sum_{i \in [k]} a_i\}$, answering and generalising a question of R\"{o}dl and Ruci\'{n}ski. Their arguments use complex absorbing methods which fail when all of $a_2, \cdots, a_k$ are small. We consider the remaining cases and, in particular, show that when $\sum_{i=2}^k a_i \leq \sqrt{\frac{n}{k+1}}$, $H$ in fact contains a matching of size at least $\min\{n, \sum_{i \in [k]} a_i\}$. Our proof uses a novel approach, making use of Aharoni and Haxell's `Hall's Theorem for Hypergraphs' and rainbow matchings.

Comments are closed.