Extremal Ideals of the Lattice of Multisets
S.L. Bezrukov, V.P. Voronin
We present here constructions of ideals A of the poset of n-vectors (x1 ; :::; xn ) with
integer entries, P ordered P coordinatewise, on which the maximal and minimal values of W' (A) = x2A '( n=1 xi ) are achieved for a given unimodal function i '. As a consequence we get a new approach to prove the well-known ClementsLindstrom Theorem 6].
Let d1 ; :::; dn be arbitrary integers and d1
integer coordinates from the range 0 the number n by dimension of I .
d2 ::: dn. di, for 1 i n. We call I by a grid and
De nition 1 Denote by I the collection of all n-dimensional vectors (x1 ; :::; xn) with
De nition 2 The coordinate sum of a vector x = (x1 ; :::; xn) 2 I is called the weight of x and denoted by kxk. If '(z) is a positive-valued real function de ned for nonnegative z then we call the number W' (x) = '(kxk) by the modi ed weight of x 2 I with respect P
to the function ', and the number W' (A)= A I with respect to '.
x2A W' (x)
by the modi ed weight of a set
De nition 3 A subset A
(y1; :::yn) with yi
I is called ideal, if for any x = (x1 ; :::; xn) 2 A and y = xi for 1 i n it follows y 2 A.
For a lot of applications (see 1,2,3], for example) one has to nd among all the m-element subsets A I a subset, on which an extremal value of some function f is achieved. Usually it is su cient to proceed the search of an extremal subset A in the class of ideals only. Moreover, very often it is possible to choose a function ' such that the value of the function f equals the modi ed weight of the ideal with respect to '. A typical example of such situation is the problem of nding an m-element subset of I with maximal possible number of induced Hamming edges, i.e. the pairs (x; y), x; y 2 A, with (x; y) = 1, where is the Hamming metric 2,3,4,5]. After some simple arguments which allow to restrict 1
the class of considered subsets by ideals, it is not di cult to show that the number of Hamming edges for an ideal A equals W'(A) with '(t) = t. A important aspect in the theory of extremal subsets is the analysis of proof techniques. Such analysis, as a rule, allows not only to understand the structure one works with more deeply, but also to simplify the known proofs, and so to design more powerful methods. It is also always of interest to prove that some problem is a consequence of some other problem. For example, it is known that the mentioned problem of nding an m-element subset with maximal size of f(x; y)g with (x; y) = 1 is equivalent to the problem of nding an m-element ideal with maximal possible weight 4,6]. We will show below that these two problems are equivalent to the well-known Theorem of Clements and Lindstrom 6] (see also Corollary 1) and, in fact, present a new simple proof of it. The main problem we are concerned in this paper with, is to nd an ideal A 2 I of a xed size on which an extremal value of W' (A) is achieved. Such type of function is the general type of a symmetric function, i.e. which depends only of the number of vectors of weight i in A for all i. Denote wi = '(kxk) for kxk = i and d = d1 + ::: + dn. If d1 = ::: = dn = 1, i.e. when I is the n-dimensional unit cube, then the extremal ideals were constructed in 1] in the case when ' is of one of the following types: w0 ::: wi wi+1 ::: wd and w0 ::: wi wi+1 ::: wd: In our paper we prove similar results for arbitrary numbers d1; :::; dn. The paper is organized by the following. The next two sections are devoted to the solution of our problem for some special class of subsets. The main result of these sections is Theorem 1, which is formulated in Section 2. Section 3 consists of the proof of Theorem 1 and in Section 4 with the help of this Theorem we obtain the solutions of our problem for the class of arbitrary ideals of I .
2 Some auxiliary propositions and the approach
De nition 4 We say that x = (x1; :::; xn ) 2 I is greater y = (y1; :::; yn) 2 I in the
Denote by Ln(m) the collection of the rst m vectors of I in the lexicographic order.
lexicographic order (denotation x y), if either x1 > y1 or if xi = yi for i = 1; 2; :::; s and some s < n, and xs+1 > ys+1 .
De nition 5 We say that a set A I is an initial segment if A = Ln(m) for some m.
I t(i) = fx 2 I : xi = tg:
De nition 6 A set A I is called i-compressed if A \ I t (i) is an initial segment of I t(i)
for all t = 0; :::; di.
Lemma 1 Let n 3, A I and A is i-compressed for i = 1; :::; n. Then either (i) A = Ln(jAj), or
(ii) there exist numbers a; p and q for which
where m0 = a
A = Ln(m0 ) f(x1; :::; xn) 2 I : x1 = a +1; x2 = ::: = xn?1 = 0; 0 xn q < p dng;
Qn (di + 1) + (p + 1) Qn?1(di + 1). i=2 i=2
Proof. The proof of the Lemma is based on the fact that for such A I the condition x = (x1 ; :::; xn) 2 A implies y = (y1; :::; yn) 2 A for any y x, maybe with some exceptions de ned in (ii). Assume that there exists an index i for which xi = yi = t. Then x; y 2 I t(i) and y 2 A, since A is i-compressed. Let now xi 6= yi for i = 1; :::; n. Obviously x1 > y1. If xn > yn, then consider the vector
z = (x1 ; :::; xn?1; yn):
It is easy to verify that x z y and x1 = z1, yn = zn. Therefore, z 2 A since A is 1-compressed, and hence y 2 A since A is n-compressed. If xn < yn and there exists an index i, 2 i n ? 1, such that yi < di, we consider the vector z = (y1; :::; yi?1; yi + 1; 0; :::; 0; xn): One has x z y, and similarly z 2 A and y 2 A. If xn < yn, yi = di for 2 i n ? 1 and x1 > y1 + 1, then considering the vector
z = (x1 ? 1; d2; :::; dn?1; xn);
for which x z y, one also gets y 2 A. Let now x1 = y1 + 1, xn < yn, yi = di for 2 i n ? 1 and there exists an index j , 2 j n ? 1, for which xj 6= 0. Then, considering the vector
z = (x1 ; :::; xj?1; xj ? 1; xj+1; :::; yn);
we get again x z y and so, y 2 A. We have to consider the last case:
x = (a + 1; 0; :::; 0; xn); y = (a; d2; :::; dn?1; yn)
with xn < yn. In this case it is impossible to guarantee y 2 A. However, if y 2 A, then (i) holds. If y 62 A then A is the union of the initial segment S with lexicographically greatest vector of the form (a; d2; :::; dn?1; p); with p = yn?1, and q = xn +1 vectors of the form (a+1; 0; :::; 0; t) with 0 t q < p dn. One has only notice that the size of S equals
?1 n Y(d + 1) + (p + 1) nY (d + 1): i i
Remark 1 For n = 1; 2 the Lemma is not true in general.
Ik = fx 2 I : kxk = kg Ik;k?1 = Ik Ik?1 Ak = A \ Ik :
Up to the end of this Section we assume A Ik;k?1.
of I .
De nition 7 A set A is called monotone if A is an intersection of Ik;k?1 with some ideal
F (A) = wk?1 jAk?1j + wk jAk j; where wk , wk?1 are some nonnegative numbers and denote by Ln ?1(m) the m-element k;k subset, which is the intersection of Ik;k?1 and some initial segment of I .
(i) if wk > wk?1 then the maximal value of F (A) among all m-element monotone subsets of Ik;k?1 is achieved on Ln ?1(m); k;k (ii) if wk < wk?1 then the maximal value of F (A) among all m-element monotone subsets of Ik;k?1 is achieved on arbitrary collection of m vectors of Ik?1 for m jIk?1 j and on the union of Ik?1 with arbitrary collection of m ? jIk?1 j vectors of Ik for m > jIk?1j; (iii) if wk = wk?1 then F (A) = const for any A Ik;k?1, jAj = m. Since the propositions (ii) and (iii) of Theorem 1 obviously hold, we will prove (i) only. Let A Ik;k?1 be a monotone set and jAj = m. 4
De nition 8 The set A is called optimal if F (A) F (B ) for any m-element monotone
Denote P (A) = fx = (x1; :::; xn ) 2 I : kxk > k and yi xi; 1 i n; for some y 2 Ag; T (A) = fx = (x1; :::; xn ) 2 I : jxj < k ? 1 and xi yi; 1 i n; for some y 2 Ag:
De nition 9 The set A] = A P (A) T (A) is called the closure of A.
We will prove in the next Lemma that among all optimal subsets there exists a subset such that for any i; j i A \ Ik;k?1(j ) = Ln?i;k?i?1(mi;j ); k n (j )j. Furthermore, in Lemma 3 we will show that the closure of where mi;j = jA \ Ik;k?1 Ln ?1(m) is an initial segment of I . These facts will allow later to propose that among all k;k monotone subsets A satisfying Lemma 2, there exists a subset A, such that A] satis es Lemma 1. It will give us a possibility to determine the structure of A very precisely and to prove Theorem 1 in Section 3. Notice that the proof of Theorem 1 could be simpli ed by using the Clements-Lindstrom theorem 6]. However, we did not use this theorem because, as it is shown in Section 4, it is an easy consequence of Theorem 1. In order to formulate our next propositions it is convenient to introduce the operators of compression C (A) and Cj (A). For a subset A Ik;k?1 put C (A) = Ln ?1(jAj) and k;k
Cj (A) =
where Ai(j ) = A \ I i(j ) and the operator C in the right hand side is applied in n ? 1 dimensions.
C (Ai (j ));
Lemma 2 Let A Ik;k?1 be a monotone set and Theorem 1 is true in n ? 1 dimensions. Then there exists a subset A0 Ik;k?1 such that jAj = jA0j, F (A) F (A0) and Cj (A0 ) = A0
for 1 j
Proof. Let us x the index j and replace each subset Ak \ I i(j ) with the equal-sized initial i segment of Ik (j ). Proceed by the same way with Ak?1 \ I i(j ) for all i. We obtain a subset B Ik;k?1 for which F (A) = F (B ) holds. However B may be nonmonotone. It may happen only if for some i, 0 i dj the set B i(j ) is nonmonotone in I i(j ). Replacing now this B i (j ) with Ln?i;k?i?1(jB i(j )j) in the corresponding (n ? 1)-subgrids, k we obtain a monotone set D. Since Theorem 1 is true for I i(j ), then F (D) F (B ). Now if Cj (D) = D, then jump to the last paragraph of the proof. Otherwise there is an index i for which n?1 Di(j ) 6= Lk?i;k?i?1(jDi(j )j):
i Denote by u the lexicographically greatest vector of Dk?1(j ), and by v the lexicographii (j ) n Di (j ). Then u v . cally least vector of Ik k Now we are going to show that if Cj (D) 6= D then there exists a monotone subset E such that F (E ) F (D) and the sum of the S lexicographical numbers of vectors of D is greater then one for E . Indeed, if E 0 = (D n u) v is monotone then let E = E 0 and we are done. If E 0 is nonmonotone then consider three cases: i i i i Case 1. Let i > 0, jDk (j )j = jDk?1 (j )j and either i = dj or jDk?1(j )j > jDk+1(j )j for ?1 i < dj . Denote by r the vector obtained from v by decreasing vi on 1 and denote
E = (D n u) r:
i i i i Case 2. Let i < dj , jDk?1(j )j = jDk+1(j )j and either i = 0 or jDk?1 (j )j > jDk (j )j for ?1
i > 0. Denote by s the vector obtained from u by increasing ui on 1 and let E = (D n s) v:
i i i i Case 3. Let 0 < i < di and jDk?1 (j )j = jDk (j )j, jDk?1(j )j = jDk+1(j )j. Denote ?1 E = (D n fu; sg) fr; vg:
In any case the set E is monotone and F (E ) F (D). If now Cj (E ) 6= E then we can repeat the procedure above. Since the sum of the lexicographic numbers of vectors of the new sets cannot decrease in nitely, then after a nite number of transformations we obtain a monotone subset G such that Cj (G) = G. To complete the proof of the whole Lemma we have to repeat our procedure for j = 1; 2; ::: until we obtain the desired set A0. 2
Lemma 3 If A Ik;k?1 and C (A) = A then A] is an initial segment in I .
Proof. Denote by u the lexicographically greatest vector of A] and by v the lexicographically least vector of I n A]. If v u then the Lemma is true. Assume v u. Let kvk kuk. There exists an index j such that ui = vi for 1 i j ? 1 and vj < uj . Consider an arbitrary vector r 2 I such that krk = kvk, ri = ui for 1 i j ? 1, rj > vj and ri ui for j + 1 i n. Such vector r already exists since kuk kvk. By the de nition of T (A), r 2 A]. Furthermore, v r u. Since A] \ It is a collection of the rst vectors of It in the lexicographic order for any t (see 6], Lemma 3), then v 2 A. A contradiction. Therefore, kvk kuk. If kvk > k, then by the de nition of P (A) there exists a vector s 2 I such that s 62 A], ksk = kvk ? 1 and si vi for 1 i n, i.e. s v, which contradicts to the choice of v. Therefore kvk = k and hence, kuk = k ? 1. However, v u contradicts to C (A) = A. 2
3 Proof of Theorem 1
We proceed by induction on n. Since we use Lemma 1, which is true for n > 3 only, we have to prove Theorem 1 for n = 2. Let I be a d1 d2 (d1 d2 ) two-dimensional grid. Notice that for d1 2 the Theorem is true. Assume that it is true for all two-dimensional d d2 grids with d d1 and consider the case d = d1. Let A Ik;k?1 be a monotone subset. Without loss of generality we may assume A0(1) 6= ;, i.e. 1 jA0 (1)j 2. Consider (d1 ? 1) d2 subgrid I 0, obtained from I by deleting the column I 0(1) and denote A0 = A n A0(1). Then A0 is a monotone subset of Ik?1;k?2 and F (A) = w1 jAk \ I 0(1)j + w2 jAk?1 \ I 0 (1)j + F (A0); where F (A0) is computed in the subgrid I 0. Replacing A0 with L2?1;k?2(jA0j) in the subgrid k I 0, we obtain a set B I . Using the inductive hypothesis for B , one gets F (B ) F (A). Now if jB 0(1)j = 2, then B = L2 ?1(jB j). If jB 0 (1)j = 1, then denote by r the vector k;k (0; k) 2 I n B and by u and v the lexicographically greatest and least vectors of Bk and Bk?1 respectively. It is easy to verify that either (B n u) r or (B n v) r is equal to D = L2 ?1(jB j) and F (D) F (B ). Therefore the Theorem is true for n = 2. k;k Let n 3 and A Ik;k?1 be a monotone set. By Lemma 2, there exists a monotone set B Ik;k?1, such that Cj (B ) = B for 1 j n. Denote by mj the maximal value of the j -th entry of vectors of B . If there exists a vector u 2 Ik n B such that uj < mj and each vector obtained from u by decreasing of any nonzero entry (i.e. compatible with u) belongs to Bk?1, then replace the lexicographically greatest vector v of Bk \ I m (j ) with n?1 u, and the set D = B m (j ) with the set Lk?m ;k?m ?1(jDj) in the subgrid I m (j ). Since the sum of the lexicographical numbers of vectors cannot increase in nitely, then after a su ciently large number of the transformations we obtain a monotone subset E such that F (E ) F (B ) and Cj (E ) = E for 1 j n. Furthermore, if there exists a vertex u 2 Ik n E , such that any compatible with it vertex of Ik?1 belongs to E then uj = j for 1 j n. Now we will show that for E ] one can apply Lemma 1. First notice that (P (E ))i(j ) P (E i(j )): Moreover, equality holds here. Indeed, assume that there exists a vector u 2 P (E i(j )) n P (E i(j )): Denote by v the vector obtained from u by replacing uj = i with i ? 1. Then kvk k. Without loss of generality we may let v 62 P (E i?1(j )). Since E is monotone set then for all t 1 and i 1 one has j E ] \ Iti?1 (j )j j E 0] \ Iti?1 (j )j; which leads to a contradiction when kvk > k. If kvk = k then since E is monotone then each vector of weight k ? 1 compatible with v, belongs to E and since v 62 E then by de nition of E , vj = mj , i.e. i = mj + 1 and u 2 E i(j ) = ;, which is a contradiction too.
j j j j j
Further, notice that
(T (E ))i(j ) T (E i(j )): We show by reversed induction on j , that E ]i(j ) is an initial segment in I i(j ). By Lemma 3 it is so if i = mj . Consider the case i = mj ? 1 and assume that (T (E ))i(j ) 6= T (E i(j )). i i Denote by G Ik?1;k?2(j ) the set, for which Gk?1 = Ek?1(j ) and Gk?2 is obtained from i+1 (j ) by decreasing on 1 the j -th entry in all vectors u 2 E i+1 (j ). By the de nition Ek?1 k?1 of E , E ]i(j ) = G] and the set G is an initial segment of I i(j ). Therefore by Lemma 3, E ]i(j ) is an initial segment of the subgrid I i(j ). For i < mj ? 1 the inductive step may be covered similarly. Therefore we can apply Lemma 1 to E . If the case (i) of it holds then the Theorem 1 is obviously true. Let the case (ii) holds and E 6= Ln ?1(m) (here m = jE j). Then by k;k Lemma 1 either E = N fug or E = N fu; vg, where N = Ln ?1(m0 ) and u; v are of k;k the form u = (a + 1; 0; :::; 0; p); v = (a + 1; 0; :::; 0; p + 1) with kuk = k ? 1, kvk = k. On the other hand by Lemma 1 either N = J n fsg or N = J n fs; rg, where 0 a J = Ik;k?1(1) ::: Ik?a;k?a?1(1) and s; r (krk = k ? 1, ksk = k) are the two lexicographically greatest vectors of J . Now if E = N u then N = J n s, since E 6= Ln ?1(m). Therefore G = (E n u) s = Ln ?1(m) k;k k;k and F (G) > F (E ). If E = N fu; vg, then if N = J n s, then denote G = (E n v) s and if N = J n fr; sg, then denote G = (E n fu; vg) fr; sg. In the both cases G = Ln ?1(m) k;k and F (G) F (E ). 2 Using the similar techniques one can prove the proposition on the minimization of F , which is obtained from Theorem 1 by replacing the inequalities wk > wk?1 with wk < wk?1, and the words "maximum" with "minimum". Let A Ik . Denote Ti(A) = T (A) \ Ik?i; Pi(A) = P (A) \ Ik+i:
Corollary 1 (The Clements-Lindstrom theorem 6]). (i) jT1(Ln(m))j jT1(A)j for any A Ik ; jAj = m; k (ii) jP1(Ln(m))j jP1(A)j for any A Ik ; jAj = m: k
Proof. Consider an arbitrary set B = A T1 (A) and let jB j = t. Denote D = Ln ?1(t). By k;k Theorem 1(i), F (D) F (B ). Since jDj = t and D is a monotone subset then jDk j jAj; jDk?1j jT1(A)j; Ln (m) Dk : k Hence, T1 (Ln(m)) Dk?1, i.e. jT1 (Ln(m))j jT1(A)j. The proposition (ii) may be k k proved similarly. 2
Let k > l. Denote
Ik;l = Ik Ik?1 ::: Il ; and let Ln (m) denotes the m-element set which is an intersection of Ik;l and an initial k;l segment of I . For A Ik;l consider the function Fk;l = wk jAk j + wk?1 jAk?1j + ::: + wl jAl j; where wi are some xed nonnegative numbers.
De nition 10 The set A Ik;l is called (k; l)-monotone if for any i, l + 1 i k, the
T1 (Ai) holds.
De nition 11 We call the set A quasisphere if
A = I0 I1 ::: It?1 A0 for some t, where A0 is the collection of the rst jA0j vectors of It in the lexicographic
(i) if wl ::: wk (wl ::: wk ), then the maximum (minimum) of Fk;l among all m-element subsets of Ik;l is achieved on Ln (m); k;l (ii) if wl ::: wk (wl ::: wk ), then the maximum (minimum) of Fk;l among all m-element subsets of Ik;l is achieved on the intersection of a quasisphere with Ik;l.
Proof. It is su cient to prove (i) for wl ::: wk . Replace Ai to Ln (jAij) with i = l; :::; k. i We obtain a set B which is (k; l)-monotone by Corollary 1. Furthermore, for each pair Ii, Ii?1 we replace Bi;i?1 with Ln ?1(jBi;i?1j). It is easy to show that all the new sets are i;i (k; l)-monotone and by Theorem 1 every nontrivial transformation leads to increasing of Fk;l. Hence, after a nite number of steps we obtain a set D, which is invariant under such transformation. Denote by u the lexicographically greatest vector of D and by v the lexicographically least vector of Ik;l n D. If v u then D = Ln (m). So let v u, k;l kuk = p, kvk = q. If q > p then any vector r such that krk = q ? 1 and ri vi, 1 i n, belongs to A and the set (D \ Ip+1;p) n u is monotone in Ip+1;p. Hence, E = (D n u) v is (k; l)-monotone and Fk;l (E ) > Fk;l(D). Therefore either we can transform D into Ln (m), or q < p. k;l If q < p, then consider the following sequence of vectors r1; r2; :::; rp. The vectors r1; :::; ru are obtained from u by decreasing un to 1, 2,..., u respectively. The next un?1 vectors are obtained from ru by decreasing it's (n ? 1)-st entry to 1; 2; :::; un?1 and so forth with the (n ? 2)-nd entry, (n ? 3)-rd,.... It is easy to verify that krik = kuk ? i and that the vector r of weight q from this sequence is the lexicographically greatest in Tp?q (fug) and r 2 D. Hence, if v r then v 2 D by the de nition of D. If v r, then v u and we get a contradiction. 2
Corollary 2 Let A be a (k; l)-monotone set and jAj = m. Then
4 The extremal ideals
(i) if w0 w1 ::: wi?1 wi ::: wd for some i, then the maximum of W' is achieved on the intersection of some initial segment with a quasisphere . (ii) if w0 w1 ::: wi?1 wi ::: wd for some i, then the maximum of W' is achieved on the union of some initial segment with a quasisphere.
Proof. Notice that for any k; l and m.
Ln (m) P1(Ln (m)) = Ln+1;l(m0 ) and k;l k;l k Ln (m) T1 (Ln (m)) = Ln ?1(m00 ); k;l k;l k;l 0 and m00 are the cardinalities of the unions. If A is an ideal then after replacing where m Ak with Ln(jAk j) for all k, the obtained set is an ideal either by the Clements-Lindstrom k Theorem and the value of W' on it equals to W' (A). So we may assume Ak = Ln(jAk j). k (i) Replace Ai?1;0 with Ln?1;0(jAi?1;0j). The obtained set B is an ideal by the Clementsi Lindstrom Theorem and W' (A) W' (B ) by the Corollary 1. Replace Bi+1 with P1(Bi), Bi+2 with P1(Bi+1 ) ,..., Bi+t with P1 (Bi+t?1) for t such that Bi+t+1 P1(Bi+t ) and Bs 6= ; for s > i + t + 1. We obtain a set D and Di+t;0 = Ln+t;0 (jDi+t;0j): i
Hence, D is the intersection of some initial segment in I with a quasisphere. (ii) Replace Ad;i with Ln (jAd;ij), where d = d1 + ::: + dn. By the Corollary 2, for the d;i obtained ideal B we have W'(A) W'(B ). Replace now Bi?1 with T1 (Bi), Bi?2 with T1(Bi?1 ),...,Bi?t+1 with T1(Bi?t+2 ), Bi+t T1 (Bi?t+1 ) with Is for s i ? t ? 1. Then for the obtained set D we have Dd;i?t+1 = Ln ?t+1 (jDd;i?t+1j) and Di?t;0 is a quasisphere. d;i Hence, D is the union of a quasisphere and an initial segment. 2
1] Ahlswede R., Katona G.O.H. Contributions to the geometry of Hamming spaces // Discr. Math. -1977. -v.17, No 1, 1-22. 2] Kleitman D.J., Krieger M.M., Rothschild B.L. Con gurations maximizing the number of pairs of Hamming-adjacent lattice points // Stud. Appl. Math., 1971, v.L, No 2, 115-119. 3] Lindstrom B., Zetterstrom H.-O. A combinatorial problem in the K -adic number system // Proc. Amer. Math. Soc., 1967, v.18, No 2, 166-170. 10
4] Clements G.F. Sets of lattice points which contain a maximal number of edges // Proc. Amer. Math. Soc., 1971, v.27, No 1, 13-15. 5] Lindsey J.H. Assignment of numbers to vertices // Amer. Math. Monthly, 1964, v.71, 508-516. 6] Clements G.F., Lindstrom B. A generalization of a combinatorial theorem of Macaulay // J. Combin. Theory, 1969, v.7, No 2, 230-238.