Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-02-06T20:27:29.951Z Has data issue: false hasContentIssue false
  • English
  • Français

A Stability Theorem for Matchings in Tripartite 3-Graphs

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  02 April 2018

PENNY HAXELL  and
LOTHAR NARINS
PENNY HAXELL
Affiliation:
Combinatorics and Optimization Department, University of Waterloo, Waterloo, ON, CanadaN2L 3G1 (e-mail: pehaxell@uwaterloo.ca)
LOTHAR NARINS
Affiliation:
Combinatorics and Optimization Department, University of Waterloo, Waterloo, ON, CanadaN2L 3G1 (e-mail: pehaxell@uwaterloo.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 + ϵ)n/2 is close in structure to the extremal configuration, where ‘closeness’ is measured by an explicit function of ϵ.

MSC classification

Primary: 05C65: Hypergraphs
Secondary: 05C70: Factorization, matching, partitioning, covering and packing 05D15: Transversal (matching) theory
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 5 , September 2018 , pp. 774 - 793
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

†

Partially supported by NSERC. This author also thanks the Mittag-Leffler Institute in Djursholm, Sweden, where part of this work was done.

References

[1] Adamaszek, M. and Barmak, J. A. (2011) On a lower bound for the connectivity of the independence complex of a graph. Discrete Math. 311 2566–2569.Google Scholar
[2] Aharoni, R. (2001) Ryser's conjecture for tripartite 3-graphs. Combinatorica 21 1–4.Google Scholar
[3] Aharoni, R., Alon, N., Amir, M., Haxell, P., Hefetz, D., Jiang, Z., Kronenberg, G. and Naor, A. (2017) Ramsey-nice families of graphs. arXiv:1708.07369Google Scholar
[4] Aharoni, R. and Berger, E. (2006) The intersection of a matroid and a simplicial complex. Trans. Amer. Math. Soc. 358 4895–4917.Google Scholar
[5] Aharoni, R., Berger, E. and Ziv, R. (2007) Independent systems of representatives in weighted graphs. Combinatorica 27 253–267.Google Scholar
[6] Aharoni, R. and Haxell, P. (2000) Hall's theorem for hypergraphs. J. Graph Theory 35 83–88.Google Scholar
[7] Alon, N. and Kim, J. H. (1997) On the degree, size, and chromatic index of a uniform hypergraph. J. Combin. Theory Ser. A 77 165–170.Google Scholar
[8] Haxell, P., Narins, L. and Szabó, T. Extremal hypergraphs for Ryser's conjecture. J. Combin. Theory Ser. A, to appearGoogle Scholar
[9] Meshulam, R. (2003) Domination numbers and homology. J. Combin. Theory Ser. A 102 321–330.Google Scholar
[10] Milnor, J. (1956) Construction of universal bundles, II. Ann. of Math. 63 430–436.Google Scholar
[11] Narins, L. (2014) Extremal hypergraphs for Ryser's conjecture. PhD thesis, Freie Universität Berlin.Google Scholar
[12] Ryser, H. (1967) Neuere Probleme der Kombinatorik. In Vorträge über Kombinatorik Oberwolfach, Mathematisches Forschungsinstitut Oberwolfach, Colloquia Mathematica Societatis János Bolyai, pp. 69–91.Google Scholar
[13] Sperner, E. (1928) Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. Abh. Math. Sem. Univ. Hamburg 6 265–272.Google Scholar