Revlex-initial 0/1-polytopes (Q2497967)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Revlex-initial 0/1-polytopes
scientific article

    Statements

    Revlex-initial 0/1-polytopes (English)
    0 references
    0 references
    0 references
    4 August 2006
    0 references
    The authors of this article examine certain polytopes whose vertices are a subset of the vertices of the unit cube, specifically, the vertices (elements of \(\{0,1\}^d\)) consist of all binary representations of numbers \(0,1,\dots,n-1\) for some \(n\). Such polytopes are called revlex-initial 0/1-polytopes. The work is motivated by experiments by the authors with certain convex hull algorithms. The algorithms were more efficient than the authors expected, and they found that intermediate steps of the algorithms tended to be working with polytopes which were similar to revlex-initial 0/1-polytopes. The authors charaterise the facets of revlex-initial 0/1-polytopes, and find systems of linear inequalities that yield the polytopes. The vertex-edge graphs of the polytopes are described, and the authors calculate the number of edges and average degree of the graphs, showing them to be surprisingly sparse. They also show that the edge-expansion is at least one, supporting a conjecture by Mihail and Vazirani. Some graphs are given showing the quantities calculated for wide ranges of \(n\), and other graphs given showing the computational efficiency of the convex hull algorithms applied to random 0/1-polytopes.
    0 references
    0/1 polytope
    0 references
    extremal f-vector
    0 references
    facets
    0 references
    edges
    0 references
    graph
    0 references
    edge expansion
    0 references
    convex hull algorithm
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references