ABSTRACT

The shortest k-dimension paths (k-paths) between vertices of n-cube are considered on the basis a bijective mapping of k-faces into words over a finite alphabet. The presentation of such paths is proposed as matrix of characters from the same alphabet. A classification of the paths is founded on numerical invariant as special partition. The partition consists of n parts, which correspond to columns of the matrix.

Keywords:n-Cube; Bijection; Cubant; k-Face; k-Path; Partition; Numerical Invariant; Hausdorff-Hamming Metrics

1. Introduction

Discovery of n-cube combinatoric properties remains a relevant topic, which extends the connections of mathematical fields [1] -[4] . The bijective mappings play an important role in enumerative combinatorics as broad alighted in classical works of G.-C. Rota and R. P. Stanley [5] [6] . Bijective form for some constructive world [7] could be considered not only as suitable for enumerative problems, but also with point of view of effective computing synthesis (algorithms and operations with the potential large parallelism) in such frame. Such approach is considered in the article on the base of constructions (computing) for k-paths as complexes of k-faces in n-cube.

2. Shortly on Cubants

One of bijections for k-faces of n-cube was proposed in [8] . Let be—reper in, alphabet and the set of all n-digits words. So some word of the set is. Each k-face can be represent as Cartesian product of unit-segments for and translation along the rest basis such, that. So the bijection for k-face can be written as next:

where for and for. for translation along and, when translation is out. Such representation allows to store traditional coding for n-cube vertex coding (vertice is 0-face). Let character be supplement and then. Character-oriented operation multiplication (intersection) is determined on (all quaternary n-digital words) with next rules:

Really it’s intersection of sets: “0, 1”—endpoints of unit-segment and “2” corresponds full unit-segment. For short all words from are titled as cubants. So we can say the set of cubants forms monoid with unit-cubant (n-face in n-cube, i.e. itself n-cube).

The character-oriented operation of addition for cubants is prescribed by next rules:

Result of the operation is cubant for convex hull face and therefore one can write:

.

Short-list of operations on cubants is outlined below:

1)—counting of character in cubant. Result is from.

2)—exchanging of all “0” to “1” and all “1” to “0” in cubant. Result is cubant for antipodal (a.p.) face.

3)—operation multiplication. Result is cubant for common face, if. In case it’s—length of shortest path along edges between faces with cubants and, in accordance with (1).

4). Result is cubant in accordance with (2).

5). Exchanging letters “2” on “0” in such of, for which, and “2” on “1”, for which. Result has got properties and.

6).

Calculation of Hausdorff-Hamming (HH) distance for faces with cubants, [9] .

7)—boundary for face with cubant. Result is a set of cubants corresponding the all hyperfaces.

Algorithm of HH-distance calculation was proposed in [9] and all k-faces of n-cube form finite metric HH-space. Simplicity of the algorithm gives foundation to add it to operations for cubants. By the way the same algorithm realized calculation of Gromov-Hausdorff (GH) distance between cubes (as finite metric spaces) of different dimensions.

3. Matrix Representation of k-Path

Below we consider complexes of k-faces (here k-dimension of face in contrast to [4] , where k-length along edges as shortest paths between vertex). Now we will give definition of k-path between two of antipodal (a.p.) vertices in terminology of cubants. No limits of common we can consider cubants and for a.p. vertices. Then the set of cubants, is bijectivial form of shortest k-path such, that next conditions are satisfied for:

We represent set of such cubants in more visible form of matrix:

It’s easy to check next matrix corresponds to k-path for available and:

The columns of the matrix are denoted by. Then available permutation of columns stores satisfying of conditions (3) and. All such matrices (under permutations from symmetric group) represent the isomorphic k-paths with partition:. For case (4):

Evidently the matrices with different partitions correspond non-isomorphic k-paths. Therefore we can define the such partitions as numerical invariants, which allow one to distinguish among non-isomorphic k-paths, i.e. to classify k-paths. Now we must remark a specific property of. Here the columns are written as horizontal rows. So each can have view only of four types:

Roughly speaking the sequence of the same characters in denies “gaps”, since otherwise the condition of is not satisfied.

The specific property leads to situation, when some partitions are not represented in frame of T. For example the number of non-isomorphic k-paths classes for, is equal 4, though,:

, , , ,

At that time,:

, , , , ,

So.

Now we consider common form of matrix of special type (conditions (3) are satisfied):

Number of vertical columns with “2” (VC) can lay in interval from 0 to and each of them corresponds to “2-stairs” (SC) from to 1, for. The case must be analyze separately. So for and common bounds of classes number are next:

Now about case. Set SC columns includes such, which have character 2, i.e. coincide with one of VC-column. The number of such SC columns is equal to. Therefore:

One can combine (6) and (7) in single result:

One can give title the staircase for of type (5).

We considered above k-paths for antipodal (a.p.) vertices and. Now let available two vertices in n-cube are given and hamming distance between them is equal to. Then computing of matrix for k-path is reduced to a.p. case. Therefore we delete in pares the same digits. So the rest digits correspond a.p. vertices in face-convex hull for these cut vertices. Our previous techniques may be successfully here with addition of deleted digits in columns of. Shortly speaking the sequence of steps looks like this: extraction of a.p. part in given vertices (deleting of differing in pairs digits) the choice of matrix of type (5) inserting of columns with deleted digits in.

More general problem is to construct of k-path, when two a.p. vertices, and k-face are given. Without loss of generality let left digit of is “2”. So the first row of matrix is. Algorithm consists of sequential generations, which follows in matrix. For case and we assign and shift character 2 in nearest digit, for which. In common case if such digit in is absent, the procedure is completed. Let here then we assign for digits character “2” and the same characters from for.

In common case for, we produced in analogous fashion, beginning with duplicating in the same characters of before first meeting “2”. Then we assign “1” for next digit of and further digits are determined in accordance with rules for. One can represent the digit-wise rules as next scheme:

One can give title of the procedure as pressing characters “2” with single inversion 0 - 1.

Examples of 2-paths in 6-cube is represented step by step below (Figure 1).

HH-distance may be taken in account constructing some k-paths (operation 6)). So table for and (2-paths in 6-cube) is following:

, ,

It follows: (Figure 1).

To remark although our exposition is short, the most of operations for cubants are realized digitwise, i.e. in parallel. It’s clearly visible, if we’ll use for computer the bitwise mapping, , ,.

4. Conclusions

In conclusion, we give the main statement of the article.

Minimal number s of k-faces in k-path between a.p. vertices in n-cube is equal to. The bounds for number of non-isomorphic k-path classes are, where are partitions integer in parts with constraint for maximal part. Lower bound is always realized by staircase matrix.

References