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.



Line graphs of complete hypergraphs as complement of Kneser graphs
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.


