ALEA-Network Workshop

16-18 November 2015

The Alea-Network workshop aims at bringing together researchers, Ph.D. students and young postdoc researchers around the topics of the ALEA-Network.

Any researcher interested in participating the workshop is welcome to register to attend and every participant should feel free to propose a talk [before October the 15th] . There is no registration fee. However, note that we have no funding for participants' travel and accomodation. Only lunches and coffee breaks will be provided.

If you want to participate, please email the organiser Jean-François Marckert mentioning your full name, your institution and a link to your webpage, and if you want to give a talk, mention it in your message.

Lecture 1 : An introduction to ribbon graphs

Iain Moffatt University of London

Consider a graph drawn on a surface. Take a small neighbourhood of it. What results is a topological graph'' with 2-dimensional discs as vertices and 2-dimensional ribbons as edges. This object is a ribbon graph. While ribbon graphs describe exactly cellularly embedded graphs, and so are the fundamental objects of study in topological graph theory, most recent advances on ribbon graphs have developed from applications to graph polynomials and knot theory, so ribbon graph theory has developed a different flavour to classical topological graph theory.

In this series of talks I will give an introduction to this recent theory of ribbon graphs. I will cover a range of topics such as minors, duals, knots, and matroids. Throughout I will emphasise how our ribbon graph constructions and results arise as natural topological counterparts of classical graph theoretic constructions and results.

I will keep these talks as accessible as possible, with basic graph theory and some geometric intuition as the only prerequisites.

Lecture 2 : Percolation games, branching processes, and probabilistic cellular automata

James Martin University of Oxford

I will survey "percolation games" in various contexts and discuss a variety of probabilistic objects connected with them.

Let $G$ be a graph (directed or undirected), and let $v$ be some vertex. Consider the following two-player combinatorial game. A token starts at $v$. The players take turns to move, and each move of the game consists of moving the token along an edge of the graph, to a vertex that has not yet been visited. A player who is unable to move loses the game.

If the graph is finite, then one player or the other must have a winning strategy. In the case of an infinite graph, it may be that, with optimal play, the game continues for ever.

I'll discuss these games played on various types of random graph:

(i) random directed lattices, for instance $\mathbb{Z}^d$ with each vertex deleted independently with some probability $p$. There are connections to questions of ergodicity of probabilistic cellular automata, to the hard-core model in statistical mechanics, and to the enumeration of lattice animals. See http://arxiv.org/abs/1503.05614 for details (joint work with Alexander Holroyd and Irène Marovici).

(ii) Trees of Galton-Watson branching processes. I will discuss various types of phase transition arising in branching processes, and related ideas such as endogeny of a recursive distributional equation; there are links to the emergence of the giant component and the $k$-core in sparse random graphs.

(iii) random undirected lattices, again for example $\mathbb{Z}^d$ with vertices deleted independently with probability $p$. I'll talk about connections to problems involving maximum matchings and independent sets, and also bootstrap percolation. See http://arxiv.org/abs/1505.07485 (joint work with Riddhipratim Basu, Alexander Holroyd and Johan Wästlund).

Talks

Emeric Gioan , LIRMM, Université de Montpellier 2

A Survey on The Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids

The active bijection maps any directed graph, resp. signed hyperplane arrangement or oriented matroid, defined on a linearly ordered edge set, resp. ground set, onto one of its spanning trees, resp. bases.

It relates all spanning trees to all orientations of a graph, all bases to all reorientations of an hyperplane arrangement or, more generally, an oriented matroid. It preserves activities: for bases in the sense of Tutte, for orientations in the sense of Las Vergnas, yielding a bijective interpretation of the equality of two expressions of the Tutte polynomial. It preserves also some active partitions associated with orientations and bases. It can be mathematically defined in a short way, and can be built, characterized, particularized, or refined in several ways.

Notably, we get a bijection between bounded regions (bipolar orientations in the case of a graph) and bases with internal activity one and external activity zero, which can be seen as an advanced refinement of real (pseudo)linear programming. We get a bijection between classes of reorientations and bases, using a decomposition into bounded regions of minors of the primal and the dual, which also has a counterpart for decomposing matroid bases, and yields an expression of the Tutte polynomial using only beta invariants of minors.

