Clique number of a generalized Johnson graph $J(n, k, k/2)$

Question

The generalized Johnson graph $J(n,k,r)$ is defined to be the graph whose vertex set is the set of all k-element subsets of ${1,2,…,n}$, and with two vertices adjacent iff their intersection has exactly r elements. Now, is there some upper bound for the clique number of $J(n,k,k/2)$? It should be bounded by $n$ or something close to.

Answer 1

Represent the vertices by $01$-vectors of length $n$, each with exactly $k$ entries equal to 1. Let $C$ be a clique. I claim that the vectors representing the vertices in $C$ are linearly independent, whence it follows that $|C|\le n$.

To prove the claim, let $G$ be the Gram matrix of the vectors belonging to $C$. If $J$ is the all-ones matrix, we have \[ G = \frac{k}2(I+J) \] and since $I+J$ is invertible, $G$ is invertible and therefore it is the Gram matrix of a linearly independent set of vectors.