J. Almeida ; J. C. Costa ; M. Zeitoun.
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
Gwen Spencer.
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
Joshua Cooper ; Danny Rorabaugh.
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
Eyal Ackerman ; Michelle M. Allen ; Gill Barequet ; Maarten Löffler ; Joshua Mermelstein ; Diane L. Souvaine ; Csaba D. Tóth.
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
Paul Dorbec ; Seethu Varghese ; Ambat Vijayakumar.
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
Dorota Kuziak ; Iztok Peterin ; Ismael G. Yero.
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
Miklós Bóna.
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
David Coudert ; Stéphane Pérennes ; Hervé Rivano ; Marie-Emilie Voge.
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
Clemens Heuberger ; Daniel Krenn ; Sara Kropf.
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
Tadeja Kraner Šumenjak ; Iztok Peterin ; Douglas F. Rall ; Aleksandra Tepeh.
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
Sara Kropf.
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
Tomáš Dvořák.
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
F. Thomas Bruss ; Guy Louchard.
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
Jean Cardinal ; Michael S. Payne ; Noam Solomon.
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
Janusz Brzozowski ; Sylvie Davies ; Bo Yang Victor Liu.
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
Edita Pelantová ; Štěpán Starosta.
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
Alice L. L. Gao ; Emily X. L. Gao ; Patxi Laborde-Zubieta ; Brian Y. Sun.
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
Frédéric Chapoton.
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
M Archana ; V Kannan.
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.
Stefan Felsner ; Daniel Heldt.
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