Choosability of multipartite hypergraphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915693461504000 |
|---|---|
| author | Bradshaw, Peter Dhawan, Abhishek Dinh, Nhi Mulye, Shlok Rathi, Rohan |
| author_facet | Bradshaw, Peter Dhawan, Abhishek Dinh, Nhi Mulye, Shlok Rathi, Rohan |
| contents | A $k$-uniform hypergraph (or $k$-graph) $H = (V, E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1, \ldots, V_k$ such that each edge in $E$ contains precisely one vertex from each $V_i$. We show that $k$-partite $k$-graphs of maximum degree $Δ$ are $q$-choosable for $q \geq \left(\frac{4}{5}(k-1 + o(1))Δ/\log Δ\right)^{1/(k-1)}$. Our proof yields an efficient randomized algorithm for finding such a coloring, which shows that the conjectured algorithmic barrier for coloring pseudorandom $k$-graphs does not apply to $k$-partite $k$-graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21222 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Choosability of multipartite hypergraphs Bradshaw, Peter Dhawan, Abhishek Dinh, Nhi Mulye, Shlok Rathi, Rohan Combinatorics A $k$-uniform hypergraph (or $k$-graph) $H = (V, E)$ is $k$-partite if $V$ can be partitioned into $k$ sets $V_1, \ldots, V_k$ such that each edge in $E$ contains precisely one vertex from each $V_i$. We show that $k$-partite $k$-graphs of maximum degree $Δ$ are $q$-choosable for $q \geq \left(\frac{4}{5}(k-1 + o(1))Δ/\log Δ\right)^{1/(k-1)}$. Our proof yields an efficient randomized algorithm for finding such a coloring, which shows that the conjectured algorithmic barrier for coloring pseudorandom $k$-graphs does not apply to $k$-partite $k$-graphs. |
| title | Choosability of multipartite hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.21222 |