Advancing the Rödl Nibble: New bounds on matchings and the list chromatic index of hypergraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912709311725568 |
|---|---|
| author | Gould, Stephen Kelly, Tom |
| author_facet | Gould, Stephen Kelly, Tom |
| contents | 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 \textit{Rödl 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=ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11375 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Advancing the Rödl Nibble: New bounds on matchings and the list chromatic index of hypergraphs Gould, Stephen Kelly, Tom Combinatorics 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 \textit{Rödl 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=ω(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. |
| title | Advancing the Rödl Nibble: New bounds on matchings and the list chromatic index of hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.11375 |