We also get activity preserving bijections between all reorientations and all subsets (related to a four-variable expression of the Tutte polynomial), between regions and no-broken-circuit subsets (acyclic case), between reorientations with fixed orientations for smallest elements of positive circuits/cocircuits (directed cycles/cocycles) and bases (spanning trees), between increasing trees and permutations (complete graph case), et cetera.

It is the subject of a series of paper, joint with Michel Las Vergnas.

Irène Marcovici Institut Elie Cartan de Lorraine, Université de Lorraine

Ergodicity of probabilistic cellular automata: some tools and results

A probabilistic cellular automaton (PCA) is said to be ergodic if it "forgets" its initial condition, meaning that it has a unique and attractive invariant measure. A variety of tools have been developed to study the ergodicity of PCA. But most of them only allow to handle PCA for which the transition probability to any state given any neighbourhood states is large enough. For PCA having some transitions close to being deterministic, proving the ergodicity is often very difficult, even in cases where it appears clear from heuristics or simulations. I will recall the notion of envelope PCA and the coupling method, and present a non-trivial example of its use for some PCA having deterministic components, in link with a percolation game presented by J. Martin.

Then, I will focus on the ergodicity of some PCA that are random perturbations of deterministic CA having specific dynamical properties, such as nilpotence or permutivity (work in progress with M. Sablik and S. Taati).

Wenjie Fang LIAFA, Université Paris 7 + LaBRI, Université de Bordeaux

Bijective link between generalized Tamari intervals and non-separable planar maps

Let $v$ be an arbitrary path made of north and east steps. The lattice $Tam(v)$, based on all paths weakly above the path v sharing the same endpoints as $v$, was introduced by Préville-Ratelle and Viennot(2014) and corresponds to the usual Tamari lattice in the case $v=(NE)^n$. They also show that $Tam(v)$ is isomorphic to the dual of $Tam(\overleftarrow{v})$, where $\overleftarrow{v}$ is a mirror image of $v$ in some sense. We discover a bijection between intervals in $Tam(v)$ and non-separable planar maps. As a consequence, we show that the number of intervals in $Tam(v)$ over all $v$ of length $n$ is $\frac{2 (3n+3)!}{(n+2)! (2n+3)!}$. This formula was obtained by Tutte(1963) for non-separable planar maps. We also show that the isomorphism between $Tam(v)$ and the dual of $Tam(\overleftarrow{v})$ is equivalent to the duality of planar maps under our bijection.

Pierre-Yves Louis Laboratoire de Mathématiques, Poitiers

Through mean field interacting systems of reinforced stochastic processes

We present different asymptotics results for finite systems of interacting stochastic dynamics. Each individual's dynamics consists in a two colours urn with a Polya reinforcement scheme: each urn's reinforcement depends both on the urn's content and on the average content of all urns (mean-field). Urn's states are updated simultaneously. This system can be considered as a generalised PCA with [0,1] as alphabet. This is an ongoing joint work with I. Crimaldi., P. Dai Pra, and I. Minelli.

Program

The workshop starts the 16th of November at 9:00, and ends the 18th of November at 12:00.

Participants

Jean-Christophe Aval , LaBRI, Bordeaux

Nicolas Bonichon , LaBRI, Bordeaux

Yvan Le Borgne , LaBRI, Bordeaux

Mireille Bousquet-Mélou , LaBRI, Bordeaux

Sylvain Carrozza, LaBRI,Bordeaux

Philippe Chassaing, Institut Elie Cartan, Nancy

Brigitte Chauvin , LMV, Université de Versailles St Quentin en Yvelines

Linxiao Chen, département de mathématiques, Université de Paris-Sud

Bruno Courcell , LaBRI, Bordeaux

Henry Derycke, LaBRI, Bordeaux

Paul Dorbec , LaBRI, Bordeaux

Wenjie Fang , LIAFA, Université Paris 7 + LaBRI, Université de Bordeaux

Emeric Gioan , LIRMM, Montpellier 2

Thomas Krajewski, CPT, Marseille

Olivier Hénard LMO, Paris Sud

Patxi Laborde Zubieta, LaBRI, Bordeaux

Pierre-Yves Louis , Laboratoire de Mathématiques, Poitiers

Jean-François Marckert , LaBRI, Bordeaux

Irène Marcovici , IECN, Nancy

James Martin , Oxford

Iain Moffatt, University of London

Michèle Soria LIP6, Paris 6