Complete balanced Howell rotations for 8k+5 teams

Complete balanced Howell rotations are mathematical designs for highly structured paired-comparison experiments. They have been widely used in bridge tournaments, and many special cases are applicable to round-robin tournaments for all kinds of sports. In this paper we construct complete balanced Howell rotations of 8k + 5 teams, for 8k + 5 a prime power greater than 5. We also show that “table balanced” complete balanced Howell rotations for 8k + 5 teams do not exist unless 8k + 5 is the sum of two squares of integers.     

New constructions for balanced Howell rotations

Howell rotations have been used in bridge tournaments for a long time. But it was not until 1955 that Parker and Mood first gave a rigorous definition of a balanced Howell rotation and began a systematic study of its mathematical properties. Later, Berlekamp and Hwang extended this work to the study of complete balanced Howell rotations (which are special cases of balanced Howell rotations). Surprisingly, even though the concept of balanced Howell rotations precedes that of complete balanced Howell rotations, systematic construction methods have been studied only for the latter. Most of these construction methods use the properties of a Galois field GF(p^γ) where p^γ is a prime power. In this paper, we use the properties of a Galois domain GD(p^γq^s) to construct balanced Howell rotations for n partnerships where n ? 1 is the product of two prime powers satisfying certain conditions. In particular, we construct a balanced Howell rotation for 36 partnerships, this being the smallest number for which the existence of a balanced Howell rotation was not previously known. We also give two composition methods for the constructions of balanced Howell rotations.     

New classes of complete balanced Howell rotations

Complete balanced Howell rotations (CBHR) owe their origins to duplicate bridge tournaments but have since been shown to possess of deep combinatorial properties. They include many other combinatorial designs as special cases, such as: balanced Howell rotations, weak complete balanced Howell rotations, Room squares, Howell designs, and a class of balanced incomplete block designs.All known CBHR's are for n partnerships such that n = 2^t(p^r + 1), where p^r is an odd prime power and t a natural number. In most cases, p^r ≡ 3(mod 4) is also assumed. Berlekamp and Hwang gave constructions of CBHR's for each such n > 3 with t = 0; Schellenberg gave constructions for each such n with t = 1. In this paper, we construct CBHR for each such n with t arbitrary.     

Characterization of the graphs of the Johnson schemes G(3k, k) and G(3k + 1, k)

The graphs of the Johnson schemes G(3k, k) and G(3k + 1, k) are characterized by their parameters. In particular this finishes the characterization of the tetrahedral graphs G(n, 3).     

On the mutual embeddability of (2k, k, k − 1) and (2k − 1, k, k) quasi-residual designs

The complements of blocks containing a given point in a (2k ? 1, k, k) design, enlarged by this point, and the blocks not containing it, form a (2k ? 1, k, k) design. Likewise, the complements of blocks containing a given point in a (2k, k, k ? 1) design and the blocks not containing it, form a (2k ? 1, k, k) design. In this paper we show that if a quasi-residual (2k ? 1, k, k) design is obtained from an embeddable (2k ? 1, k, k) or (2k, k, k ? 1) design, then it is also embeddable, and describe an example of non-embeddable (12, 6, 5) design such that all (11, 6, 6) designs obtained from it are embeddable.     

On integers of the forms k−2 and k2+1

In this paper we prove that if (r,12)?3, then the set of positive odd integers k such that k^r−2ⁿ has at least two distinct prime factors for all positive integers n contains an infinite arithmetic progression. The same result corresponding to k^r2ⁿ+1 is also true.     

Howell designs of type H(P − 1, P + 1)

If p > 3 is a prime, it is shown that a Howell design of type H(p ? 1, p + 1) can be constructed. When p = 5 or p > 3 and p ≡ ±3, ±13 (mod 40), the construction can be accomplished by an extension of the familiar strong starter method used to build Room squares.     

Polynomial algorithms for m × (m + 1) integer programs and m × (m + k) diophantine systems

Recent results of Kannan and Bachem (on computing the Smith Normal Form of a matrix) and Lenstra (on solving integer inequality systems) are used with classical results by Smith to obtain polynomial-time algorithms for solving m × (m + 1) equality constrained integer programs and m × (m + k) systems of diophantine equations for fixed k.     

On some t−(2k, k, λ) designs

