Counting Strict Gridlock on Graphs

1. Problem Statement

The paper addresses a gap in understanding distributed consensus formation on networks. While traditional graph coloring (proper coloring) models anti-coordination problems (where neighbors must differ), many social and biological systems involve coordination problems where a group seeks a uniform coloring (all vertices share the same color).

In a distributed setting where individuals have limited information (only seeing their neighbors), naive greedy strategies often fail to reach a global consensus. Instead, the system may get stuck in a gridlocked state. The authors define these states as:

• Locally-Optimal Coloring: A coloring where every vertex shares a color with a plurality of its neighbors (i.e., no single neighbor color appears more frequently than the vertex's own color).
• Strict Gridlock Coloring: A locally-optimal coloring that is not a uniform consensus (i.e., at least two distinct colors exist in the graph).

The core problem is to count the number of such strict gridlock colorings for a given graph $G$ and $k$ colors, denoted as $SG_k(G)$. This count serves as a mathematical measure of how much a specific network structure hinders consensus.

2. Methodology

The authors develop a combinatorial framework to count these colorings, moving from definitions to a recursive algorithm.

A. Definitions and Properties

• LO-Polynomial ($LO_k(G)$): The total number of locally-optimal $k$-colorings.
• SG-Polynomial ($SG_k(G)$): The number of strict gridlock colorings, defined as $SG_k(G) = LO_k(G) - k$ (subtracting the $k$ trivial consensus colorings).
• Theorem 1: Proves that $LO_k(G)$ is a polynomial in $k$.

B. Recursive Algorithm

To compute $LO_k(G)$, the authors derive recurrence relations based on vertex degrees:

1. Low-Degree Vertices:

   • Degree 1 (Leaves): A leaf must share the color of its unique neighbor.
   • Degree 2 (Bivalent): A bivalent vertex must share the color of both neighbors (implying the neighbors must also share colors).
   • Bivalent-Dense Graphs: If a graph is "bivalent-dense" (most neighbors of non-bivalent vertices are bivalent), the polynomial simplifies to $k^p$, where $p$ is the number of connected components in the subgraph induced by edges incident to bivalent vertices.

2. Degree 3 (Trivalent) Recurrence:
   For a vertex $v$ with neighbors $a, b, c$, the authors use the Inclusion-Exclusion Principle. A locally-optimal coloring requires at least two neighbors to share $v$'s color. By subdividing edges (inserting a new vertex), they map the problem to graphs where specific neighbors are forced to share colors.
   $$LO_k(G) = LO_k(G_{ab}) + LO_k(G_{ac}) + LO_k(G_{bc}) - 2LO_k(G_{abc})$$
   Where $G_{ab}$ is $G$ with edge $va$ and $vb$ subdivided.

3. General Degree ($n \ge 3$) Recurrence:
   The authors generalize the trivalent case using a complex inclusion-exclusion formula (Theorem 10) involving subsets of neighbors. To handle high-degree vertices efficiently, they introduce "non-voting edges" (edges that force endpoints to have the same color but do not count toward the plurality calculation).

   • Theorem 12: Provides a recurrence for $n$-valent vertices with $b$ bivalent neighbors, utilizing non-voting edges to reduce the problem to bivalent-dense subgraphs.

4. Set Partition Perspective:
   The paper also establishes that $LO_k(G)$ can be calculated by summing over locally-optimal partitions of the vertex set:
   $$LO_k(G) = \sum_{\pi \vdash G} k^{|\pi|}$$
   Where $\pi$ is a partition where every vertex has a plurality of neighbors in its own part. This provides an alternative proof that $LO_k(G)$ is a polynomial.

3. Key Contributions

• New Graph Invariants: Introduction of the LO-polynomial and SG-polynomial, providing a rigorous mathematical tool to quantify "gridlock" in networks.
• Recursive Counting Algorithm: A complete algorithm to compute these polynomials for any graph by recursively reducing it to bivalent-dense graphs using edge subdivision and non-voting edges.
• Theoretical Proof: Proof that the number of locally-optimal colorings is always a polynomial in the number of colors $k$.
• Structural Sensitivity: Demonstration that graphs with identical community structures (modularity) can have vastly different gridlock properties based on the specific placement of inter-community edges.

4. Results

• Polynomial Nature: The authors successfully prove that $LO_k(G)$ is a polynomial, allowing for the analysis of gridlock behavior across varying numbers of available choices ($k$).
• Degree Bounds: For a connected graph with $n \ge 3$ vertices, the degree of $LO_k(G)$ is bounded by $\lfloor n/3 \rfloor$. This implies that in a gridlocked state, every color must be assigned to at least three vertices.
• Case Study (Figure 6): The authors compare two graphs with 5 cliques of 5 vertices.
  • Graph A: Between-clique edges connect pairs.
  • Graph B: Interior vertices connect to all other cliques.
  • Result: Despite having similar modularity, Graph B has significantly more strict gridlock colorings than Graph A (e.g., for $k=2$, Graph B has 20 gridlocks while Graph A has 0). This proves that fine-grained network topology (edge placement) is a stronger predictor of consensus failure than coarse community structure.

5. Significance

• Social Science Application: The work bridges graph theory and social science, offering a quantitative measure for why groups fail to reach consensus. It explains why some network topologies lead to stagnation even when individuals act "rationally" (locally optimally).
• Beyond Community Detection: The paper argues that standard community detection methods (like modularity) are insufficient for predicting consensus dynamics. The SG-polynomial captures subtle structural nuances that standard clustering misses.
• Future Directions: The framework opens avenues for studying:
  • Weak Gridlock: States that are not locally optimal but cannot reach consensus via local updates.
  • Proper Coloring Gridlock: Applying similar logic to anti-coordination problems (finding proper colorings).
  • Dynamic Processes: Moving from static combinatorial counting to stochastic processes involving noise, stubbornness, or random updates.

In summary, this paper provides a novel mathematical toolkit for analyzing the "dead ends" of distributed decision-making, showing that the specific arrangement of connections in a network is critical in determining whether a group can successfully coordinate or will remain stuck in a gridlocked state.