On the Chromatic Numbers of Random Hypergraphs

Yu A. Demidovich; D. A. Shabanov

doi:10.1134/S1064562420050312

On the Chromatic Numbers of Random Hypergraphs

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

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	380-383
Number of pages	4
Journal	Doklady Mathematics
Volume	102
Issue number	2
DOIs	https://doi.org/10.1134/S1064562420050312
State	Published - 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.

Keywords

chromatic number
random hypergraph
second moment method

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1134/S1064562420050312

Cite this

@article{49b0c02d821f471da1ce65979e60514e,

title = "On the Chromatic Numbers of Random Hypergraphs",

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

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

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

note = "Funding Information: Shabanov acknowledges the support of the Russian Science Foundation, project no. 16-11-10014. Publisher Copyright: {\textcopyright} 2020, Pleiades Publishing, Ltd.",

year = "2020",

month = sep,

doi = "10.1134/S1064562420050312",

language = "English (US)",

volume = "102",

pages = "380--383",

journal = "Doklady Mathematics",

issn = "1064-5624",

publisher = "Pleiades Publishing",

number = "2",

}

TY - JOUR

T1 - On the Chromatic Numbers of Random Hypergraphs

AU - Demidovich, Yu A.

AU - Shabanov, D. A.

PY - 2020/9

Y1 - 2020/9

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

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

KW - chromatic number

KW - random hypergraph

KW - second moment method

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

U2 - 10.1134/S1064562420050312

DO - 10.1134/S1064562420050312

M3 - Article

AN - SCOPUS:85099472373

SN - 1064-5624

VL - 102

SP - 380

EP - 383

JO - Doklady Mathematics

JF - Doklady Mathematics

IS - 2

ER -

On the Chromatic Numbers of Random Hypergraphs

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this