On Turán problems for Cartesian products of graphs

Let be disjoint sets of sizes and . Let be a family of quadruples, having elements from and from , such that any subset with and contains one of the quadruples. We prove that the smallest size of is as . We also solve asymptotically a more general two‐partite Turán problem for quadruples.     

A complete solution to existence of H designs

An H design is a triple , where is a set of points, a partition of into disjoint sets of size , and a set of ‐element transverses of , such that each ‐element transverse of is contained in exactly one of them. In 1990, Mills determined the existence of an H design with . In this paper, an efficient construction shows that an H exists for any integer with . Consequently, the necessary and sufficient conditions for the existence of an H design are , , and , with a definite exception .     

A method to construct 1‐rotational factorizations of complete graphs and solutions to the oberwolfach problem

The concept of a 1‐rotational factorization of a complete graph under a finite group was studied in detail by Buratti and Rinaldi. They found that if admits a 1‐rotational 2‐factorization, then the involutions of are pairwise conjugate. We extend their result by showing that if a finite group admits a 1‐rotational ‐factorization with even and odd, then has at most conjugacy classes containing involutions. Also, we show that if has exactly conjugacy classes containing involutions, then the product of a central involution with an involution in one conjugacy class yields an involution in a different conjugacy class. We then demonstrate a method of constructing a 1‐rotational ‐factorization under given a 1‐rotational 2‐factorization under a finite group . This construction, given a 1‐rotational solution to the Oberwolfach problem , allows us to find a solution to when the ’s are even (), and when is an odd prime, with no restrictions on the ’s.     

The enumeration of cyclic mutually nearly orthogonal Latin squares

In this paper, we study collections of mutually nearly orthogonal Latin squares (MNOLS), which come from a modification of the orthogonality condition for mutually orthogonal Latin squares. In particular, we find the maximum such that there exists a set of cyclic MNOLS of order for , as well as providing a full enumeration of sets and lists of cyclic MNOLS of order under a variety of equivalences with . This resolves in the negative a conjecture that proposed that the maximum for which a set of cyclic MNOLS of order exists is .     

High nonassociativity in order 8 and an associative index estimate

Let be a quasigroup. Put and assume that . Let and be the number of left and right translations of that are fixed point free. Put . Denote by the number of idempotents of . It is shown that . Call extremely nonassociative if . The paper reports what seems to be the first known example of such a quasigroup, with , , and . It also provides supporting theory for a search that verified for all quasigroups of order .     

On the honeymoon Oberwolfach problem

The honeymoon Oberwolfach problem HOP asks the following question. Given newlywed couples at a conference and round tables of sizes , is it possible to arrange the participants at these tables for meals so that each participant sits next to their spouse at every meal and sits next to every other participant exactly once? A solution to HOP is a decomposition of , the complete graph with additional copies of a fixed 1‐factor , into 2‐factors, each consisting of disjoint ‐alternating cycles of lengths . It is also equivalent to a semi‐uniform 1‐factorization of of type ; that is, a 1‐factorization such that for all , the 2‐factor consists of disjoint cycles of lengths . In this paper, we first introduce the honeymoon Oberwolfach problem and then present several results. Most notably, we completely solve the case with uniform cycle lengths, that is, HOP. In addition, we show that HOP has a solution in each of the following cases: ; is odd and ; as well as for all . We also show that HOP has a solution whenever is odd and the Oberwolfach problem with tables of sizes has a solution.     

Covering arrays for some equivalence classes of words

Covering arrays for words of length over a ‐letter alphabet are arrays with entries from the alphabet so that for each choice of columns, each of the ‐letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case known as partitioning hash families, words are equivalent if they induce the same partition of a element set. In the second case, words of the same weight are equivalent. In both cases, we produce logarithmic upper bounds on the minimum size of a covering array. Definitive results for , as well as general results, are provided.     

New necessary conditions on Paley‐type partial difference sets in abelian groups

Let be an abelian group of order , where are distinct odd prime numbers. In this paper, we prove that if contains a regular Paley‐type partial difference set (PDS), then for any is congruent to 3 modulo 4 whenever is odd. These new necessary conditions further limit the specific order of an abelian group in which there can exist a Paley‐type PDS. Our result is similar to a result on abelian Hadamard (Menon) difference sets proved by Ray‐Chaudhuri and Xiang in 1997.     

Dimension of the space generated by Steiner systems

To every Steiner system with parameters on and blocks , we can assign its characteristic vector , which is a ‐vector whose entries are indexed by the ‐subsets of such that for each ‐subset of if and only if . In this paper, we show that the dimension of the vector space generated by all of the characteristic vectors of Steiner systems with parameters is , provided that and there is at least one such system.     

The maximum,supremum, and spectrum for critical set sizes in (0,1)‐matrices

