5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

This is a really old post, but I saw it and knew the answer, mostly.

In the notes, on that chapter, Godsil and Royle mention that this problem is easier if you know something about Hadamard matrices. The reason for this claim of theirs is that, showing such a clique exists is equivalent to showing that a Hadamard design exists. (For anyone who finds this, you will have to figure out on your own why this is the case. In my opinion it is worth the effort.) These are also sometimes called Balanced Incomplete Block Designs, $(v, k, λ)$-designs, or specifically in this case a $(4n-1,2n-1,n-1)$-design BIBD.

last I checked there are still open questions about the existance of Hadamard matrices. So in the case of the book exercise, you will have to decide what they actually are looking for.

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