New bounds on the size of nearly perfect matchings in almost regular hypergraphs

Dong Yeap Kang, Daniela Kรผhn, Abhishek Methuku, Deryk Osthus*

*Corresponding author for this work

Research output: Contribution to journal โ€บ Article โ€บ peer-review

75 Downloads (Pure)

Abstract

Let ๐ป be a ๐‘˜-uniform ๐ท-regular simple hypergraph on ๐‘ vertices. Based on an analysis of the Rรถdl nibble, in 1997, Alon, Kim and Spencer proved that if ๐‘˜ โฉพ 3, then ๐ป contains a matching covering all but at most ๐‘๐ทโˆ’1โˆ•(๐‘˜โˆ’1)+๐‘œ(1) vertices, and asked whether this bound is tight. In this paper we improve their bound by showing that for all ๐‘˜>3, ๐ป contains a matching covering all but at most ๐‘๐ทโˆ’1โˆ•(๐‘˜โˆ’1)โˆ’๐œ‚ vertices for some ๐œ‚ = ฮ˜(๐‘˜โˆ’3)>0, when ๐‘ and ๐ท are sufficiently large. Our approach consists of showing that the Rรถdl nibble process not only constructs a large matching but it also produces many well-distributed โ€˜augmenting starsโ€™ which can then be used to significantly improve the matching constructed by the Rรถdl nibble process. Based on this, we also improve the results of Kostochka and Rรถdl from 1998 and Vu from 2000 on the size of matchings in almost regular hypergraphs with small codegree. As a consequence, we improve the best known bounds on the size of large matchings in combinatorial designs with general parameters. Finally, we improve the bounds of Molloy and Reed from 2000 on the chromatic index of hypergraphs with small codegree (which can be applied to improve the best known bounds on the chromatic index of Steiner triple systems and more general designs).
Original languageEnglish
Number of pages46
JournalJournal of the London Mathematical Society
Early online date31 Jul 2023
DOIs
Publication statusE-pub ahead of print - 31 Jul 2023

Bibliographical note

DO: Note that the article was submitted prior to 1 April 2022. Moreover, the LMS has 0 months embargo for publication e.g. on arxiv etc. According to the UKRI website, this makes a green open access option compliant with REF and UKRI.

Fingerprint

Dive into the research topics of 'New bounds on the size of nearly perfect matchings in almost regular hypergraphs'. Together they form a unique fingerprint.

Cite this