**Vaguery + dynamical-systems**
207

[1808.07409] The domino shuffling height process and its hydrodynamic limit

2 days ago by Vaguery

The famous domino shuffling algorithm was invented to generate the domino tilings of the Aztec Diamond. Using the domino height function, we view the domino shuffling procedure as a discrete-time random height process on the plane. The hydrodynamic limit from an arbitrary continuous profile is deduced to be the unique viscosity solution of a Hamilton-Jacobi equation ut+H(ux)=0, where the determinant of the Hessian of H is negative everywhere. The proof involves interpolation of the discrete process and analysis of the limiting semigroup of the evolution. In order to identify the limit, we use the theories of dimer models as well as Hamilton-Jacobi equations.

It seems that our result is the first example in d>1 where such a full hydrodynamic limit with a nonconvex Hamiltonian can be obtained for a discrete system. We also define the shuffling height process for more general periodic dimer models, where we expect similar results to hold.

combinatorics
graph-theory
feature-construction
rather-interesting
dynamical-systems
domino-tiling
to-understand
It seems that our result is the first example in d>1 where such a full hydrodynamic limit with a nonconvex Hamiltonian can be obtained for a discrete system. We also define the shuffling height process for more general periodic dimer models, where we expect similar results to hold.

2 days ago by Vaguery

[1804.02515] Periodic ellipsoidal billiard trajectories and extremal polynomials

2 days ago by Vaguery

A comprehensive study of periodic trajectories of billiards within ellipsoids in d-dimensional Euclidean space is presented. The novelty of the approach is based on a relationship established between periodic billiard trajectories and extremal polynomials on the systems of d intervals on the real line. By leveraging deep, but yet not widely known results of the Krein-Levin-Nudelman theory of generalized Chebyshev polynomials, fundamental properties of billiard dynamics are proven for any d, viz., that the sequences of winding numbers are monotonic and that the frequency maps are diffeomorphisms almost everywhere. By employing the potential theory we prove injectivity of the frequency map. As a byproduct, for d=2 a new proof of the monotonicity of the rotation number is obtained. The case study of trajectories of small periods T, d≤T≤2d is given. In particular, it is proven that all d-periodic trajectories are contained in a coordinate-hyperplane and that for a given ellipsoid, there is a unique set of caustics which generates d+1-periodic trajectories. A complete catalog of billiard trajectories with small periods is provided for d=3.

nonlinear-dynamics
billiards
rather-interesting
dynamical-systems
representation
increase-the-N
2 days ago by Vaguery

[1005.3466] Mathematical retroreflectors

7 weeks ago by Vaguery

Retroreflectors are optical devices that reverse the direction of incident beams of light. Here we present a collection of billiard type retroreflectors consisting of four objects; three of them are asymptotically perfect retroreflectors, and the fourth one is a retroreflector which is very close to perfect. Three objects of the collection have recently been discovered and published or submitted for publication. The fourth object - notched angle - is a new one; a proof of its retroreflectivity is given.

dynamical-systems
engineering-design
rather-interesting
performance-measure
approximation
to-write-about
to-simulate
consider:looking-to-see
nudge-targets
7 weeks ago by Vaguery

[1304.4005] Bodies with mirror surface invisible from two points

7 weeks ago by Vaguery

Here we are concerned with a special issue of billiard invisibility, where a bounded set with a piecewise smooth boundary in Euclidean space is identified with a body with mirror surface, and the billiard in the complement of the set is identified with the dynamics of light rays outside the body in the framework of geometric optics. We show that in this setting it is possible to construct a body invisible from two points.

billiards
dynamical-systems
rather-interesting
inverse-problems
invisibility
nudge-targets
consider:looking-to-see
7 weeks ago by Vaguery

[1602.06455] On the bicycle transformation and the filament equation: results and conjectures

7 weeks ago by Vaguery

The paper concerns a simple model of bicycle kinematics: a bicycle is represented by an oriented segment of constant length in n-dimensional space that can move in such a way that the velocity of its rear end is aligned with the segment (the rear wheel is fixed on the bicycle frame). Starting with a closed trajectory of the rear end, one obtains the two respective trajectories of the front end, corresponding to the opposite directions of motion. These two curves are said to be in the bicycle correspondence. Conjecturally, this correspondence is completely integrable; we present a number of results substantiating this conjecture. In dimension three, the bicycle correspondence is the Backlund transformation for the filament equation; we discuss bi-Hamiltonian features of the bicycle correspondence and its integrals.

plane-geometry
chords
construction
dynamical-systems
rather-interesting
mathematical-recreations
7 weeks ago by Vaguery

[1107.3633] Liouville-Arnold integrability of the pentagram map on closed polygons

7 weeks ago by Vaguery

The pentagram map is a discrete dynamical system defined on the moduli space of polygons in the projective plane. This map has recently attracted a considerable interest, mostly because its connection to a number of different domains, such as: classical projective geometry, algebraic combinatorics, moduli spaces, cluster algebras and integrable systems. Integrability of the pentagram map was conjectured by R. Schwartz and later proved by V. Ovsienko, R. Schwartz and S. Tabachnikov for a larger space of twisted polygons. In this paper, we prove the initial conjecture that the pentagram map is completely integrable on the moduli space of closed polygons. In the case of convex polygons in the real projective plane, this result implies the existence of a toric foliation on the moduli space. The leaves of the foliation carry affine structure and the dynamics of the pentagram map is quasi-periodic. Our proof is based on an invariant Poisson structure on the space of twisted polygons. We prove that the Hamiltonian vector fields corresponding to the monodoromy invariants preserve the space of closed polygons and define an invariant affine structure on the level surfaces of the monodromy invariants.

plane-geometry
construction
rather-interesting
dynamical-systems
consider:relaxation
consider:affine-intermediates
to-simulate
7 weeks ago by Vaguery

[1304.5708] Pentagram Spirals

7 weeks ago by Vaguery

We introduce a geometric construction which relates to the pentagram map much in the way that a logarithmic spiral relates to a circle. After introducing the construction, we establish some basic geometric facts about it, and speculate on some of the deeper algebraic structure, such as the complete integrability of the associated dynamical system.

dynamical-systems
mathematical-recreations
plane-geometry
geometry
construction
rather-interesting
looking-to-see
7 weeks ago by Vaguery

[1102.4635] Outer Billiards on the Penrose Kite: Compactification and Renormalizaiton

7 weeks ago by Vaguery

In this long paper we give a fairly complete analysis of outer billiards on the Penrose kite. Our analysis reveals that this 2-dimensional non-compact system has a 3-dimensional compactification, a certain polyhedron exchange map, and that this compactification has a renormalization scheme. These two features allow us to make some sharp statements concerning the distribution, large-scale geometry, fine-scale geometry, and hidden algebraic symmetries of the orbits. For instance, one of our results is that the union of the unbounded orbits has Hausdorff dimension 1. We give a computer-aided proof of the results concerning the compactification and the renormalization. This proof involves finitely many calculations done with exact integer arithmetic.

dynamical-systems
tiling
billiards
rather-interesting
nonlinear-dynamics
purdy-pitchers
7 weeks ago by Vaguery

[1307.0646] Square Turning Maps and their Compactifications

9 weeks ago by Vaguery

In this paper we introduce some infinite rectangle exchange transformations which are based on the simultaneous turning of the squares within a sequence of square grids. We will show that such noncompact systems have higher dimensional dynamical compactifications. In good cases, these compactifications are polytope exchange transformations based on pairs of Euclidean lattices. In each dimension 8m+4 there is a 4m+2 dimensional family of them. Here m=0,1,2,... The case m=0, which we studied in depth in an earlier paper, has close connections to the E4 Weyl group and the (2,4,∞) hyperbolic triangle group.

rewriting-systems
dynamical-systems
rather-interesting
consider:Lindenmayer-systems
to-simulate
to-write-about
consider:generative-models
9 weeks ago by Vaguery

[1809.07876] Tiling Billards on Triangle Tilings, and Interval Exchange Transformations

9 weeks ago by Vaguery

We consider the dynamics of light rays in triangle tilings where triangles are transparent and adjacent triangles have equal but opposite indices of refraction. We find that the behavior of a trajectory on a triangle tiling is described by an orientation-reversing three-interval exchange transformation on the circle, and that the behavior of all the trajectories on a given triangle tiling is described by a polygon exchange transformation. We show that, for a particular choice of triangle tiling, certain trajectories approach the Rauzy fractal, under rescaling.

tiling
dynamical-systems
rather-interesting
to-simulate
consider:maximizing-paths
9 weeks ago by Vaguery

[1609.00772] Periodicity and ergodicity in the trihexagonal tiling

9 weeks ago by Vaguery

We consider the dynamics of light rays in the trihexagonal tiling where triangles and hexagons are transparent and have equal but opposite indices of refraction. We find that almost every ray of light is dense in a region of a particular form: the regions have infinite area and consist of the plane with a periodic family of triangles removed. We also completely describe initial conditions for periodic and drift-periodic light rays.

billiards
tiling
rather-interesting
mathematical-recreations
dynamical-systems
to-simulate
9 weeks ago by Vaguery

[0807.3498] Billiards in Nearly Isosceles Triangles

9 weeks ago by Vaguery

We prove that any sufficiently small perturbation of an isosceles triangle has a periodic billiard path. Our proof involves the analysis of certain infinite families of Fourier series that arise in connection with triangular billiards, and reveals some self-similarity phenomena in irrational triangular billiards. Our analysis illustrates the surprising fact that billiards on a triangle near a Veech triangle is extremely complicated even though Billiards on a Veech triangle is very well understood.

