Local rainbow colorings 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_ | 1866915282986991616 |
|---|---|
| author | Li, Zhenyu Liu, Weichan Sun, Guowei Wang, Xia Wei, Shunan |
| author_facet | Li, Zhenyu Liu, Weichan Sun, Guowei Wang, Xia Wei, Shunan |
| contents | In this paper, we generalize the concepts related to rainbow coloring to hypergraphs. Specifically, an $(n,r,H)$-local coloring is defined as a collection of $n$ edge-colorings, $f_v: E(K^{(r)}_n) \rightarrow [k]$ for each vertex $v$ in the complete $r$-uniform hypergraph $K^{(r)}_n$, with the property that for any copy $T$ of $H$ in $K^{(r)}_n$, there exists at least one vertex $u$ in $T$ such that $f_u$ provides a rainbow edge-coloring of $T$ (i.e., no two edges in $T$ share the same color under $f_u$). The minimum number of colors required for this coloring is denoted as the local rainbow coloring number $C_r(n, H)$.
We first establish an upper bound of the local rainbow coloring number for $r$-uniform hypergraphs $H$ consisting of $h$ vertices, that is, $C_r(n, H)= O\left( n^{\frac{h-r}{h}} \cdot h^{2r + \frac{r}{h}} \right)$. Furthermore, we identify a set of $r$-uniform hypergraphs whose local rainbow coloring numbers are bounded by a constant. A notable special case indicates that $C_3(n,H) \leq C(H)$ for some constant $C(H)$ depending only on $H$ if and only if $H$ contains at most 3 edges and does not belong to a specific set of three well-structured hypergraphs, possibly augmented with isolated vertices. We further establish two 3-uniform hypergraphs $H$ of particular interest for which $C_3(n,H) = n^{o(1)}$.
Regarding lower bounds, we demonstrate that for every $r$-uniform hypergraph $H$ with sufficiently many edges, there exists a constant $b = b(H) > 0$ such that $C_r(n,H) = Ω(n^b)$. Additionally, we obtain lower bounds for several hypergraphs of specific interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07025 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Local rainbow colorings of hypergraphs Li, Zhenyu Liu, Weichan Sun, Guowei Wang, Xia Wei, Shunan Combinatorics In this paper, we generalize the concepts related to rainbow coloring to hypergraphs. Specifically, an $(n,r,H)$-local coloring is defined as a collection of $n$ edge-colorings, $f_v: E(K^{(r)}_n) \rightarrow [k]$ for each vertex $v$ in the complete $r$-uniform hypergraph $K^{(r)}_n$, with the property that for any copy $T$ of $H$ in $K^{(r)}_n$, there exists at least one vertex $u$ in $T$ such that $f_u$ provides a rainbow edge-coloring of $T$ (i.e., no two edges in $T$ share the same color under $f_u$). The minimum number of colors required for this coloring is denoted as the local rainbow coloring number $C_r(n, H)$. We first establish an upper bound of the local rainbow coloring number for $r$-uniform hypergraphs $H$ consisting of $h$ vertices, that is, $C_r(n, H)= O\left( n^{\frac{h-r}{h}} \cdot h^{2r + \frac{r}{h}} \right)$. Furthermore, we identify a set of $r$-uniform hypergraphs whose local rainbow coloring numbers are bounded by a constant. A notable special case indicates that $C_3(n,H) \leq C(H)$ for some constant $C(H)$ depending only on $H$ if and only if $H$ contains at most 3 edges and does not belong to a specific set of three well-structured hypergraphs, possibly augmented with isolated vertices. We further establish two 3-uniform hypergraphs $H$ of particular interest for which $C_3(n,H) = n^{o(1)}$. Regarding lower bounds, we demonstrate that for every $r$-uniform hypergraph $H$ with sufficiently many edges, there exists a constant $b = b(H) > 0$ such that $C_r(n,H) = Ω(n^b)$. Additionally, we obtain lower bounds for several hypergraphs of specific interest. |
| title | Local rainbow colorings of hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.07025 |