BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Daniel Horsley

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record
math.COInformation Theorymath.IT

Catalog footprint

Research overview

19works
3topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

19 publications

preprint2021arXiv

Countable homogeneous Steiner triple systems avoiding specified subsystems

In this article we construct uncountably many new homogeneous locally finite Steiner triple systems of countably infinite order as Fra\"ıssé limits of classes of finite Steiner triple systems avoiding certain subsystems. The construction relies on a new embedding result: any finite partial Steiner triple system has an embedding into a finite Steiner triple system that contains no nontrivial proper subsystems that are not subsystems of the original partial system. Fra\"ıssé's construction and its variants are rich sources of examples that are central to model-theoretic classification theory, and recently infinite Steiner systems obtained via Fra\"ıssé-type constructions have received attention from the model theory community.

Open access
preprint2021arXiv

Disjoint spread systems and fault location

When kk factors each taking one of vv 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 NN exist in which each partition contains vv classes and no two classes in the partitions are equal.

Open access
preprint2021arXiv

Distributing hash families with few rows

Column replacement techniques for creating covering arrays rely on the construction of perfect and distributing hash families with few rows, having as many columns as possible for a specified number of symbols. To construct distributing hash families in which the number of rows is less than the strength, we examine a method due to Blackburn and extend it in three ways. First, the method is generalized from homogeneous hash families (in which every row has the same number of symbols) to heterogeneous ones. Second, the extension treats distributing hash families, in which only separation into a prescribed number of parts is required, rather than perfect hash families, in which columns must be completely separated. Third, the requirements on one of the main ingredients are relaxed to permit the use of a large class of distributing hash families, which we call fractal. Constructions for fractal perfect and distributing hash families are given, and applications to the construction of perfect hash families of large strength are developed.

Open access
preprint2020arXiv

Decompositions of complete multigraphs into stars of varying sizes

In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size mm exists whenever some obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes m1,…,mtm_1,\ldots,m_t. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes m1,…,mtm_1,\ldots,m_t is NP\mathsf{NP}-complete, but that it becomes tractable if we place a strong enough upper bound on max⁡(m1,…,mt)\max(m_1,\ldots,m_t). We determine the upper bound at which this transition occurs. Along the way we also give a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes m1,…,mtm_1,\ldots,m_t with specified centres, and a generalisation of Landau's theorem on tournaments.

Open access
preprint2020arXiv

Generating infinite digraphs by derangements

A set S\mathcal{S} of derangements (fixed-point-free permutations) of a set VV generates a digraph with vertex set VV and arcs (x,xσ)(x,x^σ) for x∈Vx\in V and σ∈Sσ\in\mathcal{S}. We address the problem of characterising those infinite (simple loopless) digraphs which are generated by finite sets of derangements. The case of finite digraphs was addressed in earlier work by the second and third authors. A criterion is given for derangement generation which resembles the criterion given by De Bruijn and Erdős for vertex colourings of graphs in that the property for an infinite digraph is determined by properties of its finite sub-digraphs. The derangement generation property for a digraph is linked with the existence of a finite 11-factor cover for an associated bipartite (undirected) graph.

Open access
preprint2020arXiv

On determining when small embeddings of partial Steiner triple systems exist

A partial Steiner triple system of order uu is a pair (U,A)(U,\mathcal{A}) where UU is a set of uu elements and A\mathcal{A} is a set of triples of elements of UU such that any two elements of UU occur together in at most one triple. If each pair of elements occur together in exactly one triple it is a Steiner triple system. An embedding of a partial Steiner triple system (U,A)(U,\mathcal{A}) is a (complete) Steiner triple system (V,B)(V,\mathcal{B}) such that U⊆VU \subseteq V and A⊆B\mathcal{A} \subseteq \mathcal{B}. For a given partial Steiner triple system of order uu it is known that an embedding of order v≥2u+1v \geq 2u+1 exists whenever vv satisfies the obvious necessary conditions. Determining whether "small" embeddings of order v<2u+1v < 2u+1 exist is a more difficult task. Here we extend a result of Colbourn on the NP\mathsf{NP}-completeness of these problems. We also exhibit a family of counterexamples to a conjecture concerning when small embeddings exist.

Open access
preprint2020arXiv

On the minimum degree required for a triangle decomposition

We prove that, for sufficiently large nn, every graph of order nn with minimum degree at least 0.852n0.852n has a fractional edge-decomposition into triangles. We do this by refining a method used by Dross to establish a bound of 0.9n0.9n. By a result of Barber, Kühn, Lo and Osthus, our result implies that, for each ε>0ε>0, every graph of sufficiently large order nn with minimum degree at least (0.852+ε)n(0.852+ε)n has a triangle decomposition if and only if it has all even degrees and number of edges a multiple of three.

Open access
preprint2016arXiv

Decomposing Ku+w−KuK_{u+w}-K_u into cycles of various lengths

We prove that the complete graph with a hole Ku+w−KuK_{u+w}-K_u can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, each cycle has length at most min⁡(u,w)\min(u,w), and the longest cycle is at most three times as long as the second longest. This generalises existing results on decomposing the complete graph with a hole into cycles of uniform length, and complements work on decomposing complete graphs, complete multigraphs, and complete multipartite graphs into cycles of arbitrary specified lengths.

Open access
preprint2016arXiv

Generalising Fisher's inequality to coverings and packings

