On the Chromatic Number of a Random 3-Uniform Hypergraph

Yury A. Demidovich; Dmitry A. Shabanov

doi:10.1007/978-3-030-83266-7_14

On the Chromatic Number of a Random 3-Uniform Hypergraph

Yury A. Demidovich^*, Dmitry A. Shabanov

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 language	English (US)
Title of host publication	Recent Developments in Stochastic Methods and Applications - ICSM-5, Selected Contributions
Editors	Albert N. Shiryaev, Konstantin E. Samouylov, Dmitry V. Kozyrev
Publisher	Springer
Pages	190-203
Number of pages	14
ISBN (Print)	9783030832650
DOIs	https://doi.org/10.1007/978-3-030-83266-7_14
State	Published - 2021
Event	5th International Conference on Stochastic Methods, ICSM-5 2020 - Moscow, Russian Federation Duration: Nov 23 2020 → Nov 27 2020

Publication series

Name	Springer Proceedings in Mathematics and Statistics
Volume	371
ISSN (Print)	2194-1009
ISSN (Electronic)	2194-1017

Conference

Conference	5th International Conference on Stochastic Methods, ICSM-5 2020
Country/Territory	Russian Federation
City	Moscow
Period	11/23/20 → 11/27/20

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.

Keywords

Colorings
Doubly stochastic matrices
Random hypergraphs
Second moment method

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1007/978-3-030-83266-7_14

Cite this

Demidovich, Y. A., & Shabanov, D. A. (2021). On the Chromatic Number of a Random 3-Uniform Hypergraph. In A. N. Shiryaev, K. E. Samouylov, & D. V. Kozyrev (Eds.), Recent Developments in Stochastic Methods and Applications - ICSM-5, Selected Contributions (pp. 190-203). (Springer Proceedings in Mathematics and Statistics; Vol. 371). Springer. https://doi.org/10.1007/978-3-030-83266-7_14

@inproceedings{14b74fd68740443e879f7b61e276405a,

title = "On the Chromatic Number of a Random 3-Uniform Hypergraph",

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

keywords = "Colorings, Doubly stochastic matrices, Random hypergraphs, Second moment method",

author = "Demidovich, {Yury A.} and Shabanov, {Dmitry A.}",

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: {\textcopyright} 2021, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 5th International Conference on Stochastic Methods, ICSM-5 2020 ; Conference date: 23-11-2020 Through 27-11-2020",

year = "2021",

doi = "10.1007/978-3-030-83266-7_14",

language = "English (US)",

isbn = "9783030832650",

series = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer",

pages = "190--203",

editor = "Shiryaev, {Albert N.} and Samouylov, {Konstantin E.} and Kozyrev, {Dmitry V.}",

booktitle = "Recent Developments in Stochastic Methods and Applications - ICSM-5, Selected Contributions",

address = "Germany",

}

Demidovich, YA & Shabanov, DA 2021, On the Chromatic Number of a Random 3-Uniform Hypergraph. in AN Shiryaev, KE Samouylov & DV Kozyrev (eds), Recent Developments in Stochastic Methods and Applications - ICSM-5, Selected Contributions. Springer Proceedings in Mathematics and Statistics, vol. 371, Springer, pp. 190-203, 5th International Conference on Stochastic Methods, ICSM-5 2020, Moscow, Russian Federation, 11/23/20. https://doi.org/10.1007/978-3-030-83266-7_14

On the Chromatic Number of a Random 3-Uniform Hypergraph. / Demidovich, Yury A.; Shabanov, Dmitry A.
Recent Developments in Stochastic Methods and Applications - ICSM-5, Selected Contributions. ed. / Albert N. Shiryaev; Konstantin E. Samouylov; Dmitry V. Kozyrev. Springer, 2021. p. 190-203 (Springer Proceedings in Mathematics and Statistics; Vol. 371).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On the Chromatic Number of a Random 3-Uniform Hypergraph

AU - Demidovich, Yury A.

AU - Shabanov, Dmitry A.

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

PY - 2021

Y1 - 2021

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

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

KW - Colorings

KW - Doubly stochastic matrices

KW - Random hypergraphs

KW - Second moment method

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

U2 - 10.1007/978-3-030-83266-7_14

DO - 10.1007/978-3-030-83266-7_14

M3 - Conference contribution

AN - SCOPUS:85113714874

SN - 9783030832650

T3 - Springer Proceedings in Mathematics and Statistics

SP - 190

EP - 203

BT - Recent Developments in Stochastic Methods and Applications - ICSM-5, Selected Contributions

A2 - Shiryaev, Albert N.

A2 - Samouylov, Konstantin E.

A2 - Kozyrev, Dmitry V.

PB - Springer

T2 - 5th International Conference on Stochastic Methods, ICSM-5 2020

Y2 - 23 November 2020 through 27 November 2020

ER -

On the Chromatic Number of a Random 3-Uniform Hypergraph

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this