## Section16.1On-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.

### Example16.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{.}$$

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{.}$$

### Discussion16.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.

### Subsection16.1.1Doing 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.

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.

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.