We present a class of array code of size n/spl times/l, where l=2n or 2n+1, called B-Code. The distances of the B-Code and its dual are 3 and l-1, respectively. The B-Code and its dual are optimal in the sense that i) they are maximum-distance separable (MDS), ii) they have an optimal encoding property, i.e., the number of the parity bits that are affected by change of a single information bit is minimal, and iii) they have optimal length. Using a new graph description of the codes, we prove an equivalence relation between the construction of the B-Code (or its dual) and a combinatorial problem known as perfect one-factorization of complete graphs, thus obtaining constructions of two families of the B-Code and its dual, one of which is new. Efficient decoding algorithms are also given, both for erasure correcting and for error correcting. The existence of perfect one-factorizations for every complete graph with an even number of nodes is a 35 years long conjecture in graph theory. The construction of B-Codes of arbitrary odd length will provide an affirmative answer to the conjecture.

For any simplicial complex $\Delta $ and field K, one can associate a graded K-algebra $K[\Delta ]$ (the Stanley–Reisner ring). For certain $\Delta $ and K, the Stanley–Reisner rings have a homogeneous system of parameters, $\Theta $, such that $K[\Delta ]/\langle \Theta \rangle $ is finite-dimensional, and coefficients of its Hilbert series are the h-vector of $\Delta $. The previous constructions of $\Theta $ were noncombinatorial. In the special case of cographic matroids, we give (for any field K) a combinatorial description of a homogeneous system of parameters in terms of the graph structure, as well as an explicit basis for the resulting quotient algebra. The results have applications to a central problem of reliability, namely the association of a multicomplex to a connected graph, such that the reliability is a simple function of the rank numbers.

We investigate a class of generating series which enumerate multi-analogues of set partitions with very general weights and constraints imposed, and develop some of the relevant theory. The weights and constraints we consider are embodied in the definition of a “system,” which includes weighted multiset systems as a simple special case. Three topics are discussed. First, we derive a composition formula valid for all systems, which specializes to composition formulas for familiar combinatorial structures in many cases. Second, we extend the Heilmann–Lieb theorem on matching polynomials to a similar statement valid for more general factors of multigraphs. Finally, we introduce a multi-analogue of the order polynomial of a labelled poset, and by applying our general composition theorem give a formula for the effect of composition of labelled posets on their E-polynomials.