The polytope of degree partitions

MaRDI QIDQ2500965zbMATH OpenFDO

Authors Yanyan Li

Publication date 30 August 2006

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

Full work available at URL https://arxiv.org/abs/math/0512402, https://eudml.org/doc/126663, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r46.html

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

zbMATH Keywords

degree sequence

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Vertex degrees (05C07)

Abstract: The degree partition of a simple graph is its degree sequence rearranged in weakly decreasing order. The polytope of degree partitions (respectively, degree sequences) is the convex hull of all degree partitions (respectively, degree sequences) of a fixed length. We think of the degree sequence polytope as the symmetrization of the degree partition polytope and the degree partition polytope as the asymmetric part of the degree sequence polytope. The degree sequence polytope is a well studied object with formulas (generating functions) known for its face numbers, volume, and number of lattice points. We study the degree partition polytope and determine its extreme points, edges, and facets. In particular, the degree partition polytope on n vertices has 2^{n-1} extreme points.

Recommendations

• The polytope of degree sequences
• The polytope of degree sequences of hypergraphs
• The polytope of dual degree partitions
• scientific article; zbMATH DE number 17664
• Polytopes of partitions of numbers

Cited in

(12)

• The polytope of degree sequences
• On dynamic threshold graphs and related classes
• Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
• The polytope of dual degree partitions
• A survey of discrete methods in (algebraic) statistics for networks
• The Burge correspondence and crystal graphs
• Geometry of paired comparisons
• scientific article; zbMATH DE number 992951 (Why is no real title available?)
• Relations on generalized degree sequences
• scientific article; zbMATH DE number 5799883 (Why is no real title available?)
• Some approaches for solving the general (t,k)-design existence problem and other related problems
• Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number

This page was built for publication: The polytope of degree partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500965)