Gray codes extending quadratic matchings

Is it true that every matching in the n-dimensional hypercube can be extended to a Gray code? More than two decades have passed since Ruskey and Savage asked this question and the problem still remains open. A solution is known only in some special cases, including perfect matchings or matchings of linear size. This article shows that the answer to the Ruskey–Savage problem is affirmative for every matching of size at most . The proof is based on an inductive construction that extends balanced matchings in the completion of the hypercube by edges of into a Hamilton cycle of . On the other hand, we show that for every there is a balanced matching in of size that cannot be extended in this way.     

A tripling construction for mutually orthogonal symmetric hamiltonian double Latin squares

We provide two new constructions for pairs of mutually orthogonal symmetric hamiltonian double Latin squares. The first is a tripling construction, and the second is derived from known constructions of hamilton cycle decompositions of when is prime.     

On the threshold problem for Latin boxes

Let m ≤ n ≤ k. An m × n × k 0‐1 array is a Latin box if it contains exactly m n ones, and has at most one 1 in each line. As a special case, Latin boxes in which m = n = k are equivalent to Latin squares. Let be the distribution on m × n × k 0‐1 arrays where each entry is 1 with probability p, independently of the other entries. The threshold question for Latin squares asks when contains a Latin square with high probability. More generally, when does support a Latin box with high probability? Let ε > 0. We give an asymptotically tight answer to this question in the special cases where n = k and , and where n = m and . In both cases, the threshold probability is . This implies threshold results for Latin rectangles and proper edge‐colorings of K_n,n.     

一类正交空间填充设计的构造

空间填充设计在计算机试验中应用十分广泛,当拟合回归模型时,正交的空间填充设计保证了因子效应估计的独立性.基于广义正交设计,文章给出了构造二阶正交拉丁超立方体设计和列正交设计的方法,新构造的设计不仅满足任意两列之间相互正交,还能保证每一列与任一列元素平方组成的列以及任两列元素相乘组成的列都正交.当某些正交的空间填充设计不存在时,具有较小相关系数的近似正交设计可作为替代设计使用.设计构造的灵活性为计算机试验在实践中的广泛应用提供了必要的支持.     

The Order of Automorphisms of Quasigroups

We prove quadratic upper bounds on the order of any autotopism of a quasigroup or Latin square, and hence also on the order of any automorphism of a Steiner triple system or 1‐factorization of a complete graph. A corollary is that a permutation σ chosen uniformly at random from the symmetric group will almost surely not be an automorphism of a Steiner triple system of order n, a quasigroup of order n or a 1‐factorization of the complete graph . Nor will σ be one component of an autotopism for any Latin square of order n. For groups of order n it is known that automorphisms must have order less than n, but we show that quasigroups of order n can have automorphisms of order greater than n. The smallest such quasigroup has order 7034. We also show that quasigroups of prime order can possess autotopisms that consist of three permutations with different cycle structures. Our results answer three questions originally posed by D.  Stones.     

Classification of Graeco‐Latin Cubes

A q‐ary code of length n, size M, and minimum distance d is called an code. An code with is said to be maximum distance separable (MDS). Here one‐error‐correcting () MDS codes are classified for small alphabets. In particular, it is shown that there are unique (5, 5³, 3)₅ and (5, 7³, 3)₇ codes and equivalence classes of (5, 8³, 3)₈ codes. The codes are equivalent to certain pairs of mutually orthogonal Latin cubes of order q, called Graeco‐Latin cubes.     

Research problems from the BCC22

Open problems from the problem session at the 22nd British Combinatorial Conference at St Andrews, on 10 July 2009.     

Improved book-embeddings of incomplete hypercubes

In this paper, we show that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻² vertices can be embedded in n−1 pages for all n≥4. For the case n≥4, this result improves Fang and Lai’s result that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹ vertices can be embedded in n−1 pages for all n≥2.Besides this, we show that the result can be further improved when n is large — e.g., any incomplete hypercube with at most 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷ (respectively, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷+2ⁿ⁻²³⁰) vertices can be embedded in n−1 pages for all n≥9 (respectively, n≥232).     

Routing of 2-D switching networks by their embedding into cubes

The proposed all-optical 2-D switching networks are (i) M×N-gon prism switches (M2, N3) and (ii) 3-D grids of any geometry N3. For the routing we assume (1) the projection of the spatial architectures onto plane graphs (2) the embedding of the latter guest graphs into (in)complete host hypercubes (N=4) and generally, into N-cube networks (N3) and (3) routing by means of the cube algorithms of the host. By the embedding mainly faulty cubes (synonyms: injured cubes, incomplete cubes) arise which complicate the routing and analysis. The application of N-cube networks (i) extend the hypercube principles to any N3 (ii) increase the number of plane host graphs and (iii) reduce the incompleteness of the host cubes. Several different embeddings of the intersection graphs (IGs) of 2-D switching networks and several different routings are explained for N=4 and 6 by various examples. By the expansion of the grids (enlargement) internal waveguides (WGs) and internal switches are introduced which interact with the switches of the original 3-D grid without increasing the number of stages (NS). The embeddings by expansion apply to interconnection networks whereas dilation-2 embeddings (dilation ≡ distance of the nearest-neighbour nodes of the guest graph at the host) are rather suitable for the emulation of algorithms. Concepts for fault-tolerant routing and algorithm mapping are briefly explained.     

幻方的几个充要条件

建立等重方阵的概念,并运用它阐述幻方、2次幻方、3次幻方及中心对称互补幻方的充要条件,根据这些结论构作出一些8阶、9阶2次中心对称互补幻方.