1. Introduction

In ?) it is claimed that

2. A Note on Notation

It should be noted that in this paper, the notation S_{2}(t) is used to denote the size of the 2-stacks at time t. This is different than previous papers were S_{t} was used to denote the number of items not in a 3-stack.

3. One-Stacks Stay Small Until n^{1/3}

For a vertex to be a member of a 1-stack at time t, it must have been chosen twice to have a color from its color list removed. Each of the other t − 2 times it was not selected to be colored and was not adjacent to a vertex being colored. This means that the probability of a given vertex being in a 1-stack at time t is at least

p_{1}(t) = \binom{t}{2} (\frac{c}{n})^{2} (1 − \frac{c}{n})^{t−2} .

This implies that the number of 1-stack vertices up to time m is stochastically dominated by

∑_{t=1}^{m} np_{1}(t) ≤ ∑_{t=1}^{m} \frac{t^{2}}{2} \frac{c^{2}}{n} = \frac{c^{2}}{6n}m^{3} + o(n)

Therefore, for large enough n, up to time n^{1/3}, the probability that the 1stack size is greater than zero is small.

4. The Upper Bound of S_{2}(t)

For t where 1 ≤ t ≤ nε, the number of 3-color vertices that become 2-color vertices is stochastically dominated by

b_{t} ∼ Bin(n, c/n).

This implies

max_{1≤t≤nε} S_{2}(t) ≤ ∑_{t=1}^{nε} b_{t}

and therefore to get an upper bound on the biggest S_{2}(t) it is sufficient to get a bound on the size of the sum of b_{t}. This can be done by centering each of the b_{t} values and then applying the Bennett Inequality

ℙ {∑_{t=1}^{nε} b_{t} ≥ ν} = ℙ {∑_{t=1}^{nε} b_{t} − nεc ≥ ν − nεc}

≤ exp (−\frac{(ν − nεc)^{2}}{nεc(1 − c/n)}ψ (\frac{(ν − nεc)}{εc(1 − c/n)}))

where

ψ(x) = 1 + x^{−1} + x^{−2} log(x + 1).

As ν gets larger than the expected value of the sum of b_{t}’s, that is ν > nεc, there is a sharp decrease in the probability of getting an S_{2}(t) larger than ν.