Bounds for threshold probabilities for fractional colorability properties of random hypergraphs

Автор: Shabanov D.A., Shaikheeva T.M.

Журнал: Труды Московского физико-технического института @trudy-mipt

Рубрика: Математика

Статья в выпуске: 3 (63) т.16, 2024 года.

Бесплатный доступ

The paper deals with the well-known problem concerning the threshold probabilities for coloring properties of random hypergraphs. We consider the binomial model of a random k-uniform hypergraph H(n, k, p) in the sparse regime, when the expected number of edges is a linear function of the number of vertices. As the main result we obtain the estimates of the sharp threshold probability for the property of proper (5 : 2)-fractional colorability of H(n, k, p).

Random hypergraphs, fractional colorings, second moment method

Короткий адрес: https://sciup.org/142243261

IDR: 142243261

Статья научная