DEGREE SEQUENCES AND MAJORIZATION

A classical result concerning majorization is: given two nonnegative integer sequences a and b such that a majorizes b, a rearrangement of b can be obtained from a by a sequence of unit transformations. A recent result says that a degree sequence is a threshold sequence (degree sequence of a threshold graph) if and only if it is not strictly majorized by any degree sequence. Motivated by this, we define the majorization gap of a degree sequence to be the minimum number of successive reverse unit transformations required to transform it into a threshold sequence. We derive a formula for the majorization gap by establishing a lower bound for it and exhibiting reverse unit transformations achieving the bound. We also discuss the relationship between the majorization gap and the threshold gap (introduced elsewhere), and show that they are equal. The degree sequences having the maximum majorization gap for a fixed number of edges or vertices are characterized.