Stability of Cellular Automata Trajectories Revisited: Branching Walks and Lyapunov Profiles

We study non-equilibrium defect accumulation dynamics on a cellular automaton trajectory: a branching walk process in which a defect creates a successor on any neighborhood site whose update it affects. On an infinite lattice, defects accumulate at different exponential rates in different directions, giving rise to the Lyapunov profile. This profile quantifies instability of a cellular automaton evolution and is connected to the theory of large deviations. We rigorously and empirically study Lyapunov profiles generated from random initial states. We also introduce explicit and computationally feasible variational methods to compute the Lyapunov profiles for periodic configurations, thus developing an analog of Floquet theory for cellular automata.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

Some applications of propositional logic to cellular automata

In this paper we give a new proof of Richardson's theorem [31]: a global function G_?? of a cellular automaton ?? is injective if and only if the inverse of G_?? is a global function of a cellular automaton. Moreover, we show a way how to construct the inverse cellular automaton using the method of feasible interpolation from [20]. We also solve two problems regarding complexity of cellular automata formulated by Durand [12] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The graph structure of a deterministic automaton chosen at random

An n‐state deterministic finite automaton over a k‐letter alphabet can be seen as a digraph with n vertices which all have k labeled out‐arcs. Grusho (Publ Math Inst Hungarian Acad Sci 5 (1960), 17–61). proved that whp in a random k‐out digraph there is a strongly connected component of linear size, i.e., a giant, and derived a central limit theorem. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of tree‐like structures, and present a new proof of Grusho's theorem. Among other things, we pinpoint the phase transition for strong connectivity. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 428–458, 2017     

Large deviation analysis for layered percolation problems on the complete graph

We analyze the large deviation properties for the (multitype) version of percolation on the complete graph – the simplest substitutive generalization of the Erd&0151;s‐Rènyi random graph that was treated in article by Bollobás et al. (Random Structures Algorithms 31 (2007), 3–122). Here the vertices of the graph are divided into a fixed finite number of sets (called layers) the probability of {u,v} being in our edge set depends on the respective layers of u and v. We determine the exponential rate function for the probability that a giant component occupies a fixed fraction of the graph, while all other components are small. We also determine the exponential rate function for the probability that a particular exploration process on the random graph will discover a certain fraction of vertices in each layer, without encountering a giant component.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 460–492, 2012     

Hitting time results for Maker‐Breaker games

We study Maker‐Breaker games played on the edge set of a random graph. Specifically, we analyze the moment a typical random graph process first becomes a Maker's win in a game in which Maker's goal is to build a graph which admits some monotone increasing property \begin{align*}\mathcal{P}\end{align*}. We focus on three natural target properties for Maker's graph, namely being k ‐vertex‐connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the k ‐vertex connectivity game exactly at the time the random graph process first reaches minimum degree 2k; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree 2; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree 4. The latter two statements settle conjectures of Stojakovi? and Szabó. We also prove generalizations of the latter two results; these generalizations partially strengthen some known results in the theory of random graphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

The Median of the Number of Simple Paths on Three Vertices in the Random Graph

We study the asymptotic behavior of the random variable equal to the number of simple paths on three vertices in the binomial random graph in which the edge probability equals the threshold probability of the appearance of such paths. We prove that, for any fixed nonnegative integer b and a sufficiently large number n of vertices of the graph, the probability that the number of simple paths on three vertices in the given random graph is b decreases with n. As a consequence of this result, we obtain the median of the number of simple paths on three vertices for sufficiently large n.

     

Cardy's formula for some dependent percolation models

We prove Cardy's formula for rectangular crossing probabilities in dependent site percolation models that arise from a deterministic cellular automaton with a random initial state. The cellular automaton corresponds to the zero-temperature case of Domany's stochastic Ising ferromagnet on the hexagonal lattice  (with alternating updates of two sublattices) [7]; it may also be realized on the triangular lattice 𝕋 with flips when a site disagrees with six, five and sometimes four of its six neighbors. Received: 24 December 2001     

Bootstrap percolation with inhibition

We study a variant of the classical bootstrap percolation process on Erd?s Rényi random graphs. The graphs we consider have inhibitory vertices obstructing the diffusion of activity and excitatory vertices facilitating it. We study both a synchronous and an asynchronous version of the process. Both begin with a small initial set of active vertices, and the activation spreads to all vertices for which the number of excitatory active neighbors exceeds the number of inhibitory active neighbors by a certain amount. We show that in the synchronous process, inhibitory vertices may cause unstable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. We further show that in the asynchronous model the process becomes stable and stops with an active set containing a nontrivial deterministic constant fraction of all vertices. Moreover, we show that percolation occurs significantly faster asynchronously than synchronously.     

