On set systems with restricted k‐wise L‐intersection modulo a prime,and beyond

In this paper, we derive the following bound on the size of a k‐wise L‐intersecting family (resp. cross L‐intersecting families) modulo a prime number:

• (i) Let p be a prime, , and . Let and be two disjoint subsets of such that , or . Suppose that is a family of subsets of [n] such that for every and for every collection of k distinct subsets in . Then, This result may be considered as a modular version of Theorem 1.10 in [J. Q. Liu, S. G. Zhang, S. C. Li, H. H. Zhang, Eur. J. Combin. 58 (2016), 166‐180].
• (ii) Let p be a prime, , and . Let and be two subsets of such that , or , or . Suppose that and are two families of subsets of [n] such that (1) for every pair ; (2) for every ; (3) for every . Then,

This result extends the well‐known Alon–Babai–Suzuki theorem to two cross L‐intersecting families.     

Optimal Tight Equi‐Difference Conflict‐Avoiding Codes of Length n = 2k ± 1 and Weight 3

For a k‐subset X of , the set of differences on X is the set (mod n): . A conflict‐avoiding code CAC of length n and weight k is a collection of k‐subsets of such that = ? for any distinct . Let CAC() be the class of all the CACs of length n and weight k. The maximum size of codes in CAC(n, k) is denoted by . A code CAC(n, k) is said to be optimal if = . An optimal code is tight equi‐difference if = and each codeword in is of the form . In this paper, the necessary and sufficient conditions for the existence problem of optimal tight equi‐difference conflict‐avoiding codes of length n = and weight 3 are given. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 21: 223–231, 2013     

Enclosings of decompositions of complete multigraphs in 2‐factorizations

Let k, m, n, λ, and μ be positive integers. A decomposition of into edge‐disjoint subgraphs is said to be enclosed by a decomposition of into edge‐disjoint subgraphs if and, after a suitable labeling of the vertices in both graphs, is a subgraph of and is a subgraph of for all . In this paper, we continue the study of enclosings of given decompositions by decompositions that consist of spanning subgraphs. A decomposition of a graph is a 2‐factorization if each subgraph is 2‐regular and spanning, and is Hamiltonian if each subgraph is a Hamiltonian cycle. We give necessary and sufficient conditions for the existence of a 2‐factorization of that encloses a given decomposition of whenever and . We also give necessary and sufficient conditions for the existence of a Hamiltonian decomposition of that encloses a given decomposition of whenever and either or and , or , , and .     

Latin squares with disjoint subsquares of two orders

Let and . The integer partition of n is said to be realized if there is a latin square of order n with pairwise disjoint subsquares of order for each . In this paper, we construct latin squares realizing partitions of the form ; that is, partitions with s parts of size a and t parts of size b, where . Heinrich (1982) showed that (1) if and , then there is a latin square realizing , (2) is realized if and only if , and (3) is realized if and only if . In this paper, we resolve the open cases. We show that is realized if and only if and is realized if and only if .     

Twofold triple systems with cyclic 2‐intersecting Gray codes

Given a combinatorial design with block set , the block‐intersection graph (BIG) of is the graph that has as its vertex set, where two vertices and are adjacent if and only if . The i‐block‐intersection graph (i‐BIG) of is the graph that has as its vertex set, where two vertices and are adjacent if and only if . In this paper, several constructions are obtained that start with twofold triple systems (TTSs) with Hamiltonian 2‐BIGs and result in larger TTSs that also have Hamiltonian 2‐BIGs. These constructions collectively enable us to determine the complete spectrum of TTSs with Hamiltonian 2‐BIGs (equivalently TTSs with cyclic 2‐intersecting Gray codes) as well as the complete spectrum for TTSs with 2‐BIGs that have Hamilton paths (i.e. for TTSs with 2‐intersecting Gray codes). In order to prove these spectrum results, we sometimes require ingredient TTSs that have large partial parallel classes; we prove lower bounds on the sizes of partial parallel classes in arbitrary TTSs, and then construct larger TTSs with both cyclic 2‐intersecting Gray codes and parallel classes.     

