Uğur Küçük ; A. C. Cem Say ; Abuzer Yakaryılmaz.
We examine inkdots placed on the input string as a way of providing advice to
finite automata, and establish the relations between this model and the
previously studied models of advised finite automata. The existence of an
infinite hierarchy of classes of languages that can be recognized with the help
of increasing numbers of inkdots as advice is shown. The effects of different
forms of advice on the succinctness of the advised machines are examined. We
also study randomly placed inkdots as advice to probabilistic finite automata,
and demonstrate the superiority of this model over its deterministic version.
Even very slowly growing amounts of space can become a resource of meaningful
use if the underlying advised model is extended with access to secondary
memory, while it is famously known that such small amounts of space are not
useful for unadvised one-way Turing machines.
Section:
Automata, Logic and Semantics
Zbigniew Lonc ; Paweł Naroski ; Paweł Rzążewski.
By a tight tour in a $k$-uniform hypergraph $H$ we mean any sequence of its
vertices $(w_0,w_1,\ldots,w_{s-1})$ such that for all $i=0,\ldots,s-1$ the set
$e_i=\{w_i,w_{i+1}\ldots,w_{i+k-1}\}$ is an edge of $H$ (where operations on
indices are computed modulo $s$) and the sets $e_i$ for $i=0,\ldots,s-1$ are
pairwise different. A tight tour in $H$ is a tight Euler tour if it contains
all edges of $H$. We prove that the problem of deciding if a given $3$-uniform
hypergraph has a tight Euler tour is NP-complete, and that it cannot be solved
in time $2^{o(m)}$ (where $m$ is the number of edges in the input hypergraph),
unless the ETH fails. We also present an exact exponential algorithm for the
problem, whose time complexity matches this lower bound, and the space
complexity is polynomial. In fact, this algorithm solves a more general problem
of computing the number of tight Euler tours in a given uniform hypergraph.
Section:
Analysis of Algorithms
Matthieu Josuat-Vergès.
The PASEP (Partially Asymmetric Simple Exclusion Process) is a probabilistic
model of moving particles, which is of great interest in combinatorics, since
it appeared that its partition function counts some tableaux. These tableaux
have several variants such as permutations tableaux, alternative tableaux,
tree- like tableaux, Dyck tableaux, etc. We introduce in this context certain
excursions in Young's lattice, that we call stammering tableaux (by analogy
with oscillating tableaux, vacillating tableaux, hesitating tableaux). Some
natural bijections make a link with rook placements in a double staircase,
chains of Dyck paths obtained by successive addition of ribbons, Laguerre
histories, Dyck tableaux, etc.
Section:
Combinatorics
Silvio Capobianco ; Jarkko Kari ; Siamak Taati.
We discuss cellular automata over arbitrary finitely generated groups. We
call a cellular automaton post-surjective if for any pair of asymptotic
configurations, every pre-image of one is asymptotic to a pre-image of the
other. The well known dual concept is pre-injectivity: a cellular automaton is
pre-injective if distinct asymptotic configurations have distinct images. We
prove that pre-injective, post-surjective cellular automata are reversible.
Moreover, on sofic groups, post-surjectivity alone implies reversibility. We
also prove that reversible cellular automata over arbitrary groups are
balanced, that is, they preserve the uniform measure on the configuration
space.
Section:
Automata, Logic and Semantics
Jan Kynčl ; Bernard Lidický ; Tomáš Vyskočil.
An irreversible $k$-threshold process (also a $k$-neighbor bootstrap
percolation) is a dynamic process on a graph where vertices change color from
white to black if they have at least $k$ black neighbors. An irreversible
$k$-conversion set of a graph $G$ is a subset $S$ of vertices of $G$ such that
the irreversible $k$-threshold process starting with $S$ black eventually
changes all vertices of $G$ to black. We show that deciding the existence of an
irreversible 2-conversion set of a given size is NP-complete, even for graphs
of maximum degree 4, which answers a question of Dreyer and Roberts.
Conversely, we show that for graphs of maximum degree 3, the minimum size of an
irreversible 2-conversion set can be computed in polynomial time. Moreover, we
find an optimal irreversible 3-conversion set for the toroidal grid,
simplifying constructions of Pike and Zou.
Section:
Graph Theory
Sherry H. F. Yan ; Robin D. P. Zhou.
Tree-like tableaux are certain fillings of Ferrers diagrams originally
introduced by Aval et al., which are in simple bijections with permutation
tableaux coming from Postnikov's study of totally nonnegative Grassmanian and
alternative tableaux introduced by Viennot. In this paper, we confirm two
conjectures of Gao et al. on the refined enumeration of non-occupied corners in
tree-like tableaux and symmetric tree-like tableaux via intermediate structures
of alternative tableaux, linked partitions, type $B$ alternative tableaux and
type $B$ linked partitions.
Section:
Combinatorics
Andrea Jiménez ; Yoshiko Wakabayashi.
In this work, we study conditions for the existence of length-constrained
path-cycle decompositions, that is, partitions of the edge set of a graph into
paths and cycles of a given minimum length. Our main contribution is the
characterization of the class of all triangle-free graphs with odd distance at
least $3$ that admit a path-cycle decomposition with elements of length at
least $4$. As a consequence, it follows that Gallai's conjecture on path
decomposition holds in a broad class of sparse graphs.
Section:
Graph Theory
Arpitha P. Bharathi ; Minati De ; Abhiruk Lahiri.
A pair of non-adjacent edges is said to be separated in a circular ordering
of vertices, if the endpoints of the two edges do not alternate in the
ordering. The circular separation dimension of a graph $G$, denoted by
$\pi^\circ(G)$, is the minimum number of circular orderings of the vertices of
$G$ such that every pair of non-adjacent edges is separated in at least one of
the circular orderings. This notion is introduced by Loeb and West in their
recent paper. In this article, we consider two subclasses of planar graphs,
namely $2$-outerplanar graphs and series-parallel graphs. A $2$-outerplanar
graph has a planar embedding such that the subgraph obtained by removal of the
vertices of the exterior face is outerplanar. We prove that if $G$ is
$2$-outerplanar then $\pi^\circ(G) = 2$. We also prove that if $G$ is a
series-parallel graph then $\pi^\circ(G) \leq 2$.
Section:
Graph Theory
Lingjuan Shi ; Heping Zhang.
Let $G$ be a simple graph with a perfect matching. Deng and Zhang showed that
the maximum anti-forcing number of $G$ is no more than the cyclomatic number.
In this paper, we get a novel upper bound on the maximum anti-forcing number of
$G$ and investigate the extremal graphs. If $G$ has a perfect matching $M$
whose anti-forcing number attains this upper bound, then we say $G$ is an
extremal graph and $M$ is a nice perfect matching. We obtain an equivalent
condition for the nice perfect matchings of $G$ and establish a one-to-one
correspondence between the nice perfect matchings and the edge-involutions of
$G$, which are the automorphisms $\alpha$ of order two such that $v$ and
$\alpha(v)$ are adjacent for every vertex $v$. We demonstrate that all extremal
graphs can be constructed from $K_2$ by implementing two expansion operations,
and $G$ is extremal if and only if one factor in a Cartesian decomposition of
$G$ is extremal. As examples, we have that all perfect matchings of the
complete graph $K_{2n}$ and the complete bipartite graph $K_{n, n}$ are nice.
Also we show that the hypercube $Q_n$, the folded hypercube $FQ_n$ ($n\geq4$)
and the enhanced hypercube $Q_{n, k}$ ($0\leq k\leq n-4$) have exactly $n$,
$n+1$ and $n+1$ nice perfect matchings respectively.
Section:
Graph Theory
Colin Defant.
Let $[K_n,f,\pi]$ be the (global) SDS map of a sequential dynamical system
(SDS) defined over the complete graph $K_n$ using the update order $\pi\in S_n$
in which all vertex functions are equal to the same function $f\colon\mathbb
F_2^n\to\mathbb F_2^n$. Let $\eta_n$ denote the maximum number of periodic
orbits of period $2$ that an SDS map of the form $[K_n,f,\pi]$ can have. We
show that $\eta_n$ is equal to the maximum number of codewords in a binary code
of length $n-1$ with minimum distance at least $3$. This result is significant
because it represents the first interpretation of this fascinating
coding-theoretic sequence other than its original definition.
Section:
Combinatorics
Ruixia Wang.
We describe a new type of sufficient condition for a balanced bipartite
digraph to be hamiltonian. Let $D$ be a balanced bipartite digraph and $x,y$ be
distinct vertices in $D$. $\{x, y\}$ dominates a vertex $z$ if $x\rightarrow z$
and $y\rightarrow z$; in this case, we call the pair $\{x, y\}$ dominating. In
this paper, we prove that a strong balanced bipartite digraph $D$ on $2a$
vertices contains a hamiltonian cycle if, for every dominating pair of vertices
$\{x, y\}$, either $d(x)\ge 2a-1$ and $d(y)\ge a+1$ or $d(x)\ge a+1$ and
$d(y)\ge 2a-1$. The lower bound in the result is sharp.
Section:
Graph Theory
Dmitry N. Kozlov.
In this paper we introduce and study a new family of combinatorial simplicial
complexes, which we call immediate snapshot complexes. Our construction and
terminology is strongly motivated by theoretical distributed computing, as
these complexes are combinatorial models of the standard protocol complexes
associated to immediate snapshot read/write shared memory communication model.
In order to define the immediate snapshot complexes we need a new combinatorial
object, which we call a witness structure. These objects are indexing the
simplices in the immediate snapshot complexes, while a special operation on
them, called ghosting, describes the combinatorics of taking simplicial
boundary. In general, we develop the theory of witness structures and use it to
prove several combinatorial as well as topological properties of the immediate
snapshot complexes.
Section:
Distributed Computing and Networking
Jonathan Chappelon.
A binary triangle of size $n$ is a triangle of zeroes and ones, with $n$ rows, built with the same local rule as the standard Pascal triangle modulo $2$. A binary triangle is said to be balanced if the absolute difference between the numbers of zeroes and ones that constitute this triangle is at most $1$. In this paper, the existence of balanced binary triangles of size $n$, for all positive integers $n$, is shown. This is achieved by considering periodic balanced binary triangles, that are balanced binary triangles where each row, column or diagonal is a periodic sequence.
Section:
Combinatorics
Stéphane Devismes ; David Ilcinkas ; Colette Johnen.
We deal with the problem of maintaining a shortest-path tree rooted at some process r in a network that may be disconnected after topological changes. The goal is then to maintain a shortest-path tree rooted at r in its connected component, V_r, and make all processes of other components detecting that r is not part of their connected component. We propose, in the composite atomicity model, a silent self-stabilizing algorithm for this problem working in semi-anonymous networks, where edges have strictly positive weights. This algorithm does not require any a priori knowledge about global parameters of the network. We prove its correctness assuming the distributed unfair daemon, the most general daemon. Its stabilization time in rounds is at most 3nmax+D, where nmax is the maximum number of non-root processes in a connected component and D is the hop-diameter of V_r. Furthermore, if we additionally assume that edge weights are positive integers, then it stabilizes in a polynomial number of steps: namely, we exhibit a bound in O(maxi nmax^3 n), where maxi is the maximum weight of an edge and n is the number of processes.
Section:
Distributed Computing and Networking
Robert A. Proctor ; Matthew J. Willis.
Fix an integer partition lambda that has no more than n parts. Let beta be a
weakly increasing n-tuple with entries from {1,..,n}. The flagged Schur
function indexed by lambda and beta is a polynomial generating function in x_1,
.., x_n for certain semistandard tableaux of shape lambda. Let pi be an
n-permutation. The type A Demazure character (key polynomial, Demazure
polynomial) indexed by lambda and pi is another such polynomial generating
function. Reiner and Shimozono and then Postnikov and Stanley studied
coincidences between these two families of polynomials. Here their results are
sharpened by the specification of unique representatives for the equivalence
classes of indexes for both families of polynomials, extended by the
consideration of more general beta, and deepened by proving that the polynomial
coincidences also hold at the level of the underlying tableau sets. Let R be
the set of lengths of columns in the shape of lambda that are less than n.
Ordered set partitions of {1,..,n} with block sizes determined by R, called
R-permutations, are used to describe the minimal length representatives for the
parabolic quotient of the nth symmetric group specified by the set
{1,..,n-1}\R. The notion of 312-avoidance is generalized from n-permutations to
these set partitions. The R-parabolic Catalan number is defined to be the
number of these. Every flagged Schur function arises as a Demazure polynomial.
Those Demazure polynomials are precisely indexed by the […]
Section:
Combinatorics
Hao Lin ; Xiumei Wang.
In connection with Fulkerson's conjecture on cycle covers, Fan and Raspaud
proposed a weaker conjecture: For every bridgeless cubic graph $G$, there are
three perfect matchings $M_1$, $M_2$, and $M_3$ such that $M_1\cap M_2 \cap
M_3=\emptyset$. We call the property specified in this conjecture the three
matching intersection property (and 3PM property for short). We study this
property on matching covered graphs. The main results are a necessary and
sufficient condition and its applications to characterization of special
graphs, such as the Halin graphs and 4-regular graphs.
Section:
Graph Theory
Alexis Cornet ; Christian Laforest.
Total dominating set, connected vertex cover and Steiner tree are well-known graph problems. Despite the fact that they are NP-complete to optimize, it is easy (even trivial) to find solutions, regardless of their size. In this paper, we study a variant of these problems by adding conflicts, that are pairs of vertices that cannot be both in a solution. This new constraint leads to situations where it is NP-complete to decide if there exists a solution avoiding conflicts. This paper proposes NP-completeness proofs of the existence of a solution for different restricted classes of graphs and conflicts, improving recent results. We also propose polynomial time constructions in several restricted cases and we introduce a new parameter, the stretch, to capture the locality of the conflicts.
Section:
Graph Theory