On the Chromatic Number of a Random 3-Uniform Hypergraph

Yury A. Demidovich*, Dmitry A. Shabanov

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


This paper is devoted to the problem concerning the chromatic number of a random 3-uniform hypergraph. We consider the binomial model H(n, 3, p) and show that if p= p(n) decreases fast enough then the chromatic number of H(n, 3, p) is concentrated in 2 or 3 consecutive values which can be found explicitly as functions of n and p. This result is derived as an application of the solution of an extremal problem for doubly stochastic matrices.

Original languageEnglish (US)
Title of host publicationRecent Developments in Stochastic Methods and Applications - ICSM-5, Selected Contributions
EditorsAlbert N. Shiryaev, Konstantin E. Samouylov, Dmitry V. Kozyrev
Number of pages14
ISBN (Print)9783030832650
StatePublished - 2021
Event5th International Conference on Stochastic Methods, ICSM-5 2020 - Moscow, Russian Federation
Duration: Nov 23 2020Nov 27 2020

Publication series

NameSpringer Proceedings in Mathematics and Statistics
ISSN (Print)2194-1009
ISSN (Electronic)2194-1017


Conference5th International Conference on Stochastic Methods, ICSM-5 2020
Country/TerritoryRussian Federation

Bibliographical note

Funding Information:
Acknowledgments. Research of Yu.A. Demidovich was supported by the RFBR, project number 19-31-90016. Research of D.A. Shabanov was supported by the grant of the President of Russian Federation no. MD-1562.2020.1

Publisher Copyright:
© 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.


  • Colorings
  • Doubly stochastic matrices
  • Random hypergraphs
  • Second moment method

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'On the Chromatic Number of a Random 3-Uniform Hypergraph'. Together they form a unique fingerprint.

Cite this