Colorful Subhypergraphs in Uniform Hypergraphs

2016/05/21 by Alishahi, Meysam
#05C15 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1605.06701

Abstract

There are several topological results ensuring the existence of a large complete bipartite subgraph in any properly colored graph satisfying some special topological regularity conditions. In view of ℤ_p-Tucker lemma, Alishahi and Hajiabolhassan [\it On the chromatic number of general Kneser hypergraphs, Journal of Combinatorial Theory, Series B, 2015] introduced a lower bound for the chromatic number of Kneser hypergraphs \rm KG^r(\mathcal H). Next, Meunier [\it Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal of Combinatorics, 2014] improved their result by proving that any properly colored general Kneser hypergraph \rm KG^r(\mathcal H) contains a large colorful r-partite subhypergraph provided that r is prime. In this paper, we give some new generalizations of ℤ_p-Tucker lemma. Hence, improving Meunier's result in some aspects. Some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs are presented as well.

Related

• Colorful hypergraphs in Kneser hypergraphs
• On some topological and combinatorial lower bounds on chromatic number of Kneser type hyper graphs
• Coloring Properties of Categorical Product of General Kneser Hypergraphs
• Colorful subgraphs in Kneser-like graphs
• Chromatic Number of Random Kneser Hypergraphs