Estimating the r-colorability threshold for a random hypergraph

Autor:	Dmitry A. Shabanov
Rok vydání:	2020
Předmět:	Binomial distribution Combinatorics Hypergraph Linear function (calculus) Applied Mathematics Discrete Mathematics and Combinatorics Expected value Mathematics
Zdroj:	Discrete Applied Mathematics. 282:168-183
ISSN:	0166-218X
DOI:	10.1016/j.dam.2019.10.031
Popis:	The paper deals with estimating the r -colorability threshold for a random k -uniform hypergraph in the binomial model H ( n , k , p ) . We consider the sparse case, when the expected number of edges is a linear function of n , p n k = c n , and c > 0 , k ⩾ 4 , r ⩾ 3 are some fixed constants. We show that if c r k − 1 ln r − 1 2 ln r − r − 1 r + O ( k 2 r 1 − k ∕ 3 ln r ) then H ( n , k , c n ∕ n k ) is r -colorable with probability tending to 1 as n → ∞ .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::e74d5e797c8efc3f2393b64b265a346c https://doi.org/10.1016/j.dam.2019.10.031 Zobrazit plný text záznamu Full Text from ScienceDirect