In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation is one of the simplest cellular automata. The most widely studied model is the so-called r-neighbour bootstrap percolation, in which we consider the spread of infection on a graph G according to the following deterministic rule: infected vertices of G remain infected forever and in successive rounds healthy vertices with at least r already infected neighbours become infected. Percolation is said to occur if eventually every vertex is infected. In Chapter 1 we consider a particular extremal problem in 2-neighbour bootstrap percolation on the n \times n square grid. We show that the maximum time an infection process started from an initially infected set of size n can take to infect the entire vertex set is equal to the integer nearest to (5n^2-2n)/8. In Chapter 2 we relax the condition on the size of the initially infected sets and show that the maximum time for sets of arbitrary size is 13n^2/18+O(n). In Chapter 3 we consider a similar problem, namely the maximum percolation time for 2-neighbour bootstrap percolation on the hypercube. We give an exact answer to this question showing that this time is \lfloor n^2/3 \rfloor. In Chapter 4 we consider the following probabilistic problem in bootstrap percolation: let T be an infinite tree with branching number \br(T) = b. Initially, infect every vertex of T independently with probability p > 0. Given r, define the critical probability, p_c(T,r), to be the value of p at which percolation becomes likely to occur. Answering a problem posed by Balogh, Peres and Pete, we show that if b \geq r then the value of b itself does not yield any non-trivial lower bound on p_c(T,r). In other words, for any \varepsilon > 0 there exists a tree T with branching number \br(T) = b and critical probability p_c(T,r) < \varepsilon. However, in Chapter 5 we prove that this is false if we limit ourselves to the well-studied family of Galton--Watson trees. We show that for every r \geq 2 there exists a constant c_r>0 such that if T is a Galton--Watson tree with branching number \br(T) = b \geq r then \[ p_c(T,r) > \frac{c_r}{b} e^{-\frac{b}{r-1}}. \] We also show that this bound is sharp up to a factor of O(b) by describing an explicit family of Galton--Watson trees with critical probability bounded from above by C_r e^{-\frac{b}{r-1}} for some constant C_r>0.

No description available.

Le modèle du tas de sable est un modèle de diffusion discret et isotrope introduit par les physiciens Bak, Tang et Wiesenfeld comme illustration de la criticalité auto-organisée. Pour tout graphe, souvent supposé fini, Dhar a formalisé de nombreuses propriétés simplifiant son analyse. Cette thèse propose des études de ce modèle sur la grille bidimensionnelle usuelle et certains de ses sous-graphes également infinis que sont les bandes bi-infinies de hauteur finie. Des approximations du comportement de la pile de sable peuvent se rapprocher de certains modèles de bootstrap percolation avec un support de stabilisation rectangulaire. Les lois sur son demi-périmètre peuvent se décrire à l’aide de statistiques sur les permutations. Un sous-produit de ce travail fait apparaître une différence de deux séries génératrices comptant des permutations selon deux statistiques mahoniennes classiques dont est extrait un polynôme à coefficients entiers et surtout positifs. La suite de cette thèse revisite dans le cadre de ces graphes infinis, des structures jusque-là bien définies uniquement dans le cas des graphes finis, notamment la récurrence. Dans le modèle sur une bande de hauteur finie H, l’existence donnée par Járai et Lyons d’automates finis reconnaissant les configurations récurrentes lues colonne par colonne est étendu par une construction explicite d’automates avec un nombre moindre d’états, se rapprochant de la conjecture de Gamlin. Dans une seconde approche, l’étude se concentre sur les configurations sur la grille entière qui sont périodiques dans les deux directions. Le puits, un sommet du graphe garantissant la terminaison de la stabilisation, est placé à l’infini dans une direction de pente rationnelle. Ceci permet à la fois de préserver la bipériodicité et de proposer une forme affaiblie du critère de Dhar caractérisant ainsi par un algorithme effectif les configurations récurrentes. Ces configurations récurrentes bipériodiques sont des candidates naturelles pour être les éléments de sous-groupes finis de l’éventuel groupe du tas de sable sur la grille. Des éléments de construction de cette loi de groupe donnent expérimentalement quelques sous-groupes finis. / The sandpile model is a discrete model for diffusion of grains on a graph introduced by physicists Bak, Tang and Wiesenfeld as an illustration for self-organised criticality. For any finite graph, Dhar identified many of its numerous structures which simplify its analysis. This thesis focus on the usual square lattice and its subgraphs which are strips of height H, both notions of infinite graphs. Approximations on the behaviour of the stabilisation of a large stack of grains at the origin of the square lattice lead to some random distribution of grains, which stabilisation is connected to some models of bootstrap percolation where modified vertices by this stabilisation forms a rectangle. The laws of the half-perimeter of this rectangle are described by statistics on permutations. As a byproduct, the difference between the generating functions over some permutations of two classical mahonian statistics on permutations appears to mainly be a polynomial with coefficients which are integers and especially positive. Then, this thesis visits in the case of the studied infinite graphs some well-defined structures on finite graphs, in particular the recurrence. In the model on an horizontal strip of height H, we extend the existence of finite automata recognizing recurrent configurations read column by column presented by Járai and Lyons to new automata with significantly less states and these numbers are closer to a conjecture due to Gamlin. An implementation leads to explicit automata for heights 3 and 4 while up to now only the case 2 was obtained by hand. In a second approach, we consider the configurations on the twodimensional square lattice which are periodic in two directions. We suggest to place the sink ensuring that the stabilisation ends at infinity in a direction of rational slope which allows to preserve biperiodicity and a weaker form of Dhar criterion for recurrent configurations. Hence we obtain an effective algorithm defining recurrent configurations among the biperiodic and stable configurations. These biperiodic and recurrent configurations are natural candidates for being the elements of finite subgroups of the hypothetical group on configurations of the sandpile model on the square lattice. We discuss some notions allowing the definition of the law of such a group and experimentally provide some finite subgroups.

