ABSTRACT
This chapter discusses various topics ranging from the Toppling Game, Revolutionary and Spies, Robot Crawler, to Seepage. For each of these games and processes, the chapter focuses on their behavior on random graphs, and uses probabilistic methods to analyze them. The toppling game was introduced by Cranston and West. It is a two-player game played on a graph G. The toppling number of binomial random graphs and complete graphs are closely connected. The game of Revolutionaries and Spies was first considered by József Beck in the mid-1990s. The revolutionaries want to arrange a one-time meeting consisting of m revolutionaries free of oversight by spies—the spies want to prevent this from happening. The preferential attachment model, introduced by Barabasi and Albert, was an early stochastic model of complex networks. The chapter analyzes Seepage and the green number when played on a random directed acyclic graph (DAG) as a model of disrupting a given hierarchical social network.
