On the dimension of affine resolvable designs and hypercubes

The equivalence between complete sets of mutually orthogonal hypercubes and affine resolvable designs, which generalizes the well-known equivalence between complete sets of mutually orthogonal latin squares and affine planes, is used to examine the dimension of designs by studying the prime classes in the associated hypercubes. Particular attention is given to designs of order n=9 including a design which is nonisomorphic to AG(3, 9) even though it possesses the same parameters and three prime classes. © 1996 John Wiley & Sons, Inc.     

Small cutsets in arc-transitive digraphs of prime degree

We give an upper bound for the size of non-trivial sets that have small boundary in a family of arc-transitive digraphs. We state the exact size for these sets in case of prime degree. We also give a lower bound for the size of a minimum non-trivial cutset in the case of arc-transitive Cayley digraphs of prime degree.     

A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs

We prove that, for a certain positive constant a and for an infinite set of values of n, the number of nonisomorphic triangular embeddings of the complete graph K_n is at least n^an2. A similar lower bound is also given, for an infinite set of values of n, on the number of nonisomorphic triangular embeddings of the complete regular tripartite graph K_n,n,n.     

Degenerate alternative algebras

We prove that each degenerate alternative algebra of characteristic ≠ 2 contains a nonzero ideal with an additive basis consisting of the absolute zero divisors of an arbitrary large order. As a corollary we establish the existence of infinitely many nonisomorphic commutative prime alternative algebras and existence of infinite series of strict and nonstrict exceptional alternative algebras with different sets of proper identities.     

On nonabelian simple groups having the same prime graph as an alternating group

All instances of coincidence between the prime graphs of nonabelian simple groups G and S are found, where G is an alternating group of degree n ≥ 5 and S is a nonabelian finite simple group. The precise bound of the maximal number of pairwise nonisomorphic nonabelian simple groups with the same prime graph is given in the case that one of these groups is an alternating group.     

Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles

We provide a variety of new upper and lower bounds and simpler proof techniques for the efficient construction of binary space partitions (BSPs) of axis-parallel rectangles of various dimensions. (a) We construct a set of $n$ disjoint axis-parallel segments in the plane such that any binary space auto-partition has size at least $2n-o(n)$, almost matching an upper bound of dAmore and Franciosa. (b) We establish a similar lower bound of $7n/3-o(n)$ for disjoint rectangles in the plane. (c) We simplify and improve BSP constructions of Paterson and Yao for disjoint segments in $\reals^d$ and disjoint rectangles in $\reals^3$. (d) We derive a worst-case bound of $\Theta(n^{5/3})$ for the size of BSPs of disjoint $2$-rectangles in $4$-space. (e) For disjoint $k$-rectangles in $d$-space, we prove the worst-case bound $\Theta(n^{d/(d-k)})$, for any $k<d/2$; this bound holds for all $k<d$ if the rectangles are allowed to intersect.     

Greedy matching in Young's lattice

If the level sets of a ranked partially ordered set are totally ordered, the greedy match between adjacent levels is defined by successively matching each vertex on one level to the first available unmatched vertex, if any, on the next level. Aigner showed that the greedy match produces symmetric chains in the Boolean algebra. We extend that result to partially ordered sets which are products of chains.It is widely thought that for Young's lattices corresponding to rectangles, the greedy match is complete. We show here that the greedy match is, in fact, complete for n×2, n×3 and n×4 rectangles but not for n×k rectangles if k5 and n is sufficiently large.     

Symmetric (41,16,6)-designs with a nontrivial automorphism of odd order

If a symmetric (41,16,6)-design has an automorphism σ of odd prime order q then q = 3 or 5. In the case q = 5 we determine all such designs and find a total of 419 nonisomorphic ones, of which 15 are self-dual. When q = 3 a combinatorial explosion occurs and the complete classification becomes impracticable. However, we give a characterization in the particular case when σ has order 3 and fixes 11 points, and find that there are 3,076 nonisomorphic designs with this property, all of them being non self-dual. The other remaining possibility is that σ, of order 3, fixes 5 points. In this case there are 960 orbit matrices (up to isomorphism and duality) and all but one of them yield designs. Here an incomplete investigation shows that in total there are at least 112,000 nonisomorphic designs. © 1993 John Wiley & Sons, Inc.     

Simplest optimal cutting patterns for equal rectangles

This paper presents branch-and-bound algorithms that can guarantee the simplest optimal cutting patterns of equal rectangles. An existing linear algorithm determines the global upper bound exactly. The branching process ends when a branch of a lower bound equal to the global upper bound is found.     

A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs

