Vaguery + dynamical-systems   207

 « earlier
[1808.07409] The domino shuffling height process and its hydrodynamic limit
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
2 days ago by Vaguery
[1804.02515] Periodic ellipsoidal billiard trajectories and extremal polynomials
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
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
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
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
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
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
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
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
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
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
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
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
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
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!
9 weeks ago by Vaguery
[1612.09295] First Families of Regular Polygons and their Mutations
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
9 weeks ago by Vaguery
[1704.01166] Regenerative random permutations of integers
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
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
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...
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
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
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
february 2019 by Vaguery
[1710.04400] Information reduction in a reverberatory neuronal network through convergence to complex oscillatory firing patterns
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
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
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
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
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
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
june 2018 by Vaguery
The meaning of model equivalence: Network models, latent variables, and the theoretical space in between | Psych Networks
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
april 2018 by Vaguery
[1803.09574] Long short-term memory and Learning-to-learn in networks of spiking neurons
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
april 2018 by Vaguery
[1706.05621] Double jump phase transition in a random soliton cellular automaton
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
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
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
january 2018 by Vaguery
[1606.05099] Invariant measures for continued fraction algorithms with finitely many digits
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.
january 2018 by Vaguery
[1710.05183] Inferring Mesoscale Models of Neural Computation
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
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
november 2017 by Vaguery
[1711.00963] The Computational Complexity of Finding Separators in Temporal Graphs
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
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
october 2017 by Vaguery
[1208.2762] Computing by Temporal Order: Asynchronous Cellular Automata
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
october 2017 by Vaguery
[1208.2762v1] Computing by Temporal Order: Asynchronous Cellular Automata
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
october 2017 by Vaguery
New Shapes Solve Infinite Pool-Table Problem | Quanta Magazine
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
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
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
october 2017 by Vaguery
[1610.01369] Self-referential Functions
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
may 2017 by Vaguery
[1110.0373] An excitable electronic circuit as a sensory neuron model
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
march 2017 by Vaguery
[1701.06148] Fast and slow domino effects in transient network dynamics
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
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
per page:    204080120160

Copy this bookmark:

description:

tags: