Antiwebs are rank-perfect (Q1885339)

From MaRDI portal
Revision as of 21:13, 28 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Antiwebs are rank-perfect
scientific article

    Statements

    Antiwebs are rank-perfect (English)
    0 references
    0 references
    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
    0 references
    0 references
    stable set polytope
    0 references
    rank constraints
    0 references
    antiwebs
    0 references