A Study of Combinatorial Games over Random Premises, a Model of Baggage Retrieval from Airports, and Union-Closed Families of Sets

Abstract

This first five chapters of this thesis are concerned with the study of some two-player combinatorial games on random premises. These chapter include 1. the k-jump normal and k-jump misere ` games on rooted Galton-Watson trees, in which the token is allowed to be moved from the vertex where it is currently located, to a descendant of this vertex that is at a distance at most k away from this vertex, 2. percolation games in their most general form, inspired by both site percolation and bond percolation, on infinite 2-dimensional lattice graphs. In the former class of games, the probabilities of the various possible outcomes have been analysed and characterized, phase transition phenomena (pertaining to how the probability of draw changes from being 0 to being strictly positive as the underlying parameter(s) is / are allowed to vary) have been investigated, and sufficient conditions for the average duration of a game to be finite have been proposed. In the latter class of games, regimes (in terms of the values of the parameter(s) under consideration) have been found in which the probability of draw equals 0 – this, in turn, helps establish, with full mathematical rigour, the ergodicity of certain classes of probabilistic cellular automaton (PCA) that arise from the corresponding game rules. The model studied in the sixth chapter involves passengers waiting around a conveyor belt, each having checked in precisely one bag, and it studies the interaction between these passengers and the bags appearing onto the belt according to a prespecified permutation. Passengers leave upon collecting their bags, while those still waiting move to positions vacated by co-passengers in front of them. We study the distribution of the time required for all passengers to retrieve their bags, as well as the distribution of the time required for the conveyor belt to become empty for the first time. We establish a fascinating connection between these quantities and the sequence of telephone numbers (where the n-th telephone number is the number of matchings on the complete labeled graph Kn). In the final chapter, we study union-closed families of sets. Given a union-closed family F of subsets of the universe [n], with F not equal to the power set of [n], a new subset A can be added to it such that the resulting family remains union-closed. We construct a new family F by adding to F all such A’s, and call this the closure of F. This work is dedicated to the study of various properties of such closures, including characterizing families whose closures equal the power set of [n], providing a criterion for the existence of closure roots of such families etc.