A stability theorem for matchings in tripartite 3-graphs

DOI10.1017/S0963548318000147MaRDI QIDQ4962591zbMATH OpenOpenAlexFDO

Authors Penny Haxell, Lothar Narins

Publication date 5 November 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.06451

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

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+varepsilon)n/2$ is close in structure to the extremal configuration, where "closeness" is measured by an explicit function of $varepsilon$. We also answer a question of Aharoni, Kotlar and Ziv about matchings in hypergraphs with a more general degree condition.

Recommendations

• Stability on matchings in 3-uniform hypergraphs
• Nearly perfect matchings in regular simple hypergraphs
• Perfect matchings in 3-partite 3-uniform hypergraphs
• A stability result on matchings in 3-uniform hypergraphs
• Matchings in hypergraphs of large minimum degree

Cites work

• Construction of universal bundles. II
• Domination numbers and homology
• Hall's theorem for hypergraphs
• Independent systems of representatives in weighted graphs
• On a lower bound for the connectivity of the independence complex of a graph
• On the degree, size, and chromatic index of a uniform hypergraph
• Ryser's conjecture for tripartite 3-graphs
• The intersection of a matroid and a simplicial complex

Cited in

(3)

• Tripartite version of the Corrádi-Hajnal theorem
• Almost all triangle-free triple systems are tripartite
• Improved integrality gap in max-min allocation, or, topology at the north pole

This page was built for publication: A stability theorem for matchings in tripartite 3-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962591)