Ascent sequences form a central class of combinatorial objects, as they are in bijection with several important families such as (2+2)-free posets, Stoimenow matchings, and other Fishburn objects, and are enumerated by the Fishburn numbers. We study pattern avoidance in ascent sequences for the five patterns of length 4: $0101$, $0102$, $0112$, $0120$, and $0121$. These patterns arise naturally from recent work on pattern avoidance in related families of Fishburn objects, including Stoimenow matchings and (2+2)-free posets. We enumerate ascent sequences avoiding any subset of these patterns, with the exception of the sets $\{0120\}$, $\{0121\}$, and $\{0120,0121\}$, for which the enumeration remains open. Our results reveal that the corresponding avoidance classes fall into $16$ Wilf equivalence classes and exhibit a wide range of enumerative behaviour, including connections to classical sequences such as the Catalan and Fibonacci numbers, as well as polynomial formulas and rational generating functions; several of the sequences we obtain appear to be new. Our methods combine structural decompositions with generating-tree techniques and, in several cases, rely on reductions to shorter patterns via restricted growth functions. This work contributes to the broader study of pattern avoidance across Fishburn families and highlights further connections between ascent sequences and other combinatorial structures.
An inversion sequence of length $n$ is an integer sequence $(a_1, \ldots, a_n)$ such that $0 \le a_i < i$ for all $i$. The study of pattern-avoiding inversion sequences was initiated in 2015 by Mansour and Shattuck and in 2016 by Corteel, Martinez, Savage and Weselcouch. Martinez and Savage later defined a new type of pattern, a triple of binary relations, of which there are currently 14 uncounted avoidance classes. We complete the enumeration for all of these classes using generating tree methods "growing on the left" and "growing on the right". For many of these classes we are able to find algebraic generating functions. We also discuss the asymptotic behaviour of the counting sequences. Added further details for some calculations of solutions, a new appendix explaining asymptotic estimates, and a Mathematica notebook as an ancillary file. Various other minor corrections and tweaks
Pin sequences play an important role in the structural study of permutation classes. In this paper, we study the permutation classes that comprise all the finite subpermutations contained in an infinite pin sequence. We prove that these permutation classes have proper growth rates and establish a procedure for calculating these growth rates.
We consider weighted automata over words and over trees where the weight algebras are strong bimonoids, i.e., semirings which may lack distributivity. It is well known that, for each such weighted automaton, its run semantics and its initial algebra semantics can be different, due to the absence of distributivity. Here we investigate the question under which conditions on a zero-sum-free strong bimonoid the support of the run semantics equals the support of the initial algebra semantics. We prove a characterization of this equality both for weighted automata over words and for weighted automata over trees in terms of two weakened distributivity laws for the strong bimonoids which are required to hold only for expressions evaluating to zero. This provides a natural extension of two classical results on the coincidence of the run semantics and the initial algebra semantics. We also consider shortly the images of the two semantics functions.
A long-standing Conjecture of S. Negami states that a connected graph has a finite planar cover if and only if it embeds in the projective plane. It is known that the Conjecture is equivalent to the fact that \emph{the graph $K_{1,2, 2, 2}$ has no finite planar cover}. We prove three theorems showing that the graph $K_{1,2, 2, 2}$ admits no planar cover with certain structural properties, and that the minimal planar cover of $K_{1,2, 2, 2}$ (if it exists) must be $4$-connected.
Let $G$ be a simple undirected graph. A function $f : V(G) \to \mathbb{Z}_{\geq 0}$ is a $\textit{resolving broadcast}$ of $G$ if for any distinct $x, y \in V(G)$, there exists a vertex $z \in V(G)$ with $f(z) > 0$ such that $\min \{ d(z, x), f(z)+1 \} \neq \min \{ d(z, y), f(z)+1 \}$. The $\textit{broadcast dimension}$ $\text{bdim}(G)$ of $G$ is the minimum of $\sum_{v \in V(G)} f(v)$ over all resolving broadcasts $f$ of $G$. Similarly, the $\textit{adjacency dimension}$ $\text{adim}(G)$ of $G$ is the minimum of $\sum_{v \in V(G)} f(v)$ over all resolving broadcasts $f$ of $G$ where $f$ takes values in $\{0,1\}$. These parameters are defined analogously for directed graphs by considering directed distances. We partially resolve a question of Zhang by obtaining precise bounds for the adjacency dimension of certain Cartesian products of path graphs, namely $\text{adim}(P_2 \square P_n)$ and $\text{adim}(P_3 \square P_n)$. Additionally, we study the behavior of adjacency and broadcast dimension on directed graphs. First, we explicitly calculate the adjacency dimension of a directed complete $k$-ary tree, where every edge is directed towards the leaves. Next, we prove that $\text{adim}(\vec{G}) = \text{bdim}(\vec{G})$ for some particular directed trees $\vec{G}$. Furthermore, we show that $\text{bdim}(G)$ can be as large as an exponential function of $\text{bdim}(\vec{G})$ or as small as a logarithmic function of $\text{bdim}(\vec{G})$. Comment: 16 pages, 12 figures
We introduce, for every surface $Σ$, a two-way connection between definability of a graph class $\mathcal C$ by FO transductions (first-order logical transformations) of the graphs embeddable in $Σ$ and a certain variant of fan-crossing drawings of the graphs from $\mathcal C$ in $Σ$. If $\mathcal C$ is additionally of bounded maximum degree, then the restriction on drawings of the graphs from $\mathcal C$ in $Σ$ is simply to have a bounded number of crossings per edge (such as being $k$-planar for fixed~$k$ if $Σ$ is the plane). For graph classes, this connection allows us to derive non-transducibility results from the nonexistence of the said drawings and, conversely, from the nonexistence of a transduction to derive nonexistence of the said drawings. One example of such reasoning is as follows; since the class of 3D-grids is not transducible from the class of planar graphs, we can conclude that the class of 3D-grids is not $k$-planar for any fixed~$k$. On the other hand, the fact that the class of 3D-grids is not $k$-planar for any fixed~$k$ is known also via other means, and this conversely implies that the class of 3D-grids is not transducible from the class of planar graphs. We hope that this connection will help to draw a path to a possible proof that not all toroidal graphs are transducible from planar graphs. The result is based on a recent characterization of weakly sparse FO transductions of classes of bounded expansion by [Gajarský, Gładkowski, Jedelský, Pilipczuk and Toruńczyk, arXiv:2505.15655].
It is well known that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo 2 generates a Sierpinski triangle. It has been shown that such patterns can occur when the alphabet is endowed with the structure of an Abelian group, provided the cellular automaton is a morphism with respect to this structure and the initial configuration has finite support. The spacetime diagram then has a property related to k-automaticity. We show that these conditions can be relaxed: the Abelian group can be a commutative monoid, the initial configuration can be k-automatic, and the spacetime diagrams still exhibit the same regularity. 35 pages, 14 figures
Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer. A fundamental computational problem in this context is the Tree Containment problem, which asks whether a given phylogenetic network is compatible with a given phylogenetic tree. However, the classical statement of the problem is not robust to poorly supported branches in biological data, possibly leading to false negatives. In an effort to address this, a relaxed version that accounts for uncertainty, called Soft Tree Containment, has been introduced by Bentert, Malík, and Weller [SWAT'18]. We present an algorithm that solves Soft Tree Containment in $2^{O(Δ_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ time, where $k = \operatorname{sw}(Γ) + Δ_N$, with $Δ_T$ and $Δ_N$ denoting the maximum out-degrees in the tree and the network, respectively, and $\operatorname{sw}(Γ)$ denoting the "scanwidth" [Berry, Scornavacca, and Weller, SOFSEM'20] of a given tree extension of the network, while $n$ is the input size. Our approach leverages the fact that phylogenetic networks encountered in practice often exhibit low scanwidth, making the problem more tractable. 24 pages. Accepted at DMTCS. An extended abstract appeared in the proceedings of SOFSEM 2026
The Union Closed Sets Conjecture is one of the most renowned problems in combinatorics. Its appeal lies in the simplicity of its statement contrasted with the potential complexity of its resolution. The conjecture posits that, in any union closed family of sets, there exists at least one element that appears in at least half of the sets within the family. We establish the graph-theoretic version of certain set-theoretic results by connecting the set-based and graph-based formulations. We then prove a theorem in which we investigate the conjecture for graphs, focusing on their decompositions and the position of certain pendant vertices. As a result, we extend the validity of the conjecture to a broader class of graph structures. 14 pages, 6 figures
