О дробных (6:3)-раскрасках случайных гиперграфов

Чебышевский сборник. 2026. Т. 27. № 3. С. 74–90.

Здержиков Н. И., Shabanov D. A., Степанов И. Д.

In this article we study one of many possible generalizations of the notion of a proper coloring when applied to hypergraphs. Namely, the so called fractional \((a:b)\)-colorings are dealt with. Such coloring is a way to match each vertex of the hypergraph with exactly \(b\) colors (out of \(a\) available ones), in a manner that no hyperedge has a color corresponding to its every vertex. We analyze the question of existence of a \((6:3)\)-coloring within the scope of random hypergraph theory.

Specifically, we consider the standard uniform model of a \(k\)-uniform random hypergraph \(H(n,k,m)\) with \(n\) vertices and \(m\) edges. We study the problem of finding the threshold probability for a fractional \((6:3)\)-coloring to exist in this model. Within an exponentially small (with respect to \(k\)) margin we estimate the constant \(\hat c\) such that whenever \(m>\hat c\cdot n\) the hypergraph asymptotically almost surely does not possess such a coloring, while when \(m<\hat c\cdot n\), it does.

Keywords: случайные гиперграфы, second moment method, random hypergraphs, метод второго момента, fractional colorings, дробные раскраски

Publication based on the results of: New methods in the study of formal computation models, computer systems and related theoretical computer science problems (2025)