pith. sign in

arxiv: 1706.02516 · v1 · pith:EVGZLMI2new · submitted 2017-06-08 · 🧮 math.MG

Generalized cut and metric polytopes of graphs and simplicial complexes

classification 🧮 math.MG
keywords metricpolytopecutpdefinegraphmetporientedcomplexes
0
0 comments X
read the original abstract

Given a graph $G$ one can define the cut polytope CUTP(G) and the metric polytope METP(G) of this graph and those polytopes encode in a nice way the metric on the graph. According to Seymour's theorem, CUTP(G) = METP(G) if and only if K_5 is not a minor of G. We consider possibly extensions of this framework: a) We compute the CUTP(G) and METP(G) for many graphs. b) We define the oriented cut polytope WOMCUTP(G) and oriented multicut polytope OMCUTP(G) as well as their oriented metric version QMETP(G) and WQMETP(G). c) We define an $n$-dimensional generalization of metric on simplicial complexes.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.