Colours, giants, and games

This thesis focuses on three independent areas of research. In the initial part, we study the occurrence of monochromatic substructures in coloured combinatorial objects across two different settings. First, we investigate the presence of monochromatic products in arbitrary, random, and randomly perturbed colourings of the integers —varying a classical line of research which originated with Schur and has since drawn considerable attention. Our results mark the first contributions in this new direction and lay the foundation for further work. Next, we determine the exact value of the Ramsey number of the squares of long paths and cycles, expanding the limited class of graphs for which this number is precisely known. In the middle part, we extend and address works and conjectures of earlier authors. First, we resolve a conjecture by Letzter and Snyder on the chromatic number of graphs with large minimum degree and no short odd cycles. Second, we extend the Transference Principle of Conlon and Gowers, thereby paving the way to strengthen and generalise existing counting results in sparse random settings. As an application, we obtain an asymptotically optimal counting version of the KŁR Conjecture. In the final part, we analyse the dynamics that arise when learning agents repeatedly interact in the framework of games. We first consider the case of players with finite recall under various monitoring conditions in repeated games. Here, we establish a Folk Theorem-like result, characterise the set of payoff vectors attainable under these dynamics, and uncover a wide spectrum of possibilities for the emergence of algorithmic collusion. We then investigate best-response dynamics in random potential games, and demonstrate the robustness of this approach across different regimes of payoff correlation.