lemmatheorem lemma propositiontheorem proposition

# An improvement of the Beck–Fiala theorem

Boris Bukh

###### Abstract

In 1981 Beck and Fiala proved an upper bound for the discrepancy of a set
system of degree $d$ that is independent of the size of the ground set. In the
intervening years the bound has been decreased from $2d-2$ to $2d-4$. We
improve the bound to $2d-\log^{*}d$.
MSC classes: 05D05, 11K38, 05C15

##  1 Introduction

Let $X$ be a finite set, and let $\mathcal{F}$ be a family of subsets of $X$.
A _two-coloring_ of $X$ is a function $\chi\colon X\to\\{-1,+1\\}$. For
$S\subset X$ we define
$\chi(S)\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\sum_{x\in S}\chi(x)$.
The _discrepancy_ of a coloring $\chi$ is

$\operatorname{disc}\chi\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\max_{S\in\mathcal{F}}\,\lvert\chi(S)\rvert.$

The discrepancy of $\mathcal{F}$ is then defined as the discrepancy of an
optimal coloring,

$\operatorname{disc}\mathcal{F}\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\min_{\chi}\operatorname{disc}\chi.$

The _degree_ of $x\in X$ in the family $\mathcal{F}$ is the number of sets
that contain $x$. Over 30 years ago Beck and Fiala [2] proved that if the
maximum degree of vertices in $\mathcal{F}$ is $d$, then
$\operatorname{disc}\mathcal{F}\leq 2d-2$. The remarkable feature of the
result is that it depends neither on the number of sets in $\mathcal{F}$ nor
on the size of $X$. If dependence on these quantities is permitted, the best
result is due to Banaszczyk [1, Theorem 2], and asserts that
$\operatorname{disc}\mathcal{F}\leq c\sqrt{d\log\lvert X\rvert}$. Let
$f(d)\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\max\operatorname{disc}\mathcal{F}$,
where the maximum is taken over all set families of degree at most $d$. In [2]
Beck and Fiala conjectured that $f(d)=O(\sqrt{d})$. If true, the conjecture
would be a strengthening of Spencer’s six deviation theorem [8]. A related,
but stronger conjecture was made by János Komlós [8, p. 680]. A relaxation of
Komlós’s conjecture to vector-valued colorings has been established by Nikolov
[7]. For a general overview of discrepancy theory see books [6, 4].

The original Beck–Fiala bound has been improved twice. First, Bednarchak and
Helm [3] proved that $f(d)\leq 2d-3$ for $d\geq 3$. Then Helm [5]
claimed111The author has been unable to understand Helm’s proof, or to reach
Martin Helm for clarification. that $f(d)\leq 2d-4$ for all sufficiently large
$d$. In this paper, we improve the bound by a function growing to infinity
with $d$:

######  Theorem.

For all sufficiently large $d$ we have

$f(d)\leq 2d-\log^{*}d.$

Here
$\log^{*}x\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\min\\{t:\log^{(t)}x\leq
1\\}$, where $\log^{(1)}x=\log x$ and $\log^{(t+1)}x=\log^{(t)}\log x$, and
the logarithms are to the base $2$.

##  2 Proof ideas

Like the proofs in [2, 3, 5], our proof uses the method of floating colors. In
this section we present the method informally, and explain the main difficulty
in its application. We present the three main ideas of our proof, and how
these ideas address the difficulty. In following sections we give the proof in
full.

A _floating coloring_ is a function $\chi\colon X\to[-1,+1]$. The value
$\chi(x)$ is the “color” of $x$ according to $\chi$. If $-1<\chi(x)<+1$, we
consider the color of $x$ “floating”, whereas $\chi(x)\in\\{-1,+1\\}$ means
that the color of $x$ is “frozen”. Once frozen, the elements never change
their color again. All the floating elements eventually turn frozen, giving a
genuine two-coloring of $X$. Our goal is to ensure that the discrepancy of
that coloring does not exceed $2d-\Delta$, where $2d-\Delta$ is the desired
bound on $f(d)$.

The purpose of evolving coloring $\chi$ gradually is to focus on the dangerous
sets. A set $S\in\mathcal{F}$ is _dangerous_ if there is a way to freeze the
floating elements to make the discrepancy exceed $2d-\Delta$. Only dangerous
sets matter in the subsequent evolution of $\chi$. In the argument of Beck and
Fiala, an invariant is maintained: for each dangerous set $S\in\mathcal{F}$ we
have $\chi(S)=0$. _Size of a dangerous set_ is the number of floating elements
in the set. It is easily shown that if the average size of dangerous sets
exceeds $d$, then the number of floating colors exceeds the number of
dangerous sets; hence, there is a way to perturb the floating colors, in a
manner that preserves the invariant. The coloring is perturbed until one of
the floating elements becomes frozen, and the process repeats.

The dangerous sets of size at most $d$ thus pose a natural problem. If not for
them, the process would never stop, and the result is a coloring of
discrepancy at most $2d-\Delta$. Let us call these particularly troublesome
dangerous sets _nasty_. The sum of the floating elements of a nasty set is
nearly $\pm d$, for otherwise the floating elements do not have enough “room”
to change much. Hence, most elements of a nasty set are close to $\pm 1$. The
_first idea_ thus is to forcibly round elements $x$ such that
$\lvert\chi(x)\rvert>1-\alpha$, where $\alpha$ is a small number. Forcible
rounding of only $O(\Delta)$ elements in a nasty set is enough to render the
set benign.

Forcible rounding introduces an “error” of at most $\alpha$ into the invariant
$\chi(S)=0$. Therefore, forcible rounding is tolerable only if the rounded
element is not contained in any very large set. The _second idea_ consists in
noting that if there are nasty sets, but no elements in them can be forcibly
rounded, then the nasty sets must be highly overlapping. Indeed, it is
possible to perturb $\chi$ if the average size of sets exceeds $d$, and the
large sets that prevent forcible rounding contribute a lot to this average.
Making this idea precise requires a charging argument, whose details are in
section 5.

We take advantage of the overlap in the nasty sets by selecting an element $b$
that is common to many nasty sets, and singling out the nasty sets containing
$b$ into a separate _cohort_. We call $b$ the cohort’s _banner_. Since
perturbation of $\chi$ might get stuck more than once, we might create several
cohorts over the course of our algorithm. We shall treat each cohort as a
fully autonomous set system. Thus it will be subject to its own invariants,
and will impose its own linear conditions in the perturbation step.

Since cohorts consist of nasty sets, the average set size in a cohort is less
than $d$, and so for the perturbation step to be possible, a cohort cannot
impose as many linear conditions as there are sets in a cohort. The _third
idea_ is to use the few available linear conditions to render some sets in a
cohort benign. The benign sets pose no threat, but still contribute elements
towards the average set size in a cohort because they contain the banner. (At
this point the term “average set size” becomes a misnomer since in the formula
$\frac{\text{number of elements}}{\text{number of sets}}$ the benign sets
contribute to the numerator, but not to the denominator. However we will keep
on using the term.)

To understand how linear conditions in a cohort work, we imagine that sets in
a cohort engage in an elimination tournament. When two nasty sets $S$ and
$S^{\prime}$ are matched against one another instead of two invariants
$\chi(S)=C$ and $\chi(S^{\prime})=C^{\prime}$, there is just one invariant
$\chi(S)+\chi(S^{\prime})=C+C^{\prime}$. The match is declared finished when
the total size of $S$ and $S^{\prime}$ drops below $d$. The loser is the
smaller of $S$ and $S^{\prime}$, for it can be shown that it became benign.
The winner, on the other hand, might have even larger error in $\chi(S)$ after
the end of the match. Fortunately for us, the winner also gets a virtual
trophy — the banner of the loser. This means that for purposes of computing
the average set size we can count the winner’s banner element twice. In
general, a winner of $D$ matches will have $2^{D}$ virtual banner elements.

The final obstacle is the possibility that the banner of a cohort might get
frozen. In that case the defeated sets cease to contribute to the average set
size, and the argument collapses. The rescue comes from the fact that when a
cohort was formed the banner was an element satisfying
$\lvert\chi(b)\rvert>1-\alpha$. So, by replacing the invariant $\chi(S)=C$ by
$\chi(S)+\beta\chi(b)=\hat{C}$, where $\beta$ is very large, we can ensure
that $b$ can be frozen only to the value that we originally attempted to round
it to. So, the banner can get frozen only in the favourable direction. If that
happens, the sets in the cohort become a bit less dangerous, but not yet
benign; so we dissolve the cohort, and return the sets to the general pool,
where they can become parts of new cohorts. After being in a cohort $\Delta$
times, a set is guaranteed to be benign, and so the error in $\chi$ cannot
explode.

Despite its length, the sketch above misses a couple of crucial technical
moments that can be seen only from details. Most crucially, it does not
explain why the final bound, $\log^{*}d$, is pitifully tiny. It is because the
winners not only accumulate virtual banners, but also lose some of their own
elements to freezing.

It turns out that the banner accumulation happens faster, but the reason is
subtle: Let $R_{D}$ be the maximal possible error in $\chi$ in a set that
defeated $D$ sets. Crudely, we may think of $R_{D}$ as the number of elements
that a set lost due to freezing. One can show that it satisfies an approximate
recurrence $R_{D+1}\approx 2R_{D}-2^{D}$, where the term $2^{D}$ reflects
$2^{D}$ virtual banners of a loser. Though $R_{D}$ eventually becomes
negative, it grows exponentially at first. In particular, a cohort might get
disbanded when $\chi$ is exponential in $R_{0}$. For any single set, this
might happen up to $\Delta$ times, and so the error might grow to be a tower
of height $\Delta$.

### Acknowledgments.

