In this post we are going to explore integer partitions and its Ferrer (Young) diagram properties and introduce integer partition lattice. Also we are going to explore graphical integer partitions (for which there exists a graph), their position in a lattice and threshold graphs which correspond to maximal graphical partitions. Kohnert's criterion is used to determine if a partition is graphical and in edge cases maximal (corresponding to threshold graph). The C++ library which is based on the material discussed in this post includes algorithms that find threshold graph from specified graph, maximal graphical integer partition from specified graphical partition, shortest maximizing chain and other. These algorithms use increasing edge rotation for graphs.

Integer partitions

What is integer partition? The definition is extremely simple: it is sum of numbers resulting in an integer: \( 10 = 1+3+6\)

You can also write it down as a descending sequence of numbers \( (6, 3 , 1)\). So for arbitrary integer n its integer partition is:

\[ (a_1, a_2, a_3, ..., a_k), where  n = a_1 + a_2 + a_3 + ... + a_k  and  a_1 \geq a_2 \geq a_3 \geq ... \geq a_k\]

Ferrers or Young diagram for integer partition is a sequence of columns consisting of blocks, where first column corresponds to \(a_1\), second to \(a_2\) and so on.

An ascending block movement is an operation which transforms one valid integer partition into another in a specific way:

\[ (a_1, ..., a_i + 1, ..., a_j - 1, ..., a_k), where  a_1 \geq a_2 \geq a_3 \geq ... \geq a_k  and  i < j \]

For example: \( (6, 3, 1) \rightarrow (7, 3) \)

A basic ascending block movement is that which cannot be split into two or more ascending block movements. The block movement above was not basic as it can be split in two ascending block movements: \((6, 3, 1) \rightarrow (6, 4) \rightarrow (7, 3)\). An example of a basic block movement is: \( (2, 1, 1, 1) \rightarrow (2, 2, 1) \):

Note that moving the fourth block to the third position is impossible since it would give us invalid integer partition \( (2, 1, 2, 1) \). It is invalid because \( a_2 = 1 < a_3 = 2 \). Obviously, the same way we can define descending basic block movement. I will skip definition for brevity.

Now let's define partial order on the integer partitions set. Let \( \lambda_1 \) and \( \lambda_2 \) be integer partitions for some number \( n \).

\[ \lambda_1 \leq \lambda_2 \Leftrightarrow \exists m_1, ..., m_k: m_1(\lambda_1) = a_2, m_2(a_2) = a_3, ..., m_k(a_k) = \lambda_2 \]

where \( m_1, ..., m_k \) – basic ascending block movements and \(a_2, ..., a_k \) – valid integer partitions of \( n \). This partially ordered set will also be a natural partition lattice for \(n\) which we will call \(NPL(n)\).

The green marked elements are called maximal graphical partitions, which will be described in details later. If we define an operation of adding the block in the end like this:

\[ (a_1, a_2, ..., a_k) \longrightarrow (a_1, a_2, ...,a_k, 1) \]

And extend operator \(\leq\) like this:

\[ \lambda_1 \leq \lambda_2 \Leftrightarrow \exists f_1, ..., f_k: f_1(\lambda_1) = a_2, f_2(a_2) = a_3, ..., f_k(a_k) = \lambda_2 \]

where \(\lambda_1\) and \(\lambda_2\) are integer partitions for some integers \(n\) and \(m\),  \(f_1...f_k\) each is either ascending basic block movement or block addition to the right side and \(a_2...a_k\) are valid integer partitions.

Then we get natural partition lattice for all integers (\(NPL\)):

Now let's explore some properties of Ferrer's diagrams of integer partitions:

The largest square of blocks contained in a Ferrer's diagram is called "Durfee square".

The top row of the Durfee square and above is called "head" and is denoted as \(hd(\lambda)\) of the integer partition.

The blocks to the right of the Durfee square are called "conjugate tail". This is denoted as \(tl^{\ast}(\lambda)\).

A conjugate integer partition is a partition that you get if you mirror the original partition across bottom-left to top-right diagonal. Conjugate to \(\lambda = (6, 3 , 1, 1)\) would be \(\lambda^{\ast} = (4, 2, 2, 1, 1, 1)\). And the tail of the \(\lambda = (6, 3 , 1, 1)\) then would be \((2)\). In other words \(tl(\lambda) = (2)\).

We call the partition graphical if there exists graph \(G\) such that \((v_1, v_2, ..., v_k)\) is a valid integer partition where \(v_i\) are degrees of vertices of \(G\) and \(v_1 \geq v_2 \geq ... \geq v_k\). The most interesting fact is probably the Kohnert's criterion and its consequences.

Kohnert's criterion

An even integer partition \(\lambda\) is graphical if and only if \(hd(\lambda) \leq tl(\lambda)\).

Also, \(\lambda\) is called maximal graphical partition if \(hd(\lambda) = tl(\lambda)\). Scroll up to \(NPL(10)\) and look at the highlighted partitions: they are all maximal graphical.

Threshold graphs

By definition a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations:

1. Addition of a single isolated vertex to the graph.
2. Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices.

Let's define simple operations on graphs called edge rotations:

A triple of vertices \(A, B, C\) in a graph \(G = <V, E>\) such that \(AB \in E\) and     \(BC \not\in E\) is called increasing (or lifting) if \(deg(A) \leq deg(C)\) and decreasing (or lowering) if \(deg(A) \geq 2 + deg(C)\).

If there is no increasing edge rotation in graph \(G\) it comes out that \(G\) is a threshold graph. If we consider integer partition corresponding to G we will find out that it is maximal graphical.

In the example above the head of the integer partition is equal to its tail therefore it is maximal graphical and corresponds to the threshold graph.

Algorithm

The question rises whether we can transform a given graph into a threshold graph using increasing edge rotations, and if we can what is the shortest sequence of such transformations.

It comes out we can always do that because increasing edge rotation always corresponds to ascending block movement and transforms given graphical partition into greater (in the lattice).

Using simple breadth first search (BFS) and increasing edge rotation we can find every shortest transformation sequence that converts our graph into a threshold graph.

You can find implementation of this algorithm and others in this C++ threshold graph and integer partition library.

References

1. On maximal graphical partitions that are the nearest to a given graphical partition (in russian language) - V. A. Baransky, T. A. Senchonok
2. On threshold graphs and implementation of graphical partitions (in russian language) - V. A. Baransky, T. A. Senchonok
3. On natural number partition lattice (2015) (in russian language) - V. A. Baransky, T. A. Senchonok, T. A. Koroleva
4. On lattice of partitions of all natural numbers (2016) (in russian language) - V. A. Baransky, T. A. Senchonok, T. A. Koroleva
5. New algorithm of generation of graphical sequences (2016) (in russian language) - V. A. Baransky, T. A. Senchonok, T. I. Nadymova
6. On maximal graphical partitions (2017) (in russian language) - V. A. Baransky, T. A. Senchonok
7. Natural numbers partitions and chromatic uniqueness of graphs (2008) (in russian language) - T. A. Koroleva
8. Graphical sequences and their generation algorithms (2016) (in russian language) - T. I. Nadymova

Wikipedia: Threshold graph, Integer partition, Lattices as partially ordered sets