 |
Discrete Mathematics & Theoretical Computer Science |
Vol. 18 no. 3
1. Factoriality and the Pin-Reutenauer procedure
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 pro-V semigroup on the same set of generators. Furthermore, we show that the natural analogue of the Pin-Reutenauer descriptive procedure for the closure of a rational language in the free group with respect to the profinite topology holds for the pseudovariety of all finite semigroups. As an application, we establish that a pseudovariety enjoys this property if and only if it is full.
Section:
Automata, Logic and Semantics
2. Sticky Seeding in Discrete-Time Reversible-Threshold Networks
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 among neighbors, we consider several planning problems in the design of \textit{Sticky Interventions}: when adoption decisions are reversible, the planner aims to find a Seed Set where temporary intervention leads to long-term behavior change. We prove that completely converting a network at minimum cost is $\Omega(\ln (OPT) )$-hard to approximate and that maximizing conversion subject to a budget is $(1-\frac{1}{e})$-hard to approximate. Optimization heuristics which rely on many objective function evaluations may still be practical, particularly in relatively-sparse networks: we prove that the long-term impact of a Seed Set can be evaluated in $O(|E|^2)$ operations. For a more descriptive model variant in which some neighbors may be more influential than others, we show that under integer edge weights from $\{0,1,2,...,k\}$ objective function evaluation requires only $O(k|E|^2)$ operations. These operation bounds are based on improvements we give for bounds on time-steps-to-convergence under discrete-time reversible-threshold updates in networks.
Section:
Distributed Computing and Networking
3. Asymptotic Density of Zimin Words
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 probability that a random length $n$ word on the alphabet $[q] = \{1,2,\cdots q\}$ is an instance of $V$. Having previously shown that $\lim_{n \rightarrow \infty} \mathbb{I}_n(V,[q])$ exists, we now calculate this limit for two Zimin words, $Z_2 = aba$ and $Z_3 = abacaba$.
Section:
Combinatorics
4. The Flip Diameter of Rectangulations and Convex Subdivisions
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 best possible for some point sets, while $\Theta(n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane.
Section:
Combinatorics
5. Heredity for generalized power domination
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 $\gamma_{p,k}(G)$, and give examples for which these bounds are tight. We characterize all graphs for which $\gamma_{p,k}(G-e) = \gamma_{p,k}(G)+1$ for any edge $e$. We also consider the behaviour of the propagation radius of graphs by similar modifications.
Section:
Graph Theory
6. Open k-monopolies in graphs: complexity and related concepts
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 $k$-monopolies in graphs which are closely related to different parameters in graphs. Given a graph $G=(V,E)$ and $X\subseteq V$, if $\delta_X(v)$ is the number of neighbors $v$ has in $X$, $k$ is an integer and $t$ is a positive integer, then we establish in this article a connection between the following three concepts: - Given a nonempty set $M\subseteq V$ a vertex $v$ of $G$ is said to be $k$-controlled by $M$ if $\delta_M(v)\ge \frac{\delta_V(v)}{2}+k$. The set $M$ is called an open $k$-monopoly for $G$ if it $k$-controls every vertex $v$ of $G$. - A function $f: V\rightarrow \{-1,1\}$ is called a signed total $t$-dominating function for $G$ if $f(N(v))=\sum_{v\in N(v)}f(v)\geq t$ for all $v\in V$. - A nonempty set $S\subseteq V$ is a global (defensive and offensive) $k$-alliance in $G$ if $\delta_S(v)\ge \delta_{V-S}(v)+k$ holds for every $v\in V$. In this article we prove that the problem of computing the minimum cardinality of an open $0$-monopoly in a graph is NP-complete even restricted to bipartite or chordal graphs. In addition we present some general bounds for the minimum cardinality of open $k$-monopolies and we derive some exact values.
Section:
Graph Theory
7. On the number of vertices of each rank in phylogenetic trees and their generalizations
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
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 cuts, or pairs of disjoint paths. In the SRLG context, the optimization criterion for these objects is no longer the number of edges they use, but the number of SRLGs involved. Unfortunately, computing these combinatorial objects is NP-hard and hard to approximate with this objective in general. Nevertheless some objects can be computed in polynomial time when the SRLGs satisfy certain structural properties of locality which correspond to practical ones, namely the star property (all links affected by a given SRLG are incident to a unique node) and the span 1 property (the links affected by a given SRLG form a connected component of the network). The star property is defined in a multi-colored model where a link can be affected by several SRLGs while the span property is defined only in a mono-colored model where a link can be affected by at most one SRLG. In this paper, we extend these notions to characterize new cases in which these optimization problems can be solved in polynomial time. We also investigate the computational impact of the transformation from the multi-colored model to the mono-colored one. Experimental results are presented to validate the proposed algorithms and […]
Section:
Distributed Computing and Networking
9. Automata in SageMath---Combinatorics meet Theoretical Computer Science
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 asymptotic Hamming weight of a non-adjacent-form-like digit expansion, which was not known before.
Section:
Analysis of Algorithms
10. Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph
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 a complete bipartite graph. The characterization is based on the existence of a certain type of weak partition of $V(G)$. For the class of trees when $H$ is complete of order at least 3, the characterization is constructive. In addition, a special type of efficient open domination graph is characterized among Cartesian products $G \Box H$ when $H$ is a 5-cycle or a 4-cycle.
Section:
Graph Theory
11. Variance and Covariance of Several Simultaneous Outputs of a Markov Chain
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 given in terms of cycles of the underlying graph of the Markov chain. Also Markov sources with higher dimensional alphabets are considered. Furthermore, the case of an unbounded covariance between two coordinates of the Markov source is combinatorically characterized. If the covariance is bounded, then the two coordinates are asymptotically independent. The results are illustrated by several examples, like the number of specific blocks in $0$-$1$-sequences and the Hamming weight of the width-$w$ non-adjacent form.
Section:
Analysis of Algorithms
12. Matchings of quadratic size extend to long cycles in hypercubes
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)$ such that every matching in the $n$-dimensional hypercube of size at most $q(n)$ may be extended to a cycle which covers at least $\frac34$ of the vertices.
Section:
Graph Theory
13. Sequential selection of the k best out of nrankable objects
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. Selection is without recall, and the idea is to investigate threshold functions which maintain allpresent information, that is thresholds which are functions of all selections made so far. Our main interest lies in the asymptoticbehaviour of these thresholds as n -> infinity and in the corresponding asymptotic performance of the threshold algorithm.
Section:
Analysis of Algorithms
14. Ramsey-type theorems for lines in 3-space
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 intersection graph of n lines in R^3 has a clique or independent set of size Omega(n^{1/3}). (2) Every set of n lines in R^3 has a subset of n^{1/2} lines that are all stabbed by one line, or a subset of Omega((n/log n)^{1/5}) such that no 6-subset is stabbed by one line. (3) Every set of n lines in general position in R^3 has a subset of Omega(n^{2/3}) lines that all lie on a regulus, or a subset of Omega(n^{1/3}) lines such that no 4-subset is contained in a regulus. The proofs of these statements all follow from geometric incidence bounds -- such as the Guth-Katz bound on point-line incidences in R^3 -- combined with Turán-type results on independent sets in sparse graphs and hypergraphs. Although similar Ramsey-type statements can be proved using existing generic algebraic frameworks, the lower bounds we get are much larger than what can be obtained with these methods. The proofs directly yield polynomial-time algorithms for finding subsets of the claimed size.
Section:
Combinatorics
15. Most Complex Regular Ideal Languages
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 $) of right, left, and two-sided regular ideals, where $L_n$ has quotient complexity (state complexity) $n$, such that $L_n$ is most complex in its class under the following measures of complexity: the size of the syntactic semigroup, the quotient complexities of the left quotients of $L_n$, the number of atoms (intersections of complemented and uncomplemented left quotients), the quotient complexities of the atoms, and the quotient complexities of reversal, star, product (concatenation), and all binary boolean operations. In that sense, these ideals are "most complex" languages in their classes, or "universal witnesses" to the complexity of the various operations.
Section:
Automata, Logic and Semantics
16. Constructions of words rich in palindromes and pseudopalindromes
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 over words over the alphabet $\{0,1\}$ and defined by $S(u_0u_1u_2\ldots) = v_1v_2v_3\ldots$, where $v_i= u_{i-1} + u_i \mod 2$. The operation $S$ enables us to construct a new class of rich words and a new class of $H$-rich words. Finally, the operation $S$ is considered on the multiliteral alphabet $\mathbb{Z}_m$ as well and applied to the generalized Thue--Morse words. As a byproduct, new binary rich and $H$-rich words are obtained by application of $S$ on the generalized Thue--Morse words over the alphabet $\mathbb{Z}_4$.
Section:
Combinatorics
17. Enumeration of Corners in Tree-like Tableaux
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 Nadeau's bijection between permutation tableaux and permutations. It allows us to interpret the number of corners as a statistic over permutations that is easier to count. The type $B$ case uses the bijection of Corteel and Kim between type $B$ permutation tableaux and signed permutations. Moreover, we give a bijection between corners and runs of size 1 in permutations, which gives an alternative proof of the enumeration of corners. Finally, we introduce conjectural polynomial analogues of these enumerations, and explain the implications on the PASEP.
Section:
Combinatorics
18. Stokes posets and serpent nests
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 constraints. These objects provide a generalisation of the existing combinatorics of cluster algebras and nonnesting partitions of type A.
Section:
Combinatorics
19. A Context free language associated with interval maps
For every interval map with finitely many periodic points of periods 1 and 2, we associate a word by taking the periods of these points from left to right. It is natural to ask which words arise in this manner. In this paper we give two different characterizations of the language obtained in this way.
20. Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs
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 up-down Markov chain on this distributive lattice corresponds to reversals of directed facial cycles in the $\alpha$-orientation. We have a positive and several negative results regarding the mixing time of such Markov chains. A 2-orientation of a plane quadrangulation is an orientation where every inner vertex has outdegree 2. We show that there is a class of plane quadrangulations such that the up-down Markov chain on the 2-orientations of these quadrangulations is slowly mixing. On the other hand the chain is rapidly mixing on 2-orientations of quadrangulations with maximum degree at most 4. Regarding examples for slow mixing we also revisit the case of 3-orientations of triangulations which has been studied before by Miracle et al.. Our examples for slow mixing are simpler and have a smaller maximum degree, Finally we present the first example of a function $\alpha$ and a class of plane triangulations of constant maximum degree such that the up-down Markov chain on the $\alpha$-orientations of these graphs is slowly mixing.
Section:
Graph Theory