Antiwebs are rank-perfect (Q1885339): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s10288-003-0032-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2036645770 / rank | |||
Normal rank |
Latest revision as of 00:01, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Antiwebs are rank-perfect |
scientific article |
Statements
Antiwebs are rank-perfect (English)
0 references
28 October 2004
0 references
For positive integers \(m\) and \(k\), \(W^k_n\) denotes the graph with vertex set \(\{1, \ldots, n\}\) and edge set \(\{ij: 0< | i-j| \leq k\mod n\}\). A web is a \(W^k_n\) for some \(n\) and \(k\), and an antiweb is the complement of a web. While not any web is rank-perfect, the author points out that it is implied by a result due to \textit{F. B. Shepherd} [``Applying Lehman's theorem to packing problems'', Math. Program. 71, No. 3(A), 353--367 (1995; Zbl 0863.05052)], that all antiwebs are rank-perfect, i.e., the stable set polytope of such a graph \(G\) is completely given by the nonnegativity constraints, \(\forall i\in\{1, \ldots, n\}, x_i\geq 0\), and the rank-constraints, \(\forall I\subseteq\{1, \ldots, n\}, \sum_{i\in I} x_i \leq \alpha(I)\). Where \(\alpha(I)\) is the independence number (the largest number of pairwise nonadjacent vertices) of the subgraph of \(G\) induced by \(I\).
0 references
stable set polytope
0 references
rank constraints
0 references
antiwebs
0 references