Multiset Colorings of Random Graphs Across Density Regimes
En palabras de los autores
We show that almost every graph admits a partition of its vertex set into three parts such that no two adjacent vertices have the same number of neighbors in each of the three parts. Equivalently, for , with high probability, improving the previously known bound of five. Here denotes the multiset chromatic number of , the minimum number of parts in a vertex partition whose neighbor-count vectors distinguish every pair of adjacent vertices. In fact, the three-part bound holds for every fixed . More generally, for every fixed , satisfies with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial--Radhakrishnan theory of essential covers. We also determine how grows when the graph is polynomially close to complete. For every fixed and , with high probability . Thus . The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov'asz Local Lemma.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.