Panchromatic colorings of random hypergraphs
type: Item
instance of: scholarly article
title: Panchromatic colorings of random hypergraphs
zbMATH Open document ID: 1459.05304
author: D. A. Kravtsov
author: N. E. Krokhmal
author: D. A. Shabanov
published in: Discrete Mathematics and Applications
publication date: 2021-02-26T00:00:00Z
review text: 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.
reviewed by: Yilun Shang
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 7316010
zbMATH Keywords: random hypergraph
zbMATH Keywords: panchromatic colorings
zbMATH Keywords: threshold probabilities
zbMATH Keywords: second moment method
MaRDI profile type: Publication
full work available at URL: dma-2021-0003
OpenAlex ID: W3132955876
cites work: On the chromatic number of a random hypergraph
cites work: Two‐coloring random hypergraphs
cites work: Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
cites work: The condensation transition in random hypergraph 2-coloring
cites work: Q4074927
cites work: On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs
cites work: On a generalization of Rubin's theorem
cites work: Panchromatic 3-colorings of random hypergraphs
cites work: The existence of panchromatic colourings for uniform hypergraphs
cites work: On the concentration of the chromatic number of a random hypergraph
cites work: Sharp thresholds for constraint satisfaction problems and homomorphisms
cites work: A note on panchromatic colorings
DOI: 10.1515/DMA-2021-0003
description: scientific article; zbMATH DE number 7316010