On the Chromatic Numbers of Random Hypergraphs

Yu A. Demidovich*, D. A. Shabanov*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Abstract: The asymptotic behavior of the chromatic number of the binomial random hypergraph H(n,k,p) is studied in the case when k ≥ 4 is fixed, n tends to infinity, and p = p(n) is a function. If p = p(n) does not decrease too slowly, we prove that the chromatic number of H(n,k,p) is concentrated in two or three consecutive values, which can be found explicitly as functions of n, p, and k.

Original languageEnglish (US)
Pages (from-to)380-383
Number of pages4
JournalDoklady Mathematics
Issue number2
StatePublished - Sep 2020

Bibliographical note

Funding Information:
Shabanov acknowledges the support of the Russian Science Foundation, project no. 16-11-10014.

Publisher Copyright:
© 2020, Pleiades Publishing, Ltd.


  • chromatic number
  • random hypergraph
  • second moment method

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'On the Chromatic Numbers of Random Hypergraphs'. Together they form a unique fingerprint.

Cite this