|
|||||
|
|
Bounds on Threshold Probabilities for Coloring Properties of Random Hypergraphs |
|
| Authors: | Semenov A S Shabanov D A |
| Affiliation: | 1.Chair of Discrete Mathematics, Department of Innovation and High Technology, Moscow Institute of Physics and Technology (State University), Moscow, Russia ;2.Laboratory of Combinatorial and Geometric Structures, Moscow Institute of Physics and Technology (State University), Moscow, Russia ;3.Department of Probability Theory, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia ;4.Faculty of Computer Science, Higher School of Economics—National Research University, Moscow, Russia ; |
| 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\). |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |
