Photo from wikipedia
We study the threshold probability for the property of existence of a special-form $$r$$ -coloring for a random $$k$$ -uniform hypergraph in the $$H(n,k,p)$$ binomial model. A parametric set of $$j$$… Click to show full abstract
We study the threshold probability for the property of existence of a special-form $$r$$ -coloring for a random $$k$$ -uniform hypergraph in the $$H(n,k,p)$$ binomial model. A parametric set of $$j$$ -chromatic numbers of a random hypergraph is considered. A coloring of hypergraph vertices is said to be $$j$$ -proper if every edge in it contains no more than $$j$$ vertices of each color. We analyze the question of finding the sharp threshold probability of existence of a $$j$$ -proper $$r$$ -coloring for $$H(n,k,p)$$ . Using the second moment method, we obtain rather tight bounds for this probability provided that $$k$$ and $$j$$ are large as compared to $$r$$ .
Journal Title: Problems of Information Transmission
Year Published: 2022
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!