Counting Strict Gridlock on Graphs
Matthew I. Jones, Zachary Winkeler · 2026
Read Counting Strict Gridlock on Graphs by Matthew I. Jones, Zachary Winkeler (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-18289.txt.
Introduction
Jones and Winkeler count strict gridlock colorings on graphs as a model of blocked consensus. Groups solving coloring tasks on networks reveal facts about structure and behavior. Strict gridlock colorings mark states where natural update rules cannot reach a uniform color. They give a recurrence that counts such colorings for a given graph. The count measures how much a graph hinders group consensus.
Catalog record
| CREATOR | Matthew I. Jones, Zachary Winkeler |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47046 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.18289
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Counting Strict Gridlock on Graphs Matthew I. Jones, Zachary Winkeler Abstract Abstract Graph colorings have been of interest to mathematicians for a long time, but relatively recently, social scientists have also found them to be interesting tools for studying group behavior. In the last 20 years, scientists have begun to study how coloring problems can be solved by groups of individuals on a graph, which has led to new insights into network structure, group dynamics, and individual human behavior. Despite this newfound utility, the exact nature of these distributed coloring problems is not well-understood, and established mathematical tools like the chromatic polynomial miss the unique challenges that arise in these social problem-solving situations with limited information. In this paper, we provide a new framework for understanding these distributed problems by defining a new kind of graph coloring with particular relevance to consensus formation on networks, in which all vertices are trying to agree on a common color. These strict gridlock colorings represent roadblocks to consensus where the group will not reach a uniform coloring using natural update processes. We describe a recurrence relation that provides an algorithm for counting these gridlocked colorings, which establishes a mathematical measure of how much a given graph hinders consensus in a group. 1 Introduction To mathematicians, graph colorings can be interesting purely for their intriguing properties and puzzle-like nature. However, they have also proven useful for a surprisingly diverse body of problems from structural questions in Ramsey theory [ 1 ] to the coloring of maps in the famous four color theorem [ 2 ] . The traditional notion of a graph coloring, which we refer to as a proper graph coloring, is a labeling of the vertices of a graph with k colors so that no two adjacent vertices have the same color, and these mathematical objects have many interesting properties. However, this core idea has been expanded in many different ways. Perhaps the most obvious extension is to color the edges of a graph, instead of the vertices. After defining proper (vertex or edge) colorings, one could introduce additional conditions on the colorings to get even more restricted sets of colorings. For example, equitable colorings require that all colors appear the same number of times [ 3 ] . Harmonious colorings require that for each pair of colors, at most one edge in the entire graphs connects vertices with those colors [ 4 ] . Rainbow colorings are colorings on the edges of a graph such that for every pair of vertices, there exists a path between them where no color appears more than once [ 5 ] . List colorings, unlike the other colorings above, assign each vertex a list of colors. In this case, the challenge is typically to find the shortest possible lists so that a proper coloring can be found by assigning each vertex colors from its list [ 6 ] . 1.1 Proper Graph Colorings in the Social Sciences These graph coloring problems appear in a wide variety of applications. In particular, graph coloring problems have been used specifically to study the behavior and coordination of groups, with each participant required to select the color for a single vertex using limited information, and with color representing some behavior or action of the individual. This has been a fruitful approach and has yielded many empirical results linking group structure and coordination. Some of the first empirical studies examined different network structures that made the problem more or less difficult [ 7 , 8 , 9 ] . Later work focused on the behavior of individuals embedded in the network, considering both random color choice [ 10 , 11 ] and altering the network structure [ 12 ] . These problems, which exist in a social setting involving many decision-makers, make the problem more challenging than the traditional graph coloring problem. (Note that solving these graph problems in a distributed setting is different than on-line graph coloring, in which vertices must be colored one at a time by a central decision-maker [ 13 ] .) Proper graph colorings can be thought of as modeling anti-coordination problems in groups, in which individuals must choose a different strategy or behavior from their neighbors. However, not every collective action problem is an anti-coordination problem. Other social challenges can also be modeled with (non-proper) graph coloring problems. As one example, Erikson and Shirado used a variation on proper graph colorings to study the division of labor on networks [ 14 ] . In this problem, it is acceptable for a vertex to share a color with its neighbors as long as it is adjacent to all the available colors. 1.2 Consensus and Uniform Colorings In other common scenarios, groups are tasked with reaching consensus on one of k possible choices. This ranges from friends choosing a restaurant for dinner to a pack of animals choosing which a direction of travel [ 15 ] to jury verdicts of guilty or not guilty [ 16 ] , each with their own complications. From a game theory perspective, all these problems fall into the broad category of coordination games, and can be further divided by the types of incentives that participants face into several well-studied games, including Matching Pennies [ 17 ] or Battle of the Sexes [ 18 ] . In the iterated setting, a natural but naive strategy is to choose the most common choice among all players in the previous round. However, when these games are played on networks and participants have limited knowledge of the group as a whole, additional challenges arise. Individuals are responsible for selecting a strategy to align with their neighbors without knowing how those choices affect the entire network. Instead of reaching consensus, naive and greedy strategies (for a rigorous description of these update rules and variants, see [ 19 ] ) can lead to gridlocked states, in which all participants are making the “best” choice and the population stagnates without deciding on a common outcome. Such challenges can be modeled by another (non-proper) graph coloring problem: find a uniform coloring in which all vertices have the same color. Of course, this is trivial from a global perspective. But when solved in a social setting with multiple decision-makers and limited information, they become highly non-trivial and represent solutions to consensus formation problems. Jones and Christakis tasked individuals with finding a uniform coloring to study the role of leaders in the formation of consensus in networks [ 20 ] . Other studies examined how groups find uniform colorings (framed as consensus or voting) with unbalanced incentives and found that network topology shaped the group’s ability to reach consensus and controlled if the majority or minority preference was selected [ 8 , 21 ] . Despite this progress, there has been very little research studying these problems analytically. Related work in the continuous space like the DeGroot Model [ 22 ] misses the challenges that are present in the discrete space. A key component to understanding the uniform graph coloring problem, and therefore understanding consensus, is to define and study the states corresponding to gridlock, the dead ends in the search for a global solution to the consensus problem. To