New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help

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