t?(2k, k, λ) designs having a property similar to that of Hadamard 3-designs are studied. We consider conditions (i), (ii), or (iii) for t?(2k, k, λ) designs: (i) The complement of each block is a block. (ii) If A and B are a complementary pair of blocks, then ∥ A ∩ C ∥ = ∥ B ∩ C ∥ ± u holds for any block C distinct from A and B, where u is a positive integer. (iii) if A and B are a complementary pair of blocks, then ∥ A ∩ C ∥ = ∥ B ∩ C ∥ or ∥ A ∩ C ∥ = ∥ B ∩ C ∥ ± u holds for any block C distinct from A and B, where u is a positive integer. We show that a t?(2k, k, λ) design with t ? 2 and with properties (i) and (ii) is a 3?(2u(2u + 1), u(2u + 1), u(2u² + u ? 2)) design, and that a t?(2k, k, λ) design with t ? 4 and with properties (i) and (iii) is the 5-(12, 6, 1) design, the 4-(8, 4, 1) design, a $\text{5?(2u}{}^2\text{, u}{}^2\text{,}\text{1}\text{4}\text{(u}{}^2\text{? 3) (u}{}^2\text{? 4))}$ design, or a $\text{5?(}\text{2}\text{3}\text{u(2u + 1),}\text{1}\text{3}\text{u(2u = 1),}\text{1}\text{5 4}\text{u(2u}{}^2\text{+ u ? 9) (2u}{}^2\text{+ u ? 12))}$ design.     

Characterization of k-variegated graphs, k ⩾ 3

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. Bednarek and Sanders [1] posed the problem of characterizing k-variegated graphs. V.N. Bhat-Nayak, S.A. Choudum and R.N. Naik [2] gave the characterization of 2-variegated graphs. In this paper we characterize k-variegated graphs for k ? 3.     

Averaging the k largest distances among n: k-centra in Banach spaces

Given a Banach space X let A⊂X containing at least k points. In location theory, reliability analysis, and theoretical computer science, it is useful to minimize the sum of distances from the k furthest points of A: this problem has received some attention for X a finite metric space (a network), see, e.g., [Discrete Appl. Math. 109 (2001) 293]; in the case X=Eⁿ, k=2 or 3, and A compact some results have been given in [Math. Notes 59 (1996) 507]; also, in the field of theoretical computer science it has been considered in [T. Tokuyama, Minimax parametric optimization problems in multi-dimensional parametric searching, in: Proc. 33rd Annu. ACM Symp. on Theory of Computing, 2001, pp. 75-84]. Here we study the above problem for a finite set A⊂X, generalizing—among others things—the results in [Math. Notes 59 (1996) 507].     

A multiplication theorem for balanced howell rotations

The concept of partitionable starters is introduced and it is shown how to construct: a balanced Howell rotation on mn players from a balanced Howell rotation on n players, a balanced Howell rotation on m players, and a partitionable starter on m players. Two results concerning the existence of partitionable starters are proved     

Sums and k-sums in abelian groups of order k

Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence a₁,…,ar that does not have 0 as a k-sum is attained at the sequence b₁,…,br−k+1,0,…,0, where b₁,…,br−k+1 is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value k−1 times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader.     

Singular sets for curvature equation of order k

We consider the removability of singular sets for the curvature equations of the form Hk[u]=ψ, which is determined by the kth elementary symmetric function, in an n-dimensional domain Ω. We prove that, for 1?k?n−1 and a compact set K whose (n−k)-dimensional Hausdorff measure is zero, any generalized solution to the curvature equation on Ω?K is always extendable to a generalized solution on the whole domain Ω.     

On 2-factors with k components

In this paper we study the minimum degree condition for a Hamiltonian graph to have a 2-factor with k components. By proving a conjecture of Faudree et al. [A note on 2-factors with two components, Discrete Math. 300 (2005) 218-224] we show the following. There exists a real number ε>0 such that for every integer k?2 there exists an integer n₀=n₀(k) such that every Hamiltonian graph G of order n?n₀ with has a 2-factor with k components.     

2-designs having an intersection number k − n

In this paper we examine 2-designs having an intersection number k ? n. This intersection number gives rise to an equivalence relation on the blocks of the design. Conditions on the sizes of these equivalence classes and some properties of any further intersection numbers are obtained. If such a design has at most three intersection numbers then it gives rise to a strongly regular graph. This leads to a result on the embedding of quasi-residual designs. As as example a quasi-residual 2-(56, 12, 3) design is constructed and embedded in a symmetric 2-(71, 15, 3) design.