Extremal edge polytopes

zbMATH Open1300.05145arXiv1307.6708MaRDI QIDQ405274FDOQ405274

Authors: Tuan Tran, Günter M. Ziegler 

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1307.6708

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• The number of edges of the edge polytope of a finite simple graph
• scientific article; zbMATH DE number 3929064
• The smallest normal edge polytopes with no regular unimodular triangulations
• Separating hyperplanes of edge polytopes
• scientific article; zbMATH DE number 2068105

zbMATH Keywords

0/1-polytopesedge polytopes of graphsextremal f-vectorsnumber of facetspseudorandom graphssubpolytopes of a hypersimplexTurán numbers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Cites Work

• Normal polytopes arising from finite graphs
• Compressed polytopes, initial ideals and complete multipartite graphs
• Title not available (Why is that?)
• Quasi-random graphs
• On cliques in graphs
• Ramanujan graphs
• Über ein Problem von K. Zarankiewicz
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• Minimal Regular Graphs of Girths Eight and Twelve
• Proofs from THE BOOK
• Polarities and \(2k\)-cycle-free graphs
• The Moore bound for irregular graphs
• Pseudo-random graphs
• Title not available (Why is that?)
• Testing subgraphs in large graphs
• On a conjecture of Erdős and Simonovits: even cycles
• On the equations of the edge cone of a graph and some applications
• Extremal properties of \(0/1\)-polytopes
• The size of bipartite graphs with a given girth
• Separating hyperplanes of edge polytopes
• A note on graphs without short even cycles
• Lower bound for the maximal number of facets of a 0/1 polytope
• Simple polytopes arising from finite graphs
• Explicit representations of the edge cone of a graph
• Symbolic Rees algebras, vertex covers and irreducible representations of Rees cones
• On the 3-local profiles of graphs
• On Minimal graphs of maximum even girth
• On 0-1 polytopes with many facets
• Roots of Ehrhart polynomials arising from graphs

Cited In (18)

• Explicit representations of the edge cone of a graph
• Edge connectivity of the vertices of polyhedra
• The smallest normal edge polytopes with no regular unimodular triangulations
• On Dantzig figures from graded lexicographic orders
• Generalized multiplicities of edge ideals
• Separating hyperplanes of edge polytopes
• Extreme points of discrete location polyhedra
• Incidence graphs and unneighborly polytopes
• Arithmetic aspects of symmetric edge polytopes
• Many faces of symmetric edge polytopes
• The excess degree of a polytope
• Any finite group is the group of some binary, convex polytope
• Facets and facet subgraphs of symmetric edge polytopes
• Elementary moves on lattice polytopes
• Laplacian simplices
• Existence of a regular unimodular triangulation of the edge polytopes of finite graphs
• Polyhedral results for the edge capacity polytope.
• The number of $4$-cycles and the cyclomatic number of a finite simple graph

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)