In 1940 Fisher famously showed that if there exists a non-trivial (v,k,λ)(v,k,λ)-design then λ(v−1)≥k(k−1)λ(v-1) \geq k(k-1). Subsequently Bose gave an elegant alternative proof of Fisher's result. Here, we show that the idea behind Bose's proof can be generalised to obtain new bounds on the number of blocks in (v,k,λ)(v,k,λ)-coverings and -packings with λ(v−1)<k(k−1)λ(v-1)<k(k-1).

Open access
preprint2015arXiv

Compressed sensing with combinatorial designs: theory and simulations

In 'An asymptotic result on compressed sensing matrices', a new construction for compressed sensing matrices using combinatorial design theory was introduced. In this paper, we use deterministic and probabilistic methods to analyse the performance of matrices obtained from this construction. We provide new theoretical results and detailed simulations. These simulations 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.

Open access
preprint2015arXiv

Doyen-Wilson results for odd length cycle systems

For each odd m≥3m \geq 3 we completely solve the problem of when an mm-cycle system of order uu can be embedded in an mm-cycle system of order vv, barring a finite number of possible exceptions. In cases where uu is large compared to mm, where mm is a prime power, or where m≤15m \leq 15, the problem is completely resolved. In other cases, the only possible exceptions occur when v−uv-u is small compared to mm. This result is proved as a consequence of a more general result which gives necessary and sufficient conditions for the existence of an mm-cycle decomposition of a complete graph of order vv with a hole of size uu in the case where u≥m−2u \geq m-2 and v−u≥m+1v-u \geq m+1 both hold.

Open access
preprint2015arXiv

More nonexistence results for symmetric pair coverings

A (v,k,λ)(v,k,λ)-covering is a pair (V,B)(V, \mathcal{B}), where VV is a vv-set of points and B\mathcal{B} is a collection of kk-subsets of VV (called blocks), such that every unordered pair of points in VV is contained in at least λλ blocks in B\mathcal{B}. The excess of such a covering is the multigraph on vertex set VV in which the edge between vertices xx and yy has multiplicity rxy−λr_{xy}-λ, where rxyr_{xy} is the number of blocks which contain the pair {x,y}\{x,y\}. A covering is symmetric if it has the same number of blocks as points. Bryant et al.(2011) adapted the determinant related arguments used in the proof of the Bruck-Ryser-Chowla theorem to establish the nonexistence of certain symmetric coverings with 22-regular excesses. Here, we adapt the arguments related to rational congruence of matrices and show that they imply the nonexistence of some cyclic symmetric coverings and of various symmetric coverings with specified excesses.

Open access
preprint2014arXiv

Embedding partial Steiner triple systems with few triples

It was proved in 2009 that any partial Steiner triple system of order uu has an embedding of order vv for each admissible integer v≥2u+1v\geq 2u+1. This result is best-possible in the sense that, for each u≥9u\geq 9, there exists a partial Steiner triple system of order uu that does not have an embedding of order vv for any v<2u+1v<2u+1. Many partial Steiner triple systems do have embeddings of orders smaller than 2u+12u+1, but little has been proved about when these embeddings exist. In this paper we construct embeddings of orders less than 2u+12u+1 for partial Steiner triple systems with few triples. In particular, we show that a partial Steiner triple system of order u≥62u \geq 62 with at most u250−11u100−11675\frac{u^2}{50}-\frac{11u}{100}-\frac{116}{75} triples has an embedding of order vv for each admissible integer v≥8u+175v \geq \frac{8u+17}{5}.

Open access
preprint2014arXiv

Hierarchical Recovery in Compressive Sensing

A combinatorial approach to compressive sensing based on a deterministic column replacement technique is proposed. Informally, it takes as input a pattern matrix and ingredient measurement matrices, and results in a larger measurement matrix by replacing elements of the pattern matrix with columns from the ingredient matrices. This hierarchical technique yields great flexibility in sparse signal recovery. Specifically, recovery for the resulting measurement matrix does not depend on any fixed algorithm but rather on the recovery scheme of each ingredient matrix. In this paper, we investigate certain trade-offs for signal recovery, considering the computational investment required. Coping with noise in signal recovery requires additional conditions, both on the pattern matrix and on the ingredient measurement matrices.

Open access
preprint2013arXiv

On balanced incomplete block designs with specified weak chromatic number

A weak cc-colouring of a balanced incomplete block design (BIBD) is a colouring of the points of the design with cc colours in such a way that no block of the design has all of its vertices receive the same colour. A BIBD is said to be weakly cc-chromatic if cc is the smallest number of colours with which the design can be weakly coloured. In this paper we show that for all c≥2c \geq 2 and k≥3k \geq 3 with (c,k)≠(2,3)(c,k) \neq (2,3), the obvious necessary conditions for the existence of a (v,k,λ)(v,k,λ)-BIBD are asymptotically sufficient for the existence of a weakly cc-chromatic (v,k,λ)(v,k,λ)-BIBD.

Open access
preprint2012arXiv

Decomposing various graphs into short even-length cycles

We prove that a complete bipartite graph can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, the length of each cycle is at most the size of the smallest part, and the longest cycle is at most three times as long as the second longest. We then use this result to obtain results on incomplete even cycle systems with a hole and on decompositions of complete multipartite graphs into cycles of uniform even length.

Open access

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.