On r-colorability of random hypergraphs

2011/10/06 by Андрей Борисович Купавский, Kupavskii, Andrei, D. A. Shabanov +1 · 1 citation
Computer Science · #05C15 #05C80 #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Data Management and Algorithms #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1110.1249

openalex publication_date 2011/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The work deals with the threshold probablity for r-colorability in the binomial model H(n,k,p) of a random k-uniform hypergraph. We prove a lower bound for this threshold which improves the previously known results in the wide range of the parameters r=r(n) and k=k(n).

Cited by

• Zero-One Law for random uniform hypergraphs

Related

• Upper bounds on the 2-colorability threshold of random d-regular k-uniform hypergraphs for k≥ 3
• On the chromatic number of a random hypergraph
• How many random edges make a dense hypergraph non-2-colorable?
• On the number of solutions in random hypergraph 2-colouring
• A note on random greedy coloring of uniform hypergraphs