The author owes the development some of the ideas in this paper to discussions
with Po-Shen Loh, to whom he is very grateful. The author is also very
thankful to the referee whose careful reading of the paper helped to eliminate
some hard-to-catch mistakes. All the remaining mistakes remain responsibility
of the author.

##  3 Two-coloring algorithm

### Data.

The only data that the Beck–Fiala algorithm remembers is the floating coloring
$\chi\colon X\to[-1,+1]$. The data that our algorithm uses is more elaborate:

Data |  Informal meaning
---|---
Function $\chi\colon X\to[-1,1]$ |  Floating coloring
Partition of the family $\mathcal{F}$ as $\mathcal{F}=\mathcal{B}\cup\mathcal{G}\cup\mathcal{C}_{1}\cup\dotsb\cup\mathcal{C}_{m}$ |  $\mathcal{B}$ contains benign sets
$\mathcal{G}$ is a general pool
$\mathcal{C}_{1},\dotsc,\mathcal{C}_{m}$ are cohorts
Elements $b_{1},\dotsc,b_{m}\in X$ |  Banners for the cohorts
Signs $\varepsilon_{1},\dotsc,\varepsilon_{m}\in\\{-1,+1\\}$ |  The color of banner $b_{i}$ is close to $\varepsilon_{i}$
Integers $r_{1},\dotsc,r_{m}\in\\{0,\dotsc,\Delta-1\\}$ |  The larger $r_{i}$ is, the less dangerous $\mathcal{C}_{i}$ is
Set families $M_{1},\dotsc,M_{m}$ |  $M_{i}$ is a current matching in a cohort $\mathcal{C}_{i}$
Integer $D[S]\in\\{0,1,\dotsc\\}$ for each $S\in\mathcal{C}_{i}$ |  Set $S$ has defeated $D[S]$ sets in its cohort

### Notation.

To describe the algorithm, and the invariants that data satisfies, we need
notation which we introduce now. An element $x\in X$ such that
$\chi(x)\in\\{-1,+1\\}$ is called _frozen_ ; otherwise $x$ is _floating_. With
this in mind, here is our notation:

$\displaystyle\operatorname{Sz}(S)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\sum_{\makebox[21.0972pt]{$\scriptstyle
x\in S\text{ floating}$}}1$ $\displaystyle\quad\text{number of floating
elements in $S$},$ $\displaystyle\chi(S)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\sum_{\makebox[21.0972pt]{$\scriptstyle
x\in S$}}\chi(x)$ $\displaystyle\quad\text{current color (discrepancy) of
$S$},$ $\displaystyle\operatorname{Fr}(S)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\sum_{\makebox[21.0972pt]{$\scriptstyle
x\in S\text{ frozen}$}}\chi(x)$ $\displaystyle\quad\text{total color of frozen
elements in $S$},$ $\displaystyle\operatorname{Fl}(S)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\sum_{\makebox[21.0972pt]{$\scriptstyle
x\in S\text{ floating}$}}\chi(x)$ $\displaystyle\quad\text{total color of
floating elements in $S$},$ $\displaystyle\mathop{Th}\nolimits_{-}(S)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\operatorname{Sz}(S)-\operatorname{Fr}(S)$
$\displaystyle\quad\text{threat of negative discrepancy},$
$\displaystyle\mathop{Th}\nolimits_{+}(S)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\operatorname{Sz}(S)+\operatorname{Fr}(S)$
$\displaystyle\quad\text{threat of positive discrepancy},$
$\displaystyle\mathop{Th}\nolimits(S)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\max\bigl{(}\mathop{Th}\nolimits_{-}(S),\mathop{Th}\nolimits_{+}(S)\bigr{)}$
$\displaystyle\quad\text{threat of discrepancy}.$

For later use we record two identities,

$\displaystyle\mathop{Th}\nolimits_{-}(S)$
$\displaystyle=\operatorname{Sz}(S)+\operatorname{Fl}(S)-\chi(S),$ (1)
$\displaystyle\mathop{Th}\nolimits_{+}(S)$
$\displaystyle=\operatorname{Sz}(S)-\operatorname{Fl}(S)+\chi(S).$ (2)

The algorithm proceeds in stages. To refer to the data at a particular stage
we use superscripts. For example, $\operatorname{Sz}^{(n)}(S)$ and
$D^{(n)}[S]$ denote the values of $\operatorname{Sz}(S)$ and $D[S]$
respectively at the $n$’th stage of the algorithm. The notation for other
quantities follows the same pattern.

### Constants.

In the proof we use several constants, which we introduce now. Their informal
meanings appear to the right of their definitions.

$\displaystyle\Delta$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\log^{*}d$
$\displaystyle\quad\text{A set $S$ is benign if $\mathop{Th}\nolimits(S)\leq
2d-\Delta$},$ $\displaystyle\alpha$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\tfrac{1}{4}$
$\displaystyle\quad\text{The threshold for rounding is }1-\alpha,$
$\displaystyle\operatorname{Tw}_{r}$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\begin{cases}\Delta&\text{if
}r\in\\{0,1\\}\\\ 2^{8\operatorname{Tw}_{r-2}}&\text{otherwise}\end{cases}$
$\displaystyle\quad\text{Tower function controlling blowup of
}\operatorname{Th},$ $\displaystyle\beta_{r}$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}4\operatorname{Tw}_{r}$
$\displaystyle\quad\text{Clamping factor for cohorts with }r_{i}=r,$
$\displaystyle W$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}d/(64\Delta^{2}\operatorname{Tw}_{\Delta-1})$
$\displaystyle\quad\text{Size of the newly-created cohorts},$ $\displaystyle
R_{D}$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}(D-2)2^{D}-(2^{D}-1)\Delta+2$
$\displaystyle\quad\text{This term controls $\chi(S)$ in a cohort}.$ (3)

Of these constants, the most important is $R_{D}$. The whole proof is based on
the fact that $R_{D}$ is eventually larger than $C2^{D}$ for any constant $C$.

In what follows we assume that $d$ is so large that $\Delta>10$ holds.

The choice of constants is fairly flexible, and the chosen constants are far
from unique or optimal. For example, any choice for $\alpha$ from
$\operatorname{Tw}_{\Delta}/d$ to a constant less than $1$ would have worked
(with minor changes in the other constants). To avoid burdening the main
exposition, we record the needed inequalities between constants here (valid
for all $r<\Delta$):

a) $\displaystyle\Delta\leq\operatorname{Tw}_{r}$ b)
$\displaystyle\operatorname{Tw}_{r}+\Delta<\beta_{r}(1-\alpha)$ (4) c)
$\displaystyle(\beta_{r}+1)\alpha+\operatorname{Tw}_{r}+\Delta\leq
4\operatorname{Tw}_{r}$ d) $\displaystyle 16\operatorname{Tw}_{r}\leq
2^{16\operatorname{Tw}_{r-2}}$ e)
$\displaystyle\operatorname{Tw}_{\Delta-1}\leq\log\log d$ f) $\displaystyle
2\operatorname{Tw}_{\Delta-1}+(2-\alpha)\Delta\leq\alpha d$ g) $\displaystyle
d\geq
W\Delta\bigl{(}\Delta+2\operatorname{Tw}_{\Delta-1}+2\bigr{)}(8+4\Delta)$ h)
$\displaystyle 2^{8\operatorname{Tw}_{r}+6}\operatorname{Tw}_{r}<W$ i)
$\displaystyle{(1-\tfrac{1}{2}\alpha)(2d-\Delta)\geq(1-\tfrac{1}{2}\alpha)d+2^{4\operatorname{Tw}_{r}+1}\beta_{r}\alpha+2^{4\operatorname{Tw}_{r}+1}\operatorname{Tw}_{r}+2^{4\operatorname{Tw}_{r}}\Delta}$
j) $\displaystyle\mathchoice{\hbox
to0.0pt{$\displaystyle{\operatorname{Tw}_{r+2}\geq
2^{4\operatorname{Tw}_{r}+1}\beta_{r}\alpha+2^{4\operatorname{Tw}_{r}+1}\operatorname{Tw}_{r}+2^{4\operatorname{Tw}_{r}}\Delta}$\hss}}{\hbox
to0.0pt{$\textstyle{\operatorname{Tw}_{r+2}\geq
2^{4\operatorname{Tw}_{r}+1}\beta_{r}\alpha+2^{4\operatorname{Tw}_{r}+1}\operatorname{Tw}_{r}+2^{4\operatorname{Tw}_{r}}\Delta}$\hss}}{\hbox
to0.0pt{$\scriptstyle{\operatorname{Tw}_{r+2}\geq
2^{4\operatorname{Tw}_{r}+1}\beta_{r}\alpha+2^{4\operatorname{Tw}_{r}+1}\operatorname{Tw}_{r}+2^{4\operatorname{Tw}_{r}}\Delta}$\hss}}{\hbox
to0.0pt{$\scriptscriptstyle{\operatorname{Tw}_{r+2}\geq
2^{4\operatorname{Tw}_{r}+1}\beta_{r}\alpha+2^{4\operatorname{Tw}_{r}+1}\operatorname{Tw}_{r}+2^{4\operatorname{Tw}_{r}}\Delta}$\hss}}$

Proofs: (a) is proved by induction on $r$; (b) and (c) are implied by (a); (d)
follows from $1\leq\Delta$ and (a); (e) is true because
$\log^{*}(16\operatorname{Tw}_{r})\leq r/2+\log^{*}(16\Delta)$ by induction on
$r$, and because $\Delta/2+\log^{*}(16\Delta)\leq\Delta-1$ for $\Delta>10$;
(f) follows from (e); (g) follows from (e) and the definition of W; (h) is
implied by (a) and (e); (i) follows from (a) and three uses of (e) to bound
each of the summands on the right; (j) is a consequence of (a) and the
definition of $\operatorname{Tw}_{r}$.∎

