New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
✍ Scribed by Van H. Vu
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 253 KB
- Volume
- 17
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
Let H be a k + 1 -uniform, D-regular hypergraph on n vertices and let H be the minimum number of vertices left uncovered by a matching in H. C j H , the j-codegree of H, is the maximum number of edges sharing a set of j vertices in common. We prove a general upper bound on H , based on the codegree sequence C 2 H C 3 H . Our bound improves and generalizes many results on the topic, including those of Grable, Alon, Kim, and Spencer, and Kostochka and Rödl. It also leads to a substantial improvement in several applications. The key ingredient of the proof is the so-called polynomial technique, which is a new and useful tool to prove concentration results for functions with large Lipschitz coefficient. This technique is of independent interest.