Switching Equivalence Classes of Perfect Codes

The authors present a 1-error correcting perfect code of length 15 and show that it is not switching equivalent to the Hamming code thereby settling a question of Avgustinovich and Solov'evaas96     

On Perfect Ternary Constant Weight Codes

We consider the space of ternary words of length n and fixed weight w with the usual Hamming distance. A sequence of perfect single error correcting codes in this space is constructed. We prove the nonexistence of such codes with other parameters than those of the sequence.     

Linear Perfect Codes and a Characterization of the Classical Designs

A new definition for the dimension of a combinatorial t-(v,k,) design over a finite field is proposed. The complementary designs of the hyperplanes in a finite projective or affine geometry, and the finite Desarguesian planes in particular, are characterized as the unique (up to isomorphism) designs with the given parameters and minimum dimension. This generalizes a well-known characterization of the binary hyperplane designs in terms of their minimum 2-rank. The proof utilizes the q-ary analogue of the Hamming code, and a group-theoretic characterization of the classical designs.     

On 3-colorings of Plane Graphs

In this paper, we prove that if G is a plane graph without 4-, 5- and 7-circuits and without intersecting triangles, then for each face f of degree at most 11, any 3-coloring of the boundary of f can be extended to G. This gives a positive support to a conjecture of Borodin and Raspaud which claims that each plane graph without 5-circuits and intersecting triangles is 3-colorable.     

Defective 2-colorings of planar graphs without 4-cycles and 5-cycles

A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define $V_i?\{v\in V\left(G\right):c\left(v\right)=i\}$ for $i=1$ and $2.$ We say that $G$ is $(d_1,d_2)$-colorable if $G$ has a 2-coloring such that $V_i$ is an empty set or the induced subgraph $G\left[V_i\right]$ has the maximum degree at most $d_i$ for $i=1$ and $2.$ Let $G$ be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether $G$ is $(0,k)$-colorable is NP-complete for every positive integer $k.$ Moreover, we construct non-$(1,k)$-colorable planar graphs without 4-cycles and 5-cycles for every positive integer $k.$ In contrast, we prove that $G$ is $(d_1,d_2)$-colorable where $(d_1,d_2)=(4,4),(3,5),$ and $(2,9).$     

Perfect cliques and colorings of Polish spaces

A coloring of a set is any subset of , where 1$"> is a natural number. We give some sufficient conditions for the existence of a perfect -homogeneous set, in the case where is and is a Polish space. In particular, we show that it is sufficient that there exist -homogeneous sets of arbitrarily large countable Cantor-Bendixson rank. We apply our methods to show that an analytic subset of the plane contains a perfect -clique if it contains any uncountable -clique, where is a natural number or (a set is a -clique in if the convex hull of any of its -element subsets is not contained in ).

     

Existence of Perfect 3-Deletion-Correcting Codes

Bours [4] recently showed some constructions for perfect 2 and 3-deletion-correcting codes from combinatorial designs. He settled existence of perfect 2-deletion-correcting codes with words of length 4. However, the existence of perfect 3-deletion-correcting codes with words of length 5, or T^*(2, 5, v), remained unsettled for v 7, 8 (mod 10) and v = 13, 14, 15, 16. In this paper we provide new constructions for these codes from combinatorial designs, and show that a T^*(2, 5, v) exists for all v.     

Two-dimensional minimax Latin hypercube designs

We investigate minimax Latin hypercube designs in two dimensions for several distance measures. For the ?^∞-distance we are able to construct minimax Latin hypercube designs of n points, and to determine the minimal covering radius, for all n. For the ?¹-distance we have a lower bound for the covering radius, and a construction of minimax Latin hypercube designs for (infinitely) many values of n. We conjecture that the obtained lower bound is attained, except for a few small (known) values of n. For the ?²-distance we have generated minimax solutions up to n=27 by an exhaustive search method. The latter Latin hypercube designs are included in the website www.spacefillingdesigns.nl.     

Graphs with full rank 3-color matrix and few 3-colorings