### Invariants.

The data satisfies the following fourteen invariants. Note that the invariants
are symmetric with respect to flipping the coloring, i.e., with respect to the
inversion $\chi\mapsto-\chi$, $\varepsilon_{i}\mapsto-\varepsilon_{i}$. Our
algorithm is also symmetric in this sense. We suggest that the reader examine
invariants $1$, $2$, $3$, $4$, $5$, $6$ and $7$, and refer to other invariants
later.

  1. Invariant $1$:

If $x\in X$ is frozen in coloring $\chi^{(i)}$, then it is also frozen in
$\chi^{(j)}$ for all $j>i$.

  2. Invariant $2$:

Every set $S\in\mathcal{B}$ satisfies $\mathop{Th}\nolimits(S)\leq 2d-\Delta$.

  3. Invariant $3$:

Every set $S\in\mathcal{F}$ satisfying $\operatorname{Sz}(S)\leq d$ also
satisfies $\mathop{Th}\nolimits(S)\leq 2d$.

  4. Invariant $4$:

Element $b_{i}$ is common to all the sets in $\mathcal{C}_{i}$.

  5. Invariant $5$:

Family $M_{i}$ is a matching on $\mathcal{C}_{i}$, i.e., $M_{i}$ consists of
pairs of sets from $\mathcal{C}_{i}$, and the pairs in $M_{i}$ are disjoint.
Note that the matching is not perfect: some sets in $\mathcal{C}_{i}$ might be
unmatched.

  6. Invariant $6$:

If $\\{S,S^{\prime}\\}\in M_{i}$, then $D[S]=D[S^{\prime}]$.

  7. Invariant $7$:

If $S\in\mathcal{C}_{i}$, then $\operatorname{Sz}(S)\leq d+1-2^{D[S]}$.

  8. Invariant $8^{+}$:

If $S\in\mathcal{C}_{i}$, and $\varepsilon_{i}=+1$ then
$\mathop{Th}\nolimits_{+}(S)\leq\Delta+2-2^{D[S]+1}$.

  9. Invariant $8^{-}$:

If $S\in\mathcal{C}_{i}$, and $\varepsilon_{i}=-1$ then
$\mathop{Th}\nolimits_{-}(S)\leq\Delta+2-2^{D[S]+1}$.

  10. Invariant $9$:

If element $b\in X$ is a banner of $k$ cohorts
$\mathcal{C}_{i_{1}},\dotsc,\mathcal{C}_{i_{k}}$, then $b$ is contained in at
least $\sum_{j=1}^{k}\bigl{(}W-\lvert\mathcal{C}_{i_{j}}\rvert\bigr{)}$ sets
of $\mathcal{B}$.

  11. Invariant $10$:

For each cohort $\mathcal{C}_{i}$ we have
$\sum_{S\in\mathcal{C}_{i}}2^{D[S]}\leq W$.

  12. Invariant $11^{+}$:

If $S\in\mathcal{G}$ and $\mathop{Th}\nolimits_{+}(S)=2d-r$, the

$\displaystyle\begin{aligned} \phantom{-}\chi(S)&\leq 0&&\quad\text{if
}r<\Delta\text{ and }\operatorname{Sz}(S)\geq d,\\\
\phantom{-}\chi(S)&\leq\operatorname{Tw}_{r}-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}(S)&&\quad\text{if
}r<\Delta\text{ and }\operatorname{Sz}(S)\leq d.\\\ \end{aligned}$

If $S\in\mathcal{G}$ and $\mathop{Th}\nolimits_{-}(S)=2d-r$, then
$\displaystyle\begin{aligned} -\chi(S)&\leq 0&&\quad\text{if }r<\Delta\text{
and }\operatorname{Sz}(S)\geq d,\\\
-\chi(S)&\leq\operatorname{Tw}_{r}-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{+}(S)&&\quad\text{if
}r<\Delta\text{ and }\operatorname{Sz}(S)\leq d.\\\ \end{aligned}$

If $\varepsilon_{i}=-1$, and a set $S\in\mathcal{C}_{i}$ is not in any edge of
$M_{i}$, and $D=D[S]$ then
$\displaystyle\phantom{-}\chi(S)+2^{D}\beta_{r_{i}}\bigl{(}\chi(b_{i})+1-\alpha\bigr{)}\leq
2^{D}\operatorname{Tw}_{r_{i}}-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}(S)-R_{D}.$

If $\varepsilon_{i}=+1$, and a set $S\in\mathcal{C}_{i}$ is not in any edge of
$M_{i}$, and $D=D[S]$ then
$\displaystyle-\chi(S)-2^{D}\beta_{r_{i}}\bigl{(}\chi(b_{i})-1+\alpha\bigr{)}\leq
2^{D}\operatorname{Tw}_{r_{i}}-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{+}(S)-R_{D}.$

If $\varepsilon_{i}=-1$, and $\\{S,S^{\prime}\\}\in M_{i}$, and
$D=D[S]=D[S^{\prime}]$ then
$\displaystyle\phantom{-}\chi(S)+\chi(S^{\prime})+2^{D+1}\beta_{r_{i}}\bigl{(}\chi(b_{i})+1-\alpha\bigr{)}\leq
2^{D+1}\operatorname{Tw}_{r_{i}}-\tfrac{1}{2}\alpha\bigl{(}\mathop{Th}\nolimits_{-}(S)+\mathop{Th}\nolimits_{-}(S^{\prime})\bigr{)}-2R_{D}.$

If $\varepsilon_{i}=+1$, and $\\{S,S^{\prime}\\}\in M_{i}$, and
$D=D[S]=D[S^{\prime}]$ then
$\displaystyle-\chi(S)-\chi(S^{\prime})-2^{D+1}\beta_{r_{i}}\bigl{(}\chi(b_{i})-1+\alpha\bigr{)}\leq
2^{D+1}\operatorname{Tw}_{r_{i}}-\tfrac{1}{2}\alpha\bigl{(}\mathop{Th}\nolimits_{+}(S)+\mathop{Th}\nolimits_{+}(S^{\prime})\bigr{)}-2R_{D}.$

If $S\in\mathcal{C}_{i}$, then $D[S]\leq 4\operatorname{Tw}_{r_{i}}$.

### Initialization of the algorithm.

At start, we set $\chi=0$, $\mathcal{B}=\emptyset$, $\mathcal{G}=\mathcal{F}$,
$\mathcal{C}=\emptyset$ and $m=0$.

### Steps of the algorithm.

The algorithm of Beck–Fiala makes progress in two ways: by using linear
perturbation of the current floating coloring, and by discarding the benign
sets. Our algorithm uses nine ways to make progress. We refer to these ways as
_steps_. For each step, there is a condition that must hold for it to be
executed. The steps are ordered, and the choice of a step to be executed is
greedy: we always execute the first step whose condition is satisfied. For
example, step 5 is executed only if steps 1 through 4 cannot be executed.

Step 1 (Moving benign sets from $\mathcal{G}$ to $\mathcal{B}$):

Execution condition: There is an $S\in\mathcal{G}$ such that
$\mathop{Th}\nolimits(S)\leq 2d-\Delta$.

Step description: Move $S$ from $\mathcal{G}$ to $\mathcal{B}$.

Step 2 (Removing empty cohorts):

Execution condition: There is a cohort $\mathcal{C}_{i}$ such that
$\mathcal{C}_{i}=\emptyset$.

Step description: Remove cohort $\mathcal{C}_{i}$ by deleting
$\mathcal{C}_{i}$, $b_{i}$, $\varepsilon_{i}$, $r_{i}$ and $M_{i}$ and
renumbering the remaining cohorts appropriately.

Step 3 (Rounding elements that are safe to round):

Execution condition:  One of the following two conditions holds:

$+$) There is an $x\in X$ such that $\chi(x)>1-\alpha$ and there exists no
$S\in\mathcal{G}$ containing $x$ that satisfies $\operatorname{Sz}(S)\geq d+1$
and $\mathop{Th}\nolimits_{+}(S)>2d-\Delta$.

$-$) There is an $x\in X$ such that $-\chi(x)>1-\alpha$ and there exists no
$S\in\mathcal{G}$ containing $x$ that satisfies $\operatorname{Sz}(S)\geq d+1$
and $\mathop{Th}\nolimits_{-}(S)>2d-\Delta$.

Step description: In case ($+$), set $\chi(x)$ equal to $+1$. In case ($-$),
set $\chi(x)$ equal to $-1$.

Step 4 (Moving benign cohort sets to $\mathcal{B}$):

Execution condition: There is an $S\in\mathcal{C}_{i}$ that is not a part of
$M_{i}$ and such that $\mathop{Th}\nolimits(S)\leq 2d-\Delta$.

Step description: Move $S$ to $\mathcal{B}$.

Step 5 (Disbanding cohorts whose banners were frozen):

Execution condition: For some $i$ we have $\chi(b_{i})\in\\{-1,+1\\}$.

Step description: Disband cohort $\mathcal{C}_{i}$ by moving all sets in
$\mathcal{C}_{i}$ to $\mathcal{G}$, and then removing cohort as in section 3.

Step 6 (Declaring some matches finished):

Execution condition: There is an edge $\\{S,S^{\prime}\\}\in M_{i}$ with
$D=D[S]=D[S^{\prime}]$ such that

$\operatorname{Sz}(S)+\operatorname{Sz}(S^{\prime})+2^{D+1}-2\leq d.$ (5)

