Search

For r ≥ 1, the r-neighbor bootstrap process in a graph G starts with a set of infected vertices and, in each time step, every vertex with at least r infected neighbors becomes infected. The initial infection percolates if every vertex of G is eventually infected. We exactly determine the minimum cardinality of a set that percolates for the 3-neighbor bootstrap process when G is a three-dimensional grid with minimum side-length at least 11. We also characterize the integers a and b for which there is a set of cardinality ab+a+b/3 that percolates for the 3-neighbor bootstrap process in the a × b grid; this solves a problem raised by Benevides et al. [HAL Research Report 03161419v4, 2021]. [ABSTRACT FROM AUTHOR]

Given a family F = {A1;: :: ;As} of subsets of Zn, define ΔF to be the multiset of all (cyclic) distances dist(x; y), where {x; y} - Ai, x 6= y, for some i 2 {1; ... s}. Taking inspiration from a Euclidean distance problem of Erd}os, we say that F is Erd}os-deep if the multiplicities of distances that occur in F are precisely 1; 2; ... k - 1 for some integer k. In the case s = 1, it is known that a modular arithmetic progression in Zn achieves this property (under mild conditions); conversely, arithmetic progressions are the only such sets, except for one sporadic case when n = 6. Here, we consider in detail the case s = 2. In particular, we classify Erd}os-deep pairs fA1;A2g when each Ai is an arithmetic progression in Zn. We also give a construction of a much wider class of Erd}os-deep families {A1,...}Asg when s is a square integer. [ABSTRACT FROM AUTHOR]

A balanced incomplete block design is a set system in which all pairs of distinct elements occur with a constant frequency. By contrast, a Sarvate-Beam design induces an interval of distinct frequencies on pairs. In this paper, we settle the existence of a Sarvate-Beam variant of group divisible designs of uniform type with block size three. [ABSTRACT FROM AUTHOR]

A Kirkman triple system of order v, KTS(v), is a resolvable Steiner triple system on v elements. In this paper, we investigate an open problem posed by Doug Stinson, namely the existence of KTS(v) which contain as a subdesign a Steiner triple system of order u, an STS(u). We present several different constructions for designs of this form. As a consequence, we completely settle the extremal case v=2u+1, for which a list of possible exceptions had remained for close to 30 years. Our new constructions also provide the first infinite classes for the more general problem. We reduce the other maximal case v=2u+3 to (at present) three possible exceptions. In addition, we obtain results for other cases of the form v=2u+w and also near v=3u. Our primary method introduces a new type of Kirkman frame which contains group divisible design subsystems. These subsystems can occur with different configurations, and we use two different varieties in our constructions. [ABSTRACT FROM AUTHOR]

In an equireplicate graph decomposition, every vertex of the host graph appears in the same number of blocks. We propose the use of colored loops as a framework for unifying various other types of local regularity conditions in graph decompositions. In the basic case where a single graph with colored loops is used as a block, an existence theory for such decompositions follows as a straightforward generalization of previous work on graph decompositions. [ABSTRACT FROM AUTHOR]

We consider the algebraic combinatorics of the set of injections from a $k$ -element set to an $n$ -element set. In particular, we give a new combinatorial formula for the spherical functions of the Gelfand pair $(S_{k} \times S_{n}, diag(S_{k}) \times S_{n-k})$. We use this combinatorial formula to give new Delsarte linear programming bounds on the size of codes over injections. [ABSTRACT FROM AUTHOR]

It is widely acknowledged across the global health sector that research programmes need to be designed and implemented in a way that maximise opportunities for strengthening local capacity. This paper examines how the United Kingdom Research and Innovation (UKRI) Grand Challenges Research Fund (GCRF) funded PRECISE (PREgnancy Care Integrating translational Science, Everywhere) Network has been established as a platform to strengthen global capacity for research focused on the improvement of maternal, fetal and newborn health in sub-Saharan Africa. Best practice principles outlined in an ESSENCE on Health Research report have been considered in relation to the PRECISE Network capacity-building activities described in this paper. These activities are described at the individual, programmatic and institutional levels, and successes, challenges and recommendations for future work are outlined. The paper concludes that the PRECISE leadership have an opportunity to review and refresh activity plans for capacity building at this stage in the project to build on achievements to date. [ABSTRACT FROM AUTHOR]

