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
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.