Hypergraphs with many Kneser colorings

Abstract: For fixed positive integers

r, k

and

e l l

with

1 l e q e l l < r

and an

r

-uniform hypergraph

H

, let

k a p p a (H, k, e l l)

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

e l l

elements. Consider the function

K C (n, r, k, e l l) = m a x_{H i n {m a t h c a l H}_{n}} k a p p a (H, k, e l l)

, where the maximum runs over the family

{m a t h c a l H}_{n}

of all

r

-uniform hypergraphs on

n

vertices. In this paper, we determine the asymptotic behavior of the function

K C (n, r, k, e l l)

for every fixed

r

,

k

and

e l l

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].

Recommendations

Cites work

Cited in

(20)

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)