MATCHING OF GIVEN SIZES IN HYPERGRAPHS

Yulin Chang, Huifen Ge, Jie Han*, Guanghui Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

For all integers k, d such that k \geq 3 and k/2 \leq d \leq k - 1, let n be a sufficiently large integer (which may not be divisible by k), and let s \leq \lfloor n/k\rfloor - 1. We show that if H is a k-uniform hypergraph on n vertices with \delta d(H) > \bigl(nk --dd\bigr) - \bigl(n -kd--ds+1\bigr) , then H contains a matching of size s. This improves a recent result of Lu, Yu, and Yuan and also answers a question of K\" uhn, Osthus, and Townsend. In many cases, our result can be strengthened to s \leq \lfloor n/k\rfloor , which then covers the entire possible range of s. On the other hand, there are examples showing that the result does not hold for certain n, k, d, and s = \lfloor n/k\rfloor .

Original languageEnglish
Pages (from-to)2323-2338
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Volume36
Issue number3
DOIs
Publication statusPublished - 2022

Keywords

  • absorbing method
  • hypergraph
  • matching

Fingerprint

Dive into the research topics of 'MATCHING OF GIVEN SIZES IN HYPERGRAPHS'. Together they form a unique fingerprint.

Cite this