The polytope of degree partitions

zbMATH Open1100.05022arXivmath/0512402MaRDI QIDQ2500965FDOQ2500965

Authors: Yanyan Li 

Publication date: 30 August 2006

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

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.

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

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

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

zbMATH Keywords

degree sequence

Mathematics Subject Classification ID

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

Cited In (12)

• Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
• On dynamic threshold graphs and related classes
• 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
• Title not available (Why is that?)
• Relations on generalized degree sequences
• Title not available (Why is that?)
• 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
• The polytope of degree sequences

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)