Geometric isomorphism check for symmetric factorial designs

Two designs are geometrically isomorphic if one design can be obtained from the other by reordering the runs, relabeling the factors and/or reversing the level order of one or more factors. In this paper, some new necessary and sufficient conditions for identifying geometric isomorphism of symmetric designs with prime levels are provided. A new algorithm for checking geometric isomorphism is proposed and a searching result for geometrically non-isomorphic 3-level orthogonal arrays of 18 runs is presented.     

A non-factorial algorithm for canonical numbering of a graph

A graph certificate or canonical form is a short unique (up to isomorphism) representation of the graph. Thus two graphs are isomorphic iff their certificates are identical. In this paper an O(cⁿ) graph isomorphism algorithm which also yields a certificate of the graph is presented. The certificate produced by this algorithm is a canonical numbering of the vertices of the graph.     

Some remarks on permutation designs

A definition of isomorphism of two permutation designs is proposed, which differs from the definition in Bandt [J. Combinatorial Theory Ser. A21 (1976), 384–392]. The proposed definition has the (generally required) property that the allowed permutations always transform a permutation design into a permutation design. It is shown that the n permutation designs coming from the partitioning of S_n into permutation designs, as constructed in Bandt [J. Combinatorial Theory Ser. A21 (1976), 384–392] are all isomorphic. Further we find that this modified definition does not increase the number of nonisomorphic (6, 4) permutation designs. The same investigation showed that one of the designs, claimed to be a (6, 4) permutation design in [J. Combinatorial Theory Ser. A21 (1976), 384–392], is actually not a (6, 4) permutation design.     

A note on optimal foldover four-level factorials

The foldover is a quick and useful technique in construction of fractional factorial designs, which typically releases aliased factors or interactions. The issue of employing the uniformity criterion measured by the centered L ₂-discrepancy to assess the optimal foldover plans was studied for four-level design. A new analytical expression and a new lower bound of the centered L ₂-discrepancy for fourlevel combined design under a general foldover plan are respectively obtained. A necessary condition for the existence of an optimal foldover plan meeting this lower bound was described. An algorithm for searching the optimal four-level foldover plans is also developed. Illustrative examples are provided, where numerical studies lend further support to our theoretical results. These results may help to provide some powerful and efficient algorithms for searching the optimal four-level foldover plans.     

Combinatorial families enumerated by quasi-polynomials

We say that the sequence (an) is quasi-polynomial in n if there exist polynomials P₀,…,Ps−1 and an integer n₀ such that, for all n?n₀, an=Pi(n) where . We present several families of combinatorial objects with the following properties: Each family of objects depends on two or more parameters, and the number of isomorphism types of objects is quasi-polynomial in one of the parameters whenever the values of the remaining parameters are fixed to arbitrary constants. For each family we are able to translate the problem of counting isomorphism types of objects into the problem of counting integer points in a union of parametrized rational polytopes. The families of objects to which this approach is applicable include combinatorial designs, linear and unrestricted codes, and dissections of regular polygons.     

The application of invariant theory to the existence of quasi-symmetric designs

Gleason and Mallows and Sloane characterized the weight enumerators of maximal self-orthogonal codes with all weights divisible by 4. We apply these results to obtain a new necessary condition for the existence of 2 − (v, k, λ) designs where the intersection numbers s₁…,s_n satisfy s₁ ≡ s₂ ≡ … ≡ s_n (mod 2). Non-existence of quasi-symmetric 2−(21, 18, 14), 2−(21, 9, 12), and 2−(35, 7, 3) designs follows directly from the theorem. We also eliminate quasi-symmetric 2−(33, 9, 6) designs. We prove that the blocks of quasi-symmetric 2−(19, 9, 16), 2−(20, 10, 18), 2-(20,8, 14), and 2−(22, 8, 12) designs are obtained from octads and dodecads in the [24, 12] Golay code. Finally we eliminate quasi-symmetric 2−(19,9, 16) and 2-(22, 8, 12) designs.     

Some optimal criteria of model-robustness for two-level non-regular fractional factorial designs

We present some optimal criteria to evaluate model-robustness of non-regular two-level fractional factorial designs. Our method is based on minimizing the sum of squares of all the off-diagonal elements in the information matrix, and considering expectation under appropriate distribution functions for unknown contamination of the interaction effects. By considering uniform distributions on the symmetric support, our criteria can be expressed as linear combinations of B _s (d) characteristic, which is used to characterize the generalized minimum aberration. We give some empirical studies for 12-run non-regular designs to evaluate our method.     

Optimum two level fractional factorial plans for model identification and discrimination