In this dissertation we solve several combinatorial problems in different areas of mathematics: automata theory, combinatorics of partially ordered sets and extremal combinatorics. Firstly, we focus on some new automata that do not seem to have occurred much in the literature, that of solvability of mazes. For our model, a maze is a countable strongly connected digraph together with a proper colouring of its edges (without two edges leaving a vertex getting the same colour) and two special vertices: the origin and the destination. A pointer or robot starts in the origin of a maze and moves naturally between its vertices, according to a sequence of specific instructions from the set of all colours; if the robot is at a vertex for which there is no out-edge of the colour indicated by the instruction, it remains at that vertex and proceeds to execute the next instruction in the sequence. We call such a finite or infinite sequence of instructions an algorithm. In particular, one of the most interesting and very natural sets of mazes occurs when our maze is the square lattice Z2 as a graph with some of its edges removed. Obviously, we need to require that the origin and the destination vertices are in the same connected component and it is very natural to take the four instructions to be the cardinal directions. In this set-up, we make progress towards a beautiful problem posed by Leader and Spink in 2011 which asks whether there is an algorithm which solves the set of all such mazes. Next, we address a problem regarding symmetric chain decompositions of posets. We ask if there exists a symmetric chain decomposition of a 2 × 2 × ... × 2 × n cuboid (k 2’s) such that no chain has a subchain of the form (a1,...,ak,0) ≺ ... ≺ (a1,...,ak,n−1)? We show this is true precisely when k≥5 and n≥3. Thisquestion arises naturally when considering products of symmetric chain decompositions which induce orthogonal chain decompositions — the existence of the decompositions provided in this chapter unexpectedly resolves the most difficult case of previous work by Spink on almost orthogonal symmetric chain decompositions (2017) which makes progress on a conjecture of Shearer and Kleitman. Moreover, we generalize our methods to other finite graded posets. Finally, we address two different problems in extremal combinatorics related to mathematical physics. Firstly, we study metastable states in the Ising model. We propose a general model for 1-flip spin systems, and initiate the study of extremal properties of their stable states. By translating local stability conditions into Sperner- type conditions, we provide non-trivial upper bounds which are often tight for large classes of such systems. The last topic we consider is a deterministic bootstrap percolation type problem. More specifically, we prove several extremal results about fast 2-neighbour percolation on the two dimensional grid.