A classical recursive construction for mutually orthogonal latin squares (MOLS) is shown to hold more generally for a class of permutation codes of length n and minimum distance n - 1 . When such codes of length p + 1 are included as ingredients, we obtain a general lower bound M (n , n - 1) ≥ n 1.0797 for large n, gaining a small improvement on the guarantee given from MOLS. [ABSTRACT FROM AUTHOR]

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, Kuhn, 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. [ABSTRACT FROM AUTHOR]

We give explicit constructions for incomplete pairwise balanced designs IPBD((v; w), K), or, equivalently, edge-decompositions of a difference of two cliques K v \ K w into cliques whose sizes belong to the set K. Our constructions produce such designs whenever v and w satisfy the usual divisibility conditions, have ratio v / w bounded away from the smallest value in K minus one, say v / w > k - 1 + ϵ , for k = min K and ϵ > 0 , and are sufficiently large (depending on K and ϵ ). As a consequence, some new results are obtained on many related designs, including class-uniformly resolvable designs, incomplete mutually orthogonal latin squares, and group divisible designs. We also include several other applications that illustrate the power of using IPBDs as 'templates'. [ABSTRACT FROM AUTHOR]

We investigate the minimum order of a linear r-regular k-uniform hypergraph, also known as an [ABSTRACT FROM AUTHOR]

We prove that for any K and d, there exists, for all sufficiently large admissible $${v}$$ , a pairwise balanced design PBD $${(v, K)}$$ of dimension d for which all d-point-generated flats are bounded by a constant independent of v. We also tighten a prior upper bound for K = {3, 4, 5}, in which case there are no divisibility restrictions on the number of points. One consequence of this latter result is the construction of latin squares 'covered' by small subsquares. [ABSTRACT FROM AUTHOR]

We introduce a generalization of group divisible designs and offer example applications to challenging problems in design theory. The generalization considers edge-decompositions of joins of arbitrary graphs, whereas group divisible designs handle only joins of edgeless graphs. Our example constructions include: (1) optimal packings with block size five for the previously unsettled congruence class $$v \equiv 13 \pmod {20}$$ ; (2) an optimal grooming with with ratio seven for the previously unsettled congruence class $$v \equiv 56 \pmod {84}$$ ; and (3) a constructive 'quadratic' embedding of partial designs with block size four. [ABSTRACT FROM AUTHOR]

Recall that in a laminar family, any two sets are either disjoint or contained one in the other. Here, a parametrized weakening of this condition is introduced. Let us say that a set system $\mathcal {F} \subseteq 2^{X}$ is t-laminar if $A,B \in \mathcal {F}$ with $|A \cap B| \ge t$ implies $A \subseteq B$ or $B \subseteq A$. We obtain very close asymptotic bounds in terms of n on the maximum size of a 2-laminar family $\mathcal {F} \subseteq 2^{[n]}$. A construction for 3-laminar families and a crude analysis for general t are also given. [ABSTRACT FROM AUTHOR]

It is well known that mutually orthogonal latin squares, or MOLS, admit a (Kronecker) product construction. We show that, under mild conditions, 'triple products' of MOLS can result in a gain of one square. In terms of transversal designs, the technique is to use a construction of Rolf Rees twice: once to obtain a coarse resolution of the blocks after one product, and next to reorganize classes and resolve the blocks of the second product. As consequences, we report a few improvements to the MOLS table and obtain a slight strengthening of the famous theorem of MacNeish. [ABSTRACT FROM AUTHOR]

The maximum number of mutually orthogonal latin squares (MOLS) of order 10 is known to be between 2 and 6. A hypothetical set of four MOLS must contain at least one of the types of group divisible designs (GDDs) classified here. The proof is based on a dimension argument modified from work by Dougherty. The argument has recently led to the discovery of a counterexample to Moorhouse's conjecture on the rank of nets, found by Howard and Myrvold. Although it is known that even three MOLS can admit no nontrivial symmetry group, we are hopeful this classification via GDDs and dimension can offer some structure to aid the eventual goal of exhausting the search for four MOLS of order 10. [ABSTRACT FROM AUTHOR]

The dimension of a linear space is the maximum positive integer d such that any d of its points generate a proper subspace. For a set K of integers at least two, recall that a pairwise balanced design $\operatorname{PBD}(v,K)$ is a linear space on v points whose lines (or blocks) have sizes belonging to K. We show that, for any prescribed set of sizes K and lower bound d on the dimension, there exists a $\operatorname{PBD}(v,K)$ of dimension at least d for all sufficiently large and numerically admissible v. [ABSTRACT FROM AUTHOR]

