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. Panhandle matroids are a specific family of lattice-path matroids corresponding to panhandle-shaped Ferrers diagrams. Their matroid polytopes are the subpolytopes carved from a hypersimplex to form matroid polytopes of paving matroids. It has been an active area of research to determine which families of matroid polytopes are Ehrhart positive. We prove Ehrhart positivity for panhandle matroid polytopes, thus confirming a conjecture of Hanely, Martin, McGinnis, Miyata, Nasr, Vindas-Meléndez, and Yin (2023). Another standing conjecture posed by Ferroni (2022) asserts that the coefficients of the Ehrhart polynomial of a connected matroid are bounded above by those of the corresponding uniform matroid. We prove Ferroni’s conjecture for paving matroids—a class conjectured to asymptotically contain all matroids. These results follow from purely enumerative statements, the main one being conjectured by Hanely, Martin, McGinnis, Miyata, Nasr, Vindas-Meléndez, and Yin, concerning the enumeration of a certain class of ordered chain forests. Thus, the content and proofs in this paper reflect an enumerative combinatorics perspective, driven by considerations in Ehrhart theory.

We prove that if a family of compact connected sets in the plane has the property that every three members of it are intersected by a line, then there are three lines intersecting all the sets in the family. This answers a question of Eckhoff [ Discrete Comput. Geom., 9 (1993), pp. 203--214], who proved that, under the same condition, there are four lines intersecting all the sets. In fact, we prove a colorful version of this result under weakened conditions on the sets. Three sets $A,B,C$ form a tight triple if $\textrm{conv}(A\cup B)\cap \textrm{conv}(A\cup C)\cap \textrm{conv}(B\cap C)\neq \emptyset.$ This notion was first introduced by Holmsen, who showed that if $\mathcal{F}$ is a family of compact convex sets in the plane in which every three sets form a tight triple, then there is a line intersecting at least $\frac{1}{8}|\mathcal{F}|$ members of $\mathcal{F}$. Here we prove that if $\mathcal{F}_1,\dots,\mathcal{F}_6$ are families of compact connected sets in the plane such that every three sets, chosen from three distinct families $\mathcal{F}_i$, form a tight triple, then there exists $1\le j\le 6$ and three lines intersecting every member of $\mathcal{F}_j$. In particular, this improves $\frac{1}{8}$ to $\frac{1}{3}$ in Holmsen's result.