Hypergraphs with many Kneser colorings

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

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

zbMATH Keywords

\(r\)-uniform hypergraph

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypergraphs with many Kneser colorings
• A structural result for hypergraphs with many restricted edge colorings
• 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
• Generalized Kneser coloring theorems with combinatorial proofs
• The number of graphs without forbidden subgraphs
• The Turán number of the Fano plane
• Edge Colourings of Graphs Avoiding Monochromatic Matchings of a Given Size
• The maximum number of K ₃ -free and K ₄ -free edge 4-colorings
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On Colourings of Hypergraphs Without Monochromatic Fano Planes
• The typical structure of graphs without given excluded subgraphs
• Asymptotic enumeration and a 0-1 law for $m$-clique free graphs
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• THE NUMBER OF EDGE COLORINGS WITH NO MONOCHROMATIC CLIQUES
• An Unstable Hypergraph Problem with a Unique Optimal Solution
• Exact Results on the Number of Restricted Edge Colorings for Some Families of Linear Hypergraphs
• Triple Systems Not Containing a Fano Configuration
• The asymptotic number of triple systems not containing a fixed one

Related Items (17)

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

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