Colorful subhypergraphs in uniform hypergraphs

MaRDI QIDQ510336zbMATH OpenFDO

Authors Meysam Alishahi

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1605.06701, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p23

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(\mathbb{Z}_p\)-box-complex\(\mathbb{Z}_p\)-Hom-complex\(\mathbb{Z}_p\)-Tucker-Ky Fan lemmachromatic number of hypergraphscolorful complete hypergraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

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 $mathbb{Z}_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 ${mKG}^r(mathcalH)$. 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 ${mKG}^r(mathcalH)$ contains a large colorful $r$-partite subhypergraph provided that $r$ is prime. In this paper, we give some new generalizations of $mathbb{Z}_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.

Review text

Summary: 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. \textit{F. Meunier} [Electron. J. Comb. 21, No. 1, Research Paper P1.8, 13 p. (2014; Zbl 1300.05202)] 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 \textit{G. Simonyi} et al. [Electron. J. Comb. 20, No. 1, Research Paper P10, 15 p. (2013; Zbl 1266.05041)] and by \textit{G. Simonyi} and \textit{G. Tardos} [Eur. J. Comb. 28, No. 8, 2188--2200 (2007; Zbl 1125.05042)] 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.

Recommendations

• Colorful subhypergraphs in Kneser hypergraphs
• A contribution to the chromatic theory of uniform hypergraphs
• Coloring uniform hypergraphs with few colors
• On r-chromatic hypergraphs
• Hom complexes and hypergraph colorings

Cites work

• A combinatorical proof of Kneser's conjecture
• A generalization of Gale's lemma
• A generalization of Kneser's conjecture
• A generalization of Tucker's combinatorial lemma with topological applications
• A new coloring theorem of Kneser graphs
• A short proof for Chen's alternative Kneser coloring lemma
• Colorful subgraphs in Kneser-like graphs
• Colorful subhypergraphs in Kneser hypergraphs
• Coloring graphs with locally few colors
• Colourful theorems and indices of homomorphism complexes
• Combinatorial Stokes formulas via minimal resolutions
• Ein Satz über abelsche Gruppen mit Anwendungen auf die Geometrie der Zahlen
• Equivariant Cohomology and Lower Bounds for Chromatic Numbers
• Generalized Kneser coloring theorems with combinatorial proofs
• Hom complexes and hypergraph colorings
• scientific article; zbMATH DE number 4075095 (Why is no real title available?)
• scientific article; zbMATH DE number 3561377 (Why is no real title available?)
• scientific article; zbMATH DE number 3102257 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Local chromatic number, Ky Fan's theorem, and circular colorings
• On the chromatic number of general Kneser hypergraphs
• Simple \(\Sigma_r\)-homotopy types of Hom complexes and box complexes assigned to \(r\)-graphs
• Simplicial complexes of graphs
• Strengthening topological colorful results for graphs
• The chromatic number of almost stable Kneser hypergraphs
• The Chromatic Number of Kneser Hypergraphs
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler

Cited in

(10)

• Colorful induced subgraphs
• New construction of graphs with high chromatic number and small clique number
• A new lower bound for the chromatic number of general Kneser hypergraphs
• Strengthening topological colorful results for graphs
• Coloring subgraphs with restricted amounts of hues
• Colorful subgraphs in Kneser-like graphs
• scientific article; zbMATH DE number 1146221 (Why is no real title available?)
• Coloring properties of categorical product of general Kneser hypergraphs
• Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

This page was built for publication: Colorful subhypergraphs in uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510336)