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