Abstract
Evolutionary graph theory provides a mathematical framework for understanding how population structure influences the spread of genetic mutations. However, traditional models often assume a uniform environment. This paper extends the theory to 2-chromatic (bipartite) graphs where fitness is determined by the interaction between an individual's type and the local environmental "color." We prove that for regular graphs, the specific topology is secondary to the arrangement of resources, and that mutant success is governed by the geometric mean of fitness across environments.
Introduction: Beyond Uniform Environments
In classical evolutionary graph theory, the "isothermal theorem" states that on regular graphs, the probability of a mutant taking over a population (fixation probability) is identical to that of a well-mixed population. This assumes every node offers the same reproductive advantage. In reality, resources are often patchy—nutrients or drug concentrations vary across space.
The challenge lies in determining how the interaction between population structure (who can replace whom) and the resource landscape (where fitness boosts are located) affects evolution. This study focuses on 2-chromatic graphs, where nodes can be divided into two sets such that connections only exist between different sets.
Methods and Modeling
The authors utilize the Moran process, a birth-death model where individuals are chosen for reproduction based on fitness, and their offspring replaces a neighbor. To account for heterogeneity, they introduce:
- Color-to-Fitness Mapping: Fitness is determined by a payoff matrix based on the individual's type (Mutant $A$ or Resident $B$) and the node's color (Green or Red).
- Martingale Analysis: Stochastic processes are used to derive exact fixation probabilities on complex structures.
- Dynamic Shuffling: A "shuffling rate" ($p$) models resource mobility, where colors are randomly permuted at each time step.
Graph Topologies and Evolutionary Equivalence
The study evaluates these theorems across several canonical graph topologies, ranging from simple cycles to complex lattices and star graphs.
A key finding is the "isothermal theorem for colored graphs." It proves that for "properly colored" regular graphs—where no two neighbors share the same color—the specific topology does not matter. Whether the population is arranged in a cycle, a 2D lattice, or a complete bipartite graph, the fixation probability remains the same if the graph is regular and properly colored.
The Geometric Mean Rule
One of the most significant theoretical contributions is the discovery that selection favors mutant $A$ over resident $B$ if and only if the product of $A$’s fitness in both environments exceeds the product of $B$’s ($a_G a_R > b_G b_R$). This implies that evolutionary success in heterogeneous environments is governed by the geometric mean of fitness, rather than the arithmetic mean. This rule provides a simple yet powerful condition for predicting the outcome of competition in patchy landscapes.
Structure-Color Synergy and Mobility
While regular graphs show equivalence, asymmetric structures like star graphs behave differently. On a star, the "proper coloring" (where the hub is one color and all leaves are another) is actually the least favorable configuration for a mutant. This highlights a "structure-color synergy" where the optimal distribution of resources depends heavily on the underlying graph.
Furthermore, the introduction of resource mobility (dynamic coloring) acts as a buffer. High mobility effectively smooths out the "peaks and valleys" of the fitness landscape, turning a heterogeneous environment into a functionally uniform one and attenuating the impact of local hotspots.
Conclusion
This research provides a rigorous analytical foundation for studying evolution in complex, changing environments. While limited to 2-chromatic graphs and birth-death updating, it opens doors for future investigations into n-chromatic graphs and the effects of directed resource flow. By bridging the gap between static graph models and fluid ecological systems, this work advances our understanding of how spatial and environmental factors co-direct the path of evolution.
Summary updated