A Stability Theorem for Matchings in Tripartite 3-Graphs

Abstract

It follows from known results that every regular tripartite hypergraph of positive degree, with $n$ vertices in each class, has matching number at least $n/2$. This bound is best possible, and the extremal configuration is unique. Here we prove a stability version of this statement, establishing that every regular tripartite hypergraph with matching number at most $(1+\epsilon )n/2$ is close in structure to the extremal configuration, where "closeness" is measured by an explicit function of $\epsilon$. We also answer a question of Aharoni, Kotlar and Ziv about matchings in hypergraphs with a more general degree condition.