Antiwebs are rank-perfect (Q1885339): Difference between revisions

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\).