Enumerating Perfect Matchings in n-Cubes

The perfect matchings in the n-cube have earlier been enumerated for n?≤?6. A dynamic programming approach is here used to obtain the total number of perfect matchings in the 7-cube, which is 391 689 748 492 473 664 721 077 609 089. The number of equivalence classes of perfect matchings is further shown to be 336 in the 5-cube, 356 788 059 in the 6-cube and 607 158 046 495 120 886 820 621 in the 7-cube. The techniques used can be generalized to arbitrary bipartite and general graphs.     

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.     

Improved Bounds for Ternary Linear Codes of Dimension 8 Using Tabu Search

In this paper, new codes of dimension 8 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Twenty three codes are given which improve or establish the bounds for ternary codes. In addition, a table of upper and lower bounds for d ₃(n, 8) is presented for n 200.     

A Note on Toeplitz’ Conjecture

In 1911, Toeplitz made a conjecture asserting that every Jordan curve in $\mathbb{R}^{2}$ contains four points forming the corners of a square. Here Conjecture C is presented, which states that the side length of the largest square on a closed curve that consists of edges of an n×n grid is at least $1/\sqrt{2}$ times the side length of the largest axis-aligned square contained inside the curve. Conjecture C implies Toeplitz’ conjecture and is verified computationally for n≤13.     

Classification of Extremal Formally Self-Dual Even Codes of Length 22

 Lengths 22 and 30 are so far the only open cases in the classification of extremal formally self-dual even codes. In this paper, a classification of the extremal formally self-dual even codes of length 22 is given. There are 41520 such codes.A variety of properties of these codes are investigated. In particular, new 2-(22, 6, 5) designs are constructed from the codes. Received: February 9, 2000     

Enumerating Cube Tilings

Cube tilings formed by $n$ -dimensional $4\mathbb Z ^n$ -periodic hypercubes with side $2$ and integer coordinates are considered here. By representing the problem of finding such cube tilings within the framework of exact cover and using canonical augmentation, pairwise nonisomorphic 5-dimensional cube tilings are exhaustively enumerated in a constructive manner. There are 899,710,227 isomorphism classes of such tilings, and the total number of tilings is 638,560,878,292,512. It is further shown that starting from a 5-dimensional cube tiling and using a sequence of switching operations, it is possible to generate any other cube tiling.     

The nonexistence of a (K6‐e)‐decomposition of the complete graph K29

We show via an exhaustive computer search that there does not exist a (K₆?e)‐decomposition of K₂₉. This is the first example of a non‐complete graph G for which a G‐decomposition of K_2|E(G)|+1 does not exist. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 94–104, 2010     

Enumeration of 2-(9, 3, λ) Designs and Their Resolutions

We consider 2-(9, 3, ) designs, which are known to exist for all 1, andenumerate such designs for = 5 and their resolutions for 3 5, the smallestopen cases. The number of nonisomorphic such structures obtained is 5 862 121 434, 426, 149 041, and 203 047732, respectively. The designs are obtained by an orderly algorithm, and the resolutions by two approaches:either by starting from the enumerated designs and applying a clique-finding algorithm on two levels or by anorderly algorithm.