On Matchings in Hypergraphs

  • Peter Frankl
  • Tomasz Łuczak
  • Katarzyna Mieczkowska
Keywords: extremal graph theory, matching, hypergraphs

Abstract

We show that if the largest matching in a $k$-uniform hypergraph $G$ on $n$ vertices has precisely $s$ edges, and $n>2k^2s/\log k$, then $H$ has at most $\binom n k - \binom {n-s} k $ edges and this upper bound is achieved only for hypergraphs in which the set of edges consists of all $k$-subsets which intersect a given set of $s$ vertices.

Author Biographies

Tomasz Łuczak, Adam Mickiewicz University

Faculty of Mathematics and Computer Science,
ul. Umultowska 87,
61-614 Poznań, Poland

Katarzyna Mieczkowska, Adam Mickiewicz University

Faculty of Mathematics and Computer Science,
ul. Umultowska 87,
61-614 Poznań, Poland

Published
2012-06-13
Article Number
P42