Projects per year
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 language | English |
---|---|
Number of pages | 46 |
Journal | Journal of the London Mathematical Society |
Early online date | 31 Jul 2023 |
DOIs | |
Publication status | E-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.Projects
- 3 Finished
-
H2020_ERC_EXTCOMB
Osthus, D. (Co-Investigator) & Kuhn, D. (Principal Investigator)
1/01/19 โ 31/12/24
Project: EU
-
Approximate Structure in Large Graphs and Hypergraphs
Osthus, D. (Principal Investigator)
Engineering & Physical Science Research Council
1/01/19 โ 31/12/21
Project: Research Councils
-
Combinatorics, Probability and Algorithms: Fellowship, Establish Career: Professor D Kuhn
Kuhn, D. (Principal Investigator)
Engineering & Physical Science Research Council
1/09/16 โ 31/08/21
Project: Research Councils