Step description: Without loss of generality,
$\operatorname{Sz}(S)\geq\operatorname{Sz}(S^{\prime})$. Perform the next
three actions: 1) Remove edge $\\{S,S^{\prime}\\}$ from $M_{i}$. 2) Move
$S^{\prime}$ to $\mathcal{B}$. 3) If $\mathop{Th}\nolimits(S)\leq 2d-\Delta$,
move $S$ to $\mathcal{B}$ as well. Otherwise, increment $D[S]$.

Step 7 (Matching unmatched sets in a cohort):

Execution condition: There are sets $S,S^{\prime}\in\mathcal{C}_{i}$ that are
not part of $M_{i}$ and such that $D[S]=D[S^{\prime}]$.

Step description: Add edge $\\{S,S^{\prime}\\}$ to $M_{i}$.

Step 8 (Linear perturbation):

Execution condition: Let
$N=\lvert\mathcal{G}\rvert+\sum_{i=1}^{m}\bigl{(}\lvert\mathcal{C}_{i}\rvert-\lvert
M_{i}\rvert\bigr{)}$. Execute this step only if the number of floating
elements exceeds $N$.

Step description: We will generate a set $E$ of $N$ linear equations in values
of an unknown function $\tau\colon X\to\mathbb{R}$. The equations will have
the property that the current floating coloring $\chi$ satisfies them all.

\- Each $S\in\mathcal{G}$ generates the equation $\tau(S)=\chi(S)$. \- Each
$S\in\mathcal{C}_{i}$ that is not in $M_{i}$ generates the equation

$\tau(S)+2^{D}\beta_{r_{i}}\tau(b_{i})=\chi(S)+2^{D}\beta_{r_{i}}\chi(b_{i}).$

\- Each edge $\\{S,S^{\prime}\\}\in M_{i}$ generates the equation

$\tau(S)+\tau(S^{\prime})+2^{D+1}\beta_{r_{i}}\tau(b_{i})=\chi(S)+\chi(S^{\prime})+2^{D+1}\beta_{r_{i}}\chi(b_{i}).$

Let $E$ be the resulting set of equations. Note that $\lvert E\rvert=N$. Let

$A\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\bigl{\\{}\tau:\tau\text{
satisfies all of }E,\text{ and }\tau(x)=\chi(x)\text{ whenever
}\chi(x)\in\\{-1,+1\\}\,\bigr{\\}}$

Since the number of floating elements exceeds $N$, set $A$ is an affine space
of positive dimension. Since $A$ contains $\chi$, it also must contain a point
$\tau\in[-1,+1]^{X}$ in which more elements are frozen than in the current
value of $\chi$. Set $\chi$ to that $\tau$.

Step 9 (Creating a new cohort):

Execution condition: Not all sets are in $\mathcal{B}$, i.e.,
$\mathcal{F}\neq\mathcal{B}$.

Step description: In section 5 we will show that this step is executed only if
there is a $b\in X$, and a family $\mathcal{D}\subset\mathcal{G}$ of size
$\lvert\mathcal{D}\rvert=W$ and a number $r<\Delta$ such that one of the
following holds. $+$) We have $\chi(b)>1-\alpha$, and each $S\in\mathcal{D}$
satisfies $b\in S$, $\mathop{Th}\nolimits_{-}(S)=2d-r$ and
$\operatorname{Sz}(S)\leq d$. $-$) We have $-\chi(b)>1-\alpha$, and each
$S\in\mathcal{D}$ satisfies $b\in S$, $\mathop{Th}\nolimits_{+}(S)=2d-r$ and
$\operatorname{Sz}(S)\leq d$.

Create a new empty cohort $\mathcal{C}_{m+1}$, move all sets in $\mathcal{D}$
from $\mathcal{G}$ to $\mathcal{C}_{m+1}$, and set $b_{m+1}=b$,
$\varepsilon_{m+1}=\operatorname{sign}\chi(b)$, $r_{m+1}=r$,
$M_{m+1}=\emptyset$ and $D[S]=0$ for all $S\in\mathcal{C}_{m+1}$.

##  4 Proof of the algorithm’s correctness

In this section we show that each step of the algorithm preserves all the
invariants enumerated in the previous section. We also show that the algorithm
terminates, and that its termination implies that the discrepancy of the set
family $\mathcal{F}$ is at most $2d-\Delta$.

In the proofs that follow we use several consequences of the invariants that
we stated. We record these consequences now.

######  Lemma .

If invariant $1$ holds, then $\mathop{Th}\nolimits_{+}^{(j)}(S)$ and
$\mathop{Th}\nolimits_{-}^{(j)}(S)$ are non-increasing functions of $j$.

###### Proof.

Suppose $j<k$. Let $r=\operatorname{Sz}^{(j)}(S)-\operatorname{Sz}^{(k)}(S)$
be the number of elements frozen between stages $j$ and $k$. Then
$\operatorname{Fr}^{(k)}\leq\operatorname{Fr}^{(j)}+r$. So
$\mathop{Th}\nolimits_{+}^{(k)}(S)=\operatorname{Sz}^{(k)}(S)+\operatorname{Fr}^{(k)}(S)\leq\bigl{(}\operatorname{Sz}^{(j)}(S)-r\bigr{)}+\bigl{(}\operatorname{Fr}^{(j)}(S)+r\bigr{)}$.
The proof for $\mathop{Th}\nolimits_{-}$ is similar. ∎

######  Lemma .

If $S\in\mathcal{F}$ satisfying $\operatorname{Sz}(S)\leq d$ also satisfies
$\mathop{Th}\nolimits_{+}(S)>2d-\Delta$, then
$\mathop{Th}\nolimits_{-}(S)<\Delta$. Conversely, if
$\mathop{Th}\nolimits_{-}(S)>2d-\Delta$, then
$\mathop{Th}\nolimits_{+}(S)<\Delta$.

###### Proof.

This follows from
$\mathop{Th}\nolimits_{+}(S)+\mathop{Th}\nolimits_{-}(S)=2\operatorname{Sz}(S)$.
∎

######  Lemma .

If invariant $1$ holds, then $\mathop{Th}\nolimits_{+}(S)\leq 2d-\Delta$
whenever $S\in\mathcal{C}_{i}$ and $\varepsilon_{i}=+1$. Similarly, if
invariant $1$ holds, then $\mathop{Th}\nolimits_{-}(S)\leq 2d-\Delta$ whenever
$S\in\mathcal{C}_{i}$ and $\varepsilon_{i}=-1$.

###### Proof.

By symmetry, we may assume $\varepsilon_{i}=+1$. In view of section 4, it
suffices to consider only the stage when $S$ is added to a cohort at section
3. At that stage, section 4 applies. ∎

######  Lemma .

Suppose invariants $8^{+}$ and $8^{-}$ hold. If $S\in\mathcal{C}_{i}$, then

$\varepsilon_{i}\cdot\chi(S)-\gamma\mathop{Th}\nolimits_{\varepsilon_{i}}(S)\leq\Delta+2-2^{D[S]+1}$

for all $0\leq\gamma\leq 1$.

###### Proof.

Assume $\varepsilon_{i}=+1$ by symmetry. We have

$\displaystyle\chi(S)-\gamma\mathop{Th}\nolimits_{+}(S)$
$\displaystyle=(1-\gamma)\chi(S)-\gamma\bigl{(}\operatorname{Sz}(S)-\operatorname{Fl}(S)\bigr{)}$
using identity (2) $\displaystyle\leq(1-\gamma)\mathop{Th}\nolimits_{+}(S)$
$\displaystyle\text{due to }\chi\leq\mathop{Th}\nolimits_{+}\text{ and
}\operatorname{Fl}\leq\operatorname{Sz}$
$\displaystyle\leq(1-\gamma)(\Delta+2-2^{D[S]+1})$ $\displaystyle\text{because
of \lx@cref{creftype~refnum}{i:otherthreatp}}.\qed$

######  Lemma .

If all the invariants hold and cohort $\mathcal{C}_{i}$ is non-empty, then
$\operatorname{sign}\chi(b_{i})=\varepsilon_{i}$.

###### Proof.

Consider the case $\varepsilon_{i}=+1$, the other case is analogous. If
$M_{i}$ is non-empty, let $\\{S,S^{\prime}\\}$ be any edge in $M_{i}$. If
$M_{i}$ is empty, let $S$ be any set in $\mathcal{C}_{i}$, and put
$S^{\prime}=S$. In either case, sections 3 and 3 imply that

$-\chi(S)-\chi(S^{\prime})-2^{D+1}\beta_{r_{i}}\bigl{(}\chi(b_{i})-1+\alpha\bigr{)}\leq
2^{D+1}\operatorname{Tw}_{r_{i}}-\tfrac{1}{2}\alpha\bigl{(}\mathop{Th}\nolimits_{+}(S)+\mathop{Th}\nolimits_{+}(S^{\prime})\bigr{)}-2R_{D}.$

By the preceding lemma with $\gamma=\tfrac{1}{2}\alpha$ and a bit of algebra,
where nearly all terms cancel, it follows that

$\displaystyle-\beta_{r_{i}}\bigl{(}\chi(b_{i})-1+\alpha\bigr{)}$
$\displaystyle\leq\operatorname{Tw}_{r_{i}}-D+\Delta,$

and the lemma follows since
$\operatorname{Tw}_{r_{i}}-D+\Delta<\beta_{r_{i}}(1-\alpha)$ by inequality
(4b). ∎

######  Lemma .

If invariants $7$, 3 and 3 hold, then for every $S\in\mathcal{C}_{i}$ that is
not in $M_{i}$ and satisfying $\mathop{Th}\nolimits(S)>2d-\Delta$, section 3
holds.

###### Proof.

Say $\varepsilon_{i}=+1$, the other case being symmetric. For brevity write
$D=D[S]$ and $r=r_{i}$. Section 4 asserts that
$\mathop{Th}\nolimits_{+}(S)\leq 2d-\Delta$, and so
$\mathop{Th}\nolimits(S)>2d-\Delta$ implies that

