Abstract: The $n$-cube $H(n,2)$ is a graph on the binary words of length $n$ ($n$-words), where two words are adjacent if and only if they differ in exactly one position. The (Hamming) distance between two words of the same length is the number of positions in which they differ. The weight of a binary word is the number of $1$s in it. A $t$-$(v,k,λ)$ design (if $λ=1$, $S(t,k,v)$), $0\le t\le k \le v$, is a set $C$ of binary $v$-words of weight $k$ such that every binary $v$-word of weight $t$ is at distance $k-t$ from exactly $λ$ words in $C$. An equitable $l$-partition of the $n$-cube is an ordered partition $(C_1,...,C_l)$ of its vertices into $l$ fibers such that for every $i$ and $j$ from $1$ to $l$ every vertex in $C_i$ has exactly $S_{ij}$ neighbors in $C_j$, where $(S_{ij})_{i,j=1}^l$ is some collection of $l^2$ constants. A set $C$ of vertices in a metric space is called strongly distance invariant (s.d.i.) if for all nonnegative $a$, $b$, $c$ there is a constant $T_{a,b,c}$ such that for every vertex $x$ in $C$ the number of pairs $(y,z)$ of vertices in $C$ at distance, respectively, $a$ and $b$ from $x$ and at distance $c$ from each other equals $T_{a,b,c}$ (and so does not depend on the choice of $x$). It is known that every fiber of an equitable partition of the $n$-cube is s.d.i. [3]. However, there are examples [2] which show that this property cannot be generalized to equitable partitions of distance-regular graphs in general. $t$-$(v,k,λ)$ design are often considered as codes in the Johnson graph J$(v,k)$ (on the binary $n$-words of weight $k$). However, some of them can be shown to be embedded into equitable partitions of the whole $v$-cube; those designs are s.d.i. THEOREM. All designs with the following parameters are strongly distance invariant: $(n-2)2$-$(n,n/2,λ)$, $(n-3)2$-$(n,(n-1)/2,λ)$, $(n-4)2$-$(n,(n-2)/2,1)$, $(n-5)2$-$(n,(n-3)/2,1)$. For example, the theorem is applicable to the small Witt design $S(5,6,12)$ and its derived $S(4,5,11)$. To compare, the following computational results show that not all $S(t,t+1,v)$ designs are s.d.i. PROPOSITION. All $4$ inequivalent $S(3,4,14)$ designs (SQS$(14)$) are not s.d.i. Among all $1054163$ inequivalent $S(3,4,16)$ designs (SQS$(16)$, [1]), only one is s.d.i. There are $S(5,6,24)$ and $S(5,6,36)$ designs that are not s.d.i. REFERENCES. [1] P. Kaski, P. R. J. Östergård, and O. Pottonen. The Steiner quadruple systems of order 16. J. Comb. Theory, Ser. A, 113(8):1764–1770, 2006. [2] D. S. Krotov. On calculation of the interweight distribution of an equitable partition. J. Algebr. Comb., 40(2):373–386, 2014. [3] A. Yu. Vasil’eva. Local and interweight spectra of completely regular codes and of perfect colorings. Probl. Inf. Transm., 45(2):151–157, 2009.

Cite: Krotov D.S.
Strong distance invariance of some designs
Международная конференция "МАЛЬЦЕВСКИЕ ЧТЕНИЯ" 14-18 Nov 2022