Date of Award

Spring 1-1-2025

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Mathematics

First Advisor

Vu, Van

Abstract

A community of n people participate in a parliamentary election with two major parties. Every person initially supports one side, and with each day, changes their opinion to match the majority among their friends. This process, commonly known as Majority Dynamics in literature, and similar processes, have been studied in many different contexts, including Statistical Physics, Computer Science, Economics and Ecology, as discussed in the influential survey by Mossel and Tamuz (2014). Tran and Vu (2019) considered the process on a Erdös-Rényi G(n, p) random graph and discovered the ``Power of Few'' phenomenon: Starting from a balanced initial state, one side can bribe a surprisingly small amount of voters to win every single vote a few days later. Since then, there has been a search for the minimum number of defectors needed for unanimous victory, for the widest possible range of the density p. This thesis aims to introduce the most recent results in this problem, proven by the author and collaborators, and how they correspond to progresses in another setting, where everyone chooses their initial opinions randomly and independently. Our first of two main theorem extends the Power of Few phenomenon for the widest possible range of densities: everything down to the connectivity threshold. Our second theorem is a substantially stronger version of the first, for half of the possible densities. This result also leads to a new best-known bound on the density required for unanimity in the settings with random initial opinions. We also briefly demonstrate two additional results: (1) the robustness of ``Power of Few'' in a more realistic setting where voters do not reliably change sides, and (2) the ``Power of Few'' effect in the sub-connectivity regime.

Download

Share

COinS