$\mathop{Th}\nolimits_{-}(S)>2d-\Delta.$ (6)

We thus have

$\displaystyle 0$ $\displaystyle\leq
2^{D}\beta_{r}\alpha+2^{D}\operatorname{Tw}_{r}-R_{D}+\chi(S)-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{+}(S)$
from section 3
$\displaystyle=2^{D}\beta_{r}\alpha+2^{D}\operatorname{Tw}_{r}-R_{D}+(1-\alpha)\operatorname{Sz}(S)+\operatorname{Fl}(S)-(1-\tfrac{1}{2}\alpha)\mathop{Th}\nolimits_{-}(S)$
using identities (1) and (2) $\displaystyle\leq
2^{D}\beta_{r}\alpha+2^{D}\operatorname{Tw}_{r}-R_{D}+(2-\alpha)\operatorname{Sz}(S)-(1-\tfrac{1}{2}\alpha)(2d-\Delta)$
from $\operatorname{Fl}(S)\leq\operatorname{Sz}(S)$ and (6) $\displaystyle\leq
2^{D}\beta_{r}\alpha+2^{D}\operatorname{Tw}_{r}-R_{D}+(2-\alpha)(d+1-2^{D})-(1-\tfrac{1}{2}\alpha)(2d-\Delta)$
from invariant $7$
$\displaystyle=2^{D}\bigl{(}\beta_{r}\alpha+\operatorname{Tw}_{r}+\Delta+\alpha-D\bigr{)}-\tfrac{1}{2}\alpha\Delta-\alpha$
from (3) and some algebra

and so $D\leq 4\operatorname{Tw}_{r}$ by inequality (4c). Hence section 3
holds. ∎

It is easy to check that the algorithm satisfies all the invariants at the
initialization stage. Only invariants $11^{+}$ and 3 require an invocation of
section 4 and of inequality (4a); the other invariants are immediate.

In what follows we assume that the algorithm satisfies all the invariants at
stage $n-1$, and that our goal is to show that the algorithm satisfies them at
stage $n$. For brevity, we write $\operatorname{Sz}(S),\operatorname{Fr}(S)$
etc in place of $S^{(n-1)}(S)$, $\operatorname{Fr}^{(n-1)}(S)$ etc. We still
write $\operatorname{Sz}^{(n)}(S)$ etc in full.

### Verification of invariant $1$:

The only steps that modify $\chi$ are sections 3 and 3. They do not unfreeze
any elements.

### Verification of invariant $2$:

The only steps that move sets into $\mathcal{B}$ are sections 3, 3 and 3. The
moves in sections 3 and 3 are preconditioned on $\mathop{Th}\nolimits(S)\leq
2d-\Delta$, and so invariant $2$ holds trivially. The only potential problem
is the movement of $S^{\prime}$ to $\mathcal{B}$ in section 3, which we now
tackle.

Assume that $\varepsilon_{i}=+1$, the other case is symmetric. Since
$\operatorname{Sz}(S^{\prime})\leq\operatorname{Sz}(S)$, it follows from the
execution condition of section 3 that $\operatorname{Sz}(S^{\prime})\leq d/2$.
By section 4, $\mathop{Th}\nolimits_{+}(S^{\prime})\leq 2d-\Delta$, so it
remains to prove that $\mathop{Th}\nolimits_{-}(S^{\prime})\leq 2d-\Delta$.

Use of the identity (1), inequality
$\operatorname{Fl}(S^{\prime})\leq\operatorname{Sz}(S^{\prime})$, and section
4 in that order, yields

$\displaystyle\mathop{Th}\nolimits_{-}(S^{\prime})$ $\displaystyle\leq
2\operatorname{Sz}(S^{\prime})-\chi(S^{\prime})\leq
2\operatorname{Sz}(S^{\prime})-\chi(S^{\prime})-\chi(S)+\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{+}(S)+\Delta+1-2^{D}.$
Applying section 3 and using
$\mathop{Th}\nolimits_{+}(S^{\prime})+\mathop{Th}\nolimits_{-}(S^{\prime})=2\operatorname{Sz}(S^{\prime})$
gives $\displaystyle\mathop{Th}\nolimits_{-}(S^{\prime})$ $\displaystyle\leq
2\operatorname{Sz}(S^{\prime})-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{+}(S^{\prime})+2^{D+1}\beta_{r_{i}}\alpha+2^{D+1}\operatorname{Tw}_{r_{i}}-2R_{D}+\Delta$
$\displaystyle=(2-\alpha)\operatorname{Sz}(S^{\prime})+\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}(S^{\prime})+2^{D+1}\beta_{r_{i}}\alpha+2^{D+1}\operatorname{Tw}_{r_{i}}-2R_{D}+\Delta.$

The invariant $2$ then follows by using $\operatorname{Sz}(S^{\prime})\leq
d/2$, section 3 and inequality (4i).

### Verification of invariant $3$:

Since $\mathop{Th}\nolimits(S)$ is non-increasing by section 4, only the steps
that might decrease $\operatorname{Sz}(S)$ need to be examined. These are
sections 3 and 3. So, let us consider a set $S$ such that
$\operatorname{Sz}(S)>d$ and $\operatorname{Sz}^{(n)}(S)\leq d$.

We will prove that $\mathop{Th}\nolimits_{+}^{(n)}(S)\leq 2d$ (the other case
is similar). We may assume that $\mathop{Th}\nolimits_{+}(S)>2d$, for else we
are done by section 4. By invariant $11^{+}$, $\chi(S)\leq 0$. Furthermore,
for section 3 we have $\chi^{(n)}(S)=\chi(S)$, whereas for section 3 we have
$\chi^{(n)}(S)\leq\chi(S)+\alpha$. Hence, identity (2) implies

$\mathop{Th}\nolimits_{+}^{(n)}(S)=\operatorname{Sz}^{(n)}(S)-\operatorname{Fl}^{(n)}(S)+\chi^{(n)}(S)\leq
2\operatorname{Sz}^{(n)}(S)+\alpha\leq 2d+\alpha.$

Since $\mathop{Th}\nolimits_{+}^{(n)}(S)$ is an integer, we conclude that
$\mathop{Th}\nolimits_{+}^{(n)}(S)\leq 2d$ as desired.

### Verification of invariant $4$:

The only step that adds sets to a cohort, or modifies a cohort’s banner is
section 3. However, that step clearly respects invariant $4$.

### Verification of invariant $5$:

The only step that adds edges to $M_{i}$ is section 3. It adds edges only
between unmatched sets.

### Verification of invariant $6$:

The only step that adds edges to $M_{i}$ is section 3. It adds edges only
between sets with equal value of $D$. The only steps that change value of
$D[S]$ are sections 3 and 3. Section 3 changes $D[S]$ only after having
removed the edge that contains $S$ from $M_{i}$. Section 3 is not a problem
either, as the cohort that it creates has empty matching.

### Verification of invariant $7$:

In view of invariant $1$, $\operatorname{Sz}(S)$ can only decrease. Thus, it
suffices to verify only the steps that either increase the value of $D[S]$ or
add sets to $\mathcal{C}_{i}$. These are sections 3 and 3 respectively.

Section 3 adds sets with $\operatorname{Sz}(S)\leq d$ and assigns $D[S]=0$ for
them, satisfying invariant $7$.

Consider section 3. Since it is that step which is executed, and not section
3, it follows that $b_{i}$ is not frozen, and so
$\operatorname{Sz}(S^{\prime})\geq 1$. Hence, from the inequality (5) we have

$\operatorname{Sz}(S)\leq d+1-2^{D[S]+1}=d+1-2^{D^{(n)}[S]}.$

### Verification of invariants $8^{+}$ and $8^{-}$:

By section 4 it suffices to check only the steps that move sets to
$\mathcal{C}_{i}$ or increase the value of $D[S]$. These are sections 3 and 3.

By symmetry it suffices to treat only invariant $8^{+}$. Note that both in
section 3 and in section 3, the sets $S$ for which we need to establish
invariant $8^{+}$ satisfy $\mathop{Th}\nolimits_{-}^{(n)}(S)>2d-\Delta$.
Hence,

$\mathop{Th}\nolimits_{+}^{(n)}(S)=\operatorname{Sz}^{(n)}(S)+\operatorname{Fr}^{(n)}(S)=2\operatorname{Sz}^{(n)}(S)-\mathop{Th}\nolimits_{-}^{(n)}(S)<2\operatorname{Sz}^{(n)}(S)-2d+\Delta,$

and invariant $8^{+}$ follows from the validity of invariant $7$ at stage $n$,
which was proved immediately above.

### Verification of invariant $9$:

We need to check only the steps that remove sets from $\mathcal{C}_{i}$, as
well as creation of new cohorts in section 3. The latter is trivial since
$\lvert\mathcal{D}\rvert=W$. The only steps that remove sets from
$\mathcal{C}_{i}$ are sections 3, 3, LABEL: and 3. Of these, sections 3 and 3
move sets from $\mathcal{C}_{i}$ to $\mathcal{B}$, thus preserving invariant
$9$. Section 3 removes sets to $\mathcal{G}$, but also disbands the cohort.
The fact that the step preserves invariant $9$ follows from
$\lvert\mathcal{C}_{i}\rvert\leq W$, which is a consequence of invariant $10$.

### Verification of invariant $10$:

We need to check only the steps that either increase the value of $D[S]$ or
add sets to $\mathcal{C}_{i}$. These are sections 3 and 3. For section 3 we
note that $D[S]=D[S^{\prime}]$ by invariant $6$, and so
$2^{D^{(n)}(S)}=2^{D[S]+1}=2^{D[S]}+2^{D[S^{\prime}]}$. For section 3 the
invariant follows from $\lvert\mathcal{D}\rvert=W$ and $D[S]=0$.

