On the structure of the set of panchromatic colorings of a random hypergraph

DOI10.1134/s1064562423700953zbMath1530.05058MaRDI QIDQ6148171

D. N. Tyapkin, Dmitriy A. Shabanov

Publication date: 11 January 2024

Published in: Doklady Mathematics (Search for Journal in Brave)

zbMATH Keywords

shatteringcolorings of hypergraphsrandom hypergraphpanchromatic colorings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Upper-bounding the \(k\)-colorability threshold by counting covers
• Panchromatic colorings of random hypergraphs
• The hardness of 3-uniform hypergraph coloring
• 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
• On the hardness of approximating minimization problems
• Two‐coloring random hypergraphs
• The Chromatic Number of Random Graphs for Most Average Degrees
• Reducibility among Combinatorial Problems
• Hardness of Rainbow Coloring Hypergraphs
• Rigid Colorings of Hypergraphs and Contiguity
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Catching the k-NAESAT threshold
• The condensation transition in random hypergraph 2-coloring

This page was built for publication: On the structure of the set of panchromatic colorings of a random hypergraph