0
$\begingroup$

Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common are joined by an edge.

For the Kneser graphs, it is readily seen to be $\left\lfloor\frac{n}{k}\right\rfloor$. For the generalized version, is it $\sum_{i=0}^{t}\left\lfloor\frac{n+i}{k+i}\right\rfloor$. Any closed forms for this sum?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ This is the question on spherical Boolean codes (maximal number of points of Hamming weight $k$ in $\{0,1\}^n$ with mutual distances at least $2(k-t)$. Unlikely (to say the least) there is an easy formula. Your formula is not true: if $k$ is about $n/2$, say, and $t=k-1$ there are cliques of exponentially large size. $\endgroup$
    – Fedor Petrov
    Commented Jan 6 at 19:23

0

Reset to default

You must log in to answer this question.