### Verification of invariants $11^{+}$ and 3:

We only treat invariant $11^{+}$, for section 3 is symmetric. We need to check
only the steps that modify $\chi$ or move sets to $\mathcal{G}$. These are
sections 3, 3 and 3. Let $S\in\mathcal{F}$ be arbitrary, and let us check that
the invariant holds for $S$.

Section 3 does not change $\chi(S)$, and may only decrease
$\mathop{Th}\nolimits_{+}(S)$ and $\mathop{Th}\nolimits_{-}(S)$, by section 4.
So, if $\operatorname{Sz}(S),\operatorname{Sz}^{(n)}(S)$ are either both
greater than $d$, or are both at most $d$, then the invariant holds at stage
$n$ because it held at stage $n-1$. So, consider the case when
$\operatorname{Sz}(S)>d$ and $\operatorname{Sz}^{(n)}(S)\leq d$. Note that
since $\operatorname{Sz}(S)>d$ and invariant $11^{+}$ held at stage $n-1$, it
follows that $\chi(S)\leq 0$. If $\mathop{Th}\nolimits_{+}^{(n)}(S)\leq
2d-\Delta$ then invariant $11^{+}$ holds vacuously. Otherwise,
$\mathop{Th}\nolimits_{-}^{(n)}(S)<\Delta$ by section 4. Thus
$\operatorname{Tw}_{r}-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}^{(n)}(S)\geq
0$ by inequality (4a). Since $\chi^{(n)}(S)=\chi(S)\leq 0$, invariant $11^{+}$
holds.

Section 3 alters $\chi(S)$, $\operatorname{Sz}(S)$,
$\mathop{Th}\nolimits_{-}(S)$ or $\mathop{Th}\nolimits_{+}(S)$ only if it
rounds an element $x$ that is in $S$. So, assume $x\in S$. There are two cases
according to the sign of $\chi(x)$:

  1. $+$)

If $\chi(x)>1-\alpha$, then for the condition of section 3 to have triggered,
we must have either $\mathop{Th}\nolimits_{+}(S)\leq 2d-\Delta$ or
$\operatorname{Sz}(S)\leq d$. In the former case,
$\mathop{Th}\nolimits_{+}^{(n)}(S)\leq\mathop{Th}\nolimits_{+}(S)$ by section
4, and so invariant $11^{+}$ holds vacuously. In the latter case,
$\chi^{(n)}(S)\leq\chi(S)+\alpha$,
$\mathop{Th}\nolimits_{+}^{(n)}(S)=\mathop{Th}\nolimits_{+}(S)$ and
$\mathop{Th}\nolimits_{-}^{(n)}(S)=\mathop{Th}\nolimits_{-}(S)-2$, and the
invariant is verified by substitution.

  2. $-$)

If $-\chi(x)>1-\alpha$, then $\chi^{(n)}(S)<\chi(S)$, and
$\mathop{Th}\nolimits_{+}^{(n)}(S)=\mathop{Th}\nolimits_{+}(S)-2$ and
$\mathop{Th}\nolimits_{-}^{(n)}(S)=\mathop{Th}\nolimits_{-}(S)$. As in the
treatment of section 3 above, the only case worthy of attention is
$\operatorname{Sz}(S)=d+1$, $\operatorname{Sz}^{(n)}(S)=d$, and the same
argument as above disposes of it.

We treat section 3 next. Suppose cohort $\mathcal{C}_{i}$ is being dissolved,
and $S\in\mathcal{C}_{i}$ is an arbitrary set in it. If $\varepsilon_{i}=+1$,
then by section 4 invariant $11^{+}$ holds vacuously. So, assume
$\varepsilon_{i}=-1$. If $S$ is not a part of $M_{i}$, declare $S^{\prime}=S$,
otherwise let $\\{S,S^{\prime}\\}\in M_{i}$ be the edge containing $S$. In
both cases we conclude (either from section 3 or section 3) that

$\chi(S)+\chi(S^{\prime})+2^{D+1}\beta_{r_{i}}\bigl{(}\chi(b_{i})+1-\alpha\bigr{)}\leq
2^{D+1}\operatorname{Tw}_{r_{i}}-\tfrac{1}{2}\alpha\bigl{(}\mathop{Th}\nolimits_{-}(S)+\mathop{Th}\nolimits_{-}(S^{\prime})\bigr{)}-2R_{D}.$

An application of section 4 to
$-\chi(S^{\prime})-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}(S^{\prime})$
gives

$\displaystyle\chi(S)$ $\displaystyle\leq
2^{D+1}\beta_{r_{i}}\alpha+2^{D+1}\operatorname{Tw}_{r_{i}}+\Delta+2-2^{D+1}-2R_{D}-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}(S)$
(7)
$\displaystyle\leq\operatorname{Tw}_{r_{i}+2}-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}(S),$

with the last line holding because of inequality (4j) and section 3.

Let $j$ be the stage when cohort $\mathcal{C}_{i}$ was created. By the
description of section 3 we had $\mathop{Th}\nolimits_{+}^{(j)}(S)=2d-r_{i}$
and banner $b_{i}$ was a floating element. So, since $\chi(b_{i})=-1$ by
section 4, we conclude that $\mathop{Th}\nolimits_{+}(S)\leq 2d-r_{i}-2$. In
view of inequality (7) above, this implies that invariant $11^{+}$ holds.

### Verification of sections 3 and 3:

We treat section 3, for section 3 is symmetric. We need to verify the steps
that remove sets from $M_{i}$, modify $D[S]$ or $\chi$, or add sets to
$\mathcal{C}_{i}$. These are sections 3, 3, 3, LABEL: and 3. We handle them in
(reverse) order.

Validity of section 3 after section 3 follows from $\chi(b_{i})+1-\alpha\leq
0$, $R_{0}=0$, $\operatorname{Sz}(S)\leq d$ and the validity of invariant
$11^{+}$ before the step.

Section 3 does not change the left-hand side of the inequality in section 3,
and might only increase the right-hand side (by decreasing
$\mathop{Th}\nolimits_{-}(S)$).

We treat section 3 next. We need to consider only the case
$\mathop{Th}\nolimits(S)>2d-\Delta$, for otherwise the invariant holds
vacuously. Let $D=D[S]$. Our goal is to bound

$\displaystyle
Q\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\chi^{(n)}(S)+2^{D^{(n)}[S]}\beta_{r_{i}}\bigl{(}\chi(b_{i})+1-\alpha\bigr{)}$
$\displaystyle=\chi(S)+2^{D+1}\beta_{r_{i}}\bigl{(}\chi(b_{i})+1-\alpha\bigr{)}.$

Since section 3 held at stage $n-1$, we conclude that

$\displaystyle Q$ $\displaystyle\leq
2^{D+1}\operatorname{Tw}_{r_{i}}-\tfrac{1}{2}\alpha\bigl{(}\mathop{Th}\nolimits_{-}(S)+\mathop{Th}\nolimits_{-}(S^{\prime})\bigr{)}-\chi(S^{\prime})-2R_{D}$
$\displaystyle\text{by \lx@cref{creftype~refnum}{i:Cchimatchedn}}.$

Hence, it suffices to prove that
$-\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{-}(S^{\prime})-\chi(S^{\prime})\leq
2R_{D}-R_{D+1}$. This follows from section 4 and from
$2R_{D}-R_{D+1}=\Delta+2-2^{D+1}$. We are thus done with section 3.

Finally, we check section 3. We may assume that $x$, the element that is
rounded, is in $S$. If $\chi(x)<1-\alpha$, then rounding decreases left-hand
side of the inequality in section 3, and does not affect the right-hand side
at all. So, we may assume that $\chi(x)>1-\alpha$. By section 4
$\chi(b_{i})<0$, and so $x\neq b_{i}$. The rounding thus increases the left-
hand side of the inequality in section 3 by at most $\alpha$. Since the right-
hand side of the inequality increases by exactly $\alpha$, we are done.

### Verification of sections 3 and 3:

We need to check only sections 3, 3 and 3 as these are the only steps that
either change $\chi$ or create an edge in $M_{i}$. The verification of
sections 3 and 3 is an almost verbatim repetition of the verification of
sections 3 and 3 for those steps, and we omit it. The validity of sections 3
and 3 after section 3 follows from the validity of sections 3 and 3
respectively before the step.

### Verification of section 3:

We need to consider only section 3 as it is the only step that increases the
value of $D[S]$. Since invariants $7$, 3 and 3 have been proved above, the
section 3 follows from section 4.

### Proof that the algorithm terminates:

Let $F$ be the number of frozen elements, and consider the quantity

$I\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}F+4\lvert\mathcal{B}\rvert-m+\sum_{i=1}^{m}\bigl{(}\lvert
M_{i}\rvert+\lvert\mathcal{C}_{i}\rvert\bigr{)}.$

We claim that each step other than section 3 increases $I$. Section 3
increases $\lvert\mathcal{B}\rvert$; section 3 decreases $m$; section 3
increases $F$; section 3 increases $4\lvert\mathcal{B}\rvert$ by $4$ and
decreases $\lvert\mathcal{C}_{i}\rvert$ by $1$; section 3 increases
$4\lvert\mathcal{B}\rvert$ by at least $4$, decreases $\lvert M_{i}\rvert$ by
$1$, and decreases $\lvert\mathcal{C}_{i}\rvert$ by at most $2$; section 3
increases $\lvert M_{i}\rvert$; section 3 increases $F$; section 3 increases
$\sum_{i}\lvert\mathcal{C}_{i}\rvert$ by $W$ and increases $m$ by $1$.

