Hypergraphs with many Kneser colorings

DOI10.1016/J.EJC.2011.09.025zbMATH Open1239.05133arXiv1102.5543OpenAlexW2066501202WikidataQ105583607 ScholiaQ105583607MaRDI QIDQ412274FDOQ412274

Hanno Lefmann, Carlos Hoppen, Yoshiharu Kohayakawa

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: For fixed positive integers $r,k$ and $ell$ with $1leqell<r$ and an $r$-uniform hypergraph $H$, let $kappa(H,k,ell)$ denote the number of $k$-colorings of the set of hyperedges of $H$ for which any two hyperedges in the same color class intersect in at least $ell$ elements. Consider the function $KC(n,r,k,ell)=ma{x}_{Hin{mathcalH}_n}kappa(H,k,ell)$, where the maximum runs over the family ${mathcalH}_n$ of all $r$-uniform hypergraphs on $n$ vertices. In this paper, we determine the asymptotic behavior of the function $KC(n,r,k,ell)$ for every fixed $r$, $k$ and $ell$ and describe the extremal hypergraphs. This variant of a problem of ErdH{o}s and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the ErdH{o}s--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {�f 12} (1961), 313--320].

Full work available at URL: https://arxiv.org/abs/1102.5543

Recommendations

• Kneser colorings of uniform hypergraphs
• On the chromatic number of generalized Kneser hypergraphs
• Edge-colorings of uniform hypergraphs avoiding monochromatic matchings
• The Chromatic Number of Kneser Hypergraphs
• Colorations Extrêmes Dans Les Hypergraphes

zbMATH Keywords

\(r\)-uniform hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Title not available (Why is that?)
• The complete intersection theorem for systems of finite sets
• Kneser's conjecture, chromatic number, and homotopy
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The number of graphs without forbidden subgraphs
• Title not available (Why is that?)
• The typical structure of graphs without given excluded subgraphs
• Generalized Kneser coloring theorems with combinatorial proofs
• The maximum number of \(K_{3}\)-free and \(K_{4}\)-free edge 4-colorings
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• Title not available (Why is that?)
• The Turán number of the Fano plane
• Triple Systems Not Containing a Fano Configuration
• Edge colourings of graphs avoiding monochromatic matchings of a given size
• On Colourings of Hypergraphs Without Monochromatic Fano Planes
• Asymptotic enumeration and a 0-1 law for $m$-clique free graphs
• Hypergraphs with many Kneser colorings
• An Unstable Hypergraph Problem with a Unique Optimal Solution
• Exact Results on the Number of Restricted Edge Colorings for Some Families of Linear Hypergraphs
• A structural result for hypergraphs with many restricted edge colorings
• The asymptotic number of triple systems not containing a fixed one

Cited In (17)

• An Unstable Hypergraph Problem with a Unique Optimal Solution
• Rainbow Erdös--Rothschild Problem for the Fano Plane
• Edge-colorings of graphs avoiding complete graphs with a prescribed coloring
• Hypergraphs with many Kneser colorings
• Colourings without monochromatic disjoint pairs
• Colouring set families without monochromatic \(k\)-chains
• Integer colorings with forbidden rainbow sums
• Integer colorings with no rainbow 3-term arithmetic progression
• Edge colorings of graphs avoiding some fixed monochromatic subgraph with linear Turán number
• A coloring problem for intersecting vector spaces
• Maximum number of sum-free colorings in finite abelian groups
• Edge-colorings of uniform hypergraphs avoiding monochromatic matchings
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• Uniform hypergraphs with many edge‐colorings avoiding a fixed rainbow expanded complete graph
• Edge-colorings of graphs avoiding fixed monochromatic subgraphs with linear Turán number
• The multichromatic numbers of some Kneser graphs
• Edge-colorings avoiding a fixed matching with a prescribed color pattern

This page was built for publication: Hypergraphs with many Kneser colorings

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