On the Spread of Information Through Graphs

Consider a graph G and an initial con guration, where each node is black or white. Assume that in discrete-time rounds, all nodes simultaneously update their color based on a prede ned rule. In the r-threshold (resp.-threshold) model, a node becomes black if at least r of its neighbors (resp. fraction of its neighbors) are black, and white otherwise. The r-monotone (resp.-monotone) model is the same as the r-threshold (resp.-threshold) model, except that a black node remains black forever. Question 1. What is the number of rounds that the process needs to stabilize ? Question 2. How many nodes must be black initially so that black color takes over (i.e., the whole graph becomes black eventually)? Question 3. Assume that each node is black initially with some probability p, independently. What is the probability that black color takes over? The main focus of this thesis is devoted to addressing the aforementioned three questions for di erent classes of graphs. Our contributions come in the following four parts. Firstly, we investigate these questions when the underlying graph is a d-dimensional torus. By de-veloping novel techniques, concepts, and tools, we resolve or advance several open problems. In the second part, we study the behavior of the-threshold model for = 1 2 on the random regular graphs and Erdos-Renyi random graph. In the third part, our main goal is to comprehend which parameters chie y lead the behavior of the above models. In particular, we characterize the answer to the above three questions in terms of di erent graph parameters, such as the number of nodes/edges, maximum/minimum degree, and expansion. The last part is dedicated to the study of the Galam model, a very well-established model in statistical physics. The updating rule in this model is identical to the one from the-threshold model for =1 2, but here the neighbors of each node are chosen in a random manner in each round.