Recall that combinatorial 2 s-designs admit a classical lower bound $b \ge\binom{v}{s}$ on their number of blocks, and that a design meeting this bound is called tight. A long-standing result of Bannai is that there exist only finitely many nontrivial tight 2 s-designs for each fixed s≥5, although no concrete understanding of 'finitely many' is given. Here, we use the Smith Bound on approximate polynomial zeros to quantify this asymptotic nonexistence. Then, we outline and employ a computer search over the remaining parameter sets to establish (as expected) that there are in fact no such designs for 5≤ s≤9, although the same analysis could in principle be extended to larger s. Additionally, we obtain strong necessary conditions for existence in the difficult case s=4. [ABSTRACT FROM AUTHOR]

A group divisible design (GDD) is a triple [ABSTRACT FROM AUTHOR]

Two orthogonal latin squares of order n have the property that when they are superimposed, each of the n ordered pairs of symbols occurs exactly once. In a series of papers, Colbourn, Zhu, and Zhang completely determine the integers r for which there exist a pair of latin squares of order n having exactly r different ordered pairs between them. Here, the same problem is considered for latin squares of different orders n and m. A nontrivial lower bound on r is obtained, and some embedding-based constructions are shown to realize many values of r. [ABSTRACT FROM AUTHOR]

A permutation code of length n and minimum distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between any distinct $${u,v \in \Gamma}$$ is at least d. As a generalization, we introduce the problem of packing injections from an m-set, m ≤ n, sometimes called m-arrangements, relative to Hamming distance. We offer some preliminary coding-theoretic bounds, a few design-theoretic connections, and a short discussion on possible applications. [ABSTRACT FROM AUTHOR]

Objectives: The Clinical Research Training Fellowship (CRTF) allows up to 3 years support for clinically qualified candidates to undertake specialised or further research training in biomedical sciences. CRTFs are perceived as a crucial step in the career development and progression of Clinical Academics but there are no published data to support this notion. We conducted an electronic survey of a large cohort of Medical Research Council (MRC) CRTFs followed for up to 20 years. Design: Retrospective analysis of CRTF outcome data held with the MRC, UK. Participants: Two cohorts comprising 40 CRFTs awarded by the MRC in the year 1991 and 299 MRC CRTFs who were awarded a fellowship between 1993 and 2003. Results: The MRC CRTF scheme built capacity in clinical academia across the UK with 40% of CRTFs progressing to a University professorship. Importantly, the CRTF scheme is also providing NHS consultants who remain research active. Conclusions: This is the first analysis of outcome of CRTFs in the UK and provides robust evidence of the importance of this capacity building mode of funding to underpin research excellence at the University--NHS interface. [ABSTRACT FROM AUTHOR]

Medium access control for multihop wireless sensor networks (WSNs) must be energy efficient because the battery-operated nodes are not practical to recharge. We give constructions for ternary schedules in which each node is in one of three states: transmitting, receiving, or asleep. For each hop (vi, vj), communication is effective only when vi is transmitting, vj is receiving, and no other node in proximity of vj is also transmitting. Since sensor nodes are prone to failure, the schedules should be independent of the detailed topology while supporting spatial reuse. We use arc-decompositions of the complete λ-fold directed graph Kn into directed complete bipartite subgraphs Ka,b as a model for ternary scheduling in WSNs. We associate the vertices of Kn with the nodes of the WSN, and occurrences of Ka,b s (blocks) in the decomposition with time slots in the schedule. A block with out-vertices A and in-vertices B corresponds to a slot in which the a nodes in A are transmitting, the b in B are receiving, and all others are asleep. Such a decomposition of λKn guarantees that every ordered pair of nodes in the WSN can communicate in λ time slots. [ABSTRACT FROM AUTHOR]

A Steiner triple system of order v, or STS( v), is a pair ( V, [InlineMediaObject not available: see fulltext.]) with V a set of v points and [InlineMediaObject not available: see fulltext.] a set of 3-subsets of V called blocks or triples, such that every pair of distinct elements of V occurs in exactly one triple. The intersection problem for STS is to determine the possible numbers of blocks common to two Steiner triple systems STS( u), ( U, [InlineMediaObject not available: see fulltext.]), and STS( v), ( V, [InlineMediaObject not available: see fulltext.]), with U⊆ V. The case where U= V was solved by Lindner and Rosa in 1975. Here, we let U⊂ V and completely solve this question for v− u=2,4 and for v≥2 u−3. [ABSTRACT FROM AUTHOR]