Download this article
Download this article For screen
For printing
Recent Issues
Volume 13, Issue 4
Volume 13, Issue 3
Volume 13, Issue 2
Volume 13, Issue 1
Volume 12, Issue 4
Volume 12, Issue 3
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 4
Volume 11, Issue 3
Volume 11, Issue 2
Volume 11, Issue 1
Volume 10, Issue 4
Volume 10, Issue 3
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 4
Volume 9, Issue 3
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
Older Issues
Volume 7, Issue 4
Volume 7, Issue 3
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 4
Volume 6, Issue 2-3
Volume 6, Issue 1
Volume 5, Issue 4
Volume 5, Issue 3
Volume 5, Issue 1-2
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 3-4
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 4
Volume 1, Issue 3
Volume 1, Issue 2
Volume 1, Issue 1
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
founded and published with the
scientific support and advice of
mathematicians from the
Moscow Institute of
Physics and Technology
Subscriptions
 
ISSN 2996-220X (online)
ISSN 2996-2196 (print)
Author Index
To Appear
 
Other MSP Journals
Estimating the strong $r$-colorability threshold in random hypergraphs

Alina Khuzieva, Tatiana Matveeva and Dmitry Shabanov

Vol. 12 (2023), No. 1, 57–88
Abstract

The paper deals with strong r-colorings of a random k-uniform hypergraph in the binomial model H(n,k,p). A vertex coloring is said to be strong for a hypergraph if any two vertices that share a common edge are colored with distinct colors. We consider the sparse case when the expected number of edges is equal to cn and the values r k 3, c > 0 remain constant as n +. We prove tight bounds for the strong r-colorability threshold as the bounds for the parameter c. As a corollary we give the explicit limit value of the strong chromatic number of the random hypergraph H(n,k,cnn k ) for almost all values of the parameter c.

Keywords
random hypergraphs, strong colorings, probability thresholds, second-moment method
Mathematical Subject Classification
Primary: 05C15, 05C80
Milestones
Received: 3 December 2021
Revised: 17 September 2022
Accepted: 2 October 2022
Published: 29 March 2023
Authors
Alina Khuzieva
Faculty of Computer Science
HSE University
Moscow
Russia
Tatiana Matveeva
Department of Probability Theory
Lomonosov Moscow State University
Moscow
Russia
Dmitry Shabanov
Moscow Institute of Physics and Technology
Laboratory of Combinatorial and Geometric Structure
Dolgoprudny
Russia
Faculty of Computer Science
HSE University
Moscow
Russia