Section 3 is executed only if there are no empty cohorts (section 3 cannot be
executed), and so $-m+\nobreak\sum\lvert\mathcal{C}_{i}\rvert\geq 0$. Hence,
after section 3 is executed, $I$ is nonnegative. Since other steps increase
$I$, and $I$ is bounded by $\lvert X\rvert+4\lvert\mathcal{F}\rvert$, it
follows that section 3 must be executed at least once every $\lvert
X\rvert+4\lvert\mathcal{F}\rvert$ steps.

After a cohort is disbanded in section 3, no new cohort with the same banner
can be created, as banner is a floating element. Furthermore, since any cohort
disbanded in section 3 is non-empty, that step can be executed at most $d$
times for any given value of the banner. So, section 3 can be executed total
of at most $d\lvert X\rvert$ times. In particular, the algorithm terminates
after at most $d\lvert X\rvert\bigl{(}\lvert
X\rvert+4\lvert\mathcal{F}\rvert\bigr{)}$ steps.

Since section 3 is executed unless $\mathcal{F}=\mathcal{B}$, when the
algorithm terminates we have $\mathop{Th}\nolimits(S)\leq 2d-\Delta$ for all
$S\in\mathcal{F}$. While it does not mean that the final coloring $\chi$ takes
only values $-1$ and $+1$, it does imply that no matter how we round the
remaining floating elements, the resulting coloring will have discrepancy at
most $2d-\Delta$.

##  5 Creation of a new cohort

In this section we prove a claim made in section 3, namely, that if that step
can be executed, then there is a family $\mathcal{D}\subset\mathcal{G}$ all of
whose sets contain a common element $b\in X$, and that satisfies the right
conditions for making a new cohort. In what follows, we assume that none of
the steps 3 through 3 can be executed, and that all the invariants hold.

######  Lemma .

For each cohort $\mathcal{C}_{i}$ we have

$d\bigl{(}\lvert\mathcal{C}_{i}\rvert-\lvert
M_{i}\rvert\bigr{)}<W+\sum_{S\in\mathcal{C}_{i}}\bigl{(}\operatorname{Sz}(S)-1\bigr{)}.$
(8)

###### Proof.

By symmetry assume $\varepsilon_{i}=+1$.

Because $D[S]=D[S^{\prime}]$ for $\\{S,S^{\prime}\\}\in M_{i}$ by invariant
$6$ and because section 3 cannot be executed, we have

$\bigl{(}\operatorname{Sz}(S)-1\bigr{)}+\bigl{(}\operatorname{Sz}(S^{\prime})-1\bigr{)}\geq
d-2^{D[S]}-2^{D[S^{\prime}]}+1\qquad\text{for all }\\{S,S^{\prime}\\}\in
M_{i}.$ (9)

Let $S\in C_{i}\setminus M_{i}$ be any unmatched cohort set, and let $D=D[S]$
for brevity. Because section 3 cannot be executed, we necessarily have
$\mathop{Th}\nolimits(S)>2d-\Delta$, which by section 4 implies that
$\mathop{Th}\nolimits_{-}(S)>2d-\Delta$, and so

$\displaystyle 2\operatorname{Sz}(S)$
$\displaystyle\geq\operatorname{Sz}(S)+\operatorname{Fl}(S)$
$\displaystyle\text{since
}\lvert\operatorname{Fl}(S)\rvert\leq\operatorname{Sz}(S)$
$\displaystyle=\mathop{Th}\nolimits_{-}(S)+\chi(S)$ because of (1)
$\displaystyle>2d-\Delta+\chi(S)=2d-\Delta-\chi(S)+2\chi(S)$
$\displaystyle\geq
2d-\Delta-\chi(S)+\alpha\mathop{Th}\nolimits_{+}(S)-2^{D+1}\beta_{r_{i}}\alpha-2^{D+1}\operatorname{Tw}_{r_{i}}+2R_{D}$
by section 3 $\displaystyle\geq
2d-2\Delta-2+2^{D+1}-2^{D+1}\beta_{r_{i}}\alpha-2^{D+1}\operatorname{Tw}_{r_{i}}+2R_{D}$
$\displaystyle\text{by \lx@cref{creftype~refnum}{lem:other_chi_bound}}.$

Hence by inequality (4c)

$\operatorname{Sz}(S)-1\geq
d-2^{D[S]+3}\operatorname{Tw}_{r_{i}}\qquad\text{for all
}S\in\mathcal{C}_{i}\setminus V(M_{i}).$

Let $L=4\operatorname{Tw}_{r_{i}}$. Since section 3 cannot be executed, for
each $D$ there is at most one set $S\in\mathcal{C}_{i}$ satisfying $D[S]=D$
that is not in $M_{i}$. Also, $D[S]\leq L$ by section 3. Thus,

$\sum_{S\in\mathcal{C}_{i}\setminus
V(M_{i})}(\operatorname{Sz}(S)-1)\geq\sum_{S\in\mathcal{C}_{i}\setminus
V(M_{i})}(d-2^{D[S]+3}\operatorname{Tw}_{r_{i}})\geq
d\lvert\mathcal{C}_{i}\setminus
V(M_{i})\rvert-2^{L+4}\operatorname{Tw}_{r_{i}}.$

Combining this with (9) we obtain

$\sum_{S\in\mathcal{C}_{i}}\bigl{(}\operatorname{Sz}(S)-1\bigr{)}\geq
d\bigl{(}\lvert\mathcal{C}_{i}\rvert-\lvert M_{i}\rvert\bigr{)}-\sum_{S\in
V(M_{i})}2^{D[S]}+\lvert M_{i}\rvert-2^{L+4}\operatorname{Tw}_{r_{i}}.$ (10)

If $\lvert M_{i}\rvert>2^{L+4}\operatorname{Tw}_{r_{i}}$, then the lemma
follows from invariant $10$. Otherwise, $\lvert M_{i}\rvert\leq
2^{L+4}\operatorname{Tw}_{r_{i}}$, hence $\lvert V(M_{i})\rvert\leq
2^{L+5}\operatorname{Tw}_{r_{i}}$, and so

$\sum_{S\in V(M_{i})}2^{D[S]}+2^{L+4}\operatorname{Tw}_{r_{i}}\leq 2^{L}\cdot
2^{L+5}\operatorname{Tw}_{r_{i}}+2^{L+4}\operatorname{Tw}_{r_{i}}\leq
2^{2L+6}\operatorname{Tw}_{r_{i}}<W$

by inequality (4h), and the lemma follows from (10). ∎

######  Lemma .

The sets in $\mathcal{G}$ satisfy

$\sum_{S\in\mathcal{G}}(\operatorname{Sz}(S)-d)\leq 0,$ (11)

and the equality is possible only if there are no cohorts.

###### Proof.

Let $F$ be the number of floating elements, and consider

$dF\geq\sum_{S\in\mathcal{F}}\operatorname{Sz}(S)=\sum_{S\in\mathcal{G}}\operatorname{Sz}(S)+\sum_{S\in\mathcal{B}}\operatorname{Sz}(S)+\sum_{i=1}^{m}\sum_{S\in\mathcal{C}_{i}}\operatorname{Sz}(S)=\Sigma_{1}+\Sigma_{2}+\Sigma_{3}.$

By invariant $9$ we have
$\Sigma_{2}\geq\sum_{i}(W-\lvert\mathcal{C}_{i}\rvert)$. Bounding $\Sigma_{3}$
by the preceding lemma we obtain

$dF\geq\sum_{S\in\mathcal{G}}\bigl{(}\operatorname{Sz}(S)-d\bigr{)}+d\lvert\mathcal{G}\rvert+d\sum_{i=1}^{m}(\lvert\mathcal{C}_{i}\rvert-\lvert
M_{i}\rvert).$ (12)

Furthermore, since the inequality in the preceding lemma is strict, the
equality in (12) can hold only if there are no cohorts.

Finally, since section 3 cannot be executed,
$F\leq\lvert\mathcal{G}\rvert+\sum_{i}(\lvert\mathcal{C}_{i}\rvert-\lvert
M_{i}\rvert)$ and so (11) holds. ∎

Let

$\displaystyle B^{+}$ $\displaystyle=\\{x\text{
floating}:\phantom{-}\chi(x)\geq 1-\alpha\\},$ $\displaystyle B^{-}$
$\displaystyle=\\{x\text{ floating}:-\chi(x)\geq 1-\alpha\\}.$

The next lemma shows that nasty sets contain many nearly-frozen elements.

######  Lemma .

Suppose $S\in\mathcal{G}$ satisfies $\operatorname{Sz}(S)\leq d$. Then the
following hold:

  1. $+$)

If $\mathop{Th}\nolimits_{+}(S)>2d-\Delta$, then $\lvert B^{-}\cap S\rvert\geq
d/2$ and $\operatorname{Sz}(S)\geq d-\Delta/2-\operatorname{Tw}_{\Delta-1}$

  2. $-$)

If $\mathop{Th}\nolimits_{-}(S)>2d-\Delta$, then $\lvert B^{+}\cap S\rvert\geq
d/2$ and $\operatorname{Sz}(S)\geq d-\Delta/2-\operatorname{Tw}_{\Delta-1}$

###### Proof.

Consider the case $\mathop{Th}\nolimits_{-}(S)>2d-\Delta$. The other case is
similar.

Define $r$ by $\mathop{Th}\nolimits_{-}(S)=2d-r$. From (1) and section 3 we
deduce that

$\tfrac{1}{2}\alpha\mathop{Th}\nolimits_{+}(S)-\operatorname{Tw}_{r}\leq\chi(S)=\operatorname{Sz}(S)+\operatorname{Fl}(S)-\mathop{Th}\nolimits_{-}(S),$