Weak Borel chromatic numbers

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G ‐independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge. We show that it is consistent with an arbitrarily large size of the continuum that every closed graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ?₁. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA. Slightly weaker results hold for F_σ‐graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable F_σ‐graph has a Borel chromatic number of at most ?₁. We refute various reasonable generalizations of these results to hypergraphs (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Finitely nonstationary nondeterministic automata with random input

Properties of generalized finitely nonstationary nondeterministic automata with an additional random input over a Boolean lattice are considered which are related to the definition of the class of languages represented by such automaton models. New notions of an elementary nondeterministic automatic structure with a random input, of a generalized finitely nonstationary nondeterministic automaton with a random input, of the generalized mapping induced by such an automaton, and of a generalized language represented by such an automaton are introduced. A number of statements substantiating synthesis for any given generalized finitely nonstationary nondeterministic automaton with a random input of an abstract probabilistic finite automaton equivalent to the given one relative to the represented generalized language probabilistic language of the stationary abstract probabilistic finite automaton. The number of states of the synthesized probabilistic automaton is estimated and a synthesis algorithm is developed in detail and illustrated by an example.     

Random approximations and random fixed point theorems for random 1-setn-contractive non-self-maps in abstract cones

In this paper, we will prove that the random version of Fan's Theorem [6, Theorem 2] is true for a random hemicompact 1-set-contractive map defined on a closed ball, a sphere and an annulus in cones. This class of random 1-set-contractive map includes random condensing maps, random continuous semicontractive maps, random LANE maps, random nonexpansive maps and others. As applications of our theorems, some random fixed point theorems of non-self-maps are proved under various well-known boundary conditions. Our results are generalizations, improvements or stochastic versions of the recent results obtained by many authors     

Forcing highly connected subgraphs

A theorem of Mader states that highly connected subgraphs can be forced in finite graphs by assuming a high minimum degree. We extend this result to infinite graphs. Here, it is necessary to require not only high degree for the vertices but also high vertex‐degree (or multiplicity) for the ends of the graph, that is, a large number of disjoint rays in each end. We give a lower bound on the degree of vertices and the vertex‐degree of the ends which is quadratic in k, the connectedness of the desired subgraph. In fact, this is not far from best possible: we exhibit a family of graphs with a degree of order 2^k at the vertices and a vertex‐degree of order k log k at the ends which have no k‐connected subgraphs. Furthermore, if in addition to the high degrees at the vertices, we only require high edge‐degree for the ends (which is defined as the maximum number of edge‐disjoint rays in an end), Mader's theorem does not extend to infinite graphs, not even to locally finite ones. We give a counterexample in this respect. But, assuming a lower bound of at least 2k for the edge‐degree at the ends and the degree at the vertices does suffice to ensure the existence (k + 1)‐edge‐connected subgraphs in arbitrary graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 331–349, 2007     

Study of discrete automaton models of gene networks of nonregular structure using symbolic calculations

We introduce the discrete automaton models of gene networks with weight functions of vertices accounting for the various forms of the regulatory interaction of agents. We study the discrete mapping that describes the operation of a fragment of the gene network of the bacteria E. coli. For this mapping, we find its fixed points (stationary states) on using the SAT approach. We also study the mappings that are defined by the random graphs of the network which we generate in accordance with the Gilbert-Erdos-Renyi and Watts-Strogatz models. For these mappings, we find the fixed points and the length 2 and 3 cycles. This article can be regarded as a survey of our results on the discrete models of gene networks and the numerical methods for studying their operation.     

Local limit theorems for occupancy models

We present a rather general method for proving local limit theorems, with a good rate of convergence, for sums of dependent random variables. The method is applicable when a Stein coupling can be exhibited. Our approach involves both Stein's method for distributional approximation and Stein's method for concentration. As applications, we prove local central limit theorems with rate of convergence for the number of germs with d neighbors in a germ‐grain model, and the number of degree‐d vertices in an Erd?s‐Rényi random graph. In both cases, the error rate is optimal, up to logarithmic factors.     

The Number of Seymour Vertices in Random Tournaments and Digraphs

Seymour’s distance two conjecture states that in any digraph there exists a vertex (a “Seymour vertex”) that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour’s conjecture, proving that almost surely there are a “large” number of Seymour vertices in random tournaments and “even more” in general random digraphs.     

A stochastic model for solitons

The soliton physics for the propagation of waves is represented by a stochastic model in which the particles of the wave can jump ahead according to some probability distribution. We demonstrate the presence of a steady state (stationary distribution) for the wavelength. It is shown that the stationary distribution is a convolution of geometric random variables. Approximations to the stationary distribution are investigated for a large number of particles. The model is rich and includes Gaussian cases as limit distribution for the wavelength (when suitably normalized). A sufficient Lindeberg‐like condition identifies a class of solitons with normal behavior. Our general model includes, among many other reasonable alternatives, an exponential aging soliton, of which the uniform soliton is one special subcase (with Gumbel's stationary distribution). With the proper interpretation, our model also includes the deterministic model proposed in Takahashi and Satsuma [A soliton cellular automaton, J Phys Soc Japan 59 (1990), 3514–3519]. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Dynamics groups of asynchronous cellular automata

We say that a finite asynchronous cellular automaton (or more generally, any sequential dynamical system) is π-independent if its set of periodic points are independent of the order that the local functions are applied. In this case, the local functions permute the periodic points, and these permutations generate the dynamics group. We have previously shown that exactly 104 of the possible 2²³=2562^{2^{3}}=256 cellular automaton rules are π-independent. In the article, we classify the periodic states of these systems and describe their dynamics groups, which are quotients of Coxeter groups. The dynamics groups provide information about permissible dynamics as a function of update sequence and, as such, connect discrete dynamical systems, group theory, and algebraic combinatorics in a new and interesting way. We conclude with a discussion of numerous open problems and directions for future research.     

Sparse graphs: Metrics and random models

Recently, Bollobás, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with n vertices and Θ(n) edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function κ: [0, 1]² → [0, ∞). To understand these models, we should like to know when different kernels κ give rise to “similar” graphs, and, given a real‐world network, how “similar” is it to a typical graph G(n, κ) derived from a given kernel κ. The analogous questions for dense graphs, with Θ(n²) edges, are answered by recent results of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in [0, 1]. Possible generalizations of these results to graphs with o(n²) but ω(n) edges are discussed in a companion article [Bollobás and Riordan, London Math Soc Lecture Note Series 365 (2009), 211–287]; here we focus only on graphs with Θ(n) edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models and vice versa. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 1‐38, 2011