Entre aléa et déterminisme : lumière sur quelques structures discrètes

This habilitation thesis presents different works on discrete structures defined on regular lattices. These works are at the interface between probability, combinatorics, and discrete dynamical systems. They are also related to questions from statistical physics and mathematical computer science. The three chapters that make up this thesis involve various objects, studied with the common ambition of shedding new light on thestructures that shape them, at the frontier between randomness and determinism.In the first chapter, we focus on paths defined on regular lattices, first in the context of Eulerian percolation (Bernoulli percolation on the edges of the grid, conditioned on all vertices being of even degree), then by studying paths confined in a triangular domain, and by relating them to Motzkin paths of bounded amplitude.The second chapter is devoted to the effects of small perturbations on the dynamics of a cellular automaton, or on tilings, for which we are interested in the existence of efficient self-stabilization mechanisms.In the third chapter, we start by studying stationary space-time diagrams of some probabilistic cellular automata with memory 2, which provide random fields with a particularly remarkable structure. Then we construct deterministic automatic sequences, in one dimension and in higher dimensions, with pseudorandom properties.Ce mémoire d’habilitation présente différents travaux portant sur des structures discrètes définies sur des réseaux réguliers. Ces travaux se situent à l’interface entre les probabilités, la combinatoire, et les systèmes dynamiques discrets. Ils sont également liés à des questions issues de la physique statistique et de l’informatique mathématique.Les trois chapitres qui composent ce mémoire font intervenir des objets variés, étudiés avec l’ambition commune d’apporter un nouvel éclairage sur les structures qui les façonnent, à la frontière entre aléa et déterminisme.Dans le premier chapitre, nous nous intéressons à des chemins définis sur des réseaux réguliers, d’abord dans le contexte de la percolation eulérienne (percolation de Bernoulli sur les arêtes de la grille, conditionnée à ce que tous les sommets soient de degré pair), puis en étudiant des chemins confinés dans un domaine triangulaire, et en les mettant en relation avec des chemins de Motzkin d’amplitude bornée.Le second chapitre est consacré aux effets que peuvent avoir de petites perturbations dans la dynamique d’un automate cellulaire, ou encore sur des pavages, pour lesquels nous nous intéressons à l’existence de mécanismes d’auto-stabilisation efficaces.Dans le troisième chapitre, nous commençons par étudier des diagrammes espacetemps stationnaires de certains automates cellulaires probabilistes à mémoire 2, qui fournissent des champs aléatoires ayant une structure particulièrement remarquable. Puis nous construisons des suites déterministes automatiques, unidimensionnelles et multidimensionnelles, ayant des propriétés pseudo-aléatoires