Advancing the Rödl Nibble: New bounds on matchings and the list chromatic index of hypergraphs

Let $H$ be a $(k+1)$-uniform hypergraph which is nearly $D$-regular, such that any set of $i$ vertices is contained in at most $D_i$ edges of $H$ for each $i=2,3,\dots ,k+1$. Influential results of Pippenger and of Frankl and Rödl show that the $\mathit{\text{R}}\ddot{\mathit{\text{o}}}\mathit{\text{dl}}\mathit{\text{Nibble}}$ – a probabilistic procedure which iteratively constructs a matching in small bits – can produce an almost-perfect matching in $H$, provided $D_2$ is much smaller than $D$. The quantitative aspects of this result were sharpened by several authors, with the previously best-known result due to Vu, whose result takes more of the codegree sequence $D_2,\dots ,D_{k+1}$ into account. We improve Vu’s result, by showing the Rödl Nibble can exhaust'' the full codegree sequence up to one of several natural bottlenecks, even tolerating extensive clustering’’ of codegree values. Up to a subpolynomial error term, we believe our result to be the optimal usage of pure nibble methodology. We also show that our matching can be taken to be ``pseudorandom’’ with respect to a set of weight functions on $V(H)$, and we use this result to derive other hypergraph matching results in partite settings, including a new bound on the list chromatic index which implies the best-known result of Molloy and Reed up to the error term, and is stronger when the hypergraph is not close to linear, i.e.\ $D_2=\omega (1)$. We also apply our results to obtain improved bounds on almost-spanning structures in Latin squares and designs, and the maximum diameter of a simplicial complex.