Partitioning the edge set of a hypergraph into almost regular cycles

A cycle of length t in a hypergraph is an alternating sequence of distinct vertices and distinct edges so that (with ). Let be the λ‐fold n‐vertex complete h‐graph. Let be a hypergraph all of whose edges are of size at least h, and . In order to partition the edge set of into cycles of specified lengths , an obvious necessary condition is that . We show that this condition is sufficient in the following cases.

• (R1) .
• (R2) , .
• (R3) , , .

In (R2), we guarantee that each cycle is almost regular. In (R3), we also solve the case where a “small” subset L of edges of is removed.     

On the Hamilton–Waterloo problem with odd cycle lengths

Let denote the complete graph if v is odd and , the complete graph with the edges of a 1‐factor removed, if v is even. Given nonnegative integers , the Hamilton–Waterloo problem asks for a 2‐factorization of into α ‐factors and β ‐factors, with a ‐factor of being a spanning 2‐regular subgraph whose components are ℓ‐cycles. Clearly, , , and are necessary conditions. In this paper, we extend a previous result by the same authors and show that for any odd the above necessary conditions are sufficient, except possibly when , or when . Note that in the case where v is odd, M and N must be odd. If M and N are odd but v is even, we also show sufficiency but with further possible exceptions. In addition, we provide results on 2‐factorizations of the complete equipartite graph and the lexicographic product of a cycle with the empty graph.     

Optimal cyclic quaternary constant‐weight codes of weight three

A cyclic code is a cyclic q‐ary code of length n, constant weight w and minimum distance d. Let denote the largest possible size of a cyclic code. The pure and mixed difference method plays an important role in the determination of upper bound on . By analyzing the distribution of odd mixed and pure differences, an improved upper bound on is obtained for . A new construction based on special sequences is provided and the exact value of is almost completely determined for all d and n except when and . Our constructions reveal intimate connections between cyclic constant weight codes and special sequences, particularly Skolem‐type sequences.     

Flag‐transitive 2‐ designs of product type

In this paper, we prove that if a 2‐ design admits a flag‐transitive automorphism group G, then G is of affine, almost simple type, or product type. Furthermore, we prove that if G is product type then is either a 2‐(25, 4, 12) design or a 2‐(25, 4, 18) design with .     

Indecomposable 1‐factorizations of the complete multigraph for every

A 1‐factorization of the complete multigraph is said to be indecomposable if it cannot be represented as the union of 1‐factorizations of and , where . It is said to be simple if no 1‐factor is repeated. For every and for every , we construct an indecomposable 1‐factorization of , which is not simple. These 1‐factorizations provide simple and indecomposable 1‐factorizations of for every and . We also give a generalization of a result by Colbourn et al., which provides a simple and indecomposable 1‐factorization of , where , , p prime.     

Constructions of augmented orthogonal arrays

Augmented orthogonal arrays (AOAs) were introduced by Stinson, who showed the equivalence between ideal ramp schemes and AOAs (Discrete Math. 341 (2018), 299–307). In this paper, we show that there is an AOA if and only if there is an OA which can be partitioned into subarrays, each being an OA, and that there is a linear AOA if and only if there is a linear maximum distance separable (MDS) code of length and dimension over , which contains a linear MDS subcode of length and dimension over . Some constructions for AOAs and some new infinite classes of AOAs are also given.     

Almost resolvable k‐cycle systems with

In this paper, we show that if and , then there exists an almost resolvable k‐cycle system of order for all except possibly for and . Thus we give a partial solution to an open problem posed by Lindner, Meszka, and Rosa (J. Combin. Des., vol. 17, pp. 404–410, 2009).     

Small arrays of maximum coverage