Model identification and discrimination are two major statistical challenges. In this paper we consider a set of models M_k for factorial experiments with the parameters representing the general mean, main effects, and only k out of all two-factor interactions. We consider the class D of all fractional factorial plans with the same number of runs having the ability to identify all the models in M_k, i.e., the full estimation capacity.The fractional factorial plans in D with the full estimation capacity for k?2 are able to discriminate between models in M_u for u?k^*, where k^*=(k/2) when k is even, k^*=((k-1)/2) when k is odd. We obtain fractional factorial plans in D satisfying the six optimality criterion functions AD, AT, AMCR, GD, GT, and GMCR for 2^m factorial experiments when m=4 and 5. Both single stage and multi-stage (hierarchical) designs are given. Some results on estimation capacity of a fractional factorial plan for identifying models in M_k are also given. Our designs D4.1 and D10 stand out in their performances relative to the designs given in Li and Nachtsheim [Model-robust factorial designs, Technometrics 42(4) (2000) 345-352.] for m=4 and 5 with respect to the criterion functions AD, AT, AMCR, GD, GT, and GMCR. Our design D4.2 stands out in its performance relative the Li-Nachtsheim design for m=4 with respect to the four criterion functions AT, AMCR, GT, and GMCR. However, the Li-Nachtsheim design for m=4 stands out in its performance relative to our design D4.2 with respect to the criterion functions AD and GD. Our design D14 does have the full estimation capacity for k=5 but the twelve run Li-Nachtsheim design does not have the full estimation capacity for k=5.     

Two graph isomorphism polytopes

The convex hull ψ_n,n of certain (n!)² tensors was considered recently in connection with graph isomorphism. We consider the convex hull ψ_n of the n! diagonals among these tensors. We show: 1. The polytope ψ_n is a face of ψ_n,n. 2. Deciding if a graph G has a subgraph isomorphic to H reduces to optimization over ψ_n. 3. Optimization over ψ_n reduces to optimization over ψ_n,n. In particular, this implies that the subgraph isomorphism problem reduces to optimization over ψ_n,n.     

On a geometrical method of construction of maximal t-linearly independent sets

The problem of constructing a maximal t-linearly independent set in V(r; s) (called a maximal L_t(r, s)-set in this paper) is a very important one (called a packing problem) concerning a fractional factorial design and an error correcting code where V(r; s) is an r-dimensional vector space over a Galois field GF(s) and s is a prime or a prime power. But it is very difficult to solve it and attempts made by several research workers have been successful only in special cases.In this paper, we introduce the concept of a {Σ_α=1^kw_α, m; t, s}-min · hyper with weight (w₁, w₂,…, w_k) and using this concept and the structure of a finite projective geometry PG(n ? 1, s), we shall give a geometrical method of constructing a maximal L_t(t + r, s)-set with length t + r + n for any integers r, n, and s such that n ? 3, n ? 1 ? r₀ ? n + s ? 2 and r₁ ? 1, where r = (r₁ + 1)v_n?1 ? r₀ and $\text{v}{}_{\mathrm{n}}\text{=}\text{(s}{}^{\mathrm{n}}\text{? 1)}\text{(s ? 1)}$.     

Hadamard 2-(63,31,15) designs invariant under the dihedral group of order 10

All Hadamard 2-(63,31,15) designs invariant under the dihedral group of order 10 are constructed and classified up to isomorphism together with related Hadamard matrices of order 64. Affine 2-(64,16,5) designs can be obtained from Hadamard 2-(63,31,15) designs having line spreads by Rahilly’s construction [A. Rahilly, On the line structure of designs, Discrete Math. 92 (1991) 291-303]. The parameter set 2-(64,16,5) is one of two known sets when there exists several nonisomorphic designs with the same parameters and p-rank as the design obtained from the points and subspaces of a given dimension in affine geometry AG(n,p^m) (p a prime). It is established that an affine 2-(64,16,5) design of 2-rank 16 that is associated with a Hadamard 2-(63,31,15) design invariant under the dihedral group of order 10 is either isomorphic to the classical design of the points and hyperplanes in AG(3,4), or is one of the two exceptional designs found by Harada, Lam and Tonchev [M. Harada, C. Lam, V.D. Tonchev, Symmetric (4, 4)-nets and generalized Hadamard matrices over groups of order 4, Designs Codes Cryptogr. 34 (2005) 71-87].     

O(n2.5) time algorithms for the subgraph homeomorphism problem on trees

The complexity of the subgraph homeomorphism problems have been open. We show O(n^2.5) time algorithms when the problems are restricted to trees, directed or undirected. The algorithm can be applied to the subtree isomorphism problem for unrooted trees with the same complexity, and improves over Reyner's O(n^3.5) algorithm for the subtree isomorphism problem.     

Small Box-Behnken design

Box-Behnken design has been popularly used for the second-order response surface model. It is formed by combining two-level factorial designs with incomplete block designs in a special manner—the treatments in each block are replaced by an identical design. In this paper, we construct small Box-Behnken design. These designs can fit the second-order response surface model with reasonably high efficiencies but with only a much smaller run size. The newly constructed designs make use of balanced incomplete block design (BIBD) or partial BIBD, and replace treatments partly by 2_III³⁻¹ designs and partly by full factorial designs. It is shown that the orthogonality properties in the original Box and Behnken designs will be kept in the new designs. Furthermore, we classify the parameters into groups and introduce Group Moment Matrix (GMM) to estimate all the parameters in each group. This allows us to significantly reduce the amount of computational costs in the construction of the designs.     

