Mathematics – Combinatorics
Scientific paper
2011-02-27
Mathematics
Combinatorics
39 pages
Scientific paper
For fixed positive integers $r, k$ and $\ell$ with $1 \leq \ell < 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)=\max_{H\in{\mathcal H}_{n}} \kappa (H, k,\ell) $, where the maximum runs over the family ${\mathcal H}_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 Erd\H{o}s and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the Erd\H{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, {\bf 12} (1961), 313--320].
Hoppen Carlos
Kohayakawa Yoshiharu
Lefmann Hanno
No associations
LandOfFree
Hypergraphs with many Kneser colorings (Extended Version) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Hypergraphs with many Kneser colorings (Extended Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypergraphs with many Kneser colorings (Extended Version) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-54245