
doi: 10.37236/12810
We introduce and study problems on coloring hypergraphs from randomly chosen color lists. Let $H=H(n)$ be an $r$-uniform hypergraph on $n$ vertices where each vertex is assigned a list of colors of size $k$ chosen independently and uniformly at random from all $k$-subsets of a set of colors of size $\sigma=\sigma(n)$. We prove a number of results concerning the probability of the existence of a list coloring of $H$ from the random lists. One such result is that for fixed $r$, $k$ and growing $n$, if $\sigma = \omega\left(n^{\frac{1}{k^2(r-1)}}\Delta^{\frac{1}{k(r-1)}}\right)$, and $H(n)$ has maximum degree $\Delta = O\left(n^{\frac{k-1}{k^2(k^2+k) r(r - 1)}}\right)$, then with probability tending to $1$, as $n \to \infty$, $H$ has a proper coloring from the random lists. The bound on $\sigma$ is tight. We also prove analogous results for hypergraphs of bounded maximum degree and complete hypergraphs where the size $k$ of the random lists either is constant or an increasing function of $n$. In particular, for the complete $r$-uniform hypergraph $K_n^r$, if $\sigma = \lceil n/(r-1) \rceil$, then the property of being colorable from random lists of size $k$ has a sharp threshold at $k(n) = \frac{\log n}{r-1}$.
randomly chosen color lists, Coloring of graphs and hypergraphs, Combinatorial probability, Discrete Mathematics, Diskret matematik, Hypergraphs, \(r\)-uniform hypergraph
randomly chosen color lists, Coloring of graphs and hypergraphs, Combinatorial probability, Discrete Mathematics, Diskret matematik, Hypergraphs, \(r\)-uniform hypergraph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