We exhibit a counterexample to a conjecture of Thomassen stating that the number of distinct 3-colorings of every graph whose 3-color matrix has full column rank is superpolynomial in the number of vertices.     

Perfect Matchings and Perfect Powers

In the last decade there have been many results about special families of graphs whose number of perfect matchings is given by perfect or near perfect powers (N. Elkies et al., J. Algebraic Combin. 1 (1992), 111–132; B.-Y. Yang, Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA, 1991; J. Propp, New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999). In this paper we present an approach that allows proving them in a unified way. We use this approach to prove a conjecture of James Propp stating that the number of tilings of the so-called Aztec dungeon regions is a power (or twice a power) of 13. We also prove a conjecture of Matt Blum stating that the number of perfect matchings of a certain family of subgraphs of the square lattice is a power of 3 or twice a power of 3. In addition we obtain multi-parameter generalizations of previously known results, and new multi-parameter exact enumeration results. We obtain in particular a simple combinatorial proof of Bo-Yin Yang's multivariate generalization of fortresses, a result whose previously known proof was quite complicated, amounting to evaluation of the Kasteleyn matrix by explicit row reduction. We also include a new multivariate exact enumeration of Aztec diamonds, in the spirit of Stanley's multivariate version.     

Stieltjes Perfect Semigroups are Perfect

An abelian *-semigroup S is perfect (resp. Stieltjes perfect) if every positive definite (resp. completely so) function on S admits a unique disintegration as an integral of hermitian multiplicative functions (resp. nonnegative such). We prove that every Stieltjes perfect semigroup is perfect. The converse has been known for semigroups with neutral element, but is here shown to be not true in general. We prove that an abelian *-semigroup S is perfect if for each s ∈ S there exist t ∈ S and m, n ∈ ℕ₀ such that m + n ≥ 2 and s + s* = s* + mt + nt*. This was known only with s = mt + nt* instead. The equality cannot be replaced by s + s* + s = s + s* + mt + nt* in general, but for semigroups with neutral element it can be replaced by s + p(s + s*) = p(s + s*) + mt + nt* for arbitrary p ∈ ℕ (allowed to depend on s).     

Large regular simplices contained in a hypercube

We prove that the n-dimensional unit hypercube contains an n-dimensional regular simplex of edge length c√n, where c > 0 is a constant independent of n. Supported by MEXT Grant-in-Aid for Scientific Research (B) 20340022.     

Restricted Perfect Group Rings

A ring R is a restricted right perfect ring if every proper homomorphic image of R is right perfect. A complete characterization of restricted right perfect group rings RG has been obtained when the f.c. center of the group G is nontrivial. The f.c. center of a group G is the set of all elements of G that have finitely many conjugates in G.     

The Classification of Some Perfect Codes

Perfect 1-error correcting codes C in Z ₂ ⁿ , where n=2 ^m–1, are considered. Let ; denote the linear span of the words of C and let the rank of C be the dimension of the vector space . It is shown that if the rank of C is n–m+2 then C is equivalent to a code given by a construction of Phelps. These codes are, in case of rank n–m+2, described by a Hamming code H and a set of MDS-codes D _h , h H, over an alphabet with four symbols. The case of rank n–m+1 is much simpler: Any such code is a Vasil'ev code.     

具有唯一完美匹配的D-图

为了研究具有完美匹配图的Tuttc集和极端集,文献[1,2]提出了一种新的图运算,并且得到了许多有趣的性质。本文中,我们刻画了level（G）=0的具有唯一完美匹配的饱和图G,并且确定了具有唯一完美匹配图的D-图的边数的紧上界。     

Finding maximin latin hypercube designs by Iterated Local Search heuristics

The maximin LHD problem calls for arranging N points in a k-dimensional grid so that no pair of points share a coordinate and the distance of the closest pair of points is as large as possible. In this paper we propose to tackle this problem by heuristic algorithms belonging to the Iterated Local Search (ILS) family and show through some computational experiments that the proposed algorithms compare very well with different heuristic approaches in the established literature.