Bounds on threshold probabilities for coloring properties of random hypergraphs

DOI10.1134/s0032946022010057zbMath1518.05067OpenAlexW4223440586MaRDI QIDQ6173449

Aleksandr S. Semenov, Dmitriy A. Shabanov

Publication date: 21 July 2023

Published in: Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0032946022010057

zbMATH Keywords

hypergraph coloringsrandom hypergraphsecond moment method\(j\)-chromatic number

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Combinatorial probability (60C05) Coloring of graphs and hypergraphs (05C15)

Related Items (1)

On the concentration of values of \(j\)-chromatic numbers of random hypergraphs

Cites Work

• Unnamed Item
• Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number
• On the number of independent sets in simple hypergraphs
• Estimating the \(r\)-colorability threshold for a random hypergraph
• General independence sets in random strongly sparse hypergraphs
• On the strong chromatic number of a random 3-uniform hypergraph
• On the weak chromatic number of random hypergraphs
• On the chromatic number of a random hypergraph
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Random hypergraph coloring algorithms and the weak chromatic number
• On the 2-colorability of random hypergraphs
• Two‐coloring random hypergraphs
• Independent Sets in Regular Hypergraphs and Multidimensional Runlength-Limited Constraints
• The chromatic number of dense random graphs
• Hypergraph Independent Sets
• Hypergraph coloring up to condensation
• Two-Colorings of a Random Hypergraph
• Catching the k-NAESAT threshold
• The condensation transition in random hypergraph 2-coloring

This page was built for publication: Bounds on threshold probabilities for coloring properties of random hypergraphs