Description of some classes of Leibniz algebras

In this paper we describe the isomorphism classes of finite-dimensional complex Leibniz algebras whose quotient algebra with respect to the ideal generated by squares is isomorphic to the direct sum of three-dimensional simple Lie algebra sl₂ and a three-dimensional solvable ideal. We choose a basis of the isomorphism classes’ representatives and give explicit multiplication tables.     

On polyvectors of vector spaces and hyperplanes of projective Grassmannians

We investigate relationships between polyvectors of a vector space V, alternating multilinear forms on V, hyperplanes of projective Grassmannians and regular spreads of projective spaces. Suppose V is an n-dimensional vector space over a field F and that A_n-1,k(F) is the Grassmannian of the (k − 1)-dimensional subspaces of PG(V) (1  ? k ? n − 1). With each hyperplane H of A_n-1,k(F), we associate an (n − k)-vector of V (i.e., a vector of ∧^n−kV) which we will call a representative vector of H. One of the problems which we consider is the isomorphism problem of hyperplanes of A_n-1,k(F), i.e., how isomorphism of hyperplanes can be recognized in terms of their representative vectors. Special attention is paid here to the case n = 2k and to those isomorphisms which arise from dualities of PG(V). We also prove that with each regular spread of the projective space PG(2k-1,F), there is associated some class of isomorphic hyperplanes of the Grassmannian A_2k-1,k(F), and we study some properties of these hyperplanes. The above investigations allow us to obtain a new proof for the classification, up to equivalence, of the trivectors of a 6-dimensional vector space over an arbitrary field F, and to obtain a classification, up to isomorphism, of all hyperplanes of A_5,3(F).     

The existence of Howell designs of odd side

Three recursive constructions for Howell designs are described, and it is shown that all Howell designs H(s, 2n) exist, with s odd, n ? s ? 2n ? 1, (s, 2n) ≠ (3, 4), (5, 6), or (5, 8). This settles the existence question for Howell designs of odd side.     

An analytic approach to stability

The stability method is very useful for obtaining exact solutions of many extremal graph problems. Its key step is to establish the stability property which, roughly speaking, states that any two almost optimal graphs of the same order n can be made isomorphic by changing o(n²) edges.Here we show how the recently developed theory of graph limits can be used to give an analytic approach to stability. As an application, we present a new proof of the Erd?s-Simonovits stability theorem.Also, we investigate various properties of the edit distance. In particular, we show that the combinatorial and fractional versions are within a constant factor from each other, thus answering a question of Goldreich, Krivelevich, Newman, and Rozenberg.     

Increasing the convergence rate of series

This paper deals with the question of obtaining from the sequence {s_n} of partial sums of a convergent series s a new sequence {t_n} which converges to the same limit s as s_n, but more rapidly. When the general term u_n of the series s possesses certain types of expansion involving inverse powers of n, it is shown how t_n is obtained by adding a fixed number of terms to s_n. When the series s is convergent, these terms tend to zero as n tends to infinity, but they are such as to make t_n much more rapidly convergent to s—in fact we can make the convergence rate as great as we wish. Explicit general formulas are obtained for a wide range of important series.     

Profiling effects in industrial data mining by non-parametric DOE methods: An application on screening checkweighing systems in packaging operations

There is a growing interest in applying robust techniques for profiling complex processes in industry. In this work, we present an approach for analyzing fractional-factorial data by building distribution-free models suitable for dealing with replicated trials in search of non-linear effects. The technique outlined in this article is synthesized by implementing four key elements: (1) the data collection efficiency of non-linear fractional factorial designs, (2) the data compression capabilities of rank-sums for repetitive sampling schemes, (3) the rank-ordering as a means to transform data, and (4) the non-parametric screening for prominent effects where the normality and sparsity assumptions are waived. The technique is tested on four controlling factors for profiling the packaging weighing operations of a pharmaceutical enterprise. The robust data mining of repeated trials based on an L₉(3⁴) orthogonal array scheme with embedded uncontrolled noise is discussed extensively. The technique has been subjected to quality control as it is tested with well-defined artificial data. Concluding remarks involve contrasting this new technique with mainstream competing schemes.     

On natural isomorphisms of cycle permutation graphs

Two problems are approached in this paper. Given a permutation onn elements, which permutations onn elements yield cycle permutation graphs isomorphic to the cycle permutation graph yielded by the given permutation? And, given two cycle permutation graphs, are they isomorphic? Here the author deals only with natural isomorphisms, those isomorphisms which map the outer and inner cycles of one cycle permutation graph to the outer and inner cycles of another cycle permutation graph. A theorem is stated which then allows the construction of the set of permutations which yield cycle permutation graphs isomorphic to a given cycle permutation graph by a natural isomorphism. Another theorem is presented which finds the number of such permutations through the use of groups of symmetry of certain drawings of cycles in the plane. These drawings are also used to determine whether two given cycle permutation graphs are isomorphic by a natural isomorphism. These two methods are then illustrated by using them to solve the first problem, restricted to natural isomorphism, for a certain class of cycle permutation graphs.