Bookmarks this page: DESCRIPTION OF GAME, SIGNIFICANT LABELS, GENERAL COMMENTS, EXAMPLES, REFERENCES, FINAL WORD
Beyond ZFC: Introduction to Lattice Graph Data Structures
In early 1997 I was preparing lecture notes for a course I regularly taught in algorithms and data structures at UCSD. I constructed a simple example (referred to below as P1) of a data structure problem and analyzed it using a branch of mathematics called Ramsey theory. I then changed example P1 ever so slightly so that I would have a second example (referred to below as P2) for the students to analyze as an exercise. Fortunately, I tried to work P2 before assigning it to the students because P2 may be impossible to prove using "normal" mathematics -- "abnormal mathematics" may be required. If you're curious about this strange example P2 and others like it that seem to lie in mathematical limbo, read on!
Shown in Figure P1 is a rectangular lattice with rooms (solid circles) and one-way tunnels (arrows). We specify each room by giving its coordinates (x,y) with respect to the axes shown. For any room (x,y), define the boundary distance of that room to be the minimum of x and y. The boundary distance tells you how close you are to at least one of the two coordinate axes. For example, the boundary distance of room (5,9) is 5. You are distance 5 units from one of the axes (the vertical axis in this case). Each room in Figure P1 has a number or "label" beside it. A label z on a room (x,y) tells you that, by starting at (x,y) and following one-way passages, it is possible to find a room (x',y') with boundary distance z. Moreover, z is the minimum such boundary distance to be found in this manner. For example, the room (5,9) has label 2. By inspecting Figure P1, you can see that 2 is the minimal boundary distance of any room that can be gotten to by starting at (5,9) (there are two such rooms with minimal boundary distance: (2,6) and (4,2)).
Figure P1
DESCRIPTION OF GAME: We imagine a game where you are placed in some room (x,y). Starting at that room, you can travel from room to room along one-way tunnels. The coordinates of each room and its label are posted on the wall of that room. No other information is given. The object of the game is to find a room (x',y') of minimal boundary distance among all rooms accessible from (x,y). When the minimal-boundary-distance room is located, you can end the game and exit the lattice. For example, suppose you are placed in room (5,9) and see (in addition to (5,9)) the label 2 posted on the wall. You know for sure that you must get out of room (5,9) to find a room of minimal boundary distance 2. There is only one way out, so you take it and end up in room (3,8) with distance 3>2. You must move on because you know that you are not at the room of minimal boundary distance (starting from (5,9)). But now you have two choices. If you take the right tunnel, you arrive at room (2,6), with boundary distance 2. You can end the game and exit the lattice. If you take the left tunnel you get stuck at room (5,3), boundary distance 3, and you have failed to find the minimal-boundary-distance room. Usually in such problems there is some sort of rule for backtracking along a tunnel to avoid getting stuck in this manner, but we'll not get into that here.
SIGNIFICANT LABELS: In Figure P1, some of the rooms have labels in parentheses and some don't. For example, (2,1) has label (1) which is the distance of (2,1) to the lattice boundary. If you are put in room (2,1) then no exploring is required. You are already at the desired room and can end the game and exit the lattice. A label z for a vertex (x,y) is called a significant label for (x,y) if z is smaller than minimum(x,y) (such a label may require a significant amount of exploration in our game scenario). All other vertices are called insignificant. Insignificant labels are in parentheses while significant labels are not. If you are placed at a room with an insignificant label, you can end the game without any search.
(1) How did the labels (or data structure) get added to the rooms and how much work was involved? For large complexes of rooms and tunnels the work could be considerable. On the other hand, if the game is going to be played over and over again, the work of adding the labels might be worth it.
(2) It would be helpful to know something about the number of different significant labels, since vertices with these labels require searching for the minimal-boundary-distance room -- perhaps considerable searching in large graphs. In Figure P1, the set of significant labels is {1, 2, 7}. There are just three different significant labels. Another thing that would be useful to know is how many rooms have significant labels (7 rooms in our example). We are going to focus on the former question, the number of different significant labels.
We analyze two examples of "lattice-exit" problems, P1 and P2. For each example, we state and prove a theorem about significant labels associated with that example. The significant-label theorem for the first example (P1: Prototype Lattice-Exit Model) can be proved in the framework of "normal" math. The very similar significant-label theorem for the second example (P2: Terminal Vertex Lattice-Exit Model) can possibly be proved using normal math, but we don't know how to give such a proof. We can, however, give a proof using "abnormal math" (out of bounds to most mathematicians). We explain further.
The basic axioms of mathematics are referred to as the "ZFC Axioms" (Zermelo, Fraenkel, plus Axiom of Choice). Virtually all mathematical discussion and research is done in the context of these axioms. Our proof of the significant-label theorem for P1 uses a result from "Ramsey theory" which is proved in ZFC. Thus, our theorem about P1 is proved within the axiomatic framework of normal mathematics. Our theorem about P2, however, uses Harvey Friedman's Jump-Free Theorem, the proof of which requires large cardinals REFERENCE (1). The existence of large cardinals cannot be proved in ZFC.
Anyone who has mastered a good undergraduate course in mathematics should be able to follow the statements and proofs used in examples P1 and P2. I have presented these examples in undergraduate courses taught by me at UCSD (Department of Computer Science and Engineering).
(1) The most comprehensive work on combinatorial results whose proofs require the use of large cardinals can be found in the deep and important work of the logician, Harvey Friedman. In terms of lattice graphs and the material we have been discussing here, his most relevant paper is Applications of Large Cardinals to Graph Theory. This paper contains a statement of Friedman's Jump-Free Theorem which is the key result we need to prove the significan-label theorem for example P2.
(2) The paper Large-Scale Regularities of Lattice Embeddings of Posets , by Jeffrey B. Remmel and S. Gill Williamson, explores applications of classical Ramsey Theory and the Jump-Free Theorem to the structure of partially ordered sets (posets) on lattices. This paper is accessible students who have had a good upper division or graduate course in discrete mathematics.
FINAL WORD In case you're interested, here are two more lattice-exit problems whose significant-label theorems follow from the Jump-Free Theorem. They will be even harder than example P2 to prove with normal math. A reformulation of the significant-label theorem for P4 is equivalent to the Jump-Free Theorem (see Section 4, Theorem 4.4, page 24 of Applications of Large Cardinals to Graph Theory).
(P3: Bureaucratic Lattice-Exit Model),
(P4: Committee Lattice-Exit Model)