On the Chromatic Numbers of Random Hypergraphs

被引：0

作者：

Demidovich, Yu A. ^{[1
]}

Shabanov, D. A. ^{[1
,2
,3
]}

机构：

[1] Natl Res Univ, Moscow Inst Phys & Technol, Dolgoprudnyi 141701, Moscow Oblast, Russia

[2] Lomonosov Moscow State Univ, Fac Mech & Math, Moscow 119991, Russia

[3] Natl Res Univ, Higher Sch Econ, Moscow 101000, Russia

来源：

DOKLADY MATHEMATICS | 2020年 / 102卷 / 02期

基金：

俄罗斯科学基金会;

关键词：

random hypergraph; chromatic number; second moment method;

D O I：

10.1134/S1064562420050312

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The asymptotic behavior of the chromatic number of the binomial random hypergraph H(n,k,p) is studied in the case when is l >= 4 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 is concentrated in two or three consecutive values, which can be found explicitly as functions of n, p, and k.

引用

页码：380 / 383

页数：4

共 50 条

[31] Bounds on Threshold Probabilities for Coloring Properties of Random Hypergraphs
A. S. Semenov
D. A. Shabanov
Problems of Information Transmission, 2022, 58 : 72 - 101
[32] Chromatic numbers of metric spaces
Raigorodskii A.M.
Journal of Mathematical Sciences, 2008, 154 (4) : 624 - 627
[33] On the Chromatic Numbers of Rational Spaces
Sokolov, A. A.
MATHEMATICAL NOTES, 2018, 103 (1-2) : 111 - 117
[34] Weak Borel chromatic numbers
Geschke, Stefan
MATHEMATICAL LOGIC QUARTERLY, 2011, 57 (01) : 5 - 13
[35] Estimating quantum chromatic numbers
Paulsen, Vern I.
Severini, Simone
Stahlke, Daniel
Todorov, Ivan G.
Winter, Andreas
JOURNAL OF FUNCTIONAL ANALYSIS, 2016, 270 (06) : 2188 - 2222
[36] On the Chromatic Numbers of Rational Spaces
A. A. Sokolov
Mathematical Notes, 2018, 103 : 111 - 117
[37] Independence numbers and chromatic numbers of some distance graphs
A. V. Bobu
O. A. Kostina
A. E. Kupriyanov
Problems of Information Transmission, 2015, 51 : 165 - 176
[38] Uniquely colorable graphs with equal chromatic and game chromatic numbers
Matsumoto, Naoki
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2022, 14 (03)
[39] Degrees in oriented hypergraphs and Ramsey p-chromatic number
Caro, Yair
Hansberg, Adriana
ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (03):
[40] REPEATED DEGREES IN RANDOM UNIFORM HYPERGRAPHS
Balister, Paul
Bollobas, Bela
Lehel, Jeno
Morayne, Michal
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) : 145 - 154

← 1 2 3 4 5 →