Enumerating Motzkin–Rabin geometries

The main result of this paper is an enumeration of all Motzkin‐Rabin geometries on up to 18 points. A Motzkin‐Rabin geometry is a two‐colored linear space with no monochromatic line. We also study the embeddings of Motzkin‐Robin geometries into projective spaces over fields and division rings. We find no Motzkin‐Rabin geometries on up to 18 points embeddable in ?² or ??₂(t)². We find many examples of Motzkin‐Rabin geometries with no proper linear subspaces. We give an example of a proper linear space embeddable in ?(?( )²). © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 179–194, 2007     

There is no Drake/Larson linear space on 30 points

A linear space is Drake/Larson if it contains at least two lines and there are no lines of size 2, 3 or 6. The existence or nonexistence of such linear spaces on v points is known except for v=30. The purpose of this article is to settle the remaining case on thirty points in the negative. This result relies on a combination of parameter calculation and exhaustive computer search. © 2009 Wiley Periodicals, Inc. J Combin Designs 28: 48–70, 2010     

Super‐simple resolvable balanced incomplete block designs with block size 4 and index 2

The necessary conditions for the existence of a super‐simple resolvable balanced incomplete block design on v points with block size k = 4 and index λ = 2, are that v ≥ 16 and . These conditions are shown to be sufficient. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 341–356, 2007     

Commuting decompositions of complete graphs

We say that two graphs G and H with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number r, the complete multigraph K is decomposable into commuting perfect matchings if and only if n is a 2‐power. Also, it is shown that the complete graph K_n is decomposable into commuting Hamilton cycles if and only if n is a prime number. © 2006 Wiley Periodicals, Inc. J Combin Designs     

A Steiner 2-design with an automorphism fixing exactly r + 2 points

Doyen conjectured that there is no Steiner 2-design having an automorphism with more than r + 1 but fewer than fixed points, where r is the replication number. The falsity of this conjecture is shown by describing 2-(45, 5, 1) designs having an automorphism of order 2 with exactly 13 fixed points. © 1999 John Wiley & Sons, Inc. J Combin Design 7: 375–380, 1999     

Binary caps with many free pairs of points

We introduce the following new viewpoint in the study of caps in PG(m,q). The objective is to maximize, among all caps of given cardinality in a given projective space, the number of free pairs of points, which we define as pairs of points not participating in any coplanar quadruple of points of the cap. We survey the known results (which were motivated by an application in statistical experiment design) and then we improve the known lower bound on the number of free pairs of points for q = 2 and the smallest cap sizes for which the maximization problem is non‐trivial. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 490–499, 2006     

A Class of 2‐(3n7, 3n−17, (3n−17−1)/2) Designs

Generalized Hadamard matrices are used for the construction of a class of quasi‐residual nonresolvable BIBD's with parameters . The designs are not embeddable as residual designs into symmetric designs if n is even. The construction yields many nonisomorphic designs for every given n ≥ 2, including more than 10¹⁷ nonisomorphic 2‐(63,21,10) designs. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 460–464, 2007     

A short proof of Totten's classification of restricted linear spaces

A restricted linear space is one which satisfies (b–v)²v, where b is the number of lines and v is the number of points. In 1976, Totten classified all restricted linear spaces as being of essentially three types. In this paper we give a short, self-contained proof of this result. Our approach is greatly simplified by the use of techniques from linear algebra.This work was supported in part by National Science Foundation Grant MCS-8217596.     

The spectrum of equitable, 4‐chromatic Steiner quadruple systems

A Steiner quadruple system of order v (briefly an SQS(v)) is a pair (X, ) with |X| = v and a set of quadruples taken from X such that every triple in X is in a unique quadruple in . Hanani [Canad J Math 12 (1960), 145–157] showed that an SQS(v) exists if and only if v is {admissible}, that is, v = 0,1 or v ≡ 2,4 (mod 6). Each SQS(v) has a chromatic number when considered as a 4‐uniform hypergraph. Here we show that a 4‐chromatic SQS(v) exists for all admissible v ≥ 20, and that no 4‐chromatic SQS(v) exists for v < 20. Each system we construct admits a proper 4‐coloring that is equitable, that is, any two color classes differ in size by at most one. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 369–392, 2007     

A classification of linear spaces based on quadrangles III

A quadrangle in a linear space can have at most 3 diagonal points. Denoting by d(Q) the number of diagonal points of a quadrangle Q, we say that a linear space L is of type T {0, 1, 2, 3}, if T is the set of values taken by d(Q) for all quadrangles Q in L. This determines a classification of linear spaces into 16 possible types. In this paper we discuss type {0, 2} finite linear spaces, determining precisely the nature of their planes and establishing a strong relationship between them and the group theoretic work of Fischer and Aschbacher and Hall.J.T. acknowledges financial support for this research by the National Research Council of Canada.     

Doubly transitive 2‐factorizations

Let be a 2‐factorization of the complete graph K_v admitting an automorphism group G acting doubly transitively on the set of vertices. The vertex‐set V(K_v) can then be identified with the point‐set of AG(n, p) and each 2‐factor of is the union of p‐cycles which are obtained from a parallel class of lines of AG(n, p) in a suitable manner, the group G being a subgroup of A G L(n, p) in this case. The proof relies on the classification of 2‐(v, k, 1) designs admitting a doubly transitive automorphism group. The same conclusion holds even if G is only assumed to act doubly homogeneously. © 2006 Wiley Periodicals, Inc. J Combin Designs     

