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

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

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.

Review text

Summary: 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 degree partitions (respectively, degree sequences) of all simple graphs on the vertex set \([n]\). The polytope of degree sequences has been very well studied. In this paper we study the polytope of degree partitions. We show that adding the inequalities \(x_1\geq x_2 \geq \cdots \geq x_n\) to a linear inequality description of the degree sequence polytope yields a linear inequality description of the degree partition polytope and we show that the extreme points of the degree partition polytope are the \(2^{n-1}\) threshold partitions (these are precisely those extreme points of the degree sequence polytope that have weakly decreasing coordinates). We also show that the degree partition polytope has \(2^{n-2}(2n-3)\) edges and \((n^2 -3n + 12)/2\) facets, for \(n\geq 4\). Our main tool is an averaging transformation on real sequences defined by repeatedly averaging over the ascending runs.

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)

• Relations on generalized degree sequences
• On dynamic threshold graphs and related classes
• The Burge correspondence and crystal graphs
• Geometry of paired comparisons
• A survey of discrete methods in (algebraic) statistics for networks
• scientific article; zbMATH DE number 992951 (Why is no real title available?)
• 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
• The polytope of degree sequences
• Inference using noisy degrees: differentially private -model and synthetic graphs
• Number of Vertices of the Polytope of Integer Partitions and Factorization of the Partitioned Number
• The polytope of dual degree partitions

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)