Abstract A sequence covering array, denoted by ( N ; t , v ), is a set of N permutations of $$\{0, \dots , v-1 \}$$ { 0 , ⋯ , v - 1 } such that each sequence of t distinct elements of $$\{0, \dots , v-1\}$$ { 0 , ⋯ , v - 1 } is a (not necessarily contiguous) subsequence of at least one permutation. The minimum number of permutations such a sequence covering array can have is t ! and it has been conjectured that for $$t > 4$$ t > 4 , if a sequence covering array with t ! permutations exists, then $$v \in \{t,t+1\}$$ v ∈ { t , t + 1 } . In this paper, we prove that an (7!; 7, 10) does not exist. We do this by analysing connections between sequence covering arrays and a special kind of covering array called an excess coverage array.

Abstract In situations where every item in a data set must be compared with every other item in the set, it may be desirable to store the data across a number of machines in such a way that any two data items are stored together on at least one machine. One way to evaluate the efficiency of such a distribution is by the largest fraction of the data it requires to be allocated to any one machine. The all-to-all comparison (ATAC) data limit formmachines is a measure of the minimum of this value across all possible such distributions. In this paper we further the study of ATAC data limits. We begin by investigating the data limits achievable using various classes of combinatorial designs. In particular, we examine the cases of transversal designs and projective Hjelmslev planes. We then observe relationships between data limits and the previously studied combinatorial parameters of fractional matching numbers and covering numbers. Finally, we prove a lower bound on the ATAC data limit that improves on one of Hall, Kelly and Tian, and examine the special cases where equality in this bound is possible.

Abstract A partial $$(n,k,t)_\lambda $$ ( n , k , t ) λ -system is a pair $$(X,{\mathcal {B}})$$ ( X , B ) where X is an n-set of vertices and $${\mathcal {B}}$$ B is a collection of k-subsets of X called blocks such that each t-set of vertices is a subset of at most $$\lambda $$ λ blocks. A sequencing of such a system is a labelling of its vertices with distinct elements of $$\{0,\ldots ,n-1\}$$ { 0 , … , n - 1 } . A sequencing is $$\ell $$ ℓ -block avoiding or, more briefly, $$\ell $$ ℓ -good if no block is contained in a set of $$\ell $$ ℓ vertices with consecutive labels. Here we give a short proof that, for fixed k, t and $$\lambda $$ λ , any partial $$(n,k,t)_\lambda $$ ( n , k , t ) λ -system has an $$\ell $$ ℓ -good sequencing for some $$\ell =\Theta (n^{1/t})$$ ℓ = Θ ( n 1 / t ) as n becomes large. This improves on results of Blackburn and Etzion, and of Stinson and Veitch. Our result is perhaps of most interest in the case $$k=t+1$$ k = t + 1 where results of Kostochka, Mubayi and Verstraëte show that the value of $$\ell $$ ℓ cannot be increased beyond $$\Theta ((n \log n)^{1/t})$$ Θ ( ( n log n ) 1 / t ) . A special case of our result shows that every partial Steiner triple system (partial $$(n,3,2)_1$$ ( n , 3 , 2 ) 1 -system) has an $$\ell $$ ℓ -good sequencing for each positive integer $$\ell \leqslant 0.0908\,n^{1/2}$$ ℓ ⩽ 0.0908 n 1 / 2 .

For positive integers $n$ and $k$ with $n \geq k$, an $(n,k,1)$-design is a pair $(V, \mathcal{B})$, where $V$ is a set of $n$ points and $\mathcal{B}$ is a collection of $k$-subsets of $V$ called blocks such that each pair of points occur together in exactly one block. If we weaken this condition to demand only that each pair of points occur together in at most one block, then the resulting object is a partial $(n,k,1)$-design. A completion of a partial $(n,k,1)$-design $(V,\mathcal{A})$ is a (complete) $(n,k,1)$-design $(V,\mathcal{B})$ such that $\mathcal{A} \subseteq \mathcal{B}$. Here, for all sufficiently large $n$, we determine exactly the minimum number of blocks in an uncompletable partial $(n,k,1)$-design. This result is reminiscent of Evans' now-proved conjecture on completions of partial Latin squares. We also prove some related results concerning edge decompositions of almost complete graphs into copies of $K_k$.

We prove that, for sufficiently large $n$, every graph of order $n$ with minimum degree at least $0.852n$ has a fractional edge-decomposition into triangles. We do this by refining a method used by Dross [ SIAM J. Discrete Math., 30 (2016), pp. 36--42] to establish a bound of $0.9n$. By a result of Barber, Kühn, Lo, and Osthus [Adv. Math., 288 (2016), pp. 337--385], our result implies that, for each $\epsilon >0$, every graph of sufficiently large order $n$ with minimum degree at least $(0.852+\epsilon)n$ has a triangle decomposition if and only if it has all even degrees and number of edges a multiple of three.

