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

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.

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 (Sk× Sn, diag(Sk) × Sn-k). We use this combinatorial formula to give new Delsarte linear programming bounds on the size of codes over injections.

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 viis transmitting, vjis receiving, and no other node in proximity of vjis 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 lambda-fold directed graph Koarrninto directed complete bipartite subgraphs Koarra,bas a model for ternary scheduling in WSNs. We associate the vertices of Koarrnwith the nodes of the WSN, and occurrences of Koarra,bs (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 lambdaKoarrnguarantees that every ordered pair of nodes in the WSN can communicate in lambda time slots.