Closed trail decompositions of complete equipartite graphs

The complete equipartite graph $K_m * {\overline{K_n}}$ has mn vertices partitioned into m parts of size n, with two vertices adjacent if and only if they are in different parts. In this paper, we determine necessary and sufficient conditions for the existence of a decomposition of $K_m * {\overline{K_n}}$ into closed trails of length k. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 374–403, 2009     

Completing Latin squares: Critical sets II

It is shown that each critical set in a Latin square of order n > 6 has to have at least empty cells. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 77–83, 2007     

Linear Ramsey Numbers for Bounded-Degree Hypergrahps

We show that the Ramsey number is linear for every uniform hypergraph with bounded degree. This is a hypergraph extension of the famous theorem for ordinary graphs which Chvátal et al. [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, Jr., The Ramsey number of a graph with bounded maximum degree, J. Combin. Theory Ser. B 34 (1983), pp. 239–243] showed in 1983. Our proof demonstrates the potential of a new regularity lemma by [Y. Ishigami, A simple regularization of hypergraphs, preprint, arXiv:math/0612838 (2006)].     

The lotto numbers L(n,3,p,2)

An (n,k,p,t)‐lotto design is an n‐set N and a set of k‐subsets of N (called blocks) such that for each p‐subset P of N, there is a block for which . The lotto number L(n,k,p,t) is the smallest number of blocks in an (n,k,p,t)‐lotto design. The numbers C(n,k,t) = L(n,k,t,t) are called covering numbers. It is easy to show that, for n ≥ k(p ? 1), For k = 3, we prove that equality holds if one of the following holds:

• (i) n is large, in particular
• (ii)
• (iii) 2 ≤ p ≤ 6.

© 2006 Wiley Periodicals, Inc. J Combin Designs 14: 333–350, 2006     

D‐optimal designs and group divisible designs

We obtain new conditions on the existence of a square matrix whose Gram matrix has a block structure with certain properties, including D‐optimal designs of order , and investigate relations to group divisible designs. We also find a matrix with large determinant for n = 39. © 2006 Wiley Periodicals, Inc. J Combin Designs 14: 451–462, 2006     

Configuration distribution and designs of codes in the Johnson scheme

The main goal of this article is to present several connections between perfect codes in the Johnson scheme and designs, and provide new tools for proving Delsarte conjecture that there are no nontrivial perfect Codes in the Johnson scheme. Three topics will be considered. The first is the configuration distribution which is akin to the weight distribution in the Hamming scheme. We prove that if there exists an e‐perfect code in the Johnson scheme then there is a formula which connects the number of vectors at distance i from any codeword in various codes isomorphic to . The second topic is the Steiner systems embedded in a perfect code. We prove a lower bound on the number of Steiner systems embedded in a perfect code. The last topic is the strength of a perfect code. We show two new methods for computing the strength of a perfect code and demonstrate them on 1‐perfect codes. We further discuss how to settle Delsarte conjecture. © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 15–34, 2007     

Unitals of PG(2,q2) Containing Conics

A unital in PG(2, q²) is a set of points such that each line meets in 1 or points. The well‐known example is the classical unital consisting of all absolute points of a unitary polarity of PG(2, q²). Unitals other than the classical one also exist in PG(2, q²) for every . Actually, all known unitals are of Buekenhout–Metz type [see F. Buekenhout, Geom Dedicata 5 (1976), 189–194, R. Metz, Geom Dedicata 8 (1979), 125–126.], and they can be obtained by a construction due to F. Buekenhout, (Geom Dedicata 5 (1976), 189–194).. The unitals constructed by R. D. Baker and G. L. Ebert (J Combin Theory Ser A 60 (1992), 67–84), and independently by J. W. P. Hirschfeld and T. Sz?nyi (Discrete Math 97 (1991), 229–242), are the union of q conics. Our Theorem  1.1 shows that this geometric property characterizes the Baker–Ebert–Hirschfeld–Sz?nyi unitals. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 101–111, 2013     

Tiling 3‐Uniform Hypergraphs With

Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3‐uniform hypergraph G of order n with minimum pair‐degree contains vertex‐disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636).     

Applications of Hajós‐Type Constructions to the Hedetniemi Conjecture

Hedetniemi conjectured in 1966 that if G and H are finite graphs with chromatic number n, then the chromatic number of the direct product of G and H is also n. We mention two well‐known results pertaining to this conjecture and offer an improvement of the one, which partially proves the other. The first of these two results is due to Burr et al. (Ars Combin 1 (1976), 167–190), who showed that when every vertex of a graph G with is contained in an n‐clique, then whenever . The second, by Duffus et al. (J Graph Theory 9 (1985), 487–495), and, obtained independently by Welzl (J Combin Theory Ser B 37 (1984), 235–244), states that the same is true when G and H are connected graphs each with clique number n. Our main result reads as follows: If G is a graph with and has the property that the subgraph of G induced by those vertices of G that are not contained in an n‐clique is homomorphic to an ‐critical graph H, then . This result is an improvement of the result by the first authors. In addition we will show that our main result implies a special case of the result by the second set of authors. Our approach will employ a construction of a graph F, with chromatic number , that is homomorphic to G and H.