If is a partially filled‐in (0,1)‐matrix with a unique completion to a (0,1)‐matrix (with prescribed row and column sums), then we say that is a defining set for . A critical set is a minimal defining set (the deletion of any entry results in more than one completion). We give a new equivalent definition of critical sets in (0,1)‐matrices and apply this theory to , the set of (0,1)‐matrices of dimensions with uniform row and column sum . The smallest possible size for a defining set of a matrix in is [N. Cavenagh, J. Combin. Des. 21 (2013), pp. 253–266], and the infimum (the largest‐smallest defining set size for members of ) is known asymptotically [N. Cavenagh and R. Ramadurai, Linear Algebra Appl. 537 (2018), pp. 38–47]. We show that no critical set of size larger than exists in an element of and that there exists a critical set of size in an element of for each such that . We also bound the supremum (the smallest‐largest critical set size for members of ) between and .     

Distinct partial sums in cyclic groups: polynomial method and constructive approaches

Let be an abelian group and consider a subset with . Given an ordering of the elements of , define its partial sums by and for . We consider the following conjecture of Alspach: for any cyclic group and any subset with , it is possible to find an ordering of the elements of such that no two of its partial sums and are equal for . We show that Alspach’s Conjecture holds for prime when and when . The former result is by direct construction, the latter is nonconstructive and uses the polynomial method. We also use the polynomial method to show that for prime a sequence of length having distinct partial sums exists in any subset of of size at least in all but at most a bounded number of cases.     

Decomposable super‐simple NRBIBDs with block size 4 and index 6

Necessary conditions for the existence of a super‐simple, decomposable, near‐resolvable ‐balanced incomplete block design (BIBD) whose 2‐component subdesigns are both near‐resolvable ‐BIBDs are (mod ) and . In this paper, we show that these necessary conditions are sufficient. Using these designs, we also establish that the necessary conditions for the existence of a super‐simple near‐resolvable ‐RBIBD, namely (mod ) and , are sufficient. A few new pairwise balanced designs are also given.     

Deza graphs with parameters and

A Deza graph with parameters is a ‐regular graph with vertices, in which any two vertices have or () common neighbours. A Deza graph is strictly Deza if it has diameter , and is not strongly regular. In an earlier paper, the two last authors et al characterised the strictly Deza graphs with and , where is the number of vertices with common neighbours with a given vertex. Here, we start with a characterisation of Deza graphs (not necessarily strictly Deza graphs) with parameters . Then, we deal with the case and , and thus complete the characterisation of Deza graphs with . It follows that all Deza graphs with , and can be made from special strongly regular graphs, and in fact are strictly Deza except for . We present several examples of such strongly regular graphs. A divisible design graph (DDG) is a special Deza graph, and a Deza graph with is a DDG. The present characterisation reveals an error in a paper on DDGs by the second author et al. We discuss the cause and the consequences of this mistake and give the required errata.     

Embedding hypertrees into steiner triple systems

In this paper, we are interested in the following question: given an arbitrary Steiner triple system on vertices and any 3‐uniform hypertree on vertices, is it necessary that contains as a subgraph provided ? We show the answer is positive for a class of hypertrees and conjecture that the answer is always positive.     

The Zarankiewicz problem in 3‐partite graphs

Let be a graph, be an integer, and write for the maximum number of edges in an ‐vertex graph that is ‐partite and has no subgraph isomorphic to . The function has been studied by many researchers. Finding is a special case of the Zarankiewicz problem. We prove an analog of the Kövári‐Sós‐Turán theorem for 3‐partite graphs by showing for . Using Sidon sets constructed by Bose and Chowla, we prove that this upper bound is asymptotically best possible in the case that and is odd, that is, for . In the cases of and , we use a result of Allen, Keevash, Sudakov, and Verstraëte, to show that a similar upper bound holds for all and gives a better constant when . Finally, we point out an interesting connection between difference families from design theory and .     

Group divisible designs with block size four and type —II

We show that the necessary conditions for the existence of group divisible designs with block size four (4‐GDDs) of type are sufficient for (mod ), = 39, 51, 57, 69, 87, 93, 111, 123 and 129, and for = 13, 17, 19, 23, 25, 29, 31 and 35. More generally, we show that for (mod 6), the possible exceptions occur only when , and there are no exceptions at all if has a divisor such that (mod 4) or is a prime not greater than 43. Hence, there are no exceptions when (mod 12). Consequently, we are able to extend the known spectrum for and 5 (mod 6). Also, we complete the spectrum for 4‐GDDs of type .     

On the spouse‐loving variant of the Oberwolfach problem

We prove that , the complete graph of even order with a 1‐factor duplicated, admits a decomposition into 2‐factors, each a disjoint union of cycles of length if and only if , except possibly when is odd and . In addition, we show that admits a decomposition into 2‐factors, each a disjoint union of cycles of lengths , whenever are all even.     

Strong Skolem starters

This paper concerns a class of combinatorial objects called Skolem starters, and more specifically, strong Skolem starters, which are generated by Skolem sequences. In 1991, Shalaby conjectured that any additive group , where or , admits a strong Skolem starter and constructed these starters of all admissible orders . Only finitely many strong Skolem starters have been known to date. In this paper, we offer a geometrical interpretation of strong Skolem starters and explicitly construct infinite families of them.     

Anti‐Pasch optimal packings with triples

It is shown that for , there exists an optimal packing with triples on points that contains no Pasch configurations. Furthermore, for all (mod 6), there exists a pairwise balanced design of order , whose blocks are all triples apart from a single quintuple, and that has no Pasch configurations amongst its triples.