Abstract: The "edge polytope" of a finite graph G is the convex hull of the columns of its vertex-edge incidence matrix. We study extremal problems for this class of polytopes. For k =2, 3, 5 we determine the maximum number of vertices of k-neighborly edge polytopes up to a sublinear term. We also construct a family of edge polytopes with exponentially-many facets.
Recommendations
Cites work
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 1538119 (Why is no real title available?)
- A note on graphs without short even cycles
- Compressed polytopes, initial ideals and complete multipartite graphs
- Explicit representations of the edge cone of a graph
- Extremal properties of \(0/1\)-polytopes
- Lower bound for the maximal number of facets of a 0/1 polytope
- Minimal Regular Graphs of Girths Eight and Twelve
- Normal polytopes arising from finite graphs
- On 0-1 polytopes with many facets
- On Graphs that do not Contain a Thomsen Graph
- On Minimal graphs of maximum even girth
- On a conjecture of Erdős and Simonovits: even cycles
- On a problem of K. Zarankiewicz
- On cliques in graphs
- On the 3-local profiles of graphs
- On the equations of the edge cone of a graph and some applications
- Polarities and \(2k\)-cycle-free graphs
- Proofs from THE BOOK
- Pseudo-random graphs
- Quasi-random graphs
- Ramanujan graphs
- Roots of Ehrhart polynomials arising from graphs
- Separating hyperplanes of edge polytopes
- Simple polytopes arising from finite graphs
- Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
- Testing subgraphs in large graphs
- The Moore bound for irregular graphs
- The size of bipartite graphs with a given girth
- Über ein Problem von K. Zarankiewicz
Cited in
(20)- Many faces of symmetric edge polytopes
- Separating hyperplanes of edge polytopes
- Facets and facet subgraphs of symmetric edge polytopes
- Incidence graphs and unneighborly polytopes
- The excess degree of a polytope
- Polyhedral results for the edge capacity polytope.
- Elementary moves on lattice polytopes
- The number of $4$-cycles and the cyclomatic number of a finite simple graph
- Edge connectivity of the vertices of polyhedra
- Generalized multiplicities of edge ideals
- Facets of random symmetric edge polytopes, degree sequences, and clustering
- The smallest normal edge polytopes with no regular unimodular triangulations
- On Dantzig figures from graded lexicographic orders
- Existence of a regular unimodular triangulation of the edge polytopes of finite graphs
- Laplacian simplices
- Faces of directed edge polytopes
- Extreme points of discrete location polyhedra
- Explicit representations of the edge cone of a graph
- Arithmetic aspects of symmetric edge polytopes
- Any finite group is the group of some binary, convex polytope
This page was built for publication: Extremal edge polytopes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405274)
