The Flood Polynomial of a Graph
Karin R. Saoub, Michael Weselcouch, Trey Wilhoit, Jackson Wills · 2025
Read The Flood Polynomial of a Graph by Karin R. Saoub, Michael Weselcouch, Trey Wilhoit, Jackson Wills (2025) 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-2504-04233.txt.
Introduction
Karin Saoub and three co-authors define a new counting tool for networks in a 2025 math paper, inspired by a video game. In Minecraft, water spills from cell to cell in cascades. The flood polynomial of a graph counts all starting sets that can flood the whole graph, weighted by size.
The team derives conditions that two graphs must meet if they share the same flood polynomial. For several graph families they give exact formulas. Many of those formulas follow a Fibonacci-like pattern, and some match the classic Fibonacci and Lucas polynomials outright. They also build pairs of genuinely different graphs with the same flood polynomial, shown as products of those classic forms. The work links a game mechanic to deep counting patterns.
Catalog record
| CREATOR | Karin R. Saoub, Michael Weselcouch, Trey Wilhoit, Jackson Wills |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-04233
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Flood Polynomial of a Graph Karin R. Saoub, Michael Weselcouch, Trey Wilhoit, Jackson Wills Abstract . The flood polynomial of a simple finite graph is a weight generating function that counts all flooding cascade sets of the graph. The flood polynomial is inspired by the water mechanics in the video game Minecraft. We give necessary conditions for two graphs to have the same flood polynomial. We then provide a formula for the flood polynomials of certain families of graphs. We will see that many flood polynomials can be expressed using a Fibonacci-like recurrence and in some cases are equal to Fibonacci or Lucas polynomials. We then provide general examples of pairs of distinct graphs with the same flood polynomial. In these examples, the flood polynomial will be expressed as the product of Fibonacci and Lucas polynomials. 1. Introduction In this article, we introduce a graph polynomial, called the flood polynomial, which is based on the water mechanics in the video game Minecraft. The flood polynomial is a weight generating function that counts certain subsets of the vertices of a given graph. In Minecraft, water blocks and air blocks have an interesting relationship. If an air block is neighbors with two or more water blocks, then the air block will convert to water, allowing a player to convert a large region of air to water with only a few initial water blocks. Although regions in Minecraft must be contained in a grid, these flooding mechanics can be extended to general graphs. In this paper, we determine families of graphs which have flood polynomials that are products of Fibonacci polynomials and Lucas polynomials, providing a new combinatorial interpretation of a well-known identity involving Fibonacci and Lucas polynomials. We give an explicit formula for finding the flood polynomials of these graphs in terms of these products. This paper presents the first study of the flood polynomial, and we anticipate more results are possible beyond what is discussed in this article. This paper is organized as follows: in Section 2, we provide the necessary background, including the definitions of cascade sets and the flood polynomial; in Section 3, we discuss properties of a graph that can be determined by its flood polynomial; in Section 4, we give formulas for the flood polynomials of certain families of graphs; in Section 5, we provide examples of pairs of distinct graphs with the same flood polynomial; we conclude with presenting open questions in Section 6. 2. Preliminaries We begin with some preliminaries about compositions and partitions, graphs, flood sets, and the flood polynomial. For more information, see [ 11 ] . 2.1. Compositions and partitions A composition \alpha=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}) of n is a finite sequence of positive integers summing to n . The compositions of n are in bijection with the subsets of [n-1] in the following way: for any composition \alpha , define D(\alpha)=\{\alpha_{1},\quad\alpha_{1}+\alpha_{2},\quad\dots,\quad\alpha_{1}+\alpha_{2}+\dots+\alpha_{k-1}\}\subseteq[n-1]. Likewise, for any subset S=\{s_{1},s_{2},\dots,s_{k-1}\}\subseteq[n-1] with s_{1}<s_{2}<\dots<s_{k-1} , we can define the composition \textrm{co}(S)=(s_{1},\quad s_{2}-s_{1},\quad s_{3}-s_{2},\quad\dots,\quad s_{k-1}-s_{k-2},\quad n-s_{k-1}). A partition of n is a composition of n whose parts are in weakly decreasing order. Given a composition \alpha and partition \lambda , we write \alpha\sim\lambda if \lambda is formed by rearranging the parts of \alpha in weakly decreasing order. We use the notation \alpha\vDash n if \alpha is a composition of n and \lambda\vdash n if \lambda is a partition of n . We use \ell(\alpha) to denote the number of parts of \alpha . 2.2. Graphs A graph G consists of two sets: the vertex set, V(G) , and the edge set, E(G) . An edge is an unordered pair of vertices. When it is clear what graph we are talking about, we will write V for V(G) and E for E(G) . Throughout the article we will use n to represent the size of the graph, i.e. n=|V| . We say that two vertices a and b are neighbors in G if ab\in E(G) , that is to say, a and b share an edge. The degree of a vertex v , denoted \deg(v) , is the number of neighbors of v . In this paper we only consider finite simple graphs, which are graphs that do not contain any loops or multi-edges. Consider the graphs shown below. The graph on the left is simple, whereas the graph on the right is not simple since it has a multi-edge. 2.3. Cascade Sets and Flood Sets Given a graph G , a cascade set of G is a subset of the vertices of G . We are going to be interested in cascade sets that “completely flood” the graph using the flooding mechanics of Minecraft. In order to make this concept mathematically rigorous, we need the following definition. Definition 2.1 . For a cascade set C and graph G , the cascade sequence is a sequence of sets C_{0},C_{1},\dots satisfying the following: (1) C_{0}=C , and (2) for k\geq 1 , C_{k}=C_{k-1}\cup\{x\in V\mid x\text{ has at least two neighbors in }C_{k-1}\} . In all future graphs, vertices in cascade sets will be denoted with an aqua coloring. Example 2.2 . Consider cascade set C=\{v_{1},v_{4},v_{6}\} for the following graph. v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{7} v_{8} We can see that both v_{2} and v_{3} have two neighbors in C , so v_{2} and v_{3} will flood. Therefore C_{1} = C \cup \{v_{2},v_{3}\} as shown below. v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{7} v_{8} Similarly, we can now see that v_{5} has two neighbors in C_{1} , namely v_{3} and v_{6} , so v_{5}\in C_{2} . You can check that no other vertices will flood in this step. Therefore C_{2} = C_{1} \cup \{v_{5}\} . v_{1} v_{2} v_{3} v_{4} v_{5} v_{6} v_{7} v_{8} Since neither v_{7} nor v_{8} have two neighbors in C_{2} , no new vertices flood and C_{3} = C_{2} . In fact, in this example, for all k\geq 3 , we have that C_{k}=C_{2} . From the definition of cascade sequence, it follows that if C_{k}=C_{k+1} for some value k , then for all j\geq k , C_{k}=C_{j} , i.e., once two terms in the sequences are equal, all subsequent terms in the sequence are the same set. Similarly, since G is finite and every cascade set is a subset of V(G) , there must exist a k\in\mathbb{N} such that for all j\geq k , C_{j}=C_{k} . Let \overline{C} denote the set to which the cascade sequence starting with C converges. Note that if C^{\prime} is a term in the cascade sequence of C , then \overline{C}=\overline{C^{\prime}} . If \overline{C}=V(G) , then we say that C completely floods G and that C is a flooding cascade set . If \overline{C}\neq V(G) , then we say C is a non-flooding cascade set . If v\in V(G)-\overline{C} , then v is not flooded by C . In Example 2.2 , we see that if C=\{v_{1},v_{4},v_{6}\} , then \overline{C}=\{v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}\} and both the vertices v_{7} and v_{8} are not flooded by C . Since there are some vertices that are not flooded by C , this means that C is a non-flooding cascade set. This leads us to the definition of the flood set. Definition 2.3 . The flood set of a graph