It has been conjectured that every Steiner triple system of order $v \neq 7$ has chromatic index at most $(v+3)/2$ when $v \equiv 3 {\:({\rm mod}\ 6)}$ and at most $(v+5)/2$ when $v \equiv 1 {\:({\rm mod}\ 6)}$. Herein, we construct a Steiner triple system of order $v$ with chromatic index at least $(v+3)/2$ for each integer $v \equiv 3 {\:({\rm mod}\ 6)}$ such that $v \geqslant 15$, with four possible exceptions. We further show that the maximum number of disjoint parallel classes in the systems constructed is sublinear in $v$. Finally, we establish for each order $v \equiv 15 {\:({\rm mod}\ 18)}$ that there are at least $v^{v^2(1/6+o(1))}$ nonisomorphic Steiner triple systems with chromatic index at least $(v+3)/2$ and that some of these systems are cyclic.

We use deterministic and probabilistic methods to analyze the performance of compressed sensing matrices constructed from Hadamard matrices and pairwise balanced designs, previously introduced by a subset of the authors. In this paper, we obtain upper and lower bounds on the sparsity of signals for which our matrices guarantee recovery. These bounds are tight to within a multiplicative factor of at most √4 2. We provide new theoretical results and detailed simulations, which indicate that the construction is competitive with Gaussian random matrices, and that recovery is tolerant to noise. A new recovery algorithm tailored to the construction is also given.

When $k$ factors each taking one of $v$ levels may affect the correctness or performance of a complex system, a test is selected by setting each factor to one of its levels and determining whether the system functions as expected (passes the test) or not (fails). In our setting, each test failure can be attributed to at least one faulty (factor, level) pair. A nonadaptive test suite is a selection of such tests to be executed in parallel. One goal is to minimize the number of tests in a test suite from which we can determine which (factor, level) pairs are faulty, if any. In this paper, we determine the number of tests needed to locate faults when exactly one (or at most one) pair is faulty. To do this, we address an equivalent problem, to determine how many set partitions of a set of size $N$ exist in which each partition contains $v$ classes and no two classes in the partitions are equal.

We construct Steiner triple systems without parallel classes for an infinite number of orders congruent to $3 \:({mod}\ 6) $. The only previously known examples have order 15 or 21.

In 2009 it was established that any partial Steiner triple system of order $u$ has an embedding of order $v$ for each $v\geq 2u+1$ such that $v \equiv 1,3$ (mod 6), in accordance with a conjecture of Lindner. It is known that for each $u\geq 9$, there exists a partial Steiner triple system of order $u$ that does not have an embedding of order $v$ for any $v<2u+1$, so this result is best possible in one sense. Many partial Steiner triple systems do have embeddings of orders smaller than $2u+1$, however, although little is known about when such embeddings exist. In this paper we construct embeddings of orders less than $2u+1$ for partial Steiner triple systems with few triples. In particular, we show that a partial Steiner triple system of order $u \geq 62$ with at most $\frac{u^2}{50}-\frac{11u}{100}-\frac{116}{75}$ triples has an embedding of order $v$ for each admissible integer $v \geq \frac{8u+17}{5}$.

Sequential processes can encounter faults as a result of improper ordering of subsets of the events. In order to reveal faults caused by the relative ordering of $t$ or fewer of $v$ events, for some fixed $t$, a test suite must provide tests so that every ordering of every set of $t$ or fewer events is exercised. Such a test suite is equivalent to a sequence covering array, a set of permutations on $v$ events for which every subsequence of $t$ or fewer events arises in at least one of the permutations. Equivalently it is a (different) set of permutations, a completely $t$-scrambling set of permutations, in which the images of every set of $t$ chosen events include each of the $t!$ possible “patterns.” In event sequence testing, minimizing the number of permutations used is the principal objective. By developing a connection with covering arrays, lower bounds on this minimum in terms of the minimum number of rows in covering arrays are obtained. An existing bound on the largest $v$ for which the minimum can equal $t!$ is improved. A conditional expectation algorithm is developed to generate sequence covering arrays whose number of permutations never exceeds a specified logarithmic function of $v$ when $t$ is fixed, and this method is shown to operate in polynomial time. A recursive product construction is established when $t=3$ to construct sequence covering arrays on $vw$ events from ones on $v$ and $w$ events. Finally computational results are given for $t \in \{3,4,5\}$ to demonstrate the utility of the conditional expectation algorithm and the product construction.

Deterministic construction of measurement matrices for compressive sensing can be effected by first constructing a relatively small matrix explicitly, and then inflating it using a column replacement technique to form a large measurement matrix that supports at least the same level of sparsity. In particular, using easily developed null space conditions for l0- and l1-recoverability, properties of the pattern matrix used to select columns lead to well-studied matrices, separating and distributing hash families. Two-stage compression and recovery techniques are developed that employ more computationally intensive l0-recoverability for small matrices and simpler l1-recoverability for one larger matrix; this can reduce the number of measurements required.