0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ So the answer is in the affirmative right! $\endgroup$
    – vidyarthi
    Commented Aug 4, 2022 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.