Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem (Q405143): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:11, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem |
scientific article |
Statements
Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem (English)
0 references
4 September 2014
0 references
Summary: Treewidth is an important and well-known graph parameter that measures the complexity of a graph. The Kneser graph Kneser\((n,k)\) is the graph with vertex set \(\binom{[n]}{k}\), such that two vertices are adjacent if they are disjoint. We determine, for large values of \(n\) with respect to \(k\), the exact treewidth of the Kneser graph. In the process of doing so, we also prove a strengthening of the Erdős-Ko-Rado theorem (for large \(n\) with respect to \(k\)) when a number of disjoint pairs of \(k\)-sets are allowed.
0 references
Kneser graph
0 references
treewidth
0 references
separators
0 references
Erdős-Ko-Rado
0 references