4
votes
Accepted
Independent sets in complement of Kneser graphs
According to [p. 8], Baranyai's theorem [B] implies that the vertex set of the Kneser graph $K(n,k)$ can be partitioned into $\left\lceil\frac{\binom{n}{k}}{\left\lfloor\frac{n}{k}\right\rfloor}\...
- 5,409
4
votes
Accepted
Simpler combinatorial proof for special case of Kneser's conjecture
We have found such a proof together with Gábor Tardos while working on the local chromatic number of Kneser graphs and their relaitives. I try to give a detailed sketch.
Let me use the notation KG(2k+...
3
votes
Chromatic number or independence number of the generalized Kneser Graph
Why are you ruling out $[2n+1]$? I will change the notation to $K(N,k,s)$ meaning vertices the $\binom{N}{k}$ $k$-subsets of $[N]$ with two connected if they intersect in $s$ or fewer elements.
For a ...
- 30.1k
2
votes
Accepted
Line graphs of complete hypergraphs as complement of Kneser graphs
Yes, the correspondence goes the following way: The complete k-uniform Hypergraph has n vertices and the edges are given by all k-element subsets of {1,...,n}. Thus, the line graph has those k-...
- 98
1
vote
Accepted
Variant of Kneser hypergraph with elements appearing more than once
Yes, I think this is the best reference: http://www.sciencedirect.com/science/article/pii/S0097316506000264
- 18.7k
Only top scored, non community-wiki answers of a minimum length are eligible