Given a finite family of combinatorial objects with a total order, ranking asks for the position of a given object, and unranking asks for the object occupying a given position. Both provide algorithmic access to families too large to enumerate. Kagey gave a polynomial-time algorithm for several position-restricted families and left open the case of $\{-1,1\}$-avoiding permutations. We show that when $|S| = 2$, the graph of forbidden squares is $2$-regular, a disjoint union of cycles, and that fixing a prefix leaves only paths and untouched cycles. This yields polynomial-time prefix counting, ranking and unranking for every two-element set of offsets, covering $\{-1,1\}$. The same structure gives a short proof that the number of $\{-1,1\}$-avoiding permutations equals the $n$-th m\'enage number for odd $n$ and exceeds it by $2$ for even $n$, proving a conjecture recorded in the OEIS entry A354152.
We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set $B$ of forbidden patterns, we study the \emph{avoider enumeration problem}: given an integer $n$, output all $B$-avoiding permutations of length $n$. Avoider enumeration is output-polynomial for every fixed $...
This work proves NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026).
Hitendra Kumar, Mathieu Mari, R. B. Sandeep· 0 citations
An isolating set of a hypergraph $H$ is a vertex set whose closed neighbourhood intersects every edge of $H$. The isolation number $\iota(H)$ is the minimum cardinality of such a set. Let $r\ge3$, and let $T$ be an $r$-uniform hypergraph whose incidence graph is a tree. We prove that, if $T$ has order $n$ and at least...
For every overlap $m\geq 3$ and every pattern length $K\geq 2m+1$, we construct an explicit permutation $p\in\mathfrak{S}_K$ such that the number of permutations containing $j$ prescribed occurrences of $p$, with successive starts separated by $K-m$, is $(2j-1)!!$ for every $j\geq 1$. Additional occurrences are permitt...
The two-stack sortable permutations of length $n$ are known to be equinumerous with permutations of length $n$ avoiding the dashed patterns $3\text{-}1\text{-}4\text{-}2$ and $2\text{-}41\text{-}3$. In this paper, we confirm an intriguing conjecture posed by Claesson, Kitaev, and Steingr\'imsson, which asserts that the...
A vertex is uni-dominated by a set $S \subseteq V(G)$ if exactly one vertex of $S$ lies in its closed neighborhood, and the uni-domination number $\mathrm{ud}^*(G)$ is the largest number of vertices a single set can uni-dominate. The graphs admitting an efficient dominating set are those with $\mathrm{ud}^*(G) = n$. He...
F. Foucaud, Y. Gérard, C. Laforest et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.