We prove a theorem that for an integer s?0, if 12s+7 is a prime number, then the number of nonisomorphic face 3-colorable nonorientable triangular embeddings of K_n, where n=(12s+7)(6s+7), is at least . By some number-theoretic arguments there are an infinite number of integers s satisfying the hypothesis of the theorem. The theorem is the first known example of constructing at least 2^αn?+o(n?), ?>1, nonisomorphic nonorientable triangular embeddings of K_n for n=6t+1, . To prove the theorem, we use a new approach to constructing nonisomorphic triangular embeddings of complete graphs. The approach combines a cut-and-paste technique and the index one current graph technique. A new connection between Steiner triple systems and constructing triangular embeddings of complete graphs is given.     

Performance Bound for Bottom-Left Guillotine Packing of Rectangles

In this article we show that bottom-left guillotine placement of rectangles ordered by decreasing width in a fixed-width bin is not more than three times the height of an optimal placement. This bound is also true for bottom-left placement of rectangles without the guillotine constraints. Thus, bottom-left guillotine placement in which rectangles are ordered by decreasing width has the same worst case performance bound as bottom-left placement of rectangles without guillotine constraints.     

Klarner systems and tiling boxes with polyominoes

Let T be a protoset of d-dimensional polyominoes. Which boxes (rectangular parallelepipeds) can be tiled by T? A nice result of Klarner and Göbel asserts that the answer to this question can always be given in a particularly simple form, namely, by giving a finite list of “prime” boxes. All other boxes that can be tiled can be deduced from these prime boxes. We give a new, simpler proof of this fundamental result. We also show that there is no upper bound to the number of prime boxes, even when restricting attention to singleton protosets. In the last section, we determine the set of prime rectangles for several small polyominoes.     

Properties of complete sets of mutually equiorthogonal frequency hypercubes

A complete set of mutually equiorthogonal frequency hypercubes (MEFH) of ordern and dimensiond, usingm distinct symbols, has (n−1) ^d /(m−1) hypercubes. In this article, we explore the properties of complete sets of MEFH. As a consequence of these properties, we show that existence of such a set implies that the number of symbolsm is a prime power. We also establish an equivalence between existence of a complete set of MEFH and existence of a certain complete set of Latin hypercubes and a certain complete orthogonal array.     

Online strip packing with modifiable boxes

In the strip packing problem the goal is to pack a set of rectangles into a vertical strip so as to minimize the total height of the strip needed. We consider a modified version of the strip packing problem. In this version it is allowed to change the form of the rectangles by lengthening them, keeping the area fixed. We introduce online algorithms to solve this modified problem. Moreover a lower bound is presented, as well.     

The Number of Cyclic Configurations of Type (v3) and the Isomorphism Problem

A configuration of points and lines is cyclic if it has an automorphism that permutes its points in a full cycle. A closed formula is derived for the number of nonisomorphic connected cyclic configurations of type (v₃), i.e. which have v points and lines, and each point/line is incident with exactly three lines/points. In addition, a Bays–Lambossy type theorem is proved for cyclic configurations if the number of points is a product of two primes or a prime power.     

On Ordered Sets with Isomorphic Marked Maximal Cards

We prove a necessary condition for two nonisomorphic ordered sets to have two isomorphic marked maximal cards. This condition is used to prove that ordered sets of width 3 with 2 maximal elements are reconstructible and that ordered sets of width 3 are reconstructible if we can reconstruct the marked maximal deck.     

Values of automorphic L-functions with prime power level at the point $$$$

We discuss in this work the distributions of values of L(1, f), where f is a primitive cusp form whose level is a prime power. We prove the upper bound part of the Montgomery–Vaughan’s first conjecture and give a weaker version of the lower bound part for automorphic L-functions in this case. We establish an unweighted trace formula in aspect of prime power level in our proof.     

Multimagic rectangles based on large sets of orthogonal arrays

Large sets of orthogonal arrays (LOAs) have been used to construct resilient functions and zigzag functions by Stinson. In this paper, an application of LOAs in constructing multimagic rectangles is given. Further, some recursive constructions for multimagic rectangles are presented, and some infinite families of bimagic rectangles are obtained.     

Negative Latin square type partial difference sets in nonabelian groups of order 64

There exist few examples of negative Latin square type partial difference sets (NLST PDSs) in nonabelian groups. We present a list of 176 inequivalent NLST PDSs in 48 nonisomorphic, nonabelian groups of order 64. These NLST PDSs form 8 nonisomorphic strongly regular graphs. These PDSs were constructed using a combination of theoretical techniques and computer search, both of which are described. The search was run exhaustively on 212/267 nonisomorphic groups of order 64.     

A note on Romanov's constant

Summary In 1934 Romanov showed that a positive proportion of the natural numbers can be written as the sum of a prime and a power of two. Yong-Gao Chen and Xue-Gong Sun proved recently that the lower asymptotic density of this set is larger than 0.0868. We improve this bound to 0.09368 and show various connections with the generalized twin prime problem and the Goldbach-Linnik problem.