Premium
New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
Author(s) -
Vu Van H.
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200008)17:1<29::aid-rsa4>3.0.co;2-w
Subject(s) - combinatorics , mathematics , discrete mathematics
Abstract 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. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 29–63, 2000