Vol. 18 no. 3

1. Factoriality and the Pin-Reutenauer procedure

Almeida, J. ; Costa, J. C. ; Zeitoun, M..
We consider implicit signatures over finite semigroups determined by sets of pseudonatural numbers. We prove that, under relatively simple hypotheses on a pseudovariety V of semigroups, the finitely generated free algebra for the largest such signature is closed under taking factors within the free […]
Section: Automata, Logic and Semantics

2. Sticky Seeding in Discrete-Time Reversible-Threshold Networks

Spencer, Gwen.
When nodes can repeatedly update their behavior (as in agent-based models from computational social science or repeated-game play settings) the problem of optimal network seeding becomes very complex. For a popular spreading-phenomena model of binary-behavior updating based on thresholds of adoption […]
Section: Distributed Computing and Networking

3. Asymptotic Density of Zimin Words

Cooper, Joshua ; Rorabaugh, Danny.
Word $W$ is an instance of word $V$ provided there is a homomorphism $\phi$ mapping letters to nonempty words so that $\phi(V) = W$. For example, taking $\phi$ such that $\phi(c)=fr$, $\phi(o)=e$ and $\phi(l)=zer$, we see that "freezer" is an instance of "cool". Let $\mathbb{I}_n(V,[q])$ be the […]
Section: Combinatorics

4. The Flip Diameter of Rectangulations and Convex Subdivisions

Ackerman, Eyal ; Allen, Michelle M. ; Barequet, Gill ; Löffler, Maarten ; Mermelstein, Joshua ; Souvaine, Diane L. ; Tóth, Csaba D..
We study the configuration space of rectangulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(n\log n)$ elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of $n$ points. This bound is the […]
Section: Combinatorics

5. Heredity for generalized power domination

Dorbec, Paul ; Varghese, Seethu ; Vijayakumar, Ambat.
In this paper, we study the behaviour of the generalized power domination number of a graph by small changes on the graph, namely edge and vertex deletion and edge contraction. We prove optimal bounds for $\gamma_{p,k}(G-e)$, $\gamma_{p,k}(G/e)$ and for $\gamma_{p,k}(G-v)$ in terms of […]
Section: Graph Theory

6. Open k-monopolies in graphs: complexity and related concepts

Kuziak, Dorota ; Peterin, Iztok ; Yero, Ismael G..
Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis problems or voting systems. We introduce here open […]
Section: Graph Theory

7. On the number of vertices of each rank in phylogenetic trees and their generalizations

Bóna, Miklós.
We find surprisingly simple formulas for the limiting probability that the rank of a randomly selected vertex in a randomly selected phylogenetic tree or generalized phylogenetic tree is a given integer.
Section: Combinatorics

8. Combinatorial optimization in networks with Shared Risk Link Groups

Coudert, David ; Pérennes, Stéphane ; Rivano, Hervé ; Voge, Marie-Emilie.
The notion of Shared Risk Link Groups (SRLG) captures survivability issues when a set of links of a network may fail simultaneously. The theory of survivable network design relies on basic combinatorial objects that are rather easy to compute in the classical graph models: shortest paths, minimum […]
Section: Distributed Computing and Networking

9. Automata in SageMath---Combinatorics meet Theoretical Computer Science

Heuberger, Clemens ; Krenn, Daniel ; Kropf, Sara.
The new finite state machine package in the mathematics software system SageMath is presented and illustrated by many examples. Several combinatorial problems, in particular digit problems, are introduced, modeled by automata and transducers and solved using SageMath. In particular, we compute the […]
Section: Analysis of Algorithms

10. Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph

Šumenjak, Tadeja Kraner ; Peterin, Iztok ; Rall, Douglas F. ; Tepeh, Aleksandra.
A graph is an efficient open domination graph if there exists a subset of vertices whose open neighborhoods partition its vertex set. We characterize those graphs $G$ for which the Cartesian product $G \Box H$ is an efficient open domination graph when $H$ is a complete graph of order at least 3 or […]
Section: Graph Theory

11. Variance and Covariance of Several Simultaneous Outputs of a Markov Chain

Kropf, Sara.
The partial sum of the states of a Markov chain or more generally a Markov source is asymptotically normally distributed under suitable conditions. One of these conditions is that the variance is unbounded. A simple combinatorial characterization of Markov sources which satisfy this condition is […]
Section: Analysis of Algorithms

12. Matchings of quadratic size extend to long cycles in hypercubes

Dvořák, Tomáš.
Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a Hamiltonian cycle. A positive answer is known for perfect matchings, but the general case has been resolved only for matchings of linear size. In this paper we show that there is a quadratic function $q(n)$ […]
Section: Graph Theory

13. Sequential selection of the k best out of nrankable objects

Bruss, F. Thomas ; Louchard, Guy.
The objective of this paper is to find in a setting of n sequential observations of objects a good online policy to select the k bestof these n uniquely rankable objects. This focus is motivated by the fact that it is hard to find closed form solutions of optimalstrategies for general k and n. […]
Section: Analysis of Algorithms

14. Ramsey-type theorems for lines in 3-space

Cardinal, Jean ; Payne, Michael S. ; Solomon, Noam.
We prove geometric Ramsey-type statements on collections of lines in 3-space. These statements give guarantees on the size of a clique or an independent set in (hyper)graphs induced by incidence relations between lines, points, and reguli in 3-space. Among other things, we prove that: (1) The […]
Section: Combinatorics

15. Most Complex Regular Ideal Languages

Brzozowski, Janusz ; Davies, Sylvie ; Liu, Bo Yang Victor.
A right ideal (left ideal, two-sided ideal) is a non-empty language $L$ over an alphabet $\Sigma$ such that $L=L\Sigma^*$ ($L=\Sigma^*L$, $L=\Sigma^*L\Sigma^*$). Let $k=3$ for right ideals, 4 for left ideals and 5 for two-sided ideals. We show that there exist sequences ($L_n \mid n \ge k $) […]
Section: Automata, Logic and Semantics

16. Constructions of words rich in palindromes and pseudopalindromes

Pelantová, Edita ; Starosta, Štěpán.
A narrow connection between infinite binary words rich in classical palindromes and infinite binary words rich simultaneously in palindromes and pseudopalindromes (the so-called $H$-rich words) is demonstrated. The correspondence between rich and $H$-rich words is based on the operation $S$ acting […]
Section: Combinatorics

17. Enumeration of Corners in Tree-like Tableaux

Gao, Alice L. L. ; Gao, Emily X. L. ; Laborde-Zubieta, Patxi ; Sun, Brian Y..
In this paper, we confirm conjectures of Laborde-Zubieta on the enumeration of corners in tree-like tableaux and in symmetric tree-like tableaux. In the process, we also enumerate corners in (type $B$) permutation tableaux and (symmetric) alternative tableaux. The proof is based on Corteel and […]
Section: Combinatorics

18. Stokes posets and serpent nests

Chapoton, Frédéric.
We study two different objects attached to an arbitrary quadrangulation of a regular polygon. The first one is a poset, closely related to the Stokes polytopes introduced by Baryshnikov. The second one is a set of some paths configurations inside the quadrangulation, satisfying some specific […]
Section: Combinatorics

19. Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs

Felsner, Stefan ; Heldt, Daniel.
We study Markov chains for $\alpha$-orientations of plane graphs, these are orientations where the outdegree of each vertex is prescribed by the value of a given function $\alpha$. The set of $\alpha$-orientations of a plane graph has a natural distributive lattice structure. The moves of the […]
Section: Graph Theory