clique number of generalized Johnson graph $J(4n-1,2n-1,n-1)$

499 Views Asked by At

The generalized Johnson graph $J(v,k,r)$ is defined to be the graph whose vertex set is the set of all $k$-element subsets of $\{1,2,\ldots,v\}$, and with two vertices adjacent iff their intersection has exactly $r$ elements. I am interested in determining the clique number of $J(4n-1,2n-1,n-1)$.

It can be shown that $J(7,3,1)$ equals 7, as follows. Let $K$ be a clique in $J(7,3,1)$. Without loss of generality, suppose the 3-subset $x=123$ is a vertex in $K$, and let $i \in x$. The number of vertices in $K$ that are neighbors of $x$ and that contain the element $i$ is at most 2. Thus, $K$ contains at most $3 \times 2=6$ other vertices besides $x$. This proves that $K$ has at most 7 vertices. Equality holds because the following 7 vertices form a clique: $123, 145, 167, 246, 257, 347, 356$.

A similar argument shows that $J(11,5,2) \le 11$, but this argument doesn't seem to generalize further.

This is an exercise in [Godsil and Royle, Algebraic Graph Theory] which asks to show that $\omega(J(4n-1,2n-1,n-1)) \le 4n-1$ and to characterize the cases where equality holds.