Quadratic Dynamical Systems

The main purpose of this talk will be to promote the study of computational aspects, primarily the convergence rate, of non-linear dynamical systems from a combinatorial perspective.

Many natural phenomenon can be described by dynamical systems in Euclidean space. In such a description, there is a fixed set of types, and a point in the system (usually referred to as a 'state' or a 'population') specifies how many elements of each type exist at a given time instant. The system evolves under a fixed map f, which attempts to capture the underlying phenomenon. A couple of examples follow that help illustrate the applicability of these systems.

In Physics, the system might describe the behaviour of gas molecules in a container. In this case, the types correspond to velocity values, and the state p specifies how many molecules of each type there are at a certain point in time. The map f should include the Newtonian laws so as to produce from each state p a new state f(p) in the next time step, under some assumption about the spatial distribution of the molecules.

Again, in Biology, the types may correspond to the genotypes of some species. A population p is then simply the number of individuals of each type in the current generation. The map f determines the population in the next generation according to a fixed set of rules that includes the genetic outcome of mating, the survival capacity of different types, random mutations etc. Thus, such systems also provide an appropriate framework for the study of genetic algorithms in combinatorial optimization.

In this talk, we will first identify the class of symmetric quadratic dynamical systems. Then, we will go on to prove several fundamental general properties of these systems, including a characterization of the set of fixed points to which the system converges.

This talk will be based on the preliminary version of a paper titled "Quadratic Dynamical Systems" authored by Yuri Rabinovich, Alistair Sinclair and Avi Wigderson.