Candida Bowtell

Oxford University

Matchings in k-partite k-graphs

Combinatorics Seminar

8th December 2020, 11:00 am – 12:00 pm
Virtual (online) Zoom seminar; a link will be sent to the Bristol Combinatorics Seminar mailing list,, the week before the seminar.

Let H be a k-partite k-graph with parts V_1,..., 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 ... \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ödl and Ruciński. Their arguments use complex absorbing methods which fail when all of a_2,..., a_k are small. We consider the remaining cases and, in particular, show that when \sum_{i=2}^k a_i \leq \sqrt{n/(k+1)}, H in fact contains a matching of size at least \min\{n, \sum_{i \in [k]} a_i\}. Our proof takes a novel approach, making use of Aharoni and Haxell's `Hall's Theorem for Hypergraphs' and rainbow matchings. Joint work with Richard Mycroft (Birmingham).

Comments are closed.