1
$\begingroup$

A Kneser hypergraph is a hypergraph with the vertices being the subsets of $M=\{1,2,\dots,m\}$ of size $l$ and the edges being the collections of size $r$ of these subsets such that any two subsets are disjoint. The Alon-Frankl-Lovasz theorem gives the chromatic number of this graph.

Has a variant of this been considered, where instead of any two subsets of the collection having to be disjoint (or equivalently, any element $i\in M$ appears in at most one subset of the collection), we require that any element $i\in M$ appears in at most $d$ subsets of the collection for some value $d>1$? If so, is there a corresponding result on the chromatic number?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, I think this is the best reference: http://www.sciencedirect.com/science/article/pii/S0097316506000264

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .