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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .