Causal Dynamics of Graphs and Discrete Manifolds

SCW'14 invited speaker, Pablo Arrighi

We formalize the intuitive idea of a discrete manifold which evolves in time, subject to two natural constraints: the evolution does not propagate information too fast; and it acts everywhere the same.

The talk will proceed as follows.

First, we explain earlier results on Causal Graph Dynamics, a model which generalizes Cellular Automata to time-varying, bounded degree graphs.

Second, we explain how to a subclass of these bounded degree graphs can be interpreted as being the dual of a simplicial complex, where attention must be paid to discrepancies between geometrical distance and graph distance, as well as the appearance of torsion.

Third, we provide provide an equivalent to the notion of Pachner moves upon these graphs, so that we are able to characterize homeomorphism in a purely combinatorial manner, and hence the notion of combinatorial manifold.

Last, we report our progress toward proving that the local rules which map combinatorial manifolds to combinatorial manifolds are enumerable.

Gilles Dowek, Simon Martiel, Vincent Nesme