Regular behavior of the maximal hypergraph chromatic number

Standard

Regular behavior of the maximal hypergraph chromatic number. / Cherkashin, Danila ; Petrov, Fedor.

In: SIAM Journal on Discrete Mathematics, Vol. 34, No. 2, 2020, p. 1326-1333.

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

BibTeX

@article{865d463422d748268bf31e7b514b0547,

title = "Regular behavior of the maximal hypergraph chromatic number",

abstract = "Let m(n, r) denote the minimal number of edges in an n-uniform hypergraph which is not r-colorable. It is known that for a fixed n one has cnrn < m(n, r) < Cnrn. We prove that for any fixed n the sequence ar:= m(n, r)/rn has a limit, which was conjectured by Alon. We also prove the list colorings analogue of this statement.",

keywords = "Erd{\H o}s-Hajnal problem, Hypergraph coloring, Subadditivity",

author = "Danila Cherkashin and Fedor Petrov",

note = "Funding Information: \ast Received by the editors August 16, 2019; accepted for publication (in revised form) March 23, 2020; published electronically June 15, 2020. https://doi.org/10.1137/19M1281861 Funding: Supported by the Russian Scientific Foundation, grant 17-71-20153. \dagger National Research University Higher School of Economics, Soyuza Pechatnikov str., 16, St. Petersburg, Russian Federation (matelk@mail.ru). \ddagger Saint Petersburg State University, Faculty of Mathematics and Mechanics; St. Petersburg Department of V. A. Steklov Institute of Mathematics of the Russian Academy of Sciences (fedyapetrov@gmail.com). Publisher Copyright: Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2020",

doi = "10.1137/19M1281861",

language = "English",

volume = "34",

pages = "1326--1333",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics",

number = "2",

}

RIS

TY - JOUR

T1 - Regular behavior of the maximal hypergraph chromatic number

AU - Cherkashin, Danila

AU - Petrov, Fedor

N1 - Funding Information: \ast Received by the editors August 16, 2019; accepted for publication (in revised form) March 23, 2020; published electronically June 15, 2020. https://doi.org/10.1137/19M1281861 Funding: Supported by the Russian Scientific Foundation, grant 17-71-20153. \dagger National Research University Higher School of Economics, Soyuza Pechatnikov str., 16, St. Petersburg, Russian Federation (matelk@mail.ru). \ddagger Saint Petersburg State University, Faculty of Mathematics and Mechanics; St. Petersburg Department of V. A. Steklov Institute of Mathematics of the Russian Academy of Sciences (fedyapetrov@gmail.com). Publisher Copyright: Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - Let m(n, r) denote the minimal number of edges in an n-uniform hypergraph which is not r-colorable. It is known that for a fixed n one has cnrn < m(n, r) < Cnrn. We prove that for any fixed n the sequence ar:= m(n, r)/rn has a limit, which was conjectured by Alon. We also prove the list colorings analogue of this statement.

AB - Let m(n, r) denote the minimal number of edges in an n-uniform hypergraph which is not r-colorable. It is known that for a fixed n one has cnrn < m(n, r) < Cnrn. We prove that for any fixed n the sequence ar:= m(n, r)/rn has a limit, which was conjectured by Alon. We also prove the list colorings analogue of this statement.

KW - Erdős-Hajnal problem

KW - Hypergraph coloring

KW - Subadditivity

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

U2 - 10.1137/19M1281861

DO - 10.1137/19M1281861

M3 - Article

AN - SCOPUS:85092267755

VL - 34

SP - 1326

EP - 1333

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -

ID: 75247704