Báo cáo toán học: A Survey on Packing and Covering Problems in the Hamming Permutation Space

A Survey on Packing and Covering Problems in the Hamming Permutation Space Jo¨rn Quistor Department 4 FHTW Berlin (University of Applied Sciences) 10313 Berlin, Germany J.Quistorff@fhtw-berlin.de Submitted: Mar 22, 2004; Accepted: Apr 17, 2006; Published: Apr 24, 2006 Mathematics Subject Classications: 05B40, 20B35 Abstract Consider the symmetric group Sn equipped with the Hamming metric dH. Pack-ing and covering problems in the nite metric space (Sn;dH) are surveyed, including a combination of both. 1 Introduction Let n be a positive integer and consider the symmetric group Sn of all permutations of the set f1;2;:::;ng. There are several metrics on Sn, surveyed in [20]. The most important one seems to be the Hamming metric dH. In the present paper, the nite metric space (Sn;dH) will be called the Hamming permutation space. The packing and covering problems in this space are the following. Let d be given and determine (or estimate) the largest cardinality of a d-packing, i.e. of a subset C Sn with the property that its elements are at a distance of at least d from each other. Let e be given and determine (or estimate) the smallest cardinality of an e-covering, i.e. of a subset C Sn with the property that the balls of radius e around the elements of C cover the whole space. The rst papers on packing in the Hamming permutation space are [19], where Deza raised the problem in 1976, and [22]. Considerable research on covering in this space was recently started by Kezdy/Snevily [26] and Cameron/Wanless [10]. But already in 1978, a problem combining packing and covering was introduced by Deza/Vanstone [21, Section 3.4.]. the electronic journal of combinatorics 13 (2006), #A1 1 Similar problems are frequently discussed in other situations. Of special interest is the classical coding theory, dealing with Qn, jQj = q 2, equipped with the Hamming (or Lee) metric, see for example [3], [6], [7], [14], [27], [28], [36]. Recently, combinations of packing and covering problems in (Qn;dH) have been considered, see [29] and its references. The connection between coding theory and the corresponding problems on permutations was pointed out by Blake et al. [5] in 1979. Packing and covering problems in graph theory, using the length of the shortest path as a metric, can be interpreted as generalizations of the respective problems in coding theory, but not of the respective problems on permutations. Modifying these problems one can get six closely connected extremal cardinalities. In 1978, Cockayne et al. [11] proved them to be related by a single string of inequalities. These cardinalities are now standard in graph theory, compare [24]. A common generalization of packing and covering problems in both graph theory and the Hamming permutation space, was given 2003 in [31] where the notion of a nite metric space is used. That paper also contains the transformation of the six extremal cardinalities mentioned above to nite metric spaces. In coding theory, a standardization of the notations regarding packing and covering has taken place, the letters A and K (more precisely: Aq(n;d) and Kq(n;R)) indicate the extremal cardinalities of the classical packing and covering problems. In graph theory, and γ (more precisely: 0(G) and γ(G)) became standard instead. Furthermore, i (more precisely: i(G)) indicates an extremal number related to a problem combining packing and covering. In [31], the letters , γ and i were transferred to nite metric spaces. The aim of the present paper is to survey results on packing and covering problems in the Hamming permutation space, including a combination of both. This seems to be necessary since some papers are hard to trace and many dierent notations have been used up to now. Furthermore, the author hopes to promote the use of , γ and i also in the Hamming permutation space. Extremal problems concerning subgroups (instead of subsets) of Sn as well as asymp-totic results will not be surveyed in this paper. The paper is organized as follows: Section 2 recalls necessary notations and some basic results. In Section 3, bounds are given which appear if the parameters of a packing or covering problem are modied, i.e. if at least two dierent Hamming permutation spaces are involved. In Section 4, so-called destructive bounds are studied which destroy the hope of nding very small sets solving the covering problem and very large sets solving the packing problem. In Section 5, so-called constructive bounds arising from constructions of suitable sets of permutations are discussed. Some conjectures are mentioned in Section 6. Finally, Section 7 presents existence problems for sets which satisfy bounds with equality. the electronic journal of combinatorics 13 (2006), #A1 2 2 Notation Let n 2 N and Sn be the symmetric group of all permutations of the set f1;2;:::;ng. The identity permutation is denoted by id. Clearly, dH : Sn Sn ! f0;1;2;:::;ng;(;0) ! jfx 2 f1;2;:::;ng : (x) = 0(x)gj is a metric on Sn, called the Hamming metric. The nite metric space (Sn;dH) will be called the Hamming permutation space. Two permutations ;0 2 Sn agree in exactly n − dH(;0) positions which is also the number of xed points of −10. Let D(Sn) := dH(SnSn) be the set of all distances which appear in Sn. Since two permutations cannot dier in exactly one position, D(Sn) = f0;2;3;4;:::;ng. A ball of radius e 2 D(Sn) around 2 Sn is denoted by Be() := f0 2 Sn : dH(;0) eg: Its volume depends only on the radius, not on the centre. Hence, e Ve := jBe()j = k=0 n! k (−1)x k x=0 x! for all 2 Sn. To avoid formal problems in Section 4, put B1() := B0() = fg and V1 := V0 = 1. Consider now a subset C of the symmetric group Sn. Its packing radius is denoted by p(C) := maxfe0 2 D(Sn) : Be0() \ Be0(0) = ;8;0 2 C with = 0g: If C contains at least two permutations, d(C) := minfdH(;0) 2 D(Sn) : ;0 2 Sn with = 0g is called the minimum distance of C. In contrast to the situation in coding theory, the inequality 2p(C) + 1 d(C) might fail: Take for example ( C = id; 1234!) 2341 4 implying p(C) = 2 and d(C) = 4. If C is nonempty then its covering radius is denoted by t(C) := maxfminfdH(;0) 2 D(Sn) : 0 2 Cg : 2 Sng and (C) := maxfdH(;0) 2 D(Sn) : ;0 2 Cg is called its diameter. Clearly, C is e-covering i t(C) e. Since e;e0 2 D(Sn) with e > e0 imply Be() n Be0() = ;, the inequality p(C) t(C) follows. If the length of the shortest path joining two vertices of a nite (undirected loop-free) graph (V;E) is used as a metric on V, then another nite metric space is generated. In the graph theoretical literature concerning that space, an e-covering is called e-domination. Furthermore, a subset C is called e-independent i its elements are at a distance > e the electronic journal of combinatorics 13 (2006), #A1 3 from each other. Hence, the connection to d-packings is obvious. In the following, only the notions of independent subsets and covering subsets will be used. Furthermore, only e 2 D(Sn) is considered, other cases like e = 1 are dull. Clearly, every subset of an e-independent set is also e-independent. Furthermore, every superset of an e-covering is also e-covering. The only minimal e-independent subset of Sn is the empty set, the only maximal e-covering subset is Sn itself. The determination of maximal e-independent subsets and of minimal e-covering subsets in case of e 2 D(Sn) n f0;ng is nontrivial while the situation e 2 f0;ng is again trivial. Clearly, a subset is maximal e-independent i it is simultaneously e-independent and e-covering. Let γn(e) denote the smallest cardinality of a minimal e-covering subset of Sn. Let in(e) and n(e) denote the smallest and the largest cardinality of a maximal e-independent subset of Sn, respectively. The words minimal in the denition of γn(e) and maximal in the denition of n(e) can be omitted. Up to now, nearly nothing has been shown about the largest cardinality of minimal e-covering subsets of Sn. The smallest cardinality f(n;s) of a subset of Sn with a covering radius n − s is considered in [10]. Hence, γn(e) = f(n;n− e). In [33], U(Sn;dH;e) is used instead. The largest cardinality of a d-packing in Sn is denoted in [35] by M(n;d). In [30] and [33], u(n;d) and u(Sn;dH;d) are used instead. The maximal cardinality of a subset of Sn with the property that any two distinct permutations agree in at most positions is denoted in [19] and [22] by R(n; ). Hence, n(e) = M(n;e + 1) = R(n; n− e− 1). In [30], the smallest cardinality of a maximal d-packing in Sn is denoted by v(n;d). In [21] and [10], the smallest cardinality of a maximal subset of Sn with the property that any two distinct permutations agree in at most k positions is denoted by Rminmax(n; k) and m(n;k), respectively. Hence, in(e) = v(n;e+1) = m(n;n−e−1) = Rminmax(n; n−e−1). Clearly, 1 γn(e) in(e) n(e) n! (1) holds true in analogy to the result of Cockayne et al. [11]. As mentioned above, the situation e 2 f0;ng is trivial since γn(0) = n! and n(n) = 1. Since γn(e);in(e);n(e) 2 N, every real lower bound 0 on one of these desired values implies the lower bound d0e and every real upper bound 00 implies the upper bound b00c. These rounding rules can be applied to all of the following estimations. 3 Modications Clearly, γn and n are monotonously decreasing functions. If the parameter n is modied, some estimations can be proved. Theorem 1 Let n;n 2 N and e 2 D(Sn) as well as e 2 D(Sn). (i) n+1γn+1(e) γn(e) γn+1(e) and γn+1(e+ 2) γn(e) if e n− 1. (ii) n+1n+1(e) n(e) n+1(e) and n+1(e+ 3) n(e) if 0 < e n− 2. (iii) minfn(e);n(e)g n+n(e+ e+ 1). the electronic journal of combinatorics 13 (2006), #A1 4 Proof: Let y 2 f1;2;:::;ng. Denote by y;n the unique transposition in Sn with y;n(y) = n and y;n(n) = y, if y < n. Otherwise put n;n := id. If 2 Sn then denote the extension of to a permutation of f1;2;:::;n + 1g with a xed point n + 1 by . If 2 Sn with (n) = n then denote the restriction of to a permutation of f1;2;:::;n − 1g by res(). If is an arbitrary permutation in Sn then put 0 := res((n);n ) 2 Sn−1. Let : f1;2;:::;ng ! fn+1;n+2;:::;n+ng;x ! n+x. Denote the concatenation of 2 Sn and 2 Sn with x ! (x) if x n and x ! −1(x) if x > n by 2 Sn+n. (i) Let C Sn+1 be e-covering with jCj = γn+1(e). Put C0 := f0 2 Sn : 2 Cg. Let 2 Sn then 9 2 C with dH(;) e. Since dH(;0) dH(;) also C0 Sn is e-covering and jC0j jCj holds true. This proves the second estimation. Let C Sn be e-covering with jCj = γn(e). Put C := f 2 Sn+1 : 2 Cg and C := y=1fy;n+1 2 Sn+1 : 2 Cg. Let 2 Sn+1 then 9 2 C with dH( ;) e. Since dH(;) dH( ;) + 2 and dH(;(n+1);n+1 ) = dH( ;) it follows that C Sn+1 is (e + 2)-covering and C is e-covering. Finally, = jCj and ~ = (n+ 1)jCj prove the third and the rst estimation, respectively. (ii) Let C Sn+1 be e-independent with jCj = n+1(e). Then Cy := f0 2 Sn : 2 C and (n+1) = yg is also e-independent 8y 2 f1;2;:::;n+1g. Furthermore, 9y with jCyj n+1jCj. This proves the rst estimation. Let C Sn be e-independent with jCj = n(e). Then C := f 2 Sn+1 : 2 Cg is also e-independent and jCj = jCj holds true. This proves the second estimation. Let C Sn+1 be (e + 3)-independent with jCj = n+1(e + 3). Then C0 := f0 2 Sn : 2 Cg is e-independent and jC0j = jCj holds true. This proves the third estimation. (iii) Let C = f1;2;:::;n(e)g Sn be e-independent and let C = f1;2; :::;n(e)g Sn be e-independent. Put C := fj j 2 Sn+n : 1 j minfn(e);n(e)gg. By construction, C is (e + e0 + 1)-independent and C = min jCj;C holds true. 2 The rst estimation of part (i) is due to Cameron/Wanless [10]. The rst and second estimation of part (ii) are given by Deza [19]. The third estimations of part (ii) as well as part (iii) are due to the present author [30]. The remaining two estimations of part (i) seem to be new. 4 Destructive Bounds In this section, lower bounds on γn(e) and in(e) as well as upper bounds on n(e) are surveyed. In general, one may say that these bounds destroy the hope of nding e-covering sets of very small cardinality as well as e-independent sets of very large cardinality. Hence, they will be called destructive in this paper. A rst trivial example is γn(e) 2 if 0 < e < n. the electronic journal of combinatorics 13 (2006), #A1 5 ... - tailieumienphi.vn