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

Yu A. Demidovich; D. A. Shabanov

doi:10.1137/S0040585X97T990861

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

Yu A. Demidovich, D. A. Shabanov

Computer Science

Research output: Contribution to journal › Article › peer-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 n^k−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 n^k−1p, these values can be explicitly evaluated as functions of n and p.

Original language	English (US)
Pages (from-to)	175-193
Number of pages	19
Journal	Theory of Probability and its Applications
Volume	67
Issue number	2
DOIs	https://doi.org/10.1137/S0040585X97T990861
State	Published - 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 ([email protected]).

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

Access to Document

10.1137/S0040585X97T990861

Cite this

@article{fd9f258b66f6465f9c72392fe406a27b,

title = "ON TWO LIMIT VALUES OF THE CHROMATIC NUMBER OF A RANDOM HYPERGRAPH",

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.",

keywords = "chromatic number, random hypergraph, second moment method",

author = "Demidovich, {Yu A.} and Shabanov, {D. A.}",

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 ([email protected]). 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: {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited.",

year = "2022",

doi = "10.1137/S0040585X97T990861",

language = "English (US)",

volume = "67",

pages = "175--193",

journal = "Theory of Probability and its Applications",

issn = "0040-585X",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

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

AU - Demidovich, Yu A.

AU - Shabanov, D. A.

N1 - 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 ([email protected]). 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.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - chromatic number

KW - random hypergraph

KW - second moment method

UR - http://www.scopus.com/inward/record.url?scp=85161851600&partnerID=8YFLogxK

U2 - 10.1137/S0040585X97T990861

DO - 10.1137/S0040585X97T990861

M3 - Article

AN - SCOPUS:85161851600

SN - 0040-585X

VL - 67

SP - 175

EP - 193

JO - Theory of Probability and its Applications

JF - Theory of Probability and its Applications

IS - 2

ER -

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

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this