Bipartite Subgraph Polytope
Contributed by Laura Galli and
Adam N. Letchford, expanded by Stefan Lörwald.
A set of edges of an undirected graph G is called bipartite, if it does not
contain the edge set of an odd cycle of G. The Bipartite Subgraph
polytope BS(n) is the convex hull of incidence vectors of bipartite
edge sets of a complete undirected graph on n nodes. See for example
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Volume
C.
Note: A facet class is the orbit of the natural action of the symmetric
group S(n) on BS(n). Only one representative of each
facet class is listed in the files.
BS(4)
Status: complete description
3 classes
Vertices
Classes (node permutations) of facets
BS(5)
Status: complete description
5 classes
Vertices
Classes (node permutations) of facets
BS(6)
Status: complete description
6 classes
Vertices
Classes (node permutations) of facets
BS(7)
Status: complete description
17 classes
Vertices
Classes (node permutations) of facets
BS(8)
Status: complete description
85 classes (incomplete description, provided by L. Galli and A.N. Letchford, 2010)
171 classes (complete description, provided by S. Lörwald, 2014)
Vertices
References
F. Barahona, M. Groetschel & A.R. Mahjoub (1985): Facets of the
bipartite subgraph polytope. Math. Oper. Res., 10, 340-358.
L. Galli & A.N. Letchford (2010): Small bipartite subgraph polytopes.
Working paper, Department of Management Science, Lancaster University.
Last modified: May 28, 2014 (SL)