Small Littlewood-Richardson coefficients
This site contains a Java implementation of the algorithms described in the paper "Deciding Positivity of Littlewood-Richardson Coefficients" and the paper "Small Littlewood-Richardson coefficients":
This applet provides an algorithm to decide the positivity of the Littlewood-Richardson coefficient and to compute small Littlewood-Richardson coefficients.
The main window displays a triangular graph visualized with black dots and edges.
Diagonals of flat rhombi are not drawn.
The blue arrows on the dual graph of the triangular graph represent a hive flow.
The input partitions lambda, mu and nu are displayed on the border of the triangular graph.
Furthermore, in the upper left corner, the current step size is shown.
The border edges of the triangular graph are either drawn thin, thick gray or thick black,
depending on whether these edges are far away from their throughput bound ("big edges"), near their throughput bound ("small edges") or already reached their throughput bound, respectively.
The algorithm searches for shortest paths from thin border edges on the right or bottom to thin border edges on the left.
If no such path is found, then the step size is decreased, which leads to some thick gray edges becoming thin.
List of commmands:
- new partitions
- You can input a triple of partitions, which are nonincreasing sequences of natural numbers.
The triple (lambda, mu, nu) must satisfy |nu|=|lambda|+|nu|.
- start again
- You start again with the zero flow and the same partitions.
- You do one step in the algorithm for deciding positivity.
There are three possibilities: (1) Find a shortest path from the right or bottom to the left through thin border edges,
which is drawn in red. (2) Augment units according to the stepsize along this path. (3) Decrease the stepsize if no path is found.
- Immediately find an optimal hive flow. This is equivalent to repeatedly pressing the step button.
- Once a capacity achieving hive flow is found, more such hive flows are listed by pressing this button.
This executes one expansion step in the breadth-first-search through the graph of all integral hive flows with fixed border constraints.
You will be asked to input a threshold to speed up the algorithm.
Implementation by Christian Ikenmeyer