Section 16.1 On-line algorithms
Many applications of combinatorics occur in a dynamic, on-line manner. It is rare that one has all the information about the challenges a problem presents before circumstances compel that decisions be made. As examples, a decision to proceed with a major construction project must be made several years before ground is broken; investment decisions are made on the basis of today's information and may look particularly unwise when tomorrow's news is available; and deciding to exit a plane with a parachute is rarely reversible.
In this section, we present two examples intended to illustrate on-line problems in a combinatorial setting. Our first example involves graph coloring. As is customary in discussions of on-line algorithms, we consider a two-person game with the players called Assigner and Builder. The two players agree in advance on a class \(\cgC\) of graphs, and the game is played in a series of rounds. At round \(1\) Builder presents a single vertex, and Assigner assigns it a color. At each subsequent rounds, Builder presents a new vertex, and provides complete information at to which of the preceding vertices are adjacent to it. In turn, Assigner must give the new vertex a color distinct from colors she has assigned previously to its neighbors.
Example 16.1.
Even if Builder is constrained to build a path on \(4\) vertices, then Assigner can be forced to use three colors. At Round 1, Builder presents a vertex \(x\) and Assigner colors it. At Round 2, Builder presents a vertex \(y\) and declares that \(x\) and \(y\) are not adjacent.
Now Assigner has a choice. She may either give \(x\) and \(y\) the same color, or she may elect to assign a new color to \(y\text{.}\) If Assigner gives \(x\) and \(y\) different colors, then in Round 3, Builder presents a vertex \(z\) and declares that \(z\) is adjacent to both \(x\) and \(y\text{.}\) Now Assigner will be forced to use a third color on \(z\text{.}\) In Round \(4\text{,}\) Builder will add a vertex \(w\) adjacent to \(y\) but to neither \(x\) nor \(z\text{,}\) but the damage has already been done.
On the other hand, if Assigner \(x\) and \(y\) the same color, then in Round 3, Builder presents a vertex \(z\text{,}\) with \(z\) adjacent to \(x\) but not to \(y\text{.}\) Assigner must use a second color on \(z\text{,}\) distinct from the one she gave to \(x\) and \(y\text{.}\) In Round 4, Builder presents a vertex \(w\) adjacent to \(z\) and \(y\) but not to \(x\text{.}\) Assigner must use a third color on \(w\text{.}\)
Note that a path is a tree and trees are forests. The next result shows that while forests are trivial to color off-line, there is a genuine challenge ahead when you have to work on-line. To assist us in keeping track of the colors used by Assigner, we will use the notation from Chapter 5 and write \(\phi(x)\) for the color given by Assigner to vertex \(x\text{.}\)
Theorem 16.2.
Let \(n\) be a positive integer. Then there is a strategy for Builder that will enable Builder to construct a forest having at most \(2^{n-1}\) vertices while forcing Assigner to use \(n\) colors.
Proof.
When \(n=1\text{,}\) all Builder does is present a single vertex. When \(n=2\text{,}\) two adjacent vertices are enough. When \(n=3\text{,}\) Builder constructs a path on \(4\) vertices as detailed in Example 16.1. Now assume that for some \(k\ge3\text{,}\) Builder has a strategy \(S_i\) for forcing Assigner to use \(i\) colors on a forest of at most \(2^{i-1}\) vertices, for each \(i=1,2,\dots,k\text{.}\) Here's how Builder proceeds to force \(k+1\) colors.
First, for each \(i=1,2,\dots,k\text{,}\) Builder follows strategy \(S_i\) to build a forest \(F_i\) having at most \(2^{i-1}\) vertices on which assigner is forced to use \(i\) colors. Furthermore, when \(1\le i\lt j\le k\text{,}\) there are no edges between vertices in \(F_i\) and vertices in \(F_j\text{.}\)
Next, Builder chooses a vertex \(y_1\) from \(F_1\text{.}\) Since Assigner uses two colors on \(F_2\text{,}\) there is a vertex \(y_2\) from \(F_2\) so that \(\phi(y_2)\neq \phi(y_1)\text{.}\) Since Assigner uses three colors on \(F_3\text{,}\) there is a vertex \(y_3\) in \(F_3\) so that \(\{\phi(y_1),\phi(y_2),\phi(y_3)\}\) are all distinct. It follows that Builder may identify vertices \(y_1,y_2,\dots,y_k\) with \(y_i\in F_i\) so that the colors \(\phi(y_i)\) satisfy \(\phi(y_i)\neq \phi(y_j)\) if \(i\neq j\text{.}\) Builder now presents a new vertex \(x\) and declares \(x\) adjacent to all vertices in \(\{y_1,y_2,\dots,y_k\}\) and to no other vertices. Clearly, the resulting graph is a forest and Assigner is forced to use a color for \(x\) distinct from the \(k\) colors she assigned previously to the vertices in \(\{y_1,y_2,\dots, y_k\}\text{.}\) Also, the total number of vertices is at most \(1+[1+2+4+8+\dots+2^{k-1}]=2^k\text{.}\)
Discussion 16.3.
Bob reads the proof and asks whether it was really necessary to treat the cases \(k=2\) and \(k=3\) separately. Wasn't it enough just to note that the case \(k=1\) holds trivially. Carlos says yes.
Subsection 16.1.1 Doing Relatively Well in an On-Line Setting
Theorem 16.2 should be viewed as a negative result. It is hard to imagine a family of graphs easier to color than forests, yet in an on-line setting, graphs in this family are difficult to color. On the other hand, in certain settings, one can do reasonably well in an on-line setting, perhaps not as well as the true optimal off-line result but good enough to be useful. Here we present a particularly elegant example involving partially ordered sets.
Recall that a poset \(P\) of height \(h\) can be partitioned into \(h\) antichains—by recursively removing the set of minimal elements. But how many antichains are required in an on-line setting? Now Builder constructs a poset \(P\) one point at a time, while Assigner constructs a partition of \(P\) into antichains. At each round, Builder will present a new point \(x\text{,}\) and list those points presented earlier that are, respectively, less than \(x\text{,}\) greater than \(x\) and incomparable with \(x\text{.}\) Subsequently, Assigner will assign \(x\) to an antichain. This will be done either by adding \(x\) to an antichain already containing one or more of the points presented previously, or by assigning \(x\) to a new antichain.
Theorem 16.4.
For each \(h\ge1\text{,}\) there is a on-line strategy for Assigner that will enable her to partition a poset \(P\) into at most \(\binom{h+1}{2}\) antichains, provided the height of \(P\) is at most \(h\text{.}\)
Proof.
It is important to note that Assigner does not need to know the value \(h\) in advance. For example, Builder may have in mind that ultimately the value of \(h\) will be \(300\text{,}\) but this information does not impact Assigner's strategy.
When the new point \(x_n\) enters \(P\text{,}\) Assigner computes the values \(r\) and \(s\text{,}\) where \(r\) is the largest integer for which there exists a chain \(C\) of \(r\) points in \(\{x_1,x_2,\dots,x_n\}\) having \(x_n\) as its least element. Also, \(s\) is the largest integer for which there exists a chain \(D\) of \(s\) points in \(\{x_1,x_2,\dots,x_n\}\) having \(x_n\) as its largest element. Assigner then places \(x\) in a set \(A(r,s)\text{,}\) claiming that any two points in this set are incomparable. To see that this claim is valid, consider the first moment where Builder has presented a new point \(x\text{,}\) Assigner places \(x\) in \(A(r,s)\) and there is already a point \(y\) in \(A(r,s)\) for which \(x\) and \(y\) are comparable.
When \(y\) was presented, there was at that moment in time a chain \(C'\) of \(r\) points having \(y\) as its least element. Also, there was a chain \(D\) of \(s\) points having \(y\) as its greatest element.
Now suppose that \(y>x\) in \(P\text{.}\) Then we can add \(x\) to \(C'\) to form a chain of \(r+1\) points having \(x\) as its least element. This would imply that \(x\) is not assigned in \(A(r,s)\text{.}\) Similarly, if \(y\lt x\) in \(P\text{,}\) then we may add \(x\) to \(D'\) to form a chain of \(s+1\) points having \(x\) as its greatest element. Again, this would imply that \(x\) is not assigned to \(A(r,s)\text{.}\)
So Assigner has indeed devised a good strategy for partitioning \(P\) into antichains, but how many antichains has she used? This is just asking how many ordered pairs \((i,j)\) of positive integers are there subject to the restriction that \(i+j-1\le h\text{.}\) And we learned how to solve this kind of question in Chapter 2. The answer of course is \(\binom{h+1}{2}\text{.}\)
The strategy for Assigner is so simple and natural, it might be the case that a more complex strategy would yield a more efficient partitioning. Not so.
Theorem 16.5. Szemerédi.
For every \(h\ge1\text{,}\) there is a strategy \(S_h\) for builder that will enable him to build a poset \(P\) of height \(h\) so that assigner is forced to (1) use at least \(\binom{h+1}{2}\) antichains in partitioning \(P\text{,}\) and (2) use at least \(h\) different antichains on the set of maximal elements.
Proof.
Strategy \(S_1\) is just to present a single point. Now suppose that the theorem holds for some integer \(h\ge1\text{.}\) We show how strategy \(S_{h+1}\) proceeds.
First Builder follows strategy \(S_h\) to form a poset \(P_1\text{.}\) Then he follows it a second time for form a poset \(P_2\text{,}\) with all points of \(P_1\) incomparable to all points in \(P_2\text{.}\) Now we consider two cases. Suppose first that Assigner has used \(h+1\) or more antichains on the set of maximal elements of \(P_1\cup P_2\text{.}\) In this case, he follows strategy \(S_h\) a third time to build a poset \(P_3\) with all points of \(P_3\) less than all maximal elements of \(P_1\cup P_2\) and incomparable with all other points.
Clearly, the height of the resulting poset is at most \(h+1\text{.}\) Also, Assigner must use \(h+1+\binom{h+1}{2}=\binom{h+2}{2}\) antichains in partitioning the poset and she has used \(h+1\) on the set of maximal elements.
So it remains only to consider the case where Assigner has used a set \(W\) of \(h\) antichains on the maximal elements of \(P_1\text{,}\) and she has used exactly the same \(h\) antichains for the maximal elements of \(P_2\text{.}\) Then Builder presents a new point \(x\) and declares it to be greater than all points of \(P_1\) and incomparable with all points of \(P_2\text{.}\) Assigner must put \(x\) in some antichain which is not in \(W\text{.}\)
Builder then follows strategy \(S_h\) a third time, but now all points of \(P_3\) are less than \(x\) and the maximal elements of \(P_2\text{.}\) Again, Assigner has been forced to use \(h+1\) different antichains on the maximal elements and \(\binom{h+2}{2}\) antichains altogether.