PDFLINK |
Graph Pebbling: A Blend of Graph Theory, Number Theory, and Optimization
Communicated by Notices Associate Editor Emilie Purvine
1. Introduction
There are many graph-theoretic subjects that could go under the umbrella of “Moving Things Around on Graphs.” For example, in network optimization, one moves packages from supplies at some vertices to demands at others, with costs accrued per package across edges, attempting to do so most cheaply. In network flow, one tries to maximize the amount of material that can move from a source to a sink, subject to the capacities along edges and the conservation of flow at other vertices along the way. In various versions of pursuit and evasion, cops and robbers take turns moving along edges with the cops trying to capture robbers by landing on them; one tries to minimize the number of cops necessary to always capture the robbers. Zero forcing, black pebbling, chip firing, black and white pebbling, graph pegging, and rigid pebbling are other examples, all with different rules for moving, different objectives, and different constraints and/or costs. While some of these topics model real-world problems, others model pure mathematical problems such as space-time tradeoffs in computational complexity, efficient matrix storage during Cholesky factorization, rigid structures in computational geometry, and matrix rank and nullity computation. The graph pebbling model we discuss here is used to translate a number-theoretic problem into graph theory. It has also developed into a rich subject in its own right.
In this article, we present a range of paradigms within this field and, for each one, share some of the major results, conjectures, and open problems. Many of these problems are accessible to those both at many levels, from undergraduate (e.g., 78919) to seasoned emeritus, and from various backgrounds, from algebra and graph theory to probability and discrete optimization. In fact, many well-known professionals (e.g., Bukh, Elledge, Gibbons, Herscovici, Moews, Pachter, Pudwell, Tomova, Wierman, Xue, Yerger, and others) have produced great graph pebbling results during their time as undergraduates. For interested readers, the two resources 1213 contain references for most of the results not cited below.
2. Number-Theoretic Origins
2.1. Zero-sum subsequences
The story of graph pebbling begins with Erdős and zero-sum problems. Zero-sum problems are combinatorial problems in the context of finite abelian groups that determine how large a set (or sequence) of elements must be such that some subset (or subsequence) with prescribed constraints has a zero sum.
This is best possible; consider the sequence of “0”s and “1”s, which has no nonempty subsequence of length that sums to .
More generally, one can ask all sorts of questions regarding the length of a sequence before the sum of some (nonempty) subsequence has a specified property. For instance, if is a sequence of elements of a group then the pigeonhole principle implies that there is a nonempty zero-sum subsequence. The minimum such length for which a zero-sum subsequence is guaranteed is called the Davenport constant of , For . , is best possible (consider a sequence of “1”s), so the Davenport constant of is .
Erdős and Lemke conjectured that there is a nonempty zero-sum subsequence of with the additional condition that A stronger condition is that . which can be written as , where we write , for the order of an element in a group (in this case This sum is often referred to as the cross number of the subsequence ). which plays a vital role in factorization theory. Kleitman and Lemke answered this stronger question in the affirmative. ,
The natural extension of their work is to arbitrary groups, which remains open for nonabelian .
2.2. Chung’s proof of the Lemke-Kleitman Theorem
The original proof of the Lemke-Kleitman Theorem relied on an inductive argument based on a multitude of possible interactions between elements. Lagarias and Saks proposed a simplified approach to the Erdős-Lemke problem, and Chung was the first one to introduce it to the literature 6. The main concept is to combine elements with like prime factorizations. Let be the prime factorization of For each element . in the sequence write , where , is relatively prime to .
Choose any exponents and let be a subsequence of containing elements of the form (where is not necessarily relatively prime to If, for some ). , then there is a subsequence , of of size at most , such that the sum of the elements in , necessarily has the form Furthermore, if each . satisfies
then
Thereafter, we will treat as a single entity, where the value of is and the notation , is taken to denote Note that these definitions are applied recursively, as an element . may itself be a set, rather than a number. By iteratively and strategically applying such groupings, one can find a zero-sum subsequence of that also obeys the cross number condition. This is exactly how Chung’s proof of the Lemke-Kleitman Theorem works. In this sense, her proof can be viewed as an abstract puzzle game. That game is graph pebbling!
The translation of the Erdős-Lemke problem into graph pebbling is not trivial. The essence of the proof is to (1) build the divisor lattice (2) view the given numbers as pebbles, placed naturally in , according to common factors with (3) observe that each pebble obeys local versions of the two required conditions, (4) model certain movements of the pebbles in the lattice by “pebbling steps” (to be defined later), (5) show that those steps preserve the two local conditions as illustrated above, (6) observe that any pebble that reaches the bottom represents a solution to the Erdős-Lemke problem, and finally (7) prove that it is always possible to move a pebble to the minimal vertex via pebbling steps, given any configuration of , pebbles. A detailed translation is given by Elledge and Hurlbert, who gave a Chung-like pebbling proof of the Lemke-Kleitman conjecture for abelian groups (originally resolved by Geroldinger).
We now illustrate the pebbling movement of this approach with a specific example as seen in Figure 1. Consider a sequence of five pebbles that are placed at such as , Because these are all multiples of . it is simpler to represent them just as those multiples, and simpler still to reduce them modulo 5, becoming the sequence , Now it is easier to spot a zero sum in . such as the final three numbers (4,2,4). Then we can move, as a pebbling step, the corresponding subsequence , down the red edge to as a single “superpebble,” labeled by the sequence Notice that . and that , This is the essence of how pebbling models both sums. Any superpebble that reaches the bottom will be a zero sum with cross number at most 1. .
The final stage (7) above is handled by reducing to the square-free case. That is, if we reduce the proof on , to that on where , is any product of distinct primes with often referred to as , the lattice subsets of , One can see that . is the product of paths, having lengths while , is the product of paths, each of length 1. Because is a sublattice of (see Figure 2)—in fact, it is a retract: a homomorphic image of images of pebbling steps in —homomorphic are pebbling steps in Chung then uses the stronger recursive nature of . to solve the problem there more easily. We will illustrate her technique in Section 3.4.
3. Lagarias-Saks Pebbling
We will assume basic familiarity with graphs as sets of vertices and edges (unordered pairs of vertices), and use the notation for the number of vertices of a graph All graphs we consider are connected. Common notation for graphs on . vertices includes the complete graph in which every pair of vertices is adjacent, the path in which only consecutive vertices are adjacent, and the cycle which adds an edge between the endpoints of For two vertices . and the distance function , measures the fewest number of edges in a path from to The eccentricity of a vertex . of is defined while the diameter of a graph , is defined Sometimes we drop the subscript . when the context is clear. We write for the base 2 logarithm. Additionally, we write (resp., if ) (resp., for some ) and all large enough and ; We also use . to mean that as .
3.1. Pebbling basics
A configuration of pebbles on the vertices of a connected graph is a function (the nonnegative integers), so that counts the number of pebbles placed on the vertex We write . for the size of i.e., the number of pebbles in the configuration. A pebbling step from a vertex ; to one of its neighbors (denoted reduces ) by two and increases by one. Given a specified target vertex we say that is fold -solvable if some sequence of pebbling steps places - pebbles on Conversely, if no such steps exist, then . is unsolvable. We are concerned with determining - the minimum positive integer , such that every configuration of size on the vertices of is -fold The invariant is well defined since, for large enough -solvable. the pigeonhole principle guarantees that some vertex will contain at least , pebbles, which can by itself solve The .fold pebbling number of - is defined to be When . we simply write , which is the pebbling number of , .
The configuration with a single pebble on every vertex except the target shows that the number of vertices of the graph , while the configuration with , pebbles on the farthest vertex from and no pebbles elsewhere, shows that , when is chosen to have .
One can also view as the graph on all binary pairs of which that differ in exactly one coordinate are joined by an edge. In this guise, -tuples, is often referred to as the dimensional hypercube. As part of her work on the Lemke-Kleitman Theorem, Chung proves the following. -
In particular, both of the previous bounds are simultaneously tight, as .
To provide an alternative solution to the Erdős-Lemke problem, Chung actually showed more. Given a positive integer let its factorization be , and define Alter the pebbling step rule so that, in . of the dimensions of , pebbles (instead of 2) must be removed from a vertex to move one pebble in those dimensions. Chung showed in this case that the pebbling number of with these generalized pebbling steps is and so the Lemke-Kleitman Theorem holds. ,
3.2. Class 0 graphs: When does ?
Returning to the two-to-one pebbling rule, graphs that, like have , have come to be known as Class 0. The terminology comes from a lovely theorem of Pachter, Snevily, and Voxman, which states that if then , thus there are two classes of diameter-two graphs—Class 0 and Class 1. If ; is disconnected for some vertex then , Let . and be different connected components of with and define the configuration , by , and , for all other vertices Then, . is of size -unsolvable The minimum number of vertices whose removal disconnects a graph is called its connectivity. Thus, Class 0 graphs are 2-connected. .
There are other properties that Class 0 graphs must have. For example, denote by the set of vertices of distance at most from vertex Cranston et al. .7 observe that if is Class 0 and and are vertices with for some and then , the configuration with —otherwise pebbles on no pebbles on other vertices of , and 1 pebble on each remaining vertex is , of size at least -unsolvable They use this Neighborhood Lemma to prove that every Class 0 graph with . vertices has at least edges. At present, the Class 0 graph with the fewest edges known is the wheel, a cycle with a central vertex adjacent to every cycle vertex, having edges. Are there Class 0 graphs with fewer edges?
The family of 2-connected Class 1 diameter-2 graphs were later characterized by Clarke, Hochberg, and Hurlbert, the main property of which is the induced containment of the (Class 1) pyramid shown in Figure 3. The other important property is that every vertex not in the pyramid lives geometrically inside one of its triangles, and vertices from different triangle interiors are not adjacent. In a probabilistic sense, almost all graphs have diameter two—think of the probability that some two vertices don’t have a common neighbor. Now consider how unlikely it is to fit into this restrictive pyramid structure: at best of all graphs are like this since, if there is a pyramid, each of the nonpyramid vertices have at least three nonneighbors. Thus, almost all graphs are Class 0.
One can say more. As shown by Postle et al. 20, graphs of diameter three can have pebbling numbers as high as but no more, while graphs of diameter four have pebbling numbers at most , The techniques used to achieve these results include “discharging” which is the main technique used in the proof of the celebrated Four-Color Theorem. A higher diameter can push pebbling numbers to the exponential range (e.g., . In general, Postle showed that a graph with diameter ). has pebbling number at most
On the other hand, high connectivity (ensuring many paths to the target) can keep pebbling numbers low. Czygrinow et al. 10 proved that for all there is a , such that every graph with diameter and connectivity at least is Class 0. The Erdős-Renyi random graph model places edges independently with probability between pairs of vertices (the counting above is for the model The authors proved that ). (it was shown by Clarke et al. to be at least and used the result to prove that a random graph with edge probability ), is almost surely Class 0. The proof used known theorems about the thresholds for having connectivity at least and diameter at most It is interesting how close this value is to the connectivity threshold of . yet there is plenty of room for improvement in the upper and lower bounds for , .
One nice application of the diameter-connectivity theorem is to Kneser graphs, known for their importance in many subareas of graph theory and combinatorics, including graph coloring, graph embedding, and extremal set theory, among others. For the Kneser graph , has all of -subsets for vertices, with edges joining disjoint pairs. is the complete graph and the famous Petersen graph , in Figure 4 is the smallest example for Readers should find it an enjoyable puzzle to prove that the Petersen graph is Class 0. (There are at least five distinct proofs in the literature, one of which follows from the diameter-two classification above; two others appear below.) In fact, it was shown in .12 that is Class 0 for all Furthermore, with the diameter-connectivity result in hand, they prove that, for any constant . there is an integer , such that, for all and , is Class 0. With this evidence, one cannot help but believe that is Class 0 for all and that some clever idea to prove it lies in wait. The subject could use more Class 0 sufficiency conditions. ,
3.3. Weight functions: An optimization approach
Along these lines, there is an opportunity to use weight functions. One can think of pebbles sitting on a target as having weight 1, on a target’s neighbors as having weight ..., and sitting on a vertex at distance , from the target as having weight The weight of a configuration is then the sum of the weights of its pebbles (see Figure .5). It is not difficult to prove, for example, that a configuration on a path can solve the target at one of its endpoints if and only if its weight is at least one. By rescaling to make all the weights integral, we can rephrase the characterization as: a configuration on a path cannot solve the target at one of its endpoints if and only if its weight is less than i.e., at most ; Interestingly, this bound equals the sum of the weights. .
This can be generalized at the cost of equivalence, and the notion leads us to techniques involving linear and integer optimization. Suppose that is a tree, with one of its leaves as target, and that Define the weight function . by where , The pair . is called a basic strategy. The Weight Function Lemma 14 says that if is an configuration on -unsolvable then ,
One can extend this to all graphs as follows. Given a target
There are some drawbacks to the approach, as you might imagine. Of course, integer optimization is typically exponential in the input size, but the input size (the number of such trees) is typically exponential (or worse!) in the number of vertices. Furthermore, consider the unsolvability polytope of an
In practice, however, one can have surprisingly good success by restricting the input to a random collection of polynomially many breadth-first subtrees of depth at most
Using the symmetries yields two other trees
so
This holds because the right-hand side of inequality 1 is the sum of the coefficients, so the same is true of any sum of such weight functions. Therefore, in a uniform sum such as inequality 2, the right-hand side, after dividing by
In some cases the method of weight functions offers the simplest proof of a graph’s pebbling number (or the best upper bound of it). The set of strategies used in such a proof is called a certificate. Changing the weighting system by reducing weights by more than half as we traverse the edges of a tree, proceeding away from the target, yields nonbasic strategies—it turns out that these are conic (i.e., nonnegative linear) combinations of basic strategies, and so satisfy the Weight Function Lemma as well. Thus, nonbasic strategies do not need to be included in the optimization constraints, but they can be used in a certificate. From the geometrical point of view of the unsolvability polytope, certificates will involve at most
A good example of this is powers of cycles 14. For a graph
where the upper bound comes from a certificate of carefully constructed strategies.
The following problem is an interesting question from 14 regarding the approximability of graph pebbling with weight functions. Let
Optimization perspectives of graph pebbling are an active area of research. For instance, Kenter et al. 15 presents optimization approaches specific to graph products. In general, describing the actual facets of the unsolvability polytopes of these approaches also remains illusive.
3.4. Graham’s conjecture: Pebbling on graph products
Chung’s proof that
As a toy example of Chung’s proof technique, we prove again that the Petersen graph