The Young graph of partitions

Diagrams are English Young diagrams and addable nodes are those of Removable and addable nodes; $[\lambda ]$ denotes the diagram of a partition $\lambda$ (Partitions, English diagrams, and conjugation).

The Young graph is the directed graph whose

• vertices are all partitions $\lambda$, including $\lambda =\mathrm{\varnothing }$ and including partitions of every size $n\ge 0$; and
• directed edges are the pairs $(\lambda ,\nu )$ for which $\nu$ is a partition and there is an addable node $y$ of $\lambda$ with $[\nu ]=[\lambda ]\cup \{y\}$, the edge pointing from $\lambda$ to $\nu$.

An edge $\lambda \to \nu$ therefore always joins a partition of some $n$ to a partition of $n+1$: inserting a node raises the size by one. The rank, or size, of a vertex $\lambda$ is $\mathrm{\mid }\lambda \mathrm{\mid }$. We say that $\lambda \to \nu$ adds the unique node $[\nu ]\setminus [\lambda ]$. A path in the Young graph is a finite sequence ${\lambda }^{(0)}\to {\lambda }^{(1)}\to \cdots \to {\lambda }^{(k)}$ of edges; its endpoints are ${\lambda }^{(0)}$ and ${\lambda }^{(k)}$, and its length is $k$. Paths of length $0$ are the single vertices.

The edge relation is well defined as a set of ordered pairs: by Removable and addable nodes, for an addable node $y$ the partition $\nu$ with $[\nu ]=[\lambda ]\cup \{y\}$ is unique, and conversely the node $[\nu ]\setminus [\lambda ]$ determines $\nu$ from $\lambda$; hence distinct addable nodes of $\lambda$ give distinct edges out of $\lambda$, and there are no multiple edges. The empty partition has $\mathrm{Add}(\mathrm{\varnothing })=\{(1,1)\}$, so its unique edge points to $(1)$, while $\mathrm{Rem}(\mathrm{\varnothing })=\mathrm{\varnothing }$, so no edge points into $\mathrm{\varnothing }$.

• Layering and acyclicity. Since every edge raises the size by one, every directed path from $\lambda$ to $\mu$ has length exactly $\mathrm{\mid }\mu \mathrm{\mid }-\mathrm{\mid }\lambda \mathrm{\mid }$; in particular $\lambda \to \nu$ and $\nu \to \lambda$ can never both occur, no directed cycle exists, and the vertices of a fixed size form an independent layer. Paths of length $k$ from $\lambda$ end at partitions of size $\mathrm{\mid }\lambda \mathrm{\mid }+k$.

• Locally finite, globally infinite. A partition $\lambda$ has at most $\mathrm{\ell }(\lambda )+1$ addable nodes, because an addable node lies at a row end $(i,{\lambda }_i+1)$ with $i=1$ or ${\lambda }_{i-1}>{\lambda }_i$, or is the node $(k+1,1)$ opening one new row; a finitely supported region of the plane can be added to a fixed diagram in only finitely many ways, so $\lambda$ has finitely many outgoing edges. Likewise, each $\nu$ has finitely many incoming edges, since a partition of $n+1$ has finitely many removable nodes. The vertex set is countably infinite, with a finite layer for each $n$: every partition of $n\ge 1$ is a list of at most $n$ entries in $\{1,\dots ,n\}$, and rank $0$ consists only of $\mathrm{\varnothing }$. There is at least one vertex at every rank.

• Row endpoints that are not addable give no edge. In $\lambda =(2,2)$ the row end $(2,3)$, a third box in the second row, is not addable: addability of $(i,{\lambda }_i+1)$ requires $i=1$ or ${\lambda }_{i-1}>{\lambda }_i$, and here ${\lambda }_1={\lambda }_2=2$. No partition of $5$ contains $(2,2)$ and $(2,3)$ without containing $(1,3)$, so the attempt to add $(2,3)$ produces no vertex and no edge. The actual edges out of $(2,2)$ are the edge to $(3,2)$, adding the addable node $(1,3)$, and the edge to $(2,2,1)$, adding the addable node $(3,1)$ that opens the third row. For partitions $\lambda$ and $\nu$ with $\mathrm{\mid }\nu \mathrm{\mid }=\mathrm{\mid }\lambda \mathrm{\mid }+1$, containment $[\lambda ]\subseteq [\nu ]$ is equivalent to an edge $\lambda \to \nu$: their unique difference node is addable because the enlarged diagram is already a Young diagram.