DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910353494900736 |
|---|---|
| author | Potapov, Vladimir N. |
| author_facet | Potapov, Vladimir N. |
| contents | We develop a connection between DP-colorings of $k$-uniform hypergraphs of order $n$ and coverings of $n$-dimensional Boolean hypercube by pairs of antipodal $(n-k)$-dimensional faces. Bernshteyn and Kostochka established that the lower bound on edges in a non-2-DP-colorable $k$-uniform hypergraph is equal to $2^{k-1}$ for odd $k$ and $2^{k-1}+1$ for even $k$. They proved that these bounds are tight for $k=3,4$. In this paper, we prove that the bound is achieved for all odd $k\geq 3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1905_04461 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces Potapov, Vladimir N. Combinatorics 05C15, 05C65, 05C35, 05B05, 51E05 We develop a connection between DP-colorings of $k$-uniform hypergraphs of order $n$ and coverings of $n$-dimensional Boolean hypercube by pairs of antipodal $(n-k)$-dimensional faces. Bernshteyn and Kostochka established that the lower bound on edges in a non-2-DP-colorable $k$-uniform hypergraph is equal to $2^{k-1}$ for odd $k$ and $2^{k-1}+1$ for even $k$. They proved that these bounds are tight for $k=3,4$. In this paper, we prove that the bound is achieved for all odd $k\geq 3$. |
| title | DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces |
| topic | Combinatorics 05C15, 05C65, 05C35, 05B05, 51E05 |
| url | https://arxiv.org/abs/1905.04461 |