ON TWO LIMIT VALUES OF THE CHROMATIC NUMBER OF A RANDOM HYPERGRAPH

Yu A. Demidovich, D. A. Shabanov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

The limit concentration of the values of the chromatic number of the random hyper-graph H(n, k, p) in the binomial model is studied. It is proved that, for a fixed k ⩾ 3 and with not too rapidly increasing nk−1p, the chromatic number of the hypergraph H(n, k, p) lies, with probability tending to 1, in the set of two consecutive values. Moreover, it is shown that, under slightly stronger constraints on the growth of nk−1p, these values can be explicitly evaluated as functions of n and p.

Original languageEnglish (US)
Pages (from-to)175-193
Number of pages19
JournalTheory of Probability and its Applications
Volume67
Issue number2
DOIs
StatePublished - 2022

Bibliographical note

Funding Information:
∗Received by the editors November 18, 2020; revised October 22, 2021. Published electronically August 4, 2022. This research was carried out with the financial support of the Russian Foundation for Basic Research (grant 20-31-70039). The second author was supported by the grant of the President of Russian Federation MD-1562.2020.1. Originally published in the Russian journal Teoriya Veroyatnostei i ee Primeneniya, 67 (2022), pp. 223–246. https://doi.org/10.1137/S0040585X97T990861 †Department of Discrete Mathematics and Laboratory of Advanced Combinatorics and Network Applications, Moscow Institute of Physics and Technology (National Research University), Dolgo-prudnyi, Moscow Region, Russia (yuradem9595@mail.ru).

Funding Information:
This research was carried out with the financial support of the Russian Foundation for Basic Research (grant 20-31-70039). The second author was supported by the grant of the President of Russian Federation MD-1562.2020.1. Originally published in the Russian journal Teoriya Veroyatnostei i ee Primeneniya, 67 (2022), pp. 223–246.

Publisher Copyright:
© by SIAM. Unauthorized reproduction of this article is prohibited.

Keywords

  • chromatic number
  • random hypergraph
  • second moment method

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint

Dive into the research topics of 'ON TWO LIMIT VALUES OF THE CHROMATIC NUMBER OF A RANDOM HYPERGRAPH'. Together they form a unique fingerprint.

Cite this