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 ErdosKoRado 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 kuniform Hypergraph has n vertices and the edges are given by all kelement subsets of {1,...,n}. Thus, the line graph has those kelement subsets as vertices and they are adjacent if and only if they intersect nontrivially. 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