Colorful Subhypergraphs in Uniform Hypergraphs

  • Meysam Alishahi
Keywords: Chromatic number of hypergraphs, $\mathbb{Z}_p$-Tucker-Ky Fan lemma, Colorful complete hypergraph, $\mathbb{Z}_p$-Box-complex, $\mathbb{Z}_p$-Hom-complex.

Abstract


There are several topological results ensuring in any properly colored graph the existence of a colorful complete bipartite subgraph, whose order is bounded from below by some topological invariants of some topological spaces associated to the graph. Meunier [Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal of Combinatorics, 2014] presented the first colorful type result for uniform hypergraphs. In this paper, we give some new generalizations of the $\mathbb{Z}_p$-Tucker lemma and by use of them, we improve Meunier's result and some other colorful results by Simonyi, Tardif, and Zsbán [Colourful theorems and indices of homomorphism complexes, The Electronic Journal of Combinatorics, 2014] and by Simonyi and Tardos [Colorful subgraphs in Kneser-like graphs, European Journal of Combinatorics, 2007] to uniform hypergraphs. Also, we introduce some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs. A hierarchy between these lower bounds is presented as well.

Published
2017-02-03
Article Number
P1.23