Treewidth of the Kneser graph and the Erdős-Ko-Rado theorem (Q405143): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C12 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C75 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D05 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6340146 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Kneser graph | |||
Property / zbMATH Keywords: Kneser graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
treewidth | |||
Property / zbMATH Keywords: treewidth / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
separators | |||
Property / zbMATH Keywords: separators / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Erdős-Ko-Rado | |||
Property / zbMATH Keywords: Erdős-Ko-Rado / rank | |||
Normal rank |
Revision as of 17:17, 29 June 2023
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