Skip to main content
MathOverflow

Return to Answer

added 45 characters in body
Source Link
AMLimbach
AMLimbach
  • 98
  • 5

SoYes, 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.

So, 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.

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.

Source Link
AMLimbach
AMLimbach
  • 98
  • 5

So, 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.