Given a set S of symbols, and integers and , an array is said to cover a t‐set of columns if all sequences in appear as rows in the corresponding subarray of A. If A covers all t‐subsets of columns, it is called an ‐covering array. These arrays have a wide variety of applications, driving the search for small covering arrays. Here, we consider an inverse problem: rather than aiming to cover all t‐sets of columns with the smallest possible array, we fix the size N of the array to be equal to and try to maximize the number of covered t‐sets. With the machinery of hypergraph Lagrangians, we provide an upper bound on the number of t‐sets that can be covered. A linear algebraic construction shows this bound to be tight; exactly so in the case when v is a prime power and divides k, and asymptotically so in other cases. As an application, by combining our construction with probabilistic arguments, we match the best‐known asymptotics of the covering array number , which is the smallest N for which an ‐covering array exists, and improve the upper bounds on the almost‐covering array number .     

Group divisible designs with block size 4 and type

Building upon the work of Wei and Ge (Designs, Codes, and Cryptography 74, 2015), we extend the range of positive integer parameters g, u, and m for which group divisible designs with block size 4 and type are known to exist. In particular, we show that the necessary conditions for the existence of these designs when and are sufficient in the following cases: , with one exception, 2⁶5¹, , and .     

An Infinite Family of Steiner Systems from Cyclic Codes

Steiner systems are a fascinating topic of combinatorics. The most studied Steiner systems are (Steiner triple systems), (Steiner quadruple systems), and . There are a few infinite families of Steiner systems in the literature. The objective of this paper is to present an infinite family of Steiner systems for all from cyclic codes. As a by‐product, many infinite families of 2‐designs are also reported in this paper.     

Partial ‐Parallelisms in Finite Projective Spaces

In this paper, we consider the following question. What is the maximum number of pairwise disjoint k‐spreads that exist in PG()? We prove that if divides and then there exist at least two disjoint k‐spreads in PG() and there exist at least pairwise disjoint k‐spreads in PG(n, 2). We also extend the known results on parallelism in a projective geometry from which the points of a given subspace were removed.     

On the number of SQSs,latin hypercubes and MDS codes

We establish that the logarithm of the number of latin d‐cubes of order n is and the logarithm of the number of sets of t ( is fixed) orthogonal latin squares of order n is . Similar estimations are obtained for systems of mutually strongly orthogonal latin d‐cubes. As a consequence, we construct a set of Steiner quadruple systems of order n such that the logarithm of its cardinality is as and .     

New lower bounds for t‐coverings

Fisher proved in 1940 that any 2‐ design with has at least v blocks. In 1975, Ray‐Chaudhuri and Wilson generalized this result by showing that every t‐ design with has at least blocks. By combining methods used by Bose and Wilson in proofs of these results, we obtain new lower bounds on the size of t‐ coverings. Our results generalize lower bounds on the size of 2‐ coverings recently obtained by the first author.     

Completions of ‐Dense Partial Latin Squares

A classical question in combinatorics is the following: given a partial Latin square P, when can we complete P to a Latin square L? In this paper, we investigate the class of ε‐dense partial Latin squares: partial Latin squares in which each symbol, row, and column contains no more than ‐many nonblank cells. Based on a conjecture of Nash‐Williams, Daykin and Häggkvist conjectured that all ‐dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this technique to study ε‐dense partial Latin squares that contain no more than filled cells in total. In this paper, we construct completions for all ε‐dense partial Latin squares containing no more than filled cells in total, given that . In particular, we show that all ‐dense partial Latin squares are completable. These results improve prior work by Gustavsson, which required , as well as Chetwynd and Häggkvist, which required , n even and greater than 10⁷.     

Transversals in Latin Arrays with Many Distinct Symbols

An array is row‐Latin if no symbol is repeated within any row. An array is Latin if it and its transpose are both row‐Latin. A transversal in an array is a selection of n different symbols from different rows and different columns. We prove that every Latin array containing at least distinct symbols has a transversal. Also, every row‐Latin array containing at least distinct symbols has a transversal. Finally, we show by computation that every Latin array of order 7 has a transversal, and we describe all smaller Latin arrays that have no transversal.