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.
The present paper considers extremal combinatorics questions in the language of matrices. An $s$-matrix is a matrix with entries in $\{0,1,\ldots, s-1\}$. An $s$-matrix is simple if it has no repeated columns. A matrix $F$ is a configuration in a matrix $A$, denoted $F\prec A$, if it is a row/column permutation of a submatrix of $A$. $\text{Avoid}(m,s,F)$ is the set of $m$-rowed, simple $s$-matrices not containing a configuration of $F$ and $\text{forb}(m,s, F)=\max\{|A|\colon A \in \text{Avoid}(m,s,F)\}$. Dillon and Sali initiated the systematic study of $\text{forb}(m,s, F)$ for $2$-matrices $F$, and computed $\text{forb}(m,s, F)$ for all 2-rowed $F$ when $s>3$. In this paper we tackle the remaining cases when $s=3$. In particular, we determine the asymptotics of $\text{forb}(m,3,p\cdot K_2)-\text{forb}(m,3,p\cdot I_2)$ for $p>3$, where $K_2$ is the $2\times 4$ simple $2$-matrix and $I_2$ is the $2\times 2$ identity matrix, as well as the exact values of $\text{forb}(m,3,F)$ for many 2-rowed $2$-matrices $F$. 19 pages
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
Michael Lampis, Valia Mitsou, Edouard Nemery, Yota Otachi, Manolis Vasilakis, Daniel Vaz
In this paper we study the Spanning Tree Congestion problem, where we are given a graph $G=(V,E)$ and are asked to find a spanning tree $T$ of minimum maximum congestion. Here, the congestion of an edge $e\in T$ is the number of edges $uv\in E$ such that the (unique) path from $u$ to $v$ in $T$ traverses $e$. We consider this well-studied NP-hard problem from the point of view of (structural) parameterized complexity and obtain the following results. We resolve a natural open problem by showing that Spanning Tree Congestion is not FPT parameterized by treewidth (under standard assumptions). More strongly, we present a generic reduction which applies to (almost) any parameter of the form ``vertex-deletion distance to class $\mathcal{C}$'', thus obtaining W[1]-hardness for parameters more restricted than treewidth, including tree-depth plus feedback vertex set, or incomparable to treewidth, such as twin cover. Via a slight tweak of the same reduction we also show that the problem is NP-complete on interval graphs of modular-width $4$. Even though it is known that Spanning Tree Congestion remains NP-hard on instances with only one vertex of unbounded degree, it is currently open whether the problem remains hard on bounded-degree graphs. We resolve this question by showing NP-hardness on graphs of maximum degree 8. Complementing the problem's W[1]-hardness for treewidth... Abstract cropped to meet arXiv's requirements. Presented at MFCS 2025