and since
$\mathop{Th}\nolimits_{-}(S)+\mathop{Th}\nolimits_{+}(S)=2\operatorname{Sz}(S)$,
this implies that

$-\operatorname{Tw}_{r}\leq(1-\alpha)\operatorname{Sz}(S)+\operatorname{Fl}(S)-\bigl{(}1-\tfrac{1}{2}\alpha\bigr{)}\mathop{Th}\nolimits_{-}(S).$
(13)

We then use bounds
$\operatorname{Fl}(S)\leq(1-\alpha)\lvert\operatorname{Sz}(S)\rvert+\alpha\lvert
B^{+}\cap S\rvert$, $\mathop{Th}\nolimits_{-}(S)\geq 2d-\Delta$ and
$\operatorname{Sz}(S)\leq d$ to obtain

$-\operatorname{Tw}_{r}\leq-\alpha d+\alpha\lvert B^{+}\cap
S\rvert+(1-\tfrac{1}{2}\alpha)\Delta$

Hence $\lvert B^{+}\cap S\rvert\geq d-\operatorname{Tw}_{r}/\alpha\geq d/2$ by
inequality (4f).

When combined with $\operatorname{Fl}(S)\leq\operatorname{Sz}(S)$, the
inequality (13) also implies that

$(2-\alpha)\operatorname{Sz}(S)\geq\bigl{(}1-\tfrac{1}{2}\alpha\bigr{)}(2d-\Delta)-\operatorname{Tw}_{r},$

and so $\operatorname{Sz}(S)\geq d-\Delta/2-\operatorname{Tw}_{r}$. ∎

We are now ready to demonstrate the claim made in section 3.

Define a _charge_ for a pair $(x,S)$ where $x\in B^{+}\cup B^{-}$ and
$S\in\mathcal{G}$ by the following rule:

$\operatorname{Ch}(x,S)=\begin{cases}\dfrac{\operatorname{Sz}(S)-d-1}{\lvert
S\cap B^{+}\rvert}&\text{if }x\in S\cap B^{+}\text{ and
}\operatorname{Sz}(S)\leq d\text{ and
}\mathop{Th}\nolimits_{-}(S)>2d-\Delta,\\\\[9.90276pt]
\dfrac{\operatorname{Sz}(S)-d-1}{\lvert S\cap B^{-}\rvert}&\text{if }x\in
S\cap B^{-}\text{ and }\operatorname{Sz}(S)\leq d\text{ and
}\mathop{Th}\nolimits_{+}(S)>2d-\Delta,\\\\[9.90276pt]
\dfrac{\operatorname{Sz}(S)-d}{4\lvert S\cap B^{+}\rvert}&\text{if }x\in S\cap
B^{+}\text{ and }\operatorname{Sz}(S)\geq d+1,\\\\[9.90276pt]
\dfrac{\operatorname{Sz}(S)-d}{4\lvert S\cap B^{-}\rvert}&\text{if }x\in S\cap
B^{-}\text{ and }\operatorname{Sz}(S)\geq d+1,\\\\[9.90276pt]
0&\text{otherwise}.\end{cases}$

Since section 3 cannot be executed, $\operatorname{Sz}(S)\leq d$ implies that
either $\mathop{Th}\nolimits_{-}(S)>2d-\Delta$ or
$\mathop{Th}\nolimits_{+}(S)>2d-\Delta$. Consider any $S\in\mathcal{G}$
satisfying $\operatorname{Sz}(S)\leq d$. By section 5 we have $S\cap(B_{+}\cup
B_{-})\neq\emptyset$, and so

$\sum_{x\in X}\operatorname{Ch}(x,S)<\operatorname{Sz}(S)-d.$ (14)

Inequality (14) also clearly holds for $S\in\mathcal{G}$ satisfying
$\operatorname{Sz}(S)>d$. So (14) holds for all $S\in\mathcal{G}$.

If $\mathcal{G}=\emptyset$, then the left-hand side of inequality (11) would
be zero, implying that there are no cohorts, and so $\mathcal{F}=\mathcal{B}$.
Since $\mathcal{F}=\mathcal{B}$ contradicts the assumption that section 3 can
be executed, we conclude that $\mathcal{G}$ is non-empty. Hence the inequality
(14) and section 5 imply

$\sum_{\begin{subarray}{c}x\in X\\\
S\in\mathcal{G}\end{subarray}}\operatorname{Ch}(x,S)<\sum_{S\in\mathcal{G}}\bigl{(}\operatorname{Sz}(S)-d\bigr{)}\leq
0.$

So, there is an element $b\in B^{+}\cup B^{-}$ such that

$\sum_{S\in\mathcal{G}}\operatorname{Ch}(b,S)<0.$ (15)

Fix such a $b$, and assume that $b\in B^{+}$ (the case $b\in B^{-}$ is
analogous). Define

$\displaystyle\mathcal{N}$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\\{S\in\mathcal{G}:b\in
S,\ \operatorname{Sz}(S)\leq d\text{ and
}\mathop{Th}\nolimits_{-}(S)>2d-\Delta\\},$ $\displaystyle\mathcal{P}$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny{def}}}}{{=}}\\{S\in\mathcal{G}:b\in
S,\ \operatorname{Sz}(S)\geq d+1\text{ and
}\mathop{Th}\nolimits_{+}(S)>2d-\Delta\\}.$

From (15) and the definition of $\operatorname{Ch}(b,S)$ it follows that
$\mathcal{N}$ is non-empty.

Since section 3 is unable to round $b$, the set $\mathcal{P}$ must be non-
empty as well. We next show that the contribution of a set from $\mathcal{P}$
to the sum (15) is very large, whereas the contribution of a set from
$\mathcal{N}$ is very small.

######  Proposition .

For each $S\in\mathcal{N}$ we have
$\operatorname{Ch}(b,S)\geq-\frac{\Delta+2\operatorname{Tw}_{\Delta-1}+2}{d}$.

######  Proposition .

For each $S\in\mathcal{P}$ we have
$\operatorname{Ch}(b,S)\geq\frac{1}{8+4\Delta}$.

###### Proof of section 5.

This follows from
$\operatorname{Ch}(b,S)=\bigl{(}\operatorname{Sz}(S)-d-1\bigr{)}/\lvert S\cap
B^{+}\rvert$, and the bounds on $\operatorname{Sz}(S)$ and on $S\cap B^{+}$
from section 5. ∎

###### Proof of section 5.

We show that $\lvert S\cap B^{+}\rvert$ is very small by bounding
$\operatorname{Fl}(S)$ both from above and from below:

$\displaystyle\operatorname{Fl}(S)$
$\displaystyle=\operatorname{Sz}(S)+\chi(S)-\mathop{Th}\nolimits_{+}(S)$ by
identity (2) $\displaystyle\leq\operatorname{Sz}(S)+\chi(S)-2d+\Delta,$
$\displaystyle\text{since }S\in\mathcal{P}$
$\displaystyle\leq\operatorname{Sz}(S)-2d+\Delta,$ by invariant $11^{+}$
$\displaystyle\operatorname{Fl}(S)$
$\displaystyle\geq-\operatorname{Sz}(S)+(2-\alpha)\lvert S\cap B^{+}\rvert.$

Since $\alpha\leq 1$, these two inequalities imply

$\lvert S\cap B^{+}\rvert\leq 2\bigl{(}\operatorname{Sz}(S)-d\bigr{)}+\Delta,$

and so
$\operatorname{Ch}(b,S)\geq\tfrac{1}{8}\cdot\frac{\operatorname{Sz}(S)-d}{\operatorname{Sz}(S)-d+\Delta/2}\geq\frac{1}{8(1+\Delta/2)}$.
∎

From the two propositions and from (15) we conclude that
$\lvert\mathcal{N}\rvert\geq\frac{d}{\Delta+2\operatorname{Tw}_{\Delta-1}+2}\cdot\frac{1}{8+4\Delta}\geq\Delta
W$ by inequality (4g). By invariant $3$ we have
$2d-\Delta<\mathop{Th}\nolimits_{-}(S)\leq 2d$ for all $S\in\mathcal{N}$.
Hence, by the pigeonhole principle there is an $0\leq r<\Delta$ and a
$\mathcal{D}\subset\mathcal{N}$ of size $\lvert\mathcal{D}\rvert=W$ such that
$\mathop{Th}\nolimits_{+}(S)=2d-r$ for all $S\in\mathcal{D}$. This completes
the proof of the claim made in section 3.

## References

  * [1] Wojciech Banaszczyk.  Balancing vectors and Gaussian measures of $n$-dimensional convex bodies.  Random Structures Algorithms, 12(4):351–360, 1998.
  * [2] József Beck and Tibor Fiala.  “Integer-making” theorems.  Discrete Appl. Math., 3(1):1–8, 1981.
  * [3] Debe Bednarchak and Martin Helm.  A note on the Beck-Fiala theorem.  Combinatorica, 17(1):147–149, 1997.
  * [4] Bernard Chazelle.  The discrepancy method.  Cambridge University Press, Cambridge, 2000.  https://www.cs.princeton.edu/~chazelle/pubs/book.pdf.
  * [5] Martin Helm.  On the Beck-Fiala theorem.  Discrete Math., 207(1-3):73–87, 1999.
  * [6] Jiří Matoušek.  Geometric discrepancy, volume 18 of Algorithms and Combinatorics.  Springer-Verlag, Berlin, 2010.  An illustrated guide, Revised paperback reprint of the 1999 original.
  * [7] Aleksandar Nikolov.  The Komlós conjecture holds for vector colorings.  arXiv:1301.4039v2, August 2013.
  * [8] Joel Spencer.  Six standard deviations suffice.  Trans. Amer. Math. Soc., 289(2):679–706, 1985.