Since the Johnson graph/triangular graph $J(n,2)$ is the complement of the Kneser graph $K(n,2)$, which is also incidentally the line graph of the complete graph $K_n$, I thought whether the same can be said about the line graphs of the complete hypergraphs $H_n^k$. That is, can we say that the line graphs of the complete hypergraphs $H_n^k$ are isomorphic to the complements of Kneser graphs $K(n,k)$? The Baranyai's theorem and the Erdos-Ko-Rado theorems seem to be pointing out in a similar direction. Any hints? Thanks beforehand.
1 Answer
$\begingroup$
$\endgroup$
1
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-element subsets as vertices and they are adjacent if and only if they intersect non-trivially. The complement graph, thus, has the same vertex set but the vertices are adjacent if and only if they intersect trivially. This is the definition of the Kneser graph.
-
$\begingroup$ So the answer is in the affirmative right! $\endgroup$ Commented Aug 4, 2022 at 16:38