billiards
dynamical-systems
visualization
plane-geometry
rather-interesting
generative-models
to-simulate
to-write-about
9 weeks ago by Vaguery

[0709.1229] Outer Billiards on Kites

9 weeks ago by Vaguery

Outer billiards is a simple dynamical system based on a convex planar shape. The Moser-Neumann question, first posed by B.H. Neumann around 1960, asks if there exists a planar shape for which outer billiards has an unbounded orbit. The first half of this monograph proves that outer billiards has an unbounded orbit defined relative to any irrational kite. The second half of the monograph gives a very sharp description of the set of unbounded orbits, both in terms of the dynamics and the Hausdorff dimension. The analysis in both halves reveals a close connection between outer billiards on kites and the modular group, as well as connections to self-similar tilings, polytope exchange maps, Diophantine approximation, and odometers.

billiards
dynamical-systems
rather-interesting
plane-geometry
open-questions
to-simulate
9 weeks ago by Vaguery

[math/0702073] Unbounded Orbits for Outer Billiards

9 weeks ago by Vaguery

Outer billiards is a basic dynamical system, defined relative to a planar convex shape. This system was introduced in the 1950's by B.H. Neumann and later popularized in the 1970's by J. Moser. All along, one of the central questions has been: is there an outer billiards system with an unbounded orbit. We answer this question by proving that outer billiards defined relative to the Penrose Kite has an unbounded orbit. The Penrose kite is the quadrilateral that appears in the famous Penrose tiling. We also analyze some of the finer orbit structure of outer billiards on the penrose kite. This analysis shows that there is an uncountable set of unbounded orbits. Our method of proof relates the problem to self-similar tilings, polygon exchange maps, and arithmetic dynamics.

billiards
mathematical-recreations
generative-models
geometry
dynamical-systems
rather-interesting
chaos
to-simulate
to-write-about
9 weeks ago by Vaguery

[1206.5223] Outer Billiards, Digital Filters and Kicked Hamiltonians

9 weeks ago by Vaguery

In 1978 Jurgen Moser suggested the outer billiards map (Tangent map) as a discontinuous model of Hamiltonian dynamics. A decade earlier, J.B. Jackson and his colleagues at Bell Labs were trying to understand the source of self-sustaining oscillations in digital filters. Some of the discrete mappings used to describe these filters show a remarkable ability to 'shadow' the Tangent map when the polygon in question is regular.

In this paper we describe a specific digital filter map (Df) that appears to have dynamics which are conjugate to the Tangent map for a regular N-gon with N even. When N is odd, there is evidence of another conjugacy between the Tangent map dynamics of N and the matching 2N-gon, so a case like N = 7 can be studied with the Df map in the context of N = 14. This provides a many-fold increase in efficiency, and also allows us to generalize the Tangent map to obtain 'step-k' versions - which have dynamics that are unexplored.

We also present some related maps, including Chua and Lin's 3-dimensional version of Df, an Analog to Digital Converter from Orla Feely, a sawtooth version of the Standard Map by Peter Ashwin and various kicked harmonic oscillators. All of these seem to shadow the Tangent map in some form. Mathematica code is provided for all mappings both here and at this http URL.

billiards
dynamical-systems
chaos
rather-interesting
purdy-pitchers
to-do
to-write-about
physics!
In this paper we describe a specific digital filter map (Df) that appears to have dynamics which are conjugate to the Tangent map for a regular N-gon with N even. When N is odd, there is evidence of another conjugacy between the Tangent map dynamics of N and the matching 2N-gon, so a case like N = 7 can be studied with the Df map in the context of N = 14. This provides a many-fold increase in efficiency, and also allows us to generalize the Tangent map to obtain 'step-k' versions - which have dynamics that are unexplored.

We also present some related maps, including Chua and Lin's 3-dimensional version of Df, an Analog to Digital Converter from Orla Feely, a sawtooth version of the Standard Map by Peter Ashwin and various kicked harmonic oscillators. All of these seem to shadow the Tangent map in some form. Mathematica code is provided for all mappings both here and at this http URL.

9 weeks ago by Vaguery

[1612.09295] First Families of Regular Polygons and their Mutations

9 weeks ago by Vaguery

Every regular N-gon generates a canonical family of regular polygons which are conforming to the bounds of the 'star polygons' determined by N. These star polygons are formed from truncated extended edges of the N-gon and the intersection points determine a scaling which defines the parameters of the family. In 'First Families of Regular Polygons' (arXiv:1503.05536) we showed that this scaling forms a basis for the maximal real subfield of the cyclotomic field of N. The traditional generator for this subfield is 2cos(2Pi/N) so it has order Phi(N)/2 where Phi is the Euler totient function. This order is known as the 'algebraic complexity' of N. The family of regular polygons shares this same scaling and complexity, so members of this family are an intrinsic part of any regular polygon - and we call them the First Family of N.

Here we start from first principles and give an algebraic derivation of the First Families showing how each star[k] point of N defines a scale[k] and also an S[k] 'tile' of the family. Under a piecewise isometry such as the outer-billiards map the 'singularity set' W can be formed by iterating the extended edges of N and we show that W can be reduced to a 'shear and rotation' which preserves the S[k], so the 'web' W can be regarded as the disjoint union (coproduct) of the local webs of the S[k]. These local webs are still very complex but we show in Lemma 4.1 that the center of each S[k] has a constant step-k orbit around N. These 'resonant' orbits set bounds on global orbits and establish a connection between geometry and dynamics. For the first time it is possible to make predictions about the small-scale geometry of the S[1] and S[2] tiles on the edges of N and give a plausible explanation for the long-standing '4k+1'conjecture of arXiv:1311.6763 about extended families of tiles when N = 8k+2. Each 8k+j family has unique edge geometry.

geometry
plane-geometry
dynamical-systems
rather-interesting
to-understand
billiards
generative-models
Here we start from first principles and give an algebraic derivation of the First Families showing how each star[k] point of N defines a scale[k] and also an S[k] 'tile' of the family. Under a piecewise isometry such as the outer-billiards map the 'singularity set' W can be formed by iterating the extended edges of N and we show that W can be reduced to a 'shear and rotation' which preserves the S[k], so the 'web' W can be regarded as the disjoint union (coproduct) of the local webs of the S[k]. These local webs are still very complex but we show in Lemma 4.1 that the center of each S[k] has a constant step-k orbit around N. These 'resonant' orbits set bounds on global orbits and establish a connection between geometry and dynamics. For the first time it is possible to make predictions about the small-scale geometry of the S[1] and S[2] tiles on the edges of N and give a plausible explanation for the long-standing '4k+1'conjecture of arXiv:1311.6763 about extended families of tiles when N = 8k+2. Each 8k+j family has unique edge geometry.

9 weeks ago by Vaguery

[1704.01166] Regenerative random permutations of integers

march 2019 by Vaguery

Motivated by recent studies of large Mallows(q) permutations, we propose a class of random permutations of ℕ+ and of ℤ, called regenerative permutations. Many previous results of the limiting Mallows(q) permutations are recovered and extended. Three special examples: blocked permutations, p-shifted permutations and p-biased permutations are studied.

combinatorics
permutations
infinite-things
dynamical-systems
probability-theory
to-understand
representation
march 2019 by Vaguery

[1703.08616] The Dynamics of Super-Apollonian Continued Fractions

march 2019 by Vaguery

We examine a pair of dynamical systems on the plane induced by a pair of spanning trees in the Cayley graph of the Super-Apollonian group of Graham, Lagarias, Mallows, Wilks and Yan. The dynamical systems compute Gaussian rational approximations to complex numbers and are "reflective" versions of the complex continued fractions of A. L. Schmidt. They also describe a reduction algorithm for Lorentz quadruples, in analogy to work of Romik on Pythagorean triples. For these dynamical systems, we produce an invertible extension and an invariant measure, which we conjecture is ergodic. We consider some statistics of the related continued fraction expansions, and we also examine the restriction of these systems to the real line, which gives a reflective version of the usual continued fraction algorithm. Finally, we briefly consider an alternate setup corresponding to a tree of Lorentz quadruples ordered by arithmetic complexity.

dynamical-systems
plane-geometry
number-theory
graph-theory
generative-models
rather-interesting
to-write-about
continued-fractions
march 2019 by Vaguery

[1807.00908] $7xpm1$: Close Relative of Collatz Problem

march 2019 by Vaguery

We show an iterated function of which iterates oscillate wildly and grow at a dizzying pace. We conjecture that the orbit of arbitrary positive integer always returns to 1, as in the case of Collatz function. The conjecture is supported by a heuristic argument and computational results.

number-theory
iteration
dynamical-systems
algorithms
open-questions
Collatz-problem
to-write-about
march 2019 by Vaguery

Math-Frolic!: Everybody Loves Raymond...

march 2019 by Vaguery

I regularly re-run my favorite old Raymond Smullyan puzzle (that actually goes back to "Annals of the New York Academy of Sciences," 1979, Vol. 321, although my version is an adaptation from Martin Gardner's presentation in his Colossal Book of Mathematics), and recently realized I failed to do so in 2018, so may as well remedy that now. Skip over if you've seen it before, but down below I have newly-tacked on a video tribute to Raymond from a prior 'Gathering For Gardner' Celebration:

dynamical-systems
mathematical-recreations
anecdote
puzzles
watch-the-video
automata
march 2019 by Vaguery

Best reply structure and equilibrium convergence in generic games | Science Advances

february 2019 by Vaguery

Game theory is widely used to model interacting biological and social systems. In some situations, players may converge to an equilibrium, e.g., a Nash equilibrium, but in other situations their strategic dynamics oscillate endogenously. If the system is not designed to encourage convergence, which of these two behaviors can we expect a priori? To address this question, we follow an approach that is popular in theoretical ecology to study the stability of ecosystems: We generate payoff matrices at random, subject to constraints that may represent properties of real-world games. We show that best reply cycles, basic topological structures in games, predict nonconvergence of six well-known learning algorithms that are used in biology or have support from experiments with human players. Best reply cycles are dominant in complicated and competitive games, indicating that in this case equilibrium is typically an unrealistic assumption, and one must explicitly model the dynamics of learning.

game-theory
dynamical-systems
complexology
it's-more-complicated-than-you-think
simulation
to-write-about
rather-interesting
nudge-targets
collective-behavior
february 2019 by Vaguery

[1806.06166] $alpha$-Expansions with odd partial quotients

february 2019 by Vaguery

We consider an analogue of Nakada's α-continued fraction transformation in the setting of continued fractions with odd partial quotients. More precisely, given α∈[12(5‾√−1),12(5‾√+1)], we show that every irrational number x∈Iα=[α−2,α) can be uniquely represented as

x=e1(x;α)d1(x;α)+e2(x;α)d2(x;α)+⋯,

with ei(x;α)∈{±1} and di(x;α)∈2ℕ−1 determined by the iterates of the transformation

φα(x):=1|x|−2[12|x|+1−α2]−1

of Iα. We also describe the natural extension of φα and prove that the endomorphism φα is exact.

continued-fractions
algebra
representation
approximation
to-understand
number-theory
dynamical-systems
x=e1(x;α)d1(x;α)+e2(x;α)d2(x;α)+⋯,

with ei(x;α)∈{±1} and di(x;α)∈2ℕ−1 determined by the iterates of the transformation

φα(x):=1|x|−2[12|x|+1−α2]−1

of Iα. We also describe the natural extension of φα and prove that the endomorphism φα is exact.

february 2019 by Vaguery

[1710.04400] Information reduction in a reverberatory neuronal network through convergence to complex oscillatory firing patterns

february 2019 by Vaguery

We study dynamics of a reverberating neural net by means of computer simulation. The net, which is composed of 9 leaky integrate-and-fire (LIF) neurons arranged in a square lattice, is fully connected with interneuronal communication delay proportional to the corresponding distance. The network is initially stimulated with different stimuli and then goes freely. For each stimulus, in the course of free evolution, activity either dies out completely or the network converges to a periodic trajectory, which may be different for different stimuli. The latter is observed for a set of 285290 initial stimuli which constitutes 83% of all stimuli applied. By applying each stimulus from the set, we found 102 different periodic end-states. By analyzing the trajectories, we conclude that neuronal firing is the necessary prerequisite for merging different trajectories into a single one, which eventually transforms into a periodic regime. Observed phenomena of self-organization in the time domain are discussed as a possible model for processes taking place during perception. The repetitive firing in the periodic regimes could underpin memory formation.

coupled-oscillators
neural-networks
simulation
rather-interesting
dynamical-systems
to-write-about
february 2019 by Vaguery

[1811.11909] Synchronization of chaotic systems: A microscopic description

february 2019 by Vaguery

The synchronization of coupled chaotic systems represents a fundamental example of self organization and collective behavior. This well-studied phenomenon is classically characterized in terms of macroscopic parameters, such as Lyapunov exponents, that help predict the systems transitions into globally organized states. However, the local, microscopic, description of this emergent process continues to elude us. Here we show that at the microscopic level, synchronization is captured through a gradual process of topological adjustment in phase space, in which the strange attractors of the two coupled systems continuously converge, taking similar form, until complete topological synchronization ensues. We observe the local nucleation of topological synchronization in specific regions of the systems attractor, providing early signals of synchrony, that appear significantly before the onset of complete synchronization. This local synchronization initiates at the regions of the attractor characterized by lower expansion rates, in which the chaotic trajectories are least sensitive to slight changes in initial conditions. Our findings offer an alternative description of synchronization in chaotic systems, exposing its local embryonic stages that are overlooked by the currently established global analysis. Such local topological synchronization enables the identification of configurations where prediction of the state of one system is possible from measurements on that of the other, even in the absence of global synchronization.

nonlinear-dynamics
coupled-oscillators
rather-interesting
synchronization
to-read
complexology
physics!
dynamical-systems
february 2019 by Vaguery

[1808.07990] Making Bubbling Practical

december 2018 by Vaguery

Bubbling is a run-time graph transformation studied for the execution of non-deterministic steps in functional logic computations. This transformation has been proven correct, but as currently formulated it requires information about the entire context of a step, even when the step affects only a handful of nodes. Therefore, despite some advantages, it does not appear to be competitive with approaches that require only localized information, such as backtracking and pull-tabbing. We propose a novel algorithm that executes bubbling steps accessing only local information. To this aim, we define graphs that have an additional attribute, a dominator of each node, and we maintain this attribute when a rewrite and/or bubbling step is executed. When a bubbling step is executed, the dominator is available at no cost, and only local information is accessed. Our work makes bubbling practical, and theoretically competitive, for implementing non-determinism in functional logic computations.

functional-languages
computer-science
programming-language
remarkably-legible
rewriting-systems
representation
dynamical-systems
ReQ
december 2018 by Vaguery

[1812.02907] Caustics of Poncelet polygons and classical extremal polynomials

december 2018 by Vaguery

A comprehensive analysis of periodic trajectories of billiards within ellipses in the Euclidean plane is presented. The novelty of the approach is based on a relationship recently established by the authors between periodic billiard trajectories and extremal polynomials on the systems of d intervals on the real line and ellipsoidal billiards in d-dimensional space. Even in the planar case, systematically studied in the present paper it leads to new results in characterizing n periodic trajectories vs. so-called n elliptic periodic trajectories, which are n-periodic in elliptical coordinates. The characterizations are done both in terms of the underlying elliptic curve and divisors on it and in terms of polynomial functional equations, like Pell's equation. This new approach also sheds light on some classical results. In particular we connect search for caustics which generate periodic trajectories with three classical classes of extremal polynomials on two intervals, introduced by Zolotarev and Akhiezer. The main classifying tool are winding numbers, for which we provide several interpretations, including one in terms of numbers of points of alternance of extremal polynomials. The latter implies important inequality between the winding numbers, which as a consequence, provides another proof of monotonicity of rotation numbers. A complete catalog of billiard trajectories with small periods is provided for n=3,4,5,6 along with an effective search for caustics. As a byproduct, an intriguing connection between Cayle type conditions and discriminantly separable polynomials has been observed for all those small periods.

dynamical-systems
billiards
polynomials
plane-geometry
rather-interesting
december 2018 by Vaguery

[1705.04353] On the records

june 2018 by Vaguery

World record setting has long attracted public interest and scientific investigation. Extremal records summarize the limits of the space explored by a process, and the historical progression of a record sheds light on the underlying dynamics of the process. Existing analyses of prediction, statistical properties, and ultimate limits of record progressions have focused on particular domains. However, a broad perspective on how record progressions vary across different spheres of activity needs further development. Here we employ cross-cutting metrics to compare records across a variety of domains, including sports, games, biological evolution, and technological development. We find that these domains exhibit characteristic statistical signatures in terms of rates of improvement, "burstiness" of record-breaking time series, and the acceleration of the record breaking process. Specifically, sports and games exhibit the slowest rate of improvement and a wide range of rates of "burstiness." Technology improves at a much faster rate and, unlike other domains, tends to show acceleration in records. Many biological and technological processes are characterized by constant rates of improvement, showing less burstiness than sports and games. It is important to understand how these statistical properties of record progression emerge from the underlying dynamics. Towards this end, we conduct a detailed analysis of a particular record-setting event: elite marathon running. In this domain, we find that studying record-setting data alone can obscure many of the structural properties of the underlying process. The marathon study also illustrates how some of the standard statistical assumptions underlying record progression models may be inappropriate or commonly violated in real-world datasets.

extreme-values
time-series
feature-extraction
rather-interesting
dynamical-systems
to-understand
june 2018 by Vaguery

[1802.03905] How to Match when All Vertices Arrive Online

june 2018 by Vaguery

We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors' arrivals. If a vertex remains unmatched until its deadline, the algorithm must then irrevocably either match it to an unmatched neighbor, or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, etc.

We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317<1−1e-competitive in our model even for bipartite graphs.

algorithms
dynamical-systems
graph-theory
rather-interesting
computational-complexity
to-write-about
to-simulate
We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317<1−1e-competitive in our model even for bipartite graphs.

june 2018 by Vaguery

The meaning of model equivalence: Network models, latent variables, and the theoretical space in between | Psych Networks

april 2018 by Vaguery

Recently, an important set of equivalent representations of the Ising model was published by Joost Kruis and Gunter Maris in Scientific Reports. The paper constructs elegant representations of the Ising model probability distribution in terms of a network model (which consists of direct relations between observables), a latent variable model (which consists of relations between a latent variable and observables, in which the latent variable acts as a common cause), and a common effect model (which also consists of relations between a latent variable and observables, but here the latent variable acts as a common effect). The latter equivalence is a novel contribution to the literature and a quite surprising finding, because it means that a formative model can be statistically equivalent to a reflective model, which one may not immediately expect (do note that this equivalence need not maintain dimensionality, so a model with a single common effect may translate in a higher-dimensional latent variable model).

However, the equivalence between the ordinary (reflective) latent variable models and network models has been with us for a long time, and I therefore was rather surprised at some people’s reaction to the paper and the blog post that accompanies it. Namely, it appears that some think that (a) the fact that network structures can mimic reflective latent variables and vice versa is a recent discovery, that (b) somehow spells trouble for the network approach itself (because, well, what’s the difference?). The first of these claims is sufficiently wrong to go through the trouble of refuting it, if only to set straight the historical record; the second is sufficiently interesting to investigate it a little more deeply. Hence the following notes.

dynamical-systems
models
models-and-modes
representation
philosophy-of-science
(in-practice)
to-write-about
via:several
However, the equivalence between the ordinary (reflective) latent variable models and network models has been with us for a long time, and I therefore was rather surprised at some people’s reaction to the paper and the blog post that accompanies it. Namely, it appears that some think that (a) the fact that network structures can mimic reflective latent variables and vice versa is a recent discovery, that (b) somehow spells trouble for the network approach itself (because, well, what’s the difference?). The first of these claims is sufficiently wrong to go through the trouble of refuting it, if only to set straight the historical record; the second is sufficiently interesting to investigate it a little more deeply. Hence the following notes.

april 2018 by Vaguery

[1803.09574] Long short-term memory and Learning-to-learn in networks of spiking neurons

april 2018 by Vaguery

Networks of spiking neurons (SNNs) are frequently studied as models for networks of neurons in the brain, but also as paradigm for novel energy efficient computing hardware. In principle they are especially suitable for computations in the temporal domain, such as speech processing, because their computations are carried out via events in time and space. But so far they have been lacking the capability to preserve information for longer time spans during a computation, until it is updated or needed - like a register of a digital computer. This function is provided to artificial neural networks through Long Short-Term Memory (LSTM) units. We show here that SNNs attain similar capabilities if one includes adapting neurons in the network. Adaptation denotes an increase of the firing threshold of a neuron after preceding firing. A substantial fraction of neurons in the neocortex of rodents and humans has been found to be adapting. It turns out that if adapting neurons are integrated in a suitable manner into the architecture of SNNs, the performance of these enhanced SNNs, which we call LSNNs, for computation in the temporal domain approaches that of artificial neural networks with LSTM-units. In addition, the computing and learning capabilities of LSNNs can be substantially enhanced through learning-to-learn (L2L) methods from machine learning, that have so far been applied primarily to LSTM networks and apparently never to SSNs.

This preliminary report on arXiv will be replaced by a more detailed version in about a month.

neural-networks
biological-engineering
dynamical-systems
rather-interesting
architecture
machine-learning
simulation
learning-by-watching
to-write-about
This preliminary report on arXiv will be replaced by a more detailed version in about a month.

april 2018 by Vaguery

[1706.05621] Double jump phase transition in a random soliton cellular automaton

february 2018 by Vaguery

In this paper, we consider the soliton cellular automaton introduced in [Takahashi 1990] with a random initial configuration. We give multiple constructions of a Young diagram describing various statistics of the system in terms of familiar objects like birth-and-death chains and Galton-Watson forests. Using these ideas, we establish limit theorems showing that if the first n boxes are occupied independently with probability p∈(0,1), then the number of solitons is of order n for all p, and the length of the longest soliton is of order logn for p<1/2, order n‾√ for p=1/2, and order n for p>1/2. Additionally, we uncover a condensation phenomenon in the supercritical regime: For each fixed j≥1, the top j soliton lengths have the same order as the longest for p≤1/2, whereas all but the longest have order at most logn for p>1/2. As an application, we obtain scaling limits for the lengths of the kth longest increasing and decreasing subsequences in a random stack-sortable permutation of length n in terms of random walks and Brownian excursions.

cellular-automata
self-organization
rather-interesting
dynamical-systems
phase-transitions
to-write-about
february 2018 by Vaguery

[1709.05601] Markov Brains: A Technical Introduction

february 2018 by Vaguery

Markov Brains are a class of evolvable artificial neural networks (ANN). They differ from conventional ANNs in many aspects, but the key difference is that instead of a layered architecture, with each node performing the same function, Markov Brains are networks built from individual computational components. These computational components interact with each other, receive inputs from sensors, and control motor outputs. The function of the computational components, their connections to each other, as well as connections to sensors and motors are all subject to evolutionary optimization. Here we describe in detail how a Markov Brain works, what techniques can be used to study them, and how they can be evolved.

representation
evolutionary-algorithms
dynamical-systems
emergent-design
to-write-about
to-invite-to-speak
hey-I-know-these-folks
february 2018 by Vaguery

Metrical properties for a class of continued fractions with increasing digits - ScienceDirect

january 2018 by Vaguery

In 2002, Hartono, Kraaikamp and Schweiger introduced the Engel continued fractions (ECF), whose partial quotients are increasing. Later, Schweiger generalized it into a class of continued fractions with increasing digits and a parameter ϵ, called generalized continued fractions (GCF). In this paper, we will give some arithmetic properties of such an expansion, and show that the GCF holds similar metric properties with ECF under the condition that

. But when it comes to the condition that

, it does not.

continued-fractions
number-theory
to-understand
algorithms
dynamical-systems
to-write-about
. But when it comes to the condition that

, it does not.

january 2018 by Vaguery

[1606.05099] Invariant measures for continued fraction algorithms with finitely many digits

january 2018 by Vaguery

In this paper we consider continued fraction (CF) expansions on intervals different from [0,1]. For every x in such interval we find a CF expansion with a finite number of possible digits. Using the natural extension, the density of the invariant measure is obtained in a number of examples. In case this method does not work, a Gauss-Kuzmin-L\'evy based approximation method is used. Finally, a subfamily of the N-expansions is studied. In particular, the entropy as a function of a parameter α is estimated for N=2 and N=36. Interesting behavior can be observed from numerical results.

continued-fractions
number-theory
looking-to-see
dynamical-systems
to-write-about
january 2018 by Vaguery

[1710.05183] Inferring Mesoscale Models of Neural Computation

november 2017 by Vaguery

Recent years have seen dramatic progress in the development of techniques for measuring the activity and connectivity of large populations of neurons in the brain. However, as these techniques grow ever more powerful---allowing us to even contemplate measuring every neuron in entire brain---a new problem arises: how do we make sense of the mountains of data that these techniques produce? Here, we argue that the time is ripe for building an intermediate or "mesoscale" computational theory that can bridge between single-cell (microscale) accounts of neural function and behavioral (macroscale) accounts of animal cognition and environmental complexity. Just as digital accounts of computation in conventional computers abstract away the non-essential dynamics of the analog circuits that implementing gates and registers, so too a computational account of animal cognition can afford to abstract from the non-essential dynamics of neurons. We argue that the geometry of neural circuits is essential in explaining the computational limitations and technological innovations inherent in biological information processing. We propose a blueprint for how to employ tools from modern machine learning to automatically infer a satisfying mesoscale account of neural computation that combines functional and structural data, with an emphasis on learning and exploiting regularity and repeating motifs in neuronal circuits. Rather than suggest a specific theory, we present a new class of scientific instruments that can enable neuroscientists to design, propose, implement and test mesoscale theories of neural computation.

dynamical-systems
machine-learning
deep-learning
representation
temporal-models
rather-interesting
inference
to-write-about
november 2017 by Vaguery

Understanding LSTM Networks -- colah's blog

november 2017 by Vaguery

Humans don’t start their thinking from scratch every second. As you read this essay, you understand each word based on your understanding of previous words. You don’t throw everything away and start thinking from scratch again. Your thoughts have persistence.

Traditional neural networks can’t do this, and it seems like a major shortcoming. For example, imagine you want to classify what kind of event is happening at every point in a movie. It’s unclear how a traditional neural network could use its reasoning about previous events in the film to inform later ones.

recurrent-neural-nets
machine-learning
architecture
dynamical-systems
explainer
Traditional neural networks can’t do this, and it seems like a major shortcoming. For example, imagine you want to classify what kind of event is happening at every point in a movie. It’s unclear how a traditional neural network could use its reasoning about previous events in the film to inform later ones.

november 2017 by Vaguery

[1711.00963] The Computational Complexity of Finding Separators in Temporal Graphs

november 2017 by Vaguery

Vertex separators, that is, vertex sets whose deletion disconnects two distinguished vertices in a graph, play a pivotal role in algorithmic graph theory. For instance, the concept of tree decompositions of graphs is tightly connected to the separator concept. For many realistic models of the real world, however, it is necessary to consider graphs whose edge set changes with time. More specifically, the edges are labeled with time stamps. In the literature, these graphs are referred to as temporal graphs, temporal networks, time-varying networks, edge-scheduled networks, etc. While there is an extensive literature on separators in "static" graphs, much less is known for the temporal setting. Building on previous work (e.g., Kempe et al. [STOC '00]), for the first time we systematically investigate the (parameterized) complexity of finding separators in temporal graphs. Doing so, we discover a rich landscape of computationally (fixed-parameter) tractable and intractable cases. In particular, we shed light on the so far seemingly overlooked fact that two frequently used models of temporal separation may lead to quite significant differences in terms of computational complexity. More specifically, considering paths in temporal graphs one may distinguish between strict paths (the time stamps along a path are strictly increasing) and non-strict paths (the time stamps along a path are monotonically non-decreasing). We observe that the corresponding strict case of temporal separators leads to several computationally much easier to handle cases than the non-strict case does.

graph-theory
combinatorics
dynamical-systems
robustness
nudge-targets
heuristics
algorithms
to-write-about
november 2017 by Vaguery

[1310.1166] Flipping Edge-Labelled Triangulations

october 2017 by Vaguery

Flips in triangulations have received a lot of attention over the past decades. However, the problem of tracking where particular edges go during the flipping process has not been addressed. We examine this question by attaching unique labels to the triangulation edges. We introduce the concept of the orbit of an edge e, which is the set of all edges reachable from e via flips.

We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight Θ(nlogn) bounds for edge-labelled triangulations of n-vertex convex polygons and combinatorial triangulations, contrasting with the Θ(n) bounds in their respective unlabelled settings. The Ω(nlogn) lower bound for the convex polygon setting might be of independent interest, as it generalizes lower bounds on certain sorting models. When simultaneous flips are allowed, the upper bound for convex polygons decreases to O(log2n), although we no longer have a matching lower bound.

Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectivity of the flip graph of a spiral polygon in linear time. We also prove an upper bound of O(n2) on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter Ω(n3).

combinatorics
dynamical-systems
computational-complexity
rather-interesting
consider:looking-to-see
consider:simulation
to-write-about
to-draw
We establish the first upper and lower bounds on the diameter of the flip graph in this setting. Specifically, we prove tight Θ(nlogn) bounds for edge-labelled triangulations of n-vertex convex polygons and combinatorial triangulations, contrasting with the Θ(n) bounds in their respective unlabelled settings. The Ω(nlogn) lower bound for the convex polygon setting might be of independent interest, as it generalizes lower bounds on certain sorting models. When simultaneous flips are allowed, the upper bound for convex polygons decreases to O(log2n), although we no longer have a matching lower bound.

Moving beyond convex polygons, we show that edge-labelled triangulated polygons with a single reflex vertex can have a disconnected flip graph. This is in sharp contrast with the unlabelled case, where the flip graph is connected for any triangulated polygon. For spiral polygons, we provide a complete characterization of the orbits. This allows us to decide connectivity of the flip graph of a spiral polygon in linear time. We also prove an upper bound of O(n2) on the diameter of each connected component, which is optimal in the worst case. We conclude with an example of a non-spiral polygon whose flip graph has diameter Ω(n3).

october 2017 by Vaguery

[1208.2762] Computing by Temporal Order: Asynchronous Cellular Automata

october 2017 by Vaguery

Our concern is the behaviour of the elementary cellular automata with state set 0,1 over the cell set Z/nZ (one-dimensional finite wrap-around case), under all possible update rules (asynchronicity).

Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

cellular-automata
rather-interesting
asynchronous
collective-behavior
out-of-the-box
dynamical-systems
representation
to-write-about
Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

october 2017 by Vaguery

[1208.2762v1] Computing by Temporal Order: Asynchronous Cellular Automata

october 2017 by Vaguery

Our concern is the behaviour of the elementary cellular automata with state set 0,1 over the cell set Z/nZ (one-dimensional finite wrap-around case), under all possible update rules (asynchronicity).

Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

cellular-automata
rather-interesting
out-of-the-box
asynchronous
collective-behavior
dynamical-systems
nudge-targets
consider:looking-to-see
to-write-about
Over the torus Z/nZ (n<= 11),we will see that the ECA with Wolfram rule 57 maps any v in F_2^n to any w in F_2^n, varying the update rule.

We furthermore show that all even (element of the alternating group) bijective functions on the set F_2^n = 0,...,2^n-1, can be computed by ECA57, by iterating it a sufficient number of times with varying update rules, at least for n <= 10. We characterize the non-bijective functions computable by asynchronous rules.

october 2017 by Vaguery

New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine

october 2017 by Vaguery

Two “rare jewels” have illuminated a mysterious multidimensional object that connects a huge variety of mathematical work.

dynamical-systems
geometry
rather-interesting
mathematical-recreations
nudge-targets
consider:looking-to-see
consider:feature-discovery
october 2017 by Vaguery

[1703.07695] Selfish Cops and Adversarial Robber: Multi-Player Pursuit Evasion on Graphs

october 2017 by Vaguery

We introduce and study the game of Selfish Cops and Adversarial Robber (SCAR) which is an N-player generalization of the classic two-player cops and robbers (CR) game. We prove that SCAR has a Nash equilibrium in deterministic strategies.

game-theory
graph-theory
dynamical-systems
feature-construction
to-write-about
to-simulate
nudge-targets
consider:looking-to-see
october 2017 by Vaguery

[1404.6238] Recurrence and transience for the frog model on trees

october 2017 by Vaguery

The frog model is a growing system of random walks where a particle is added whenever a new site is visited. A longstanding open question is how often the root is visited on the infinite d-ary tree. We prove the model undergoes a phase transition, finding it recurrent for d=2 and transient for d≥5. Simulations suggest strong recurrence for d=2, weak recurrence for d=3, and transience for d≥4. Additionally, we prove a 0-1 law for all d-ary trees, and we exhibit a graph on which a 0-1 law does not hold.

To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.

probability-theory
graph-theory
random-walks
dynamical-systems
rather-interesting
to-understand
to-write-about
consider:feature-discovery
consider:classification
To prove recurrence when d=2, we construct a recursive distributional equation for the number of visits to the root in a smaller process and show the unique solution must be infinity a.s. The proof of transience when d=5 relies on computer calculations for the transition probabilities of a large Markov chain. We also include the proof for d≥6, which uses similar techniques but does not require computer assistance.

october 2017 by Vaguery

[1610.01369] Self-referential Functions

october 2017 by Vaguery

We introduce the concept of fractels for functions and discuss their analytic and algebraic properties. We also consider the representation of polynomials and analytic functions using fractels, and the consequences of these representations in numerical analysis.

fractals
algebra
representation
dynamical-systems
to-understand
define-your-terms
to-write-about
nudge
consider:fractel-type-in-Klapaucius
october 2017 by Vaguery

[1611.02218] Self-Similar Polygonal Tiling

october 2017 by Vaguery

The purpose of this paper is to give the flavor of the subject of self-similar tilings in a relatively elementary setting, and to provide a novel method for the construction of such polygonal tilings.

tiling
aperiodic-tiling
self-similarity
rather-interesting
generative-processes
dynamical-systems
to-write-about
plane-geometry
october 2017 by Vaguery

[1709.09325] Self-Similar Tilings of Fractal Blow-Ups

september 2017 by Vaguery

New tilings of certain subsets of ℝM are studied, tilings associated with fractal blow-ups of certain similitude iterated function systems (IFS). For each such IFS with attractor satisfying the open set condition, our construction produces a usually infinite family of tilings that satisfy the following properties: (1) the prototile set is finite; (2) the tilings are repetitive (quasiperiodic); (3) each family contains self-similartilings, usually infinitely many; and (4) when the IFS is rigid in an appropriate sense, the tiling has no non-trivial symmetry; in particular the tiling is non-periodic.

fractals
IFS
rather-interesting
tiling
dynamical-systems
aperiodic-tiling
representation
to-understand
to-write-about
september 2017 by Vaguery

[1709.02171] On the stability and instability of finite dynamical systems with prescribed interaction graphs

september 2017 by Vaguery

The dynamical properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding, and in the context of hat games, such as the guessing game and Winkler's hat game. The instability of an FDS is the minimum Hamming distance between a state and its image under the FDS, while the stability is the minimum of the reciprocal of the Hamming distance; they are both directly related to Winkler's hat game. In this paper, we study the value of the (in)stability of FDSs with prescribed interaction graphs. The first main contribution of this paper is the study of the maximum stability for interaction graphs with a loop on each vertex. We determine the maximum (in)stability for large enough alphabets and also prove some lower bounds for the Boolean alphabet. We also compare the maximum stability for arbitrary functions compared to monotone functions only. The second main contribution of the paper is the study of the average (in)stability of FDSs with a given interaction graph. We show that the average stability tends to zero with high alphabets, and we then investigate the average instability. In that study, we give bounds on the number of FDSs with positive instability (i.e fixed point free functions). We then conjecture that all non-acyclic graphs will have an average instability which does not tend to zero when the alphabet is large. We prove this conjecture for some classes of graphs, including cycles.

boolean-networks
cellular-automata
automata
combinatorics
graph-theory
representation
complexology
dynamical-systems
to-write
to-cartoon-about
september 2017 by Vaguery

[1502.02053] Negative refraction and tiling billiards

september 2017 by Vaguery

We introduce a new dynamical system that we call "tiling billiards," where trajectories refract through planar tilings. This system is motivated by a recent discovery of physical substances with negative indices of refraction. We investigate several special cases where the planar tiling is created by dividing the plane by lines, and we describe the results of computer experiments.

tiling
dynamical-systems
billiards
computational-geometry
rather-interesting
mathematical-recreations
to-write-about
september 2017 by Vaguery

[0801.3306] Chip-Firing and Rotor-Routing on Directed Graphs

september 2017 by Vaguery

We give a rigorous and self-contained survey of the abelian sandpile model and rotor-router model on finite directed graphs, highlighting the connections between them. We present several intriguing open problems.

sandpiles
complexology
graph-theory
dynamical-systems
feature-construction
to-write-about
nudge-targets
consider:classification
consider:feature-discovery
september 2017 by Vaguery

[1501.03584] Formation of an interface by competitive erosion

september 2017 by Vaguery

In 2006, the fourth author proposed a graph-theoretic model of interface dynamics called competitive erosion. Each vertex of the graph is occupied by a particle that can be either red or blue. New red and blue particles alternately get emitted from their respective bases and perform random walk. On encountering a particle of the opposite color they kill it and occupy its position. We prove that on the cylinder graph (the product of a path and a cycle) an interface spontaneously forms between red and blue and is maintained in a predictable position with high probability.

combinatorics
dynamical-systems
rather-interesting
to-write-about
nudge-targets
physics!
simulation
probability-theory
september 2017 by Vaguery

News on quadratic polynomials

september 2017 by Vaguery

Many problems in mathematics have remained unsolved because of missing links between mathematical disciplines, such as algebra, geometry, analysis, or number theory. Here we introduce a recently discovered result concerning quadratic polynomials, which uses a bridge between algebra and analysis. We study the iterations of quadratic polynomials, obtained by computing the value of a polynomial for a given number and feeding the outcome into the exact same polynomial again. These iterations of polynomials have interesting applications, such as in fractal theory.

mathematics
number-theory
algebra
fractals
rather-interesting
dynamical-systems
to-write-about
mathematical-recreations
september 2017 by Vaguery

[1612.06816] Sorting via chip-firing

september 2017 by Vaguery

We investigate a variant of the chip-firing process on the infinite path graph: rather than treating the chips as indistinguishable, we label them with positive integers. To fire an unstable vertex, i.e. a vertex with more than one chip, we choose any two chips at that vertex and move the lesser-labeled chip to the left and the greater-labeled chip to the right. This labeled version of the chip-firing process exhibits a remarkable confluence property, similar to but subtler than the confluence that prevails for unlabeled chip-firing: when all chips start at the origin and the number of chips is even, the chips always end up in sorted order. Our proof of sorting relies upon an independently interesting lemma concerning unlabeled chip- firing which says that stabilization preserves a natural partial order on configurations. We also discuss some extensions of this sorting phenomenon to other graphs (variants of the infinite path), to other initial configurations, and to other Cartan-Killing types.

collective-intelligence
emergence
sorting
graph-theory
chip-firing
Brueckner-networks
to-write-about
consider:simulation
combinatorics
dynamical-systems
september 2017 by Vaguery

[0904.4507] Rotor Walks and Markov Chains

september 2017 by Vaguery

The rotor walk is a derandomized version of the random walk on a graph. On successive visits to any given vertex, the walker is routed to each of the neighboring vertices in some fixed cyclic order, rather than to a random sequence of neighbors. The concept generalizes naturally to Markov chains on a countable state space. Subject to general conditions, we prove that many natural quantities associated with the rotor walk (including normalized hitting frequencies, hitting times and occupation frequencies) concentrate around their expected values for the random walk. Furthermore, the concentration is stronger than that associated with repeated runs of the random walk, with discrepancy at most C/n after n runs (for an explicit constant C), rather than c/sqrt n.

probability-theory
combinatorics
graph-theory
rather-interesting
dynamical-systems
to-write-about
random-walks
september 2017 by Vaguery

[1107.4442] Local-to-global principles for rotor walk

september 2017 by Vaguery

In rotor walk on a finite directed graph, the exits from each vertex follow a prescribed periodic sequence. Here we consider the case of rotor walk where a particle starts from a designated source vertex and continues until it hits a designated target set, at which point the walk is restarted from the source. We show that the sequence of successively hit targets, which is easily seen to be eventually periodic, is in fact periodic. We show moreover that reversing the periodic patterns of all rotor sequences causes the periodic pattern of the hitting sequence to be reversed as well. The proofs involve a new notion of equivalence of rotor configurations, and an extension of rotor walk incorporating time-reversed particles.

combinatorics
dynamical-systems
rather-interesting
to-write-about
mathematical-recreations
graph-theory
september 2017 by Vaguery

[1705.00759] Controllability of Conjunctive Boolean Networks with Application to Gene Regulation

august 2017 by Vaguery

A Boolean network is a finite state discrete time dynamical system. At each step, each variable takes a value from a binary set. The value update rule for each variable is a local function which depends only on a selected subset of variables. Boolean networks have been used in modeling gene regulatory networks. We focus in this paper on a special class of Boolean networks, namely the conjunctive Boolean networks (CBNs), whose value update rule is comprised of only logic AND operations. It is known that any trajectory of a Boolean network will enter a periodic orbit. Periodic orbits of a CBN have been completely understood. In this paper, we investigate the orbit-controllability and state-controllability of a CBN: We ask the question of how one can steer a CBN to enter any periodic orbit or to reach any final state, from any initial state. We establish necessary and sufficient conditions for a CBN to be orbit-controllable and state-controllable. Furthermore, explicit control laws are presented along the analysis.

boolean-networks
Kauffmania
engineering-design
emergent-design
rather-interesting
to-write-about
nudge-targets
consider:feature-discovery
dynamical-systems
complexology
august 2017 by Vaguery

[1708.03216] Coarsening and Aging of Lattice Polymers: Influence of Bond Fluctuations

august 2017 by Vaguery

We present results for the nonequilibrium dynamics of collapse for a model flexible homopolymer on simple cubic lattices with fixed and fluctuating bonds between the monomers. Results from our Monte Carlo simulations show that, phenomenologically, the sequence of events observed during the collapse are independent of the bond criterion. While the growth of the clusters (of monomers) at different temperatures exhibits a nonuniversal power-law behavior when the bonds are fixed, the introduction of fluctuations in the bonds by considering the existence of diagonal bonds produces a temperature independent growth, which can be described by a universal nonequilibrium finite-size scaling function with a non-universal metric factor. We also examine the related aging phenomenon, probed by a suitable two-time density-density autocorrelation function showing a simple power-law scaling with respect to the growing cluster size. Unlike the cluster-growth exponent αc, the nonequilibrium autocorrelation exponent λC governing the aging during the collapse, however, is independent of the bond type and strictly follows the bounds proposed by two of us in Phys. Rev. E 93, 032506 (2016) at all temperatures.

lattice-polymers
physics
simulation
rather-interesting
dynamical-systems
to-write-about
august 2017 by Vaguery

[1704.08997] A Case Study on the Parametric Occurrence of Multiple Steady States

august 2017 by Vaguery

We consider the problem of determining multiple steady states for positive real values in models of biological networks. Investigating the potential for these in models of the mitogen-activated protein kinases (MAPK) network has consumed considerable effort using special insights into the structure of corresponding models. Here we apply combinations of symbolic computation methods for mixed equality/inequality systems, specifically virtual substitution, lazy real triangularization and cylindrical algebraic decomposition. We determine multistationarity of an 11-dimensional MAPK network when numeric values are known for all but potentially one parameter. More precisely, our considered model has 11 equations in 11 variables and 19 parameters, 3 of which are of interest for symbolic treatment, and furthermore positivity conditions on all variables and parameters.

nonlinear-dynamics
dynamical-systems
inverse-problems
theoretical-biology
reaction-networks
to-write-about
rather-interesting
parameter-scanning
august 2017 by Vaguery

[0711.1778] Modules identification by a Dynamical Clustering algorithm based on chaotic R"ossler oscillators

may 2017 by Vaguery

A new dynamical clustering algorithm for the identification of modules in complex networks has been recently introduced \cite{BILPR}. In this paper we present a modified version of this algorithm based on a system of chaotic Roessler oscillators and we test its sensitivity on real and computer generated networks with a well known modular structure.

community-detection
dynamical-systems
coupled-oscillators
feature-construction
rather-interesting
nonlinear-dynamics
to-write-about
nudge-targets
consider:variant-overlays
may 2017 by Vaguery

[1705.00241] Dynamic interdependence and competition in multilayer networks

may 2017 by Vaguery

From critical infrastructure, to physiology and the human brain, complex systems rarely occur in isolation. Instead, the functioning of nodes in one system often promotes or suppresses the functioning of nodes in another. Despite advances in structural interdependence, modeling interdependence and other interactions between dynamic systems has proven elusive. Here we define a broadly applicable dynamic dependency link and develop a general framework for interdependent and competitive interactions between general dynamic systems. We apply our framework to studying interdependent and competitive synchronization in multi-layer oscillator networks and cooperative/competitive contagions in an epidemic model. Using a mean-field theory which we verify numerically, we find explosive transitions and rich behavior which is absent in percolation models including hysteresis, multi-stability and chaos. The framework presented here provides a powerful new way to model and understand many of the interacting complex systems which surround us.

dynamical-systems
coupled-oscillators
network-theory
rather-interesting
to-write-about
simulation
consider:simple-examples
nudge-targets
consider:control-theory
consider:feature-discovery
may 2017 by Vaguery

[1704.00565] Dynamic Planar Embeddings of Dynamic Graphs

may 2017 by Vaguery

We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices.

Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip-linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log2n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph.

Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

graph-layout
dynamical-systems
constraint-satisfaction
multiobjective-optimization
dynamic-optimization
to-write-about
consider:simple-examples
rather-interesting
Given vertices u,v, linkable(u,v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u,v) in the embedding. For non-linkable vertices u,v, we define a new query, one-flip-linkable(u,v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log2n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph.

Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

may 2017 by Vaguery

[1110.0373] An excitable electronic circuit as a sensory neuron model

may 2017 by Vaguery

An electronic circuit device, inspired on the FitzHugh-Nagumo model of neuronal excitability, was constructed and shown to operate with characteristics compatible with those of biological sensory neurons. The nonlinear dynamical model of the electronics quantitatively reproduces the experimental observations on the circuit, including the Hopf bifurcation at the onset of tonic spiking. Moreover, we have implemented an analog noise generator as a source to study the variability of the spike trains. When the circuit is in the excitable regime, coherence resonance is observed. At sufficiently low noise intensity the spike trains have Poisson statistics, as in many biological neurons. The transfer function of the stochastic spike trains has a dynamic range of 6 dB, close to experimental values for real olfactory receptor neurons.

neural-networks
neurology
biophysics
electronics
rather-interesting
simulation
emulation
to-write-about
dynamical-systems
may 2017 by Vaguery

[1409.4178] The frustrated brain: From dynamics on motifs to communities and networks

may 2017 by Vaguery

Cognitive function depends on an adaptive balance between flexible dynamics and integrative processes in distributed cortical networks. Patterns of zero-lag synchrony likely underpin numerous perceptual and cognitive functions. Synchronization fulfils integration by reducing entropy, whilst adaptive function mandates that a broad variety of stable states be readily accessible. Here, we elucidate two complementary influences on patterns of zero-lag synchrony that derive from basic properties of brain networks. First, mutually coupled pairs of neuronal subsystems -- resonance pairs -- promote stable zero-lag synchrony amongst the small motifs in which they are embedded, and whose effects can propagate along connected chains. Second, frustrated closed-loop motifs disrupt synchronous dynamics, enabling metastable configurations of zero-lag synchrony to coexist. We document these two complementary influences in small motifs and illustrate how these effects underpin stable versus metastable phase-synchronization patterns in prototypical modular networks and in large-scale cortical networks of the macaque (CoCoMac). We find that the variability of synchronization patterns depends on the inter-node time delay, increases with the network size, and is maximized for intermediate coupling strengths. We hypothesize that the dialectic influences of resonance versus frustration may form a dynamic substrate for flexible neuronal integration, an essential platform across diverse cognitive processes.

dynamical-systems
network-theory
coupled-oscillators
emergent-design
looking-to-see
systems-biology
nudge-targets
consider:robustness
consider:looking-to-see
may 2017 by Vaguery

[1304.5008] Mechanisms of Zero-Lag Synchronization in Cortical Motifs

may 2017 by Vaguery

Zero-lag synchronization between distant cortical areas has been observed in a diversity of experimental data sets and between many different regions of the brain. Several computational mechanisms have been proposed to account for such isochronous synchronization in the presence of long conduction delays: Of these, the phenomenon of "dynamical relaying" - a mechanism that relies on a specific network motif - has proven to be the most robust with respect to parameter mismatch and system noise. Surprisingly, despite a contrary belief in the community, the common driving motif is an unreliable means of establishing zero-lag synchrony. Although dynamical relaying has been validated in empirical and computational studies, the deeper dynamical mechanisms and comparison to dynamics on other motifs is lacking. By systematically comparing synchronization on a variety of small motifs, we establish that the presence of a single reciprocally connected pair - a "resonance pair" - plays a crucial role in disambiguating those motifs that foster zero-lag synchrony in the presence of conduction delays (such as dynamical relaying) from those that do not (such as the common driving triad). Remarkably, minor structural changes to the common driving motif that incorporate a reciprocal pair recover robust zero-lag synchrony. The findings are observed in computational models of spiking neurons, populations of spiking neurons and neural mass models, and arise whether the oscillatory systems are periodic, chaotic, noise-free or driven by stochastic inputs. The influence of the resonance pair is also robust to parameter mismatch and asymmetrical time delays amongst the elements of the motif. We call this manner of facilitating zero-lag synchrony resonance-induced synchronization, outline the conditions for its occurrence, and propose that it may be a general mechanism to promote zero-lag synchrony in the brain.

systems-biology
dynamical-systems
coupled-oscillators
engineering-design
emergent-design
looking-to-see
nudge-targets
consider:looking-to-see
consider:robustness
consider:reQ-like-systems
may 2017 by Vaguery

[1306.0481] Run-and-tumble in a crowded environment: persistent exclusion process for swimmers

may 2017 by Vaguery

The effect of crowding on the run-and-tumble dynamics of swimmers such as bacteria is studied using a discrete lattice model of mutually excluding particles that move with constant velocity along a direction that is randomized at a rate α. In stationary state, the system is found to break into dense clusters in which particles are trapped or stopped from moving. The characteristic size of these clusters predominantly scales as α−0.5 both in 1D and 2D. For a range of densities, due to cooperative effects, the stopping time scales as 0.851d and as 0.82d, where d is the diffusive time associated with the motion of cluster boundaries. Our findings might be helpful in understanding the early stages of biofilm formation.

active-matter
self-organization
dynamical-systems
complexology
simulation
rather-interesting
to-write-about
consider:looking-to-see
may 2017 by Vaguery

[1703.01187] Weighted Growing Simplicial Complexes

may 2017 by Vaguery

Simplicial complexes describe collaboration networks, protein interaction networks and brain networks and in general network structures in which the interactions can include more than two nodes. In real applications, often simplicial complexes are weighted. Here we propose a non-equilibrium model for weighted growing simplicial complexes. The proposed dynamics is able to generate weighted simplicial complexes with a rich interplay between weights and topology emerging not just at the level of nodes and links, but also at the level of faces of higher dimension.

network-theory
generative-models
feature-construction
dynamical-systems
simulation
parametrization
to-understand
consider:review
may 2017 by Vaguery

[adap-org/9710002] Self-Organized Criticality with Complex Scaling Exponents in the Train Model

april 2017 by Vaguery

The train model which is a variant of the Burridge-Knopoff earthquake model is investigated for a velocity-strengthening friction law. It shows self-organized criticality with complex scaling exponents. That is, the probability density function of the avalanche strength is a power law times a log-periodic function. Exact results (scaling exponent: 3/2+2πi/ln4) are found for a nonlocal cellular automaton which approximates the overdamped train model. Further the influence of random static friction is discussed.

dynamical-systems
complexology
agent-based
nudge-targets
consider:looking-to-see
to-write-about
april 2017 by Vaguery

[1110.6327] Greedy and lazy representations in negative base systems

april 2017 by Vaguery

We consider positional numeration systems with negative real base −β, where β>1, and study the extremal representations in these systems, called here the greedy and lazy representations. We give algorithms for determination of minimal and maximal (−β)-representation with respect to the alternate order. We also show that both extremal representations can be obtained as representations in the positive base β2 and a non-integer alphabet. This enables us to characterize digit sequences admissible as greedy and lazy (−β)-representation. Such a characterization allows us to study the set of uniquely representable numbers. In case that β is the golden ratio and the Tribonacci constant, we give the characterization of digit sequences admissible as greedy and lazy (−β)-representation using a set of forbidden strings.

number-theory
representation
rather-interesting
dynamical-systems
nudge-targets
consider:looking-to-see
to-write-about
april 2017 by Vaguery

[1605.03546] ARRIVAL: A zero-player graph game in NP $cap$ coNP

april 2017 by Vaguery

Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a special nature: every time the train traverses a switch, the switch will change its position immediately afterwards. Hence, the next time the train traverses the same switch, the other direction will be taken, so that directions alternate with each traversal of the switch. Given a network with origin and destination, what is the complexity of deciding whether the train, starting at the origin, will eventually reach the destination? It is easy to see that this problem can be solved in exponential time, but we are not aware of any polynomial-time method. In this short paper, we prove that the problem is in NP ∩ coNP. This raises the question whether we have just failed to find a (simple) polynomial-time solution, or whether the complexity status is more subtle, as for some other well-known (two-player) graph games.

graph-theory
dynamical-systems
proof
mathematical-recreations
feature-construction
nudge-targets
april 2017 by Vaguery

[0712.3736] A dynamical system using the Voronoi tessellation

april 2017 by Vaguery

We introduce a dynamical system based on the vertices of Voronoi tessellations. This dynamical system acts on finite or discrete point sets in the plane, taking a point set to the vertex set of its Voronoi tessellation. We explore the behavior of this system for small point sets, then prove a general result quantifying the growth of the sizes of the point sets under iteration. We conclude by giving the most interesting open problems.

computational-geometry
tiling
rather-interesting
dynamical-systems
rewriting-systems
to-understand
april 2017 by Vaguery

[1703.10862] Edit Transactions: Dynamically Scoped Change Sets for Controlled Updates in Live Programming

april 2017 by Vaguery

Live programming environments enable programmers to edit a running program and obtain immediate feedback on each individual change. The liveness quality is valued by programmers to help work in small steps and continuously add or correct small functionality while maintaining the impression of a direct connection between each edit and its manifestation at run-time. Such immediacy may conflict with the desire to perform a combined set of intermediate steps, such as a refactoring, without immediately taking effect after each individual edit. This becomes important when an incomplete sequence of small-scale changes can easily break the running program. State-of-the-art solutions focus on retroactive recovery mechanisms, such as debugging or version control. In contrast, we propose a proactive approach: Multiple individual changes to the program are collected in an Edit Transaction, which can be made effective if deemed complete. Upon activation, the combined steps become visible together. Edit Transactions are capable of dynamic scoping, allowing a set of changes to be tested in isolation before being extended to the running application. This enables a live programming workflow with full control over change granularity, immediate feedback on tests, delayed effect on the running application, and coarse-grained undos. We present an implementation of Edit Transactions along with Edit-Transaction-aware tools in Squeak/Smalltalk. We asses this implementation by conducting a case study with and without the new tool support, comparing programming activities, errors, and detours for implementing new functionality in a running simulation. We conclude that workflows using Edit Transactions have the potential to increase confidence in a change, reduce potential for run-time errors, and eventually make live programming more predictable and engaging.

software-engineering
programming
dynamical-systems
representation
rather-interesting
to-write-about
consider:open-systems
consider:simulations
april 2017 by Vaguery

[cond-mat/0203436] Entropy estimation of symbol sequences

april 2017 by Vaguery

We discuss algorithms for estimating the Shannon entropy h of finite symbol sequences with long range correlations. In particular, we consider algorithms which estimate h from the code lengths produced by some compression algorithm. Our interest is in describing their convergence with sequence length, assuming no limits for the space and time complexities of the compression algorithms. A scaling law is proposed for extrapolation from finite sample lengths. This is applied to sequences of dynamical systems in non-trivial chaotic regimes, a 1-D cellular automaton, and to written English texts.

statistics
information-theory
probability-theory
models
dynamical-systems
nudge-targets
consider:looking-to-see
consider:representation
april 2017 by Vaguery

[1701.06790] Parallel Graph Rewriting with Overlapping Rules

april 2017 by Vaguery

We tackle the problem of simultaneous transformations of networks represented as graphs. Roughly speaking, one may distinguish two kinds of simultaneous or parallel rewrite relations over complex structures such as graphs: (i) those which transform disjoint subgraphs in parallel and hence can be simulated by successive mere sequential and local transformations and (ii) those which transform overlapping subgraphs simultaneously. In the latter situations, parallel transformations cannot be simulated in general by means of successive local rewrite steps. We investigate this last problem in the framework of overlapping graph transformation systems. As parallel transformation of a graph does not produce a graph in general, we propose first some sufficient conditions that ensure the closure of graphs by parallel rewrite relations. Then we mainly introduce and discuss two parallel rewrite relations over graphs. One relation is functional and thus deterministic, the other one is not functional for which we propose sufficient conditions which ensure its confluence.

rewriting-systems
graph-theory
generative-models
representation
dynamical-systems
to-write-about
nudge-targets
consider:looking-to-see
consider:representation
algorithms
april 2017 by Vaguery

[nlin/0311006] Complex dynamics in simple systems with seasonal parameter oscillations

april 2017 by Vaguery

We study systems with periodically oscillating parameters that can give way to complex periodic or non periodic orbits. Performing the long time limit, we can define ergodic averages such as Lyapunov exponents, where a negative maximal Lyapunov exponent corresponds to a stable periodic orbit. By this, extremely complicated periodic orbits composed of contracting and expanding phases appear in a natural way. Employing the technique of ϵ-uncertain points, we find that values of the control parameters supporting such periodic motion are densely embedded in a set of values for which the motion is chaotic. When a tiny amount of noise is coupled to the system, dynamics with positive and with negative non-trivial Lyapunov exponents are indistinguishable. We discuss two physical systems, an oscillatory flow inside a duct and a dripping faucet with variable water supply, where such a mechanism seems to be responsible for a complicated alternation of laminar and turbulent phases.

nonlinear-dynamics
dynamical-systems
rather-interesting
feature-extraction
emergent-design
to-write-about
april 2017 by Vaguery

[1304.5109] Kadanoff Sand Pile Model. Avalanche Structure and Wave Shape

april 2017 by Vaguery

Sand pile models are dynamical systems describing the evolution from N stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a fixed configuration from which no rule can be applied. Physicists L. Kadanoff {\em et al} inspire KSPM, extending the well known {\em Sand Pile Model} (SPM). In KSPM(D), we start from a pile of N stacked grains and apply the rule: D−1 grains can fall from column i onto columns i+1,i+2,…,i+D−1 if the difference of height between columns i and i+1 is greater or equal to D. Toward the study of fixed points (stable configurations on which no grain can move) obtained from N stacked grains, we propose an iterative study of KSPM evolution consisting in the repeated addition of one grain on a heap of sand, triggering an avalanche at each iteration. We develop a formal background for the study of avalanches, resumed in a finite state word transducer, and explain how this transducer may be used to predict the form of fixed points. Further precise developments provide a plain formula for fixed points of KSPM(3), showing the emergence of a wavy shape.

sandpile
self-organization
complexology
dynamical-systems
to-write-about
consider:simulation
nudge-targets
consider:extensive-properties
april 2017 by Vaguery

[1108.3620] Uniformly balanced words with linear complexity and prescribed letter frequencies

april 2017 by Vaguery

We consider the following problem. Let us fix a finite alphabet A; for any given d-uple of letter frequencies, how to construct an infinite word u over the alphabet A satisfying the following conditions: u has linear complexity function, u is uniformly balanced, the letter frequencies in u are given by the given d-uple. This paper investigates a construction method for such words based on the use of mixed multidimensional continued fraction algorithms.

strings
rewriting-systems
dynamical-systems
to-understand
fractals
to-write-about
open-questions
nudge-targets
consider:performance-measures
april 2017 by Vaguery

[1108.5574] Substitutive Arnoux-Rauzy sequences have pure discrete spectrum

april 2017 by Vaguery

We prove that the symbolic dynamical system generated by a purely substitutive Arnoux-Rauzy sequence is measurably conjugate to a toral translation. The proof is based on an explicit construction of a fundamental domain with fractal boundary (a Rauzy fractal) for this toral translation.

dynamical-systems
discrete-mathematics
rewriting-systems
to-understand
strings
representation
to-write-about
april 2017 by Vaguery

[1212.5106] Balance properties of Arnoux-Rauzy words

april 2017 by Vaguery

The paper deals with balances and imbalances in Arnoux-Rauzy words. We provide sufficient conditions for C-balancedness, but our results indicate that even a characterization of 2-balanced Arnoux-Rauzy words on a 3-letter alphabet is not immediate.

strings
formal-languages
to-understand
dynamical-systems
substitution-systems
rewriting-systems
nudge-targets
consider:looking-to-see
consider:feature-discovery
april 2017 by Vaguery

[1311.6763] Outer Billiards on Regular Polygons

march 2017 by Vaguery

In 1973, J. Moser proposed that his Twist Theorem could be used to show that orbits of the outer billiards map on a sufficiently smooth closed curve were always bounded. Five years later Moser asked the same question for a convex polygon. In 1987 F. Vivaldi and A. Shaidenko showed that all orbits for a regular polygon must be bounded. R. Schwartz recently showed that a quadrilateral known as a Penrose Kite has unbounded orbits and he proposed that 'most' convex polygons support unbounded orbits.

Except for a few special cases, very little is known about the dynamics of the outer billiards map on regular polygons. In this paper we present a unified approach to the analysis of regular polygons - using the canonical 'resonances' which are shared by all regular N-gons. In the case of the regular pentagon and regular octagon these resonances exist on all scales and the fractal structure is well documented, but these are the only non-trivial cases that have been analyzed. We present a partial analysis of the regular heptagon, but the limiting structure is poorly understood and this does not bode well for the remaining regular polygons. The minimal polynomial for the vertices of a regular N-gon has degree Phi(N)/2 where Phi is the Euler totient function, so N = 5, 7 and 11 are respectively quadratic, cubic and quintic. In the words of R. Schwartz, "A case such as N = 11 seems beyond the reach of current technology."

Some of the graphics have embedded high-resolution versions so this file is about 39Mb in size. This file and a smaller version can be downloaded at dynamicsofpolygons.org. Just click on PDFs.

This paper is dedicated to the memory of Eugene Gutkin (1946-2013) who made fundamental contributions to both inner and outer billiards.

billiards
dynamical-systems
chaos
rather-interesting
to-write-about
visualization
Except for a few special cases, very little is known about the dynamics of the outer billiards map on regular polygons. In this paper we present a unified approach to the analysis of regular polygons - using the canonical 'resonances' which are shared by all regular N-gons. In the case of the regular pentagon and regular octagon these resonances exist on all scales and the fractal structure is well documented, but these are the only non-trivial cases that have been analyzed. We present a partial analysis of the regular heptagon, but the limiting structure is poorly understood and this does not bode well for the remaining regular polygons. The minimal polynomial for the vertices of a regular N-gon has degree Phi(N)/2 where Phi is the Euler totient function, so N = 5, 7 and 11 are respectively quadratic, cubic and quintic. In the words of R. Schwartz, "A case such as N = 11 seems beyond the reach of current technology."

Some of the graphics have embedded high-resolution versions so this file is about 39Mb in size. This file and a smaller version can be downloaded at dynamicsofpolygons.org. Just click on PDFs.

This paper is dedicated to the memory of Eugene Gutkin (1946-2013) who made fundamental contributions to both inner and outer billiards.

march 2017 by Vaguery

[1701.06148] Fast and slow domino effects in transient network dynamics

march 2017 by Vaguery

It is well known that the addition of noise to a multistable dynamical system can induce random transitions from one stable state to another. For low noise, the times between transitions have an exponential tail and Kramers' escape time gives an expression for the mean escape time in the asymptotic limit. If a number of multistable systems are coupled into a network structure, a transition at one site may change the transition properties at other sites. We study the case of escape from a "quiescent" attractor to an "active" attractor in cases where transitions back can be ignored. There are qualitatively different regimes of transition, depending on coupling strength. For "weak coupling" the transition rates are simply modified but the transitions remain stochastic. For "strong coupling" transitions happen approximately in synchrony - we call this a "fast domino" effect, while in an "intermediate coupling" some transitions may happen inexorably but with some delay - we call this a "slow domino" effect. For some examples we characterise these regimes in the low noise limit in terms of bifurcations of the potential landscape of the coupled system.

dynamical-systems
stochastic-resonance
stochastic-systems
nonlinear-dynamics
rather-interesting
to-write-about
march 2017 by Vaguery

[1606.05496] Majority dynamics with one nonconformist

february 2017 by Vaguery

We consider a system in which a group of agents represented by the vertices of a graph synchronously update their opinion based on that of their neighbours. If each agent adopts a positive opinion if and only if that opinion is sufficiently popular among his neighbours, the system will eventually settle into a fixed state or alternate between two states. If one agent acts in a different way, other periods may arise. We show that only a small number of periods may arise if natural restrictions are placed either on the neighbourhood structure or on the way in which the nonconforming agent may act; without either of these restrictions any period is possible.

agent-based
complexology
feature-construction
graph-theory
dynamical-systems
to-write-about
to-do
nudge-targets
consider:classification
consider:prediction
consider:feature-discovery
february 2017 by Vaguery

**related tags**

Copy this bookmark: