Panchromatic colorings of random hypergraphs
This paper studies panchromatic colorings of random hypergraphs. Let \(H(n,k,p)\) be the binomial model of a random \(k\)-homogeneous hypergraph over \(n\) vertices with edge probability \(p\). It is shown that there exists a natural number \(k_0\) such that for each \(k>k_0\), \(3\le r<0.1\sqrt{k}\) and \(c<[(\ln r)/r][r/(r-1)]^k-[(\ln r)/2]-20k^2\ln r\big\{[r/(r-1)]\max(r^{-1/(r-1)},(r/(r+1))^2)\big\}^k\) the random hypergraph \(H(n,k,cn/\binom{n}{k})\) may be panchromatically colored with \(r\) colors almost surely as \(n\) tends to infinity. There also exists a constant \(C>0\) such that if under the same conditions \(c>[(\ln r)/r][r/(r-1)]^k-[(\ln r)/2]+C\ln r\{r(r-2)/(r-1)^2\}^k\), there does not exist a panchromatic \(r\)-coloring of the graph \(H(n,k,cn/\binom{n}{k})\) almost surely.
- A note on panchromatic colorings
- scientific article; zbMATH DE number 3492718 (Why is no real title available?)
- On a generalization of Rubin's theorem
- On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs
- On the chromatic number of a random hypergraph
- On the concentration of the chromatic number of a random hypergraph
- Panchromatic 3-colorings of random hypergraphs
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Sharp thresholds for constraint satisfaction problems and homomorphisms
- The condensation transition in random hypergraph 2-coloring
- The existence of panchromatic colourings for uniform hypergraphs
- Two‐coloring random hypergraphs
- Density conditions for panchromatic colourings of hypergraphs
- Panchromatic 3-coloring of a random hypergraph
- A note on panchromatic colorings
- Chain method for panchromatic colorings of hypergraphs
- The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
- On the chromatic numbers of random hypergraphs
- Panchromatic 3-colorings of random hypergraphs
- Random constructions of hypergraphs with large girth and without panchromatic colorings
- Random reals and polarized colorings
- Ramsey Properties of Random k-Partite, k-Uniform Hypergraphs
- The existence of panchromatic colourings for uniform hypergraphs
- Extremal problems for panchromatic colourings of uniform hypergraphs
- On two limit values of the chromatic number of a random hypergraph
- On panchromatic colourings of a random hypergraph
- On the structure of the set of panchromatic colorings of a random hypergraph
- Bounds on threshold probabilities for coloring properties of random hypergraphs
- Threshold probabilities for colourings of random hypergraphs
This page was built for publication: Panchromatic colorings of random hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996843)