Orientador: Prof. Dr. Cristian Fabio Coletti / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Matemática , 2017. / Nessa dissertação estudamos a Dinâmica de Melhor Resposta de Evilsizor e Lanchier (3). Foram revisadas as demonstrações em busca de equilíbrios evolucionariamente estáveis e analisando simulações para todos os casos pertinentes. Além desta revisão, neste trabalho introduzimos o conceito de nós teimosos e os adicionamos ao modelo a fim de desestabilizar o equilíbrio no caso estudado em (3). Através das simulações, criamos a intuição de que até nos casos onde não existem equilíbrios evolucionariamente estáveis há também um equilíbrio, porém com coexistência de estratégias. Conjecturamos que esse resultado vale para o caso geral, porém conseguimos prová-lo apenas para dois casos particulares. / In this thesis we studied the Best-Response Dynamics model of Evilsizor e Lanchier (3). We reviewed proofs in search for an Evolutionary Stable Equilibrium analysing simulations for all relevant cases. Besides this revision, we introduced the concept of stubborn players and added it to the Best-Response Dynamics model hoping destabilize the Evolutionary Stable Equilibrium. Through those simulations, we conjectured that even when there is not an Evolutionary Stable Equilibrium, the model converges to another kind of equilibrium, that has coexistent strategies. We conjectured that it states for all altruistic/altruistic cases, but we only could prove it for two specific sub-cases.

abstract: This dissertation investigates the dynamics of evolutionary games based on the framework of interacting particle systems in which individuals are discrete, space is explicit, and dynamics are stochastic. Its focus is on 2-strategy games played on a d-dimensional integer lattice with a range of interaction M. An overview of related past work is given along with a summary of the dynamics in the mean-field model, which is described by the replicator equation. Then the dynamics of the interacting particle system is considered, first when individuals are updated according to the best-response update process and then the death-birth update process. Several interesting results are derived, and the differences between the interacting particle system model and the replicator dynamics are emphasized. The terms selfish and altruistic are defined according to a certain ordering of payoff parameters. In these terms, the replicator dynamics are simple: coexistence occurs if both strategies are altruistic; the selfish strategy wins if one strategy is selfish and the other is altruistic; and there is bistability if both strategies are selfish. Under the best-response update process, it is shown that there is no bistability region. Instead, in the presence of at least one selfish strategy, the most selfish strategy wins, while there is still coexistence if both strategies are altruistic. Under the death-birth update process, it is shown that regardless of the range of interactions and the dimension, regions of coexistence and bistability are both reduced. Additionally, coexistence occurs in some parameter region for large enough interaction ranges. Finally, in contrast with the replicator equation and the best-response update process, cooperators can win in the prisoner's dilemma for the death-birth process in one-dimensional nearest-neighbor interactions. / Dissertation/Thesis / Doctoral Dissertation Applied Mathematics 2016

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}^d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q_m in Q_d. Specifically, we show that for m &ge; 2 fixed and d large there exists a subgraph G of Q_d of bounded average degree such that G does not contain a copy of Q_m but, for every G' such that G &subne; G' &sube; Q_d, the graph G' contains a copy of Q_m. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists &epsilon; &gt; 0 such that for all k and for n sufficiently large there is a collection of at most 2^{(1-&epsilon;)k} subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, P&aacute;lv&ouml;lgyi and Patk&oacute;s. We also prove that there exists a constant c &isin; (0,1) such that the smallest such collection is of cardinality 2^{(1+o(1))^ck} for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q_m in Q_d. That is, we determine the minimum number of edges in a spanning subgraph G of Q_d such that the edges of E(Q_d)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q_m. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A₀ of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A₀ percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r &ge; 2, every percolating set in Q_d has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollob&aacute;s and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset &Vscr;(q,n) consisting of all subspaces of &Fopf;_qⁿordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in &Vscr;(q,n) and a bound on the size of the largest antichain in a p-random subset of &Vscr;(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (&epsilon;_i)^&infin;_i=1 tending to zero such that, for all i &ge; 1, every weak &epsilon;_i-regular partition of W has at least exp(&epsilon;_i^-2/2^{5log&lowast;&epsilon;_i^-2}) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lov&aacute;sz and Szegedy. For positive integers p,q with p/q &VerticalSeparator;&ge; 2, a circular (p,q)-colouring of a graph G is a mapping V(G) &rarr; &Zopf;_p such that any two adjacent vertices are mapped to elements of &Zopf;_p at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 &le; p/q &LT; 4 and is PSPACE-complete for p/q &ge; 4.