Abstract A universal partial cycle (or upcycle) for $$\mathcal {A}^n$$ A n is a cyclic sequence that covers each word of length n over the alphabet $$\mathcal {A}$$ A exactly once—like a De Bruijn cycle, except that we also allow a wildcard symbol $$\mathord {\diamond }$$ ⋄ that can represent any letter of $$\mathcal {A}$$ A . Chen et al. (Discret Math Theor Comput Sci 2017. https://doi.org/10.23638/DMTCS-19-1-16) and Goeckner et al. (Theor Comput Sci 713:56–65, 2018. https://doi.org/10.1016/j.tcs.2017.12.022) showed that the existence and structure of upcycles are highly constrained, unlike those of De Bruijn cycles, which exist for every alphabet size and word length. Moreover, it was not known whether any upcycles existed for $$n \ge 5$$ n ≥ 5 . We present several examples of upcycles over both binary and non-binary alphabets for $$n = 8$$ n = 8 . We generalize two graph-theoretic representations of De Bruijn cycles to upcycles. We then introduce novel approaches to constructing new upcycles from old ones. Notably, given any upcycle for an alphabet of size a , we show how to construct an upcycle for an alphabet of size ak for any $$k \in \mathbb {N}$$ k ∈ N , so each example generates an infinite family of upcycles. We also define folds and lifts of upcycles, which relate upcycles with differing densities of $$\mathord {\diamond }$$ ⋄ characters. In particular, we show that every upcycle lifts to a De Bruijn cycle. Our constructions rely on a different generalization of De Bruijn cycles known as perfect necklaces, and we introduce several new examples of perfect necklaces. We extend the definitions of certain pseudorandomness properties to partial words and determine which are satisfied by all upcycles, then draw a conclusion about linear feedback shift registers. Finally, we prove new nonexistence results based on the word length n , alphabet size, and $$\mathord {\diamond }$$ ⋄ density.

Abstract A De Bruijn cycle is a cyclic sequence in which every word of length n over an alphabet $$\mathcal {A}$$ A appears exactly once. De Bruijn tori are a two-dimensional analogue. Motivated by recent progress on universal partial cycles and words, which shorten De Bruijn cycles using a wildcard character, we introduce universal partial tori and matrices. We find them computationally and construct infinitely many of them using one-dimensional variants of universal cycles, including a new variant called a universal partial family.

Abstract. Recently Chase determined the maximum possible number of cliques of size [Formula: see text] in a graph on [Formula: see text] vertices with given maximum degree. Soon afterward, Chakraborti and Chen answered the version of this question in which we ask that the graph have [Formula: see text] edges and fixed maximum degree (without imposing any constraint on the number of vertices). In this paper we address these problems on hypergraphs. For [Formula: see text]-graphs with [Formula: see text] a number of issues arise that do not appear in the graph case. For instance, for general [Formula: see text]-graphs we can assign degrees to any [Formula: see text]-subset of the vertex set with [Formula: see text]. We establish bounds on the number of [Formula: see text]-cliques in an [Formula: see text]-graph [Formula: see text] with [Formula: see text]-degree bounded by [Formula: see text] in three contexts: [Formula: see text] has [Formula: see text] vertices; [Formula: see text] has [Formula: see text] (hyper)edges; and (generalizing the previous case) [Formula: see text] has a fixed number [Formula: see text] of [Formula: see text]-cliques for some [Formula: see text] with [Formula: see text]. When [Formula: see text] is of a special form we characterize the extremal [Formula: see text]-graphs and prove that the bounds are tight. These extremal examples are the shadows of either Steiner systems or partial Steiner systems. On the way to proving our uniqueness results, we extend results of Füredi and Griggs on uniqueness in Kruskal–Katona from the shadow case to the clique case.