Optimization over Young diagrams
- PDF / 213,639 Bytes
- 4 Pages / 439.37 x 666.142 pts Page_size
- 82 Downloads / 195 Views
Optimization over Young diagrams Shmuel Onn1 Received: 3 September 2020 / Accepted: 22 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider the problem of finding a Young diagram minimizing the sum of evaluations of a given pair of functions on the parts of the associated pair of conjugate partitions. While there are exponentially many diagrams, we show it is polynomial time solvable. Keywords Young diagram · Number partition · Discrete optimization
1 Introduction For a Young diagram , let n = || be the number of cells, let λ n be the partition of n whose i-th part λi is the number of cells in the i-th row, and let λ∗ n be the conjugate partition of n whose j-th part λ∗j is the number of cells in the j-th column, so that λ∗j = |{i : λi ≥ j}|. For function f : [n] → Z let f (λ) = i f (λi ) be the sum of evaluations of f on the parts of λ. See [1] for more information on Young diagrams and partitions and their many applications. We consider here the following algorithmic problem. Optimization over Young diagrams Given n and functions f , f ∗ : [n] → Z, find a Young diagram which minimizes f (λ) + f ∗ (λ∗ ). Equivalently, solve min{ f (λ) + f ∗ (λ∗ ) : λ n}. Example 1.1 Let n = 6 and f (k) = f ∗ (k) = k 2 . Then, there are 11 Young diagrams with λ = (6), (5, 1), (4, 2), (4, 12 ), (32 ), (3, 2, 1), (3, 13 ), (23 ), (22 , 12 ), (2, 14 ), (16 ), λ∗ = (16 ), (2, 14 ), (22 , 12 ), (3, 13 ), (23 ), (3, 2, 1), (4, 12 ), (32 ), (4, 2), (5, 1), (6).
B 1
Shmuel Onn [email protected] Technion - Israel Institute of Technology, Haifa, Israel
123
Journal of Algebraic Combinatorics
Computing the objective function f (λ) + f ∗ (λ∗ ) exhaustively for all, we find that the unique optimal one is the self-conjugate λ = λ∗ = (3, 2, 1) with value (32 + 22 + 12 ) + (32 + 22 + 12 ) = 28. The number of Young diagrams is exponential in n and so solution by exhaustive search in general is prohibitive. Nonetheless, we show that the problem is polynomial time solvable. Theorem 1.2 Optimization over Young diagrams can be done in time polynomial in n.
2 Proof We begin with a construction of Young diagrams which will be necessary for our purposes. The type of a Young diagram and of the associated partition λ is the number of distinct parts of λ. It is easy to see that λ and λ∗ have the same type which, assuming that the diagram is drawn according to the English convention, is equal to the number of “southeast corners” of . If || = n and has type k so λ = (r1c1 , . . . , rkck ) k k for some r > · · · > r ≥ 1 and some c , . . . , c ≥ 1, then n = c r ≥ 1 k 1 k i i i=1 i=1 i √ 11 so k < 2n. For instance, √ λ = (19, . . . , 2, 1 ) is a partition of n = 200 of maximum 2n. type k = 19 < 20 = √ Let 1 ≤ k < 2n and let n ≥ r1 > · · · > rk > rk+1 = 0 and 0 = c0 < c1 < · · · < ck ≤ n. These numbers define the Young diagram of type k which, for i = 1, . . . , k, has ci − ci−1 rows with ri cells and ri − ri+1 columns with ci cells, with partition and conjugate partition
Data Loading...
