format: text

text:
# List Colouring of Graphs with at Most(2-𝑜(1))𝜒 Vertices

## 1. Introduction

Recently, a host of important results on graph colouring have been obtained via the probabilistic method. The first author presented an invited lecture at the 2002 International Congress of Mathematicians surveying a number of these results. The recent monograph  provides a more in depth survey of the topic. This paper presents one example of a result proven using the method.

An instance of List Colouring consists of a graph $`G`$ and a list $`L(v)`$ of colours for each vertex $`v`$ of $`G`$. We are asked to determine if there is an acceptable colouring of $`G`$, that is a colouring in which each vertex receives a colour from its list, and no edge has both its endpoints coloured with the same colour. The list-chromatic number of $`G`$, denoted $`\chi ^l(G)`$ is the minimum integer $`k`$ such that for every assignment of a list $`L(v)`$ of size at least $`k`$ to every vertex $`v`$ of $`G`$, there exist an acceptable colouring of $`G`$. The list-chromatic number was introduced by Vizing , and independently Erdös et al. . This parameter has received a considerable amount of attention in recent years (see, e.g. , ).

Clearly, by definition, $`\chi ^l(G)\chi (G)`$ because $`\chi (G)=k`$ precisely if an acceptable colouring exists when each $`L_v`$ is $`\{1,\mathrm{},k\}`$. However, the converse inequality is not true, e.g. $`\chi ^l(K_{3,3})=3`$ as can be easily verified by considering Figure 1. In fact, there are bipartite graphs with arbitrarily high chromatic number (indeed even for bipartite $`G`$, $`\chi ^l(G)`$ is bounded from below by a function of the minimum degree which goes to infinity, see ). This shows that the gap between $`\chi (G)`$ and $`\chi ^l(G)`$ can be arbitrarily large. Moreover it shows that $`\chi ^l(G)`$ can not be bound by any function of the chromatic number of $`G`$. This gives rise to the following intriguing question in the theory of graph colourings: Find conditions which guarantee the equality of the chromatic and list-chromatic numbers.

There are many conjectures hypothesizing conditions on $`G`$ which imply that $`\chi (G)=\chi ^l(G)`$. Probably, the most famous of these is the List Colouring Conjecture (see ) which states that this is true if $`G`$ is a line graph. One interesting example of a graph with $`\chi =\chi ^l`$ was obtained in the original paper of Erdös et al. . They proved that if $`G`$ is complete $`k`$-partite graph with each part of size two then $`\chi (G)=\chi ^l(G)=k`$. It took nearly twenty years until Ohba  noticed that this example is actually part of much larger phenomenon. He conjectured (cf. ) that $`\chi (G)=\chi ^l(G)`$ provided $`|V(G)|2\chi (G)+1`$. This conjecture if it is correct is best possible. Indeed, let $`G`$ be a complete $`k`$-partite graph with $`k1`$ parts of size $`2`$ and one part of size $`4`$. Then the number of vertices of $`G`$ is $`2k+2`$, the chromatic number is $`k`$ and it was proved in  that list-chromatic number of $`G`$ is at least $`k+1>k`$.

In his original paper Ohba obtained that $`\chi ^l(G)=\chi (G)`$ for all graphs $`G`$ with $`|V(G)|\chi (G)+\sqrt{2\chi (G)}`$. His conjecture was settled for some other special cases in . Recently the result of Ohba was substantially improved by the authors of this paper. In  they proved that Ohba’s conjecture is true for all graphs $`G`$ with at most $`\frac{5}{3}\chi (G)\frac{4}{3}`$ vertices. In this paper we want to improve this result for large graphs and prove that the conjecture is asymptotically correct. More precisely we obtain the following theorem.

###### Theorem 1

For any $`0<ϵ<1`$, there exist an $`n_0=n_0(ϵ)`$ such that $`\chi ^l(G)=\chi (G)`$ provided $`n_0|V(G)|(2ϵ)\chi (G)`$.

The rest of this paper is organized as follows. In the next section we describe the main steps in the proof of Theorem 1. More precisely, we present our key lemma and show how to deduce from it the assertion of the theorem. We will prove this lemma using probabilistic arguments. In Sections 3 and 4 we discuss the main ideas we are going to use in the proof. We present the details of the proof in Section 5. Finally, the last section of the paper contains some concluding remarks.

## 2. The key lemma

In this section we present the main steps in the proof of Theorem 1. First we need the following lemma from  whose short proof we include here for the sake of completeness.

###### Lemma 2

For any integer $`t`$, if $`\chi ^l(G)>t`$ then there exist a set of lists $`L(v),vV(G)`$ for which there is no acceptable colouring such that each list has at least $`t`$ elements and the set $`𝒜=_{vV(G)}L(v)`$ has size less than $`|V(G)|`$.

Proof. Assume $`\chi ^l(G)>t`$ and choose a set of lists $`L(v),vV(G)`$ for which there is no acceptable colouring, in which each list has size at least $`t`$ and which minimizes $`|𝒜|`$.

Now, if $`|𝒜|<|V(G)|`$ then we are done. So, we can assume the contrary. We consider the bipartite graph $`H`$ with bipartition $`(𝒜,V(G))`$ and an edge between $`c`$ and $`v`$ precisely if $`cL(v)`$. If there is a matching of size $`|V|`$ in $`H`$ then this matching saturates $`V`$ and points out an acceptable colouring for the List Colouring instance in which no colour is used more than once. Since, there is no such acceptable colouring, no such matching exists. Thus there must be a smallest subset $`B`$ of $`𝒜`$ which is not the set of endpoints of a matching in this graph and this set must have at most $`|V|`$ elements. Clearly, $`B`$ contains at least two vertices. Now, by the minimality of $`B`$ there is a matching $`M`$ in $`H`$ of size $`|B|1`$ whose endpoints in $`𝒜`$ are in $`B`$. Further, classical results in matching theory (see e.g. Theorem 1.1.3 of ) tell us that if $`W`$ is the set of endpoints of $`M`$ in $`V`$ then for $`vW`$, we have $`L(v)B=\mathrm{}`$.

Let $`x`$ be any vertex in $`GW`$ and replace $`L(v)`$ by $`L(x)`$ for every vertex $`vW`$. This yields a new List Colouring Problem in which the total number of colours in all lists is smaller than $`|𝒜|`$ (since all the new list are disjoint from B). Therefore by the minimality of our original choice, there exist an acceptable colouring of $`G`$ for this new Lists Colouring instance. In particular this implies that we can obtain an acceptable colouring of $`GW`$ for the original lists $`L(v)`$. Since no colour in $`B`$ is used in this colouring, using the colouring of $`W`$ pointed out by $`M`$ yields an extension of this colouring to a colouring of $`G`$ in which no colour of $`B`$ appears more than once. This contradicts our assumption that there is no acceptable colouring for this instance and proves the lemma. $`\mathrm{}`$

Proof of Theorem 1. Let $`0<ϵ<1`$ be a fixed constant and let $`G`$ be a graph satisfying $`|V(G)|<(2ϵ)\chi (G)`$. We assume that $`\chi ^l(G)>\chi (G)`$ and obtain a contradiction. Since adding an edge between vertices in different colour classes in an optimal colouring of $`G`$ does not change $`\chi (G)`$ and can only increase $`\chi ^l(G)`$, we will assume that $`G`$ is complete $`\chi (G)`$-partite graph. Thus $`G`$ has a unique partition into $`\chi (G)`$ stable sets. We refer to these stable sets as parts rather than colour classes so as to avoid confusion with the colours used in our acceptable colouring of $`G`$.

Now by Lemma 2, if $`\chi ^l(G)>\chi (G)`$ then there is an instance of List Colouring on $`G`$ for which no acceptable colouring exists, in which each list has length at least $`\chi (G)`$ and such that the size of the union of all lists $`L(v)`$ is less than $`|V(G)|`$. This means that in an acceptable colouring at least one colour must be used on more than one vertex. Fortunately, it also implies that for every non-singleton part $`U`$ there is at least one colour which appears on $`L(v)`$ for more than half the vertices of $`U`$ (since each $`L(v)`$ contains more than half the colours).

Our proof approach is simple. For each non-singleton part $`U`$, we choose some colour $`c_U`$ and colour with $`c_U`$ all the vertices of $`U`$ whose list contains $`c_U`$ (thus we must insist that all the $`c_U`$ are distinct). We complete the colouring by finding a bijection between the vertices not yet coloured and the colours not yet used so that each such colour is in the list of the vertex with which it is matched. This yields an acceptable colouring in which for each part $`U`$ there is at most one colour $`c_U`$ used on more than one vertex of $`U`$.

To begin, we consider the case when there is some part $`U`$ such that some colour appears on all the vertices of $`U`$. We show that we can reduce to a smaller problem by using any such colour for $`c_U`$. Iteratively repeating this process yields a graph where no such $`U`$ exists and hence, in particular, there are no parts of size two.

Our choices for the remaining $`c_U`$ are discussed in the proof of the key Lemma 3 which consists of the analysis of a probabilistic procedure for choosing the remaining $`c_U`$. Unfortunately, before discussing this procedure we need to deal with some technical details.

So, to begin we show that we can assume that $`_{vU}L(v)`$ is empty for all parts $`U`$ of size bigger than $`1`$ in the partition of $`G`$. To see this, let $`U`$ be a part of size at least $`2`$ such that $`_{vU}L(v)\mathrm{}`$. Then the graph $`GU`$ has chromatic number $`\chi (G)1`$ and at most $`|V(G)|2`$ vertices and therefore also satisfies

$$|V(GU)||V(G)|2(2ϵ)\chi (G)2=(2ϵ)(\chi (G)1)ϵ<(2ϵ)\chi (GU).$$

Note that it also satisfies $`\chi ^l(GU)>\chi (GU)=\chi (G)1`$ since otherwise we can obtain an acceptable colouring of $`G`$ from the lists $`L(v)`$. Indeed, let $`c`$ be a colour in $`_{vU}L(v)`$. Since $`\chi ^l(GU)=\chi (G)1`$, we know there is an acceptable colouring of $`GU`$ from the lists $`L(v)c`$. Colouring all vertices in $`U`$ with $`c`$ we obtain an extension of this colouring to an acceptable colouring of $`G`$ from the original lists, a contradiction. Therefore we will consider the graph $`GU`$ instead of $`G`$ and continue this process until we obtain a graph $`G^{}`$ and an instance of List Colouring on $`G^{}`$ with the following properties.

* $`G^{}`$ is $`\chi (G^{})`$-partite graph which satisfies $`|V(G^{})|<(2ϵ)\chi (G^{})`$.
* Each list $`L^{}(v)`$ has length at least $`\chi (G^{})`$ and there is no acceptable colouring of $`G^{}`$ from $`L^{}(v)`$.
* The size of the union of all lists is less than $`|V(G^{})|`$.
* $`_{vU}L^{}(v)`$ is empty for all parts of size bigger than $`1`$ in the partition of $`G^{}`$.

Since the size of the lists is $`\chi (G^{})>|V(G^{})|/2`$ we obtain that $`L^{}(x)L^{}(y)`$ is non empty for any two vertices $`\{x,y\}`$ in $`G^{}`$. In particular this implies that in the partition of $`G^{}`$ there are no parts of size two. Note that the original graph $`G`$ has at most $`|V(G)|/2`$ parts of size $`2`$ and each time we removed such a part the chromatic number of the remaining graph decreased by one. Therefore we decrease chromatic number of $`G`$ by at most $`|V(G)|/2`$ and hence the remaining graph $`G^{}`$ should have at least

$$|V(G^{})|\chi (G^{})\chi (G)\frac{|V(G)|}{2}\frac{|V(G)|}{2ϵ}\frac{|V(G)|}{2}\frac{ϵ|V(G)|}{4}$$

vertices. So by choosing an appropriate bound on the size of $`|V(G)|`$ we can make $`|V(G^{})|`$ arbitrarily large. This completes our discussion of parts $`U`$ for which some colour is in $`L(v)`$ for all vertices $`v`$ of $`U`$. We turn now to the technical details necessary before we present the rest of the ideas needed in the proof.

Let $`X`$ be the set of all the vertices in the singleton classes in the partition of $`G^{}`$. Pick $`m`$ to be a sufficiently large integer constant $`m=m(ϵ)`$ and let $`t`$ be an integer which satisfies

$`{\displaystyle \frac{t+1}{m}}{\displaystyle \frac{|X|}{\chi (G^{})}}{\displaystyle \frac{t+2}{m}}.`$ (2.1)
Since in the partition of $`G^{}`$ there are no parts of size two, we obtain that $`|X|+3(\chi (G^{})|X|)|V(G^{})|<(2ϵ)\chi (G^{})`$. This implies that $`|X|(1+ϵ)\chi (G^{})/2`$ and that $`m/2<tm2`$.

Set $`𝒜=_{vG^{}}L^{}(v)`$. Let $`H`$ be a bipartite graph with bipartition $`(X,𝒜)`$ and an edge between $`c`$ and $`v`$ precisely when $`cL^{}(v)`$. Note that the degree of every vertex from $`X`$ in $`H`$ is at least $`\chi (G^{})|V(G^{})|/2>|𝒜|/2`$. Therefore by well known results on Zarankiewicz’s problem (see, e.g., , Problem 10.37), $`H`$ contains a complete bipartite graph with $`t`$ vertices in $`X`$ and $`m`$ vertices in $`𝒜`$. Denote the set of vertices from $`X`$ and $`𝒜`$ by $`𝒮_1`$ and $`𝒞_1`$ respectively and remove them from $`H`$. Note that the bound on Zarankiewicz’s problem guarantees that we will continue to find a copy of the complete bipartite graph $`K_{t,m}`$ in $`H`$ until the minimal degree of a vertex in $`X`$ is $`o(\chi (G^{}))=o(|𝒜|).`$ Thus in the end we obtain at least $`k=(1o(1))\chi (G^{})/m`$ disjoint sets of colours $`𝒞_1,\mathrm{},𝒞_k`$ and also $`k`$ disjoint sets of singleton partition classes $`𝒮_1,\mathrm{},𝒮_k`$, such that $`𝒞_iL^{}(s)`$ for every vertex $`s𝒮_i`$. Denote by $`𝒞=_i𝒞_i`$, by $`𝒮=_i𝒮_i`$ and let $`C`$ and $`S`$ be the sizes of $`𝒞`$ and $`𝒮`$ respectively. Now using (2.1) we can obtain the following inequalities

$`|X|S`$ $`=`$ $`|X|kt{\displaystyle \frac{t+2}{m}}\chi (G^{})(1+o(1)){\displaystyle \frac{t}{m}}\chi (G^{})`$
$`=`$ $`(1+o(1)){\displaystyle \frac{2}{m}}\chi (G^{})=(2+o(1))k<3k`$
and

$$|X|S=|X|kt\frac{t+1}{m}\chi (G^{})(1+o(1))\frac{t}{m}\chi (G^{})=(1+o(1))\frac{\chi (G^{})}{m}.$$

In the above discussion and in particular in the last two inequalities we used that $`m`$ and $`t`$ are constants but $`|V(G^{})|`$ (and thus also $`\chi (G^{})`$) tends to infinity.

Let $`W`$ be the union of some set of $`r=\chi (G^{})|𝒞|`$ singleton partition classes which do not belong to $`𝒮`$. Such a set $`W`$ exists, since the number of singleton partition classes outside $`𝒮`$ is at least $`(1+o(1))\chi (G^{})/mr=\chi (G^{})km=o(\chi (G^{}))`$. Note that we can obtain an acceptable colouring of $`W`$ with the lists $`L^{}(v)𝒞`$ greedily, since the size of $`L^{}(v)𝒞`$ is equal to $`r`$. Let $`T`$ be the set of $`r`$ colours used to colour $`W`$ in one such acceptable colouring. Denote by $`G^{\prime \prime }=G^{}W`$ and let $`L^{\prime \prime }(v)=L^{}(v)T`$ for every vertex $`vG^{\prime \prime }`$. Then to finish the proof it is enough to show the existence of an acceptable colouring of the $`G^{\prime \prime }`$ from the set of lists $`L^{\prime \prime }(v)`$.

By definition, we have that $`\chi (G^{\prime \prime })=\chi (G^{})r=|𝒞|=C`$ and $`G^{\prime \prime }`$ is a complete $`C`$ partite graph. The number of vertices of $`G^{\prime \prime }`$ satisfies

$$|V(G^{\prime \prime })|=|V(G^{})|r<|V(G^{})|<(2ϵ)\chi (G^{})=(1+o(1))(2ϵ)\chi (G^{\prime \prime }).$$

So by choosing $`\delta =ϵ/2`$ we obtain that $`|V(G^{\prime \prime })|<(2\delta )\chi (G^{\prime \prime })`$. This together with above discussion implies that $`G^{\prime \prime }`$ satisfies all the condition ($`1`$$`5`$) of the next lemma. This lemma guarantees the existence of an acceptable colouring of $`G^{\prime \prime }`$ from the set of lists $`L^{\prime \prime }(v)`$ and completes the proof of Theorem 1.

###### Lemma 3

Let $`0<\delta <1`$ be a constant and let $`C,S,k,m,t`$ and $`n`$ be integers with $`m>6/\delta `$, $`C=km`$, $`S=kt`$ and $`n<(2\delta )C`$. Suppose, in addition, that $`m`$ is fixed and $`n`$ (and hence $`C`$) is a sufficiently large function of $`m`$. Let $`G`$ be a complete $`C`$-partite graph on $`n`$ vertices and let $`L(v)`$ be the set of lists of colours of size $`C`$ one for each vertex $`v`$ of $`G`$ such that the following holds.

1. $`_{vU}L(v)=\mathrm{}`$ for any part $`U`$ of size bigger than one in the partition of $`G`$.
2. $`G`$ contains a set of vertices $`𝒮`$ of size $`S`$ such that the vertices in $`𝒮`$ form parts of size one in the partition of $`G`$. The set $`𝒮`$ is partitioned into $`k`$ parts $`𝒮_1,\mathrm{},𝒮_k`$ each of size $`t`$.
3. $`G`$ contains no parts of size two and at most $`3k`$ singleton parts which do not belong to $`𝒮`$.
4. There exist a set of colours $`𝒞`$ of size $`C`$ and its partition $`𝒞_1,\mathrm{},𝒞_k`$ into $`k`$ sets of size $`m`$. Such that $`𝒞_iL(s)`$ for every vertex $`s𝒮_i`$. In particular, for any subset of $`𝒞_i`$ of size $`t`$ there exist an acceptable colouring of the vertices of $`𝒮_i`$ which uses the colours in this subset.
5. The total number of colours in the union of all the lists $`L(v)`$ is less than $`n`$.

Then there exist an acceptable colouring of $`G`$ from the lists $`L(v)`$.

We finish this section with discussion of the proof of Lemma 3. We postpone all the details to the subsequent sections of the paper.

Proof Overview. The proof proceeds as follows:

1. We choose a random partition of each $`𝒞_i`$ into two subsets $`𝒜_i`$ of size $`t`$ and $`_i`$ of size $`mt`$ where these choices are made uniformly and independently.
2. We use the colours in $`𝒜_i`$ to colour the vertices of $`𝒮_i`$ which is possible by Condition 4 of the lemma.
3. We choose a (random) bijection between $`=_{i=1}^k_i`$ and the parts of $`G`$ not in $`𝒮`$ in such a way that, for each part $`U`$ not in $`𝒮`$, $`U`$ is equally likely to correspond to each colour $`c`$. We denote by $`c_U`$ be the colour corresponding to $`U`$.
4. For each part $`U`$ not in $`𝒮`$ we colour every vertex $`v`$ of $`U`$ for which $`c_UL(v)`$ with the colour $`c_U`$.
5. We match the set $`V^{}`$ of vertices not yet assigned a colour with the set of colours not yet used (i.e those colours not in $`𝒞`$) so that every vertex is matched with a colour on its list. We colour each vertex of $`V^{}`$ with the colour with which it is matched.

If we successfully complete this five step process, we have an acceptable colouring as every colour not in $``$ appears on at most one vertex, and every colour in $``$ appears only on a subset of some part, and hence on an independent set of $`G`$.

To prove that we can find the colouring in this fashion, we need to describe and analyze our method for choosing the random bijection between the parts and the colours in $`𝒞`$ made in Steps I–IV, in order to show that (with positive probability) we can complete the colouring by finding the desired matching in Step V.

A key tool will be Hall’s Theorem which states that in a bipartite graph with bipartition $`(A,B)`$, we can find a matching $`M`$ such that every vertex of $`A`$ is the endpoint of an edge of $`M`$ provided there is no subset $`X`$ of $`A`$ such that setting $`N(X)=\{N(x)|xX\}`$ we have $`|N(X)|<|X|`$.

We remark that although Steps I–III are presented as though they are separate processes performed sequentially, in the more complicated case of our analysis we will need to interleave these processes by first choosing some of the $`_i`$, then choosing the parts with which these colours will be matched, and finally completing Step I and then Step III.

To determine if we can find the desired matching in Step V, we will need to examine the sets $`L^{}(v)=L(v)𝒞`$ for the vertices of $`V^{}`$. Let $`H`$ be a bipartite graph with bipartition $`(V^{},_vL^{}(v))`$ and an edge between $`c`$ and $`v`$ precisely when $`cL^{}(v)`$. For each vertex $`v`$, we let the weight of $`v`$, denoted $`w(v)`$, be $`\frac{1}{|L^{}(v)|}`$. For any set $`S`$ of vertices we use $`W(S)`$ to denote the sum of the weights of the vertices in $`S`$.

This definition of weight is motivated by the following immediate consequence of Hall’s Theorem:

###### Observation 4

If we cannot find the desired matching in Step 5 then there exist a subset $`X`$ of $`V^{}`$ such that $`W(X)>1`$. In this case $`W(V^{})>1`$ as well.

Proof. By Hall’s Theorem there exist a subset $`X`$ of $`V^{}`$ such that $`|N(X)|<|X|`$. Then, we obtain that

$$W(V^{})W(X)=\underset{xX}{}\frac{1}{|L^{}(v)|}=\underset{xX}{}\frac{1}{|N(x)|}\underset{xX}{}\frac{1}{|N(X)|}\frac{|X|}{|N(X)|}>1.\mathrm{}$$

Thus an analysis of the random parameter $`W(V^{})`$ will be crucial to the proof of the lemma. In the next section, by computing the expected value of the parameter, we show that the lemma holds if $`nC+S`$. In later sections, we complete the proof using a more complicated analysis along the same lines.

## 3. The expected value of $`𝑾\mathbf{(}𝑽^{\mathbf{}}\mathbf{)}`$

For each part $`U`$ which is not in $`𝒮`$, our choices in Steps I and III guarantee that each colour of $`𝒞`$ is equally likely to be $`c_U`$. Thus, for each vertex $`v`$ in such a part, the probability that $`v`$ is in $`V^{}`$, i.e., $`c_UL(v)`$, is $`1\frac{|L(v)𝒞|}{C}`$. Since $`|L(v)|=C`$, this is $`\frac{|L^{}(v)|}{C}`$. So, we have:

$$𝐄\left(W(V^{})\right)=\underset{vV𝒮}{}w(v)\mathrm{𝐏𝐫}(vV^{})=\underset{vV𝒮}{}\frac{1}{L^{}(v)}\frac{L^{}(v)}{C}=\frac{nS}{C}.$$
(3.1)
So, if $`nS+C`$, then this expected value is less than or equal to one. Since the probability that a random variable exceeds its expected value is less than one, this implies that we can make the choices in Steps I–IV so that $`W(V^{})1`$, and hence by Observation 4, the desired matching can be found in Step V.

Analyzing the behaviour of the (random) weights of various subsets of $`V^{}`$ will allow us extend our proof technique to handle larger values of $`n`$. In doing so, the following definitions and observations will prove useful.

We let $`A`$ be the number of non-singleton parts. Then by Condition 3 of the lemma, $`A`$ is at least $`CS3k`$. Since each non singleton colour class has at least three vertices and the total number of classes is $`C`$, we obtain $`(2\delta )CnC+2A`$, i.e., $`A\frac{(1\delta )C}{2}`$. On the other hand, the analysis above shows that we can assume that $`n>S+C`$ and hence that $`S(1\delta )C`$. Thus, $`A\delta C3k=\delta C\frac{3}{m}C\frac{\delta C}{2}`$. Both these bounds on $`A`$ will be useful in our analysis. Note also that

$$mt=\frac{CS}{k}\frac{C(1\delta )C}{k}=\delta \frac{C}{k}=\delta m.$$

## 4. Completing the proof: the idea

Let $`H`$ be a bipartite graph with bipartition $`(V^{},_vL^{}(v))`$ and an edge between $`c`$ and $`v`$ precisely when $`cL^{}(v)`$. Our first step will be to check Hall’s criterion for a fixed subset of colours $`K`$ in $`_vL^{}(v)`$ and show that the expected number of vertices in $`\{v|vV^{},L^{}(v)K\}`$ is less than $`|K|`$.

To begin, we note that for any such $`v`$, $`w(v)\frac{1}{|K|}`$. Therefore, defining the set $`S_K`$ to be $`S_K=\{v|vV^{},L^{}(v)K\}`$, we have that

$`𝐄\left(|S_K|\right)`$ $`=`$ $`{\displaystyle \underset{vV𝒮,L^{}(v)K}{}}\mathrm{𝐏𝐫}(vV^{})|K|{\displaystyle \underset{vV𝒮,L^{}(v)K}{}}w(v)\mathrm{𝐏𝐫}(vV^{})`$
$``$ $`|K|{\displaystyle \underset{vV𝒮}{}}w(v)\mathrm{𝐏𝐫}(vV^{})=|K|𝐄\left(W(V^{})\right)=|K|{\displaystyle \frac{nS}{C}}`$
which, since $`n(2\delta )CS+A+3k+(1\delta )C`$, is at most $`|K|(1+\frac{A+3k}{C}\delta )`$. On the other hand, this estimate is not good enough to guarantee Hall’s criterion, since it still can be greater than $`|K|`$.

To improve on this bound, we use the fact that no colour $`c`$ appears on the list of all the vertices of any non-singleton part of $`G`$. Note that $`k=C/m`$, $`m>6/\delta `$, the number of non-singleton parts is $`A`$ and the total number of vertices is at most $`n(2\delta )CS+A+3k+(1\delta )C`$. This altogether implies that for every $`c`$,

$`𝐄\left(W\left(V^{}\{v|cL^{}(v)\}\right)\right)`$ $`=`$ $`𝐄\left(W(V^{})\right){\displaystyle \underset{vV𝒮,cL^{}(v)}{}}w(v)\mathrm{𝐏𝐫}(vV^{})`$ (4.1)
$`=`$ $`𝐄\left(W(V^{})\right){\displaystyle \underset{vV𝒮,cL^{}(v)}{}}{\displaystyle \frac{1}{C}}{\displaystyle \frac{nS}{C}}{\displaystyle \frac{A}{C}}`$
$`=`$ $`{\displaystyle \frac{nSA}{C}}{\displaystyle \frac{(1\delta )C+3k}{C}}`$
$`=`$ $`1\delta +{\displaystyle \frac{3}{m}}1{\displaystyle \frac{\delta }{2}}.`$
Applying this fact for the $`c`$ in $`K`$ allows us to improve our bound on $`𝐄\left(|S_K|\right)`$. Specifically, we note that summing this bound over all the colours $`c`$ in $`K`$

$$𝐄\left(\underset{cK}{}W\left(V^{}\{v|cL^{}(v)\}\right)\right)=\underset{cK}{}𝐄\left(W\left(V^{}\{v|cL^{}(v)\}\right)\right)\left(1\frac{\delta }{2}\right)|K|.$$

Now, each vertex $`v`$ of $`S_K`$ contributes $`w(v)=1/|L^{}(v)|`$ to exactly $`|L^{}(v)|`$ terms in the first sum in this equation, so its total contribution to the sum is 1. I.e., we have:

$$𝐄\left(|S_K|\right)\left(1\frac{\delta }{2}\right)|K|.$$

So, we don’t expect any particular set $`K`$ of colours to provide an obstruction to finding the desired matching in the bipartite graph $`H`$ in Step V. However, we need to handle all the $`K`$ at once. In order to do so, we would like to prove that for each $`K`$, the size of $`S_K`$ is highly concentrated around its expected value and hence is greater than $`|K|`$ only with exponentially small probability. As above, rather than focusing on all the $`K`$ we actually consider, for each colour c, the weight of the subset $`V_c^{}`$ of $`V^{}`$ consisting of those $`v`$ with $`c`$ on $`L^{}(v)`$. There are two major difficulties which complicate our approach.

* some of the parts $`U`$ can be very large making it impossible for us to obtain the desired concentration results directly (e.g., there could be a part of size exceeding $`\frac{n}{3}`$).
* If $`L^{}(v)`$ is very small then $`w(v)=1/|L^{}(v)|`$ is large and putting $`v`$ into $`V^{}`$ can have a significant effect on the weight of the various $`V_c^{}`$. This makes proving a concentration result directly impossible.

In order to deal with these problems, we proceed as follows:

1. We colour the “big” parts first, ignoring concentration in our computation and focusing only on the expected weight of the subset of $`V^{}`$ intersecting the big parts. We note that by considering the expected overall weight and not focusing on a specific $`V_c^{}`$, we only lose a factor of $`\frac{1}{C}`$ per part. We will define big parts so that there are $`o(1)`$ of them, and hence the total loss will not be significant.
2. We treat $`v`$ with $`|L^{}(v)|`$ small separately using an expected value argument to bound the weight of the vertices in this set.

## 5. Completing the proof: the details

In this section we will complete the proof of Lemma 3 using the ideas which have already been discussed above. We choose an integer $`b`$ so that

$$\frac{\delta ^2C}{40}b(mt)\frac{\delta ^2C}{20}$$

which is possible because $`m\frac{\delta ^2C}{40}`$ (this holds, since $`m`$ and $`\delta `$ are fixed but $`C`$ tends to infinity) and $`mt>0`$ (in fact it exceeds $`\delta m`$ as we remarked at the end of Section 3.). We call the largest $`b(mt)`$ parts in our partition of $`G`$ big, and the others small. Let $`Big`$ be the union of the vertex sets of the big parts. We will need the following lemma.

###### Lemma 5

Every small non-singleton partition class contains at least two $`v`$ which satisfy:

$$|L^{}(v)|>\frac{\delta ^3}{80}C.$$

Proof. Let $`U`$ be a small non-singleton colour class. We already mentioned that every colour of $`𝒞`$ is missed by a vertex of $`U`$ so $`_{vU}|L^{}(v)|=_{vU}|𝒞L(v)||𝒞|=C`$. Now, since there are less than $`n<(2\delta )C`$ colours in total, every $`L(v)`$ must contain at least $`\delta C`$ colours in $`𝒞`$ and so the largest $`L^{}(v)=L(v)𝒞`$ in $`U`$ has at most $`(1\delta )C`$ elements. Thus, the sum of $`|L^{}(v)|`$ over the remaining vertices of $`U`$ is at least $`\delta C`$.

Since there are at least $`\frac{\delta ^2C}{40}`$ big colour classes, the largest small colour class has at most $`\frac{40n}{\delta ^2C}<\frac{80}{\delta ^2}`$ vertices. So, the second largest $`L^{}(v)`$ has size at least $`\delta C(\frac{80}{\delta ^2})^1`$. This is the desired result. $`\mathrm{}`$

With this auxiliary result in hand, we can now complete the proof. We proceed as follows:

First Process: We randomly choose $`b`$ of the $`𝒞_i`$ and a partition of each of these into subsets $`𝒜_i`$ of size $`t`$ and $`_i`$ of size $`mt`$ where these choices are all made independently and uniformly. We then choose a uniformly random bijection between the $`b(mt)`$ colours in the union of these $`_i`$ and the big parts.

Second Process: We chose a partition of each remaining $`𝒞_i`$ into $`𝒜_i`$ and $`_i`$ where again these choices are uniform, independent, and independent of all the earlier choices. We then choose a uniformly random bijection between the colours in these $`_i`$ and the small parts.

Denote by $`c_U`$ the colour which is assigned by the above bijection to the partition class $`U`$. Use the colours in $`𝒜_i`$ to colour the vertices of $`𝒮_i`$ and for each part $`U`$ not in $`𝒮`$ colour every vertex $`v`$ of $`U`$ for which $`c_UL(v)`$ with the colour $`c_U`$. Let $`V^{}`$ be a set of vertices not yet assigned a colour. We set $`V^{\prime \prime }=V^{}Big`$ and $`V^{\prime \prime \prime }=V^{}Big`$.

Note that $`V^{\prime \prime \prime }`$ is determined by our choices in the first process. So, using a computation similar to that in (3.1) we obtain

$$𝐄\left(W(V^{\prime \prime \prime })\right)=\underset{vBig}{}w(v)\mathrm{𝐏𝐫}(vV^{\prime \prime \prime })=\underset{vBig}{}\frac{1}{L^{}(v)}\frac{L^{}(v)}{C}=\frac{|Big|}{C}.$$

Furthermore, by the definition of expectation, there exist at least one set of choices for the first process such that $`W(V^{\prime \prime \prime })𝐄(W(V^{\prime \prime \prime }))=\frac{|Big|}{C}`$. We condition on any such set of choices which ensures that this inequality holds. We use $`\mathrm{𝐂𝐏}`$ and $`\mathrm{𝐂𝐄}`$ for the conditional probability of an event and conditional expectation of a variable for the second process, given this set of choices.

Let $`𝒞^{}`$ be the union of the set of colours in the $`𝒞_i`$ which were chosen in the first process. At the end of Section 3 we proved that $`mt`$ is at least $`\delta m`$. Therefore $`|𝒞^{}|=mb=\frac{m}{mt}b(mt)\delta ^1\frac{\delta ^2C}{20}=\frac{\delta C}{20}`$. Hence, we have that for every $`v`$ in a small part which is not in $`𝒮`$,

$`\mathrm{𝐂𝐏}(vV^{\prime \prime })`$ $``$ $`{\displaystyle \frac{|L^{}(v)|}{C|C^{}|}}{\displaystyle \frac{|L^{}(v)|}{C}}\left(1+{\displaystyle \frac{|C^{}|}{C|C^{}|}}\right){\displaystyle \frac{|L^{}(v)|}{C}}\left(1+{\displaystyle \frac{\delta /20}{1\delta /20}}\right)`$
$``$ $`\left(1+{\displaystyle \frac{\delta }{10}}\right){\displaystyle \frac{|L^{}(v)|}{C}}=\left(1+{\displaystyle \frac{\delta }{10}}\right)\mathrm{𝐏𝐫}(vV^{\prime \prime }).`$
Clearly, this implies that for every subset $`X`$ of the set of vertices $`V𝒮Big`$ we have

$$\mathrm{𝐂𝐄}\left(W(V^{\prime \prime }X)\right)\left(1+\frac{\delta }{10}\right)𝐄\left(W(V^{\prime \prime }X)\right).$$

In particular, for every colour $`c`$

$$\mathrm{𝐂𝐄}\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v)\}\right)\right)\left(1+\frac{\delta }{10}\right)𝐄\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v)\}\right)\right)$$
(5.1)
and also

$$\mathrm{𝐂𝐄}\left(W\left(V^{\prime \prime }\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right)\right)$$
(5.2)
$$\left(1+\frac{\delta }{10}\right)𝐄\left(W\left(V^{\prime \prime }\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right)\right).$$

Before we proceed with the proof, we need the following lemma.

###### Lemma 6

For every color $`c`$ the probability that

$$W\left(V^{\prime \prime }\left\{v\right|cL^{}(v),|L^{}(v)|\frac{n}{\mathrm{log}n}\}\right)$$

$$>\mathrm{𝐂𝐄}\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v),|L^{}(v)|\frac{n}{\mathrm{log}n}\}\right)\right)+\frac{\delta }{20}$$

is $`o(n^1)`$.

Proof. To prove the lemma we need the following variant of a standard large deviation inequality for martingales. Since the proof of this inequality is essentially the same as other proofs which already appeared in the literature (see, e.g., Section 3 of the survey ), we will omit it here.

Given a finite set $`\{1,2,\mathrm{},r\}`$, let $`S_r`$ denotes the set of all $`r!`$ permutations or linear orders on this set. Let $`𝐗=(X_1,\mathrm{},X_l)`$ be a family of independent random variables, where the random variable $`X_j`$ takes values in a finite set $`\mathrm{\Omega }_j`$. Thus $`𝐗`$ takes values in the set $`\mathrm{\Omega }=_j\mathrm{\Omega }_j`$. Let $`\pi S_r`$ be a random permutation independent from $`𝐗`$. Suppose that the non-negative real-valued function $`h:\mathrm{\Omega }\times S_r`$ satisfies the following two conditions for every $`(𝐱,\pi )`$.

* For every $`j`$, changing the value of a coordinate $`x_j`$ can change the value of $`h(𝐱,\pi )`$ by at most $`d`$.
* Swapping any two elements in permutation $`\pi `$ can change the value of $`h(𝐱,\pi )`$ by at most $`d`$.

Denote by $`𝐄h`$ the expected value of $`h`$. Then for every $`t0`$ we have that

$$\mathrm{𝐏𝐫}\left(|h𝐄h|>t\right)e^{\mathrm{\Omega }\left(\frac{t^2}{(r+l)d^2}\right)}.$$

Now fix a color $`c`$ and define the function $`h`$ to be

$$h(𝐱,\pi )=W\left(V^{\prime \prime }\left\{v\right|cL^{}(v),|L^{}(v)|\frac{n}{\mathrm{log}n}\}\right),$$

where $`(𝐱,\pi )`$ corresponds to the set of random choices for the second process. More precisely, $`x_i`$ is a random partition of the set $`𝒞_i`$ into subsets $`𝒜_i`$ and $`_i`$ and $`\pi `$ is a random bijection between the colors in these $`_i`$ and the small parts of $`G`$. Since we can fix one canonical ordering of these small parts we can assume that $`\pi `$ is just a random permutation of the set of colors which is, by definition, independent from the variables $`x_i`$.

Next, note that changing the outcome of the variable $`x_i`$, i.e., changing one particular $`_i`$ can only affect vertices in at most $`mt`$ small parts of $`G`$. As we already mentioned in the proof of Lemma 5, each small part contains at most $`80/\delta ^2`$ vertices. Since we considering only vertices $`v`$ satisfying $`|L^{}(v)|\frac{n}{\mathrm{log}n}`$, the weight of such a vertex is at most $`w(v)=1/|L^{}(v)|\frac{\mathrm{log}n}{n}`$. Therefore, changing outcome of one $`x_i`$ can change the value of $`h`$ by at most $`(mt)\frac{80}{\delta ^2}\frac{\mathrm{log}n}{n}=O\left(\frac{\mathrm{log}n}{n}\right)=d`$. Similarly swapping any two colors in $`\pi `$ can affect only vertices in two small parts of $`G`$. So again this can only change $`h`$ by at most $`d=O\left(\frac{\mathrm{log}n}{n}\right)`$.

Since the total number of random variables $`x_i`$ and also the length of permutation $`\pi `$ are bounded by $`n`$ we have that in our case $`(r+l)d^2O\left(n(\frac{\mathrm{log}n}{n})^2\right)=O\left(\frac{\mathrm{log}^2n}{n}\right)`$. Therefore it follows form the above large deviation inequality that

$$\mathrm{𝐏𝐫}\left(h𝐄h>t=\frac{\delta }{20}\right)e^{\mathrm{\Omega }\left(\frac{t^2}{(r+l)d^2}\right)}=e^{\mathrm{\Omega }\left(\frac{(\delta /20)^2}{O(\mathrm{log}^2n/n)}\right)}=e^{\mathrm{\Omega }\left(\frac{n}{\mathrm{log}^2n}\right)}=o(n^1).$$

This completes the proof of the lemma. $`\mathrm{}`$

Now, using the fact that the total number of colors is at most $`n`$, we deduce from this lemma that with probability $`1o(1)`$ the following holds for every color $`c`$

$$W\left(V^{\prime \prime }\left\{v\right|cL^{}(v),|L^{}(v)|\frac{n}{\mathrm{log}n}\}\right)$$
(5.3)
$$\mathrm{𝐂𝐄}\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v),|L^{}(v)|\frac{n}{\mathrm{log}n}\}\right)\right)+\frac{\delta }{20}.$$

In addition, we also want to satisfy the following inequality:

$$W\left(V^{\prime \prime }\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right)$$
(5.4)
$$\left(1+\frac{\delta }{10}\right)\mathrm{𝐂𝐄}\left(W\left(V^{\prime \prime }\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right)\right).$$

Since the probability that this last inequality fails is at most $`\frac{1}{1+\delta /10}<1o(1)`$, there does indeed exist a set of random choices for the second process which satisfies simultaneously (5.3) and (5.4).

Fix any such set of choices. Then, combining the inequalities (5.2) and (5.4) together with the facts that $`W(V^{\prime \prime \prime })\frac{|Big|}{C}`$ and $`V^{}=V^{\prime \prime }V^{\prime \prime \prime }`$ we obtain that

$$W\left(V^{}\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right)W\left(V^{\prime \prime }\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right)+W\left(V^{\prime \prime \prime }\right)$$

$`\left(1+{\displaystyle \frac{\delta }{10}}\right)^2𝐄\left(W\left(V^{\prime \prime }\left\{v\right||L^{}(v)|<{\displaystyle \frac{n}{\sqrt{\mathrm{log}n}}}\}\right)\right)+{\displaystyle \frac{|Big|}{C}}.`$ (5.5)
Note that, by Lemma 5, every small non-singleton partition class contains at least two vertices $`v`$ such that $`|L^{}(v)|>\frac{\delta ^3}{80}C=\mathrm{\Omega }(n)>\frac{n}{\sqrt{\mathrm{log}n}}`$. Since the number of small non-singleton partition classes is at least $`A\frac{\delta ^2}{20}C`$ we obtain that

$$\left|(V𝒮Big)\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right|nS|Big|2\left(A\frac{\delta ^2}{20}C\right)$$

$``$ $`(2\delta )CS|Big|2A+{\displaystyle \frac{\delta ^2}{10}}C`$
$`=`$ $`(1\delta )C|Big|+(CSA)A+{\displaystyle \frac{\delta ^2}{10}}C`$
$``$ $`(1\delta )C|Big|+3kA+{\displaystyle \frac{\delta ^2}{10}}C`$
$``$ $`\left(1{\displaystyle \frac{4}{5}}\delta \right)C|Big|.`$
Here, in the last inequality we used that $`A>\frac{\delta }{2}C>\frac{3}{m}C=3k`$ and $`\delta ^2\delta `$. Note that a similar computation as in (3.1) shows that for any subset $`YV𝒮`$ the expectation $`𝐄\left(W(V^{}Y)\right)=\frac{|Y|}{C}`$. In particular, for $`Y=\left(V𝒮Big\right)\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}`$ we obtain

$`𝐄\left(W\left(V^{\prime \prime }\left\{v\right||L^{}(v)|<{\displaystyle \frac{n}{\sqrt{\mathrm{log}n}}}\}\right)\right)`$ $`=`$ $`{\displaystyle \frac{\left|(V𝒮Big)\{v||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right|}{C}}`$
$``$ $`1{\displaystyle \frac{4}{5}}\delta {\displaystyle \frac{|Big|}{C}}.`$
Combining this inequality with (5.5) we have

$`W\left(V^{}\left\{v\right||L^{}(v)|<{\displaystyle \frac{n}{\sqrt{\mathrm{log}n}}}\}\right)`$ $``$ $`\left(1+{\displaystyle \frac{\delta }{10}}\right)^2\left(1{\displaystyle \frac{4}{5}}\delta {\displaystyle \frac{|Big|}{C}}\right)+{\displaystyle \frac{|Big|}{C}}`$ (5.6)
$``$ $`\left(1+{\displaystyle \frac{\delta }{4}}\right)\left(1{\displaystyle \frac{4}{5}}\delta \right)1{\displaystyle \frac{\delta }{2}}.`$
This completes our analysis of the weight of vertices with short lists. We now consider the remaining vertices.

As we already mentioned, for every color $`c`$ and every non-singleton part of $`G`$ there is at least one vertex $`v`$ in this part such that $`cL(v)`$. Since there are at least $`A\frac{\delta ^2}{20}C`$ small non-singleton parts, a similar computations as in (4.1) shows for every color $`c`$ that

$`𝐄\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v)\}\right)\right)`$ $`=`$ $`{\displaystyle \frac{\left|(V𝒮Big)\{v|cL^{}(v)\}\right|}{C}}`$
$``$ $`{\displaystyle \frac{nS|Big|(A\frac{\delta ^2}{20}C)}{C}}`$
$``$ $`{\displaystyle \frac{(2\delta )CS|Big|A}{C}}+{\displaystyle \frac{\delta ^2}{20}}`$
$`=`$ $`(1\delta )+{\displaystyle \frac{CSA}{C}}{\displaystyle \frac{|Big|}{C}}+{\displaystyle \frac{\delta ^2}{20}}`$
$``$ $`(1\delta )+{\displaystyle \frac{3k}{C}}{\displaystyle \frac{|Big|}{C}}+{\displaystyle \frac{\delta ^2}{20}}`$
$`=`$ $`(1\delta )+{\displaystyle \frac{3}{m}}{\displaystyle \frac{|Big|}{C}}+{\displaystyle \frac{\delta ^2}{20}}`$
$$1\delta +\frac{\delta }{2}+\frac{\delta ^2}{20}\frac{|Big|}{C}1\frac{2}{5}\delta \frac{|Big|}{C}.$$

Combining this inequality with (5.1) and (5.3) and using the fact that $`V^{}=V^{\prime \prime }V^{\prime \prime \prime }`$ we will have that for every color $`c`$

$$W\left(V^{}\left\{v\right|cL^{}(v),|L^{}(v)|\frac{n}{\mathrm{log}n}\}\right)$$

$``$ $`W\left(V^{\prime \prime }\left\{v\right|cL^{}(v),|L^{}(v)|{\displaystyle \frac{n}{\mathrm{log}n}}\}\right)+W\left(V^{\prime \prime \prime }\right)`$ (5.7)
$``$ $`\mathrm{𝐂𝐄}\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v),|L^{}(v)|{\displaystyle \frac{n}{\mathrm{log}n}}\}\right)\right)+{\displaystyle \frac{\delta }{20}}+{\displaystyle \frac{|Big|}{C}}`$
$``$ $`\mathrm{𝐂𝐄}\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v)\}\right)\right)+{\displaystyle \frac{\delta }{20}}+{\displaystyle \frac{|Big|}{C}}`$
$``$ $`\left(1+{\displaystyle \frac{\delta }{10}}\right)𝐄\left(W\left(V^{\prime \prime }\left\{v\right|cL^{}(v)\}\right)\right)+{\displaystyle \frac{\delta }{20}}+{\displaystyle \frac{|Big|}{C}}`$
$``$ $`\left(1+{\displaystyle \frac{\delta }{10}}\right)\left(1{\displaystyle \frac{2}{5}}\delta {\displaystyle \frac{|Big|}{C}}\right)+{\displaystyle \frac{\delta }{20}}+{\displaystyle \frac{|Big|}{C}}`$
$``$ $`\left(1+{\displaystyle \frac{\delta }{10}}\right)\left(1{\displaystyle \frac{2}{5}}\delta \right)+{\displaystyle \frac{\delta }{20}}1{\displaystyle \frac{\delta }{4}}.`$
Recall that $`H`$ is a bipartite graph with bipartition $`(V^{},_vL^{}(v))`$ and an edge between $`c`$ and $`v`$ precisely when $`cL^{}(v)`$. Let $`K`$ be any subset of colours in $`_vL^{}(v)`$ and denote by $`S_K=\{v|vV^{},L^{}(v)K\}`$. We complete the proof of the lemma by showing that the graph $`H`$ satisfies Hall’s condition, i.e., $`|S_K||K|`$ for every set $`S_K`$. Then in Step V we can match all uncoloured vertices in $`V^{}`$ with the set of colours yet not used and and produce an acceptable coloring of $`G`$.

First, note that any set $`K`$ of fewer than $`\frac{n}{\sqrt{\mathrm{log}n}}`$ colours cannot be an obstruction to the existence of the desired matching. Indeed, if $`|S_K|>|K|`$, then by Observation 4 we have that $`W(S_K)>1`$. On the other hand, for every vertex $`vS_K`$ the size of $`L^{}(v)`$ is at most $`|K|<\frac{n}{\sqrt{\mathrm{log}n}}`$. Therefore we obtain a contradiction, since by (5.6)

$$W\left(S_K\right)W\left(V^{}\left\{v\right||L^{}(v)|<\frac{n}{\sqrt{\mathrm{log}n}}\}\right)<1\frac{\delta }{2}.$$

Turning to larger $`K`$, we note next that the inequality (5.6) yields:

$$\left|V^{}\left\{v\right||L^{}(v)|\frac{n}{\mathrm{log}n}\}\right|W\left(V^{}\left\{v\right||L^{}(v)|\frac{n}{\mathrm{log}n}\}\right)\left(\underset{v,|L^{}(v)|\frac{n}{\mathrm{log}n}}{\mathrm{min}}w(v)\right)^1$$

$`\left(1{\displaystyle \frac{\delta }{2}}\right)\left(\underset{v,|L^{}(v)|\frac{n}{\mathrm{log}n}}{\mathrm{min}}{\displaystyle \frac{1}{|L^{}(v)|}}\right)^1\left(1{\displaystyle \frac{\delta }{2}}\right){\displaystyle \frac{n}{\mathrm{log}n}}<{\displaystyle \frac{n}{\mathrm{log}n}}.`$ (5.8)
Next, observe that the set of inequalities (5.7) imply that for any set of colours $`K`$

$`\left|S_K\left\{v\right||L^{}(v)|>{\displaystyle \frac{n}{\mathrm{log}n}}\}\right|`$ $`=`$ $`{\displaystyle \underset{vS_K,|L^{}(v)|>\frac{n}{\mathrm{log}n}}{}}w(v)|L^{}(v)|`$
$``$ $`{\displaystyle \underset{cK}{}}{\displaystyle \underset{\{v|cL^{}(v),|L^{}(v)|>\frac{n}{\mathrm{log}n}\}}{}}w(v)`$
$`=`$ $`{\displaystyle \underset{cK}{}}W\left(V^{}\left\{v\right|cL^{}(v),|L^{}(v)|{\displaystyle \frac{n}{\mathrm{log}n}}\}\right)`$
$``$ $`\left(1{\displaystyle \frac{\delta }{4}}\right)|K|.`$
This, together with the inequality (5.8) yields that any set of colours $`K`$ of size at least $`\frac{n}{\sqrt{\mathrm{log}n}}`$ satisfies

$`\left|S_K\right|`$ $`=`$ $`\left|S_K\left\{v\right||L^{}(v)|>{\displaystyle \frac{n}{\mathrm{log}n}}\}\right|+\left|S_K\left\{v\right||L^{}(v)|{\displaystyle \frac{n}{\mathrm{log}n}}\}\right|`$
$``$ $`\left(1{\displaystyle \frac{\delta }{4}}\right)|K|+\left|V^{}\left\{v\right||L^{}(v)|{\displaystyle \frac{n}{\mathrm{log}n}}\}\right|`$
$``$ $`\left(1{\displaystyle \frac{\delta }{4}}\right)|K|+{\displaystyle \frac{n}{\mathrm{log}n}}<|K|.`$
Thus we obtain that these larger $`K`$ also do not violate Hall’s condition and hence the desired matching of Step V does indeed exist. This completes the proof. $`\mathrm{}`$

## 6. Concluding remarks

In this paper we proved that for every $`ϵ>0`$ and for every sufficiently large graph $`G`$ of order $`n`$, the list chromatic number of $`G`$ equals its chromatic number, provided $`n(2ϵ)\chi (G)`$. A more careful analysys of our methods yields that the value of $`ϵ`$ in this result can be made as small as $`O(1/\mathrm{log}^\eta n)`$ for any constant $`0<\eta <1`$. Nevertheless the conjecture of Ohba remains open for graphs with $`2\chi (G)`$ vertices and it seems one needs new ideas to tackle this problem. Even to show that there is a constant $`N`$ such that $`\chi ^l(G)=\chi (G)`$ for every graph $`G`$ with at most $`2\chi (G)N`$ vertices, would be very interesting.

In conclusion we would like to propose a related problem, which was motivated by Ohba’s conjecture. Let $`t`$ be an integer and let $`G`$ be a graph with at most $`t\chi (G)`$ vertices. Find the smallest constant $`c_t`$ such that for any such a graph $`G`$ its list chromatic is bounded by $`c_t\chi (G)`$. Note that Ohba’s conjecture if true, implies that $`c_2=1`$. An additional intriguing question is to determine graphs with $`|V(G)|t\chi (G)`$ and for which the ratio $`\chi ^l(G)/\chi (G)`$ is maximal. Here the case $`t=2`$ gives some indication that a complete multi-partite graph with all parts of size $`t`$ may have this property.


text:
# Forced Stratified Turbulence: Successive Transitions with Reynolds Number

## I Introduction

Most atmospheric and oceanic flows on intermediate scales of $`𝒪(1)𝒪(10^3)`$ m are strongly influenced by the stable vertical density stratification, $`d\overline{\rho }(z)/dz<0`$ (with $`\widehat{𝐳}=𝐞_3`$ anti-parallel to gravity), but are less influenced by Earth’s rotation than flows on larger scales. Consequently, the turbulence in this regime is quite different from unstratified shear turbulence, convection, and geostrophic turbulence, all of which have been more extensively studied and whose behaviors are now relatively familiar. It has been argued lilly83  that the main effect of strongly stable stratification — i.e., small Froude number, $`Fr=V/NL_v`$, where $`V`$ is a horizontal velocity scale, $`N=(g/\rho _o)d\overline{\rho }/dz`$ is the Brünt Väïssäla frequency, and $`L_v`$ is vertical length scale — is to organize the flow into two distinct, non-interacting classes: nearly linear internal gravity waves and fully nonlinear stratified turbulence. The flow patterns of stratified turbulence are often called pancake vortices kimura96  or vortical modes lelong91  because of their small aspect ratio, $`H/L`$ (where $`L`$ is a horizontal length scale), and significant vertical vorticity, neither of which is generally true for internal gravity waves. Pancake vortices have an anisotropic velocity (primarily horizontal) and shear field (primarily vertical), and they evolve principally under the nonlinear influence of horizontal advection as in two-dimensional turbulence. These motions cause little vertical turbulent heat or mass flux, and they have a highly anisotropic, inhomogeneous energy cascade to small scales and dissipation godeferd94 . At moderate values of Reynolds number — $`R=VL_h/\nu `$, where $`\nu `$ is the kinematic viscosity and $`L_h`$ is a horizontal length scale — stratified turbulence evolves self-consistently, at least in freely decaying flows, in the sense that a bulk value for $`Fr`$ does not increase with time as energy dissipation causes $`R`$ to decrease metais89 . At leading order in $`Fr`$, the inviscid dynamical balances for stratified turbulence are equivalent to two-dimensional turbulence lilly83  evolving independently at each vertical level. The energy dissipation may be modeled by adding a vertical eddy diffusion embid98  that acts to couple vertically adjacent levels and diffusively selects a limiting vertical length scale. However, with the assumption of uniform asymptotic validity as $`Fr0`$, stratified turbulence is constrained by hydrostatic and cyclostrophic force balances that also act to couple adjacent layers and may internally select a finite vertical scale as $`R\mathrm{}`$ without inducing any vertically overturning motions mcwilliams85 .

These behaviors have been studied both with laboratory experiments yap93 ; fincham96  and with numerical simulations up to $`R=𝒪(100)`$; a review of this subject has recently been made by Riley & Lelong riley00 . In the ocean and atmosphere, $`R`$ values are generally several orders of magnitude larger than those commonly reached in experiments or numerical simulations. Thus, an important open question is whether the preceding wave-turbulence partition remains valid at very large $`R`$. A central part of this question is whether the pancake vortices persist and remain “stable” with respect to overturning motions.

The dynamical stability properties of a stably stratified shear flow are usually related to the Richardson number, $`Ri`$, locally defined by

$$Ri=\frac{g}{\rho _o}\frac{\rho }{z}\left(\frac{𝐮_h}{z}\right)^2=\left(N^2+\frac{\theta }{z}\right)\left(\frac{𝐮_h}{z}\right)^2,$$
(1)
where $`𝐮_h`$ is the horizontal velocity and $`\theta =g\rho ^{}/\rho _o`$ is the normalized “temperature” associated with density fluctuations $`\rho ^{}`$. Alternatively, $`Ri`$ is defined as a bulk measure in an analogous fashion with $`N^2`$ in the numerator and shear variance in the denominator (i.e., a bulk $`RiFr^2`$). In the inviscid limit, a sufficient condition for stability of a parallel vertically sheared flow (i.e., a Kelvin-Helmholtz flow) is that the local $`Ri`$ exceed 0.25 throughout the flow miles61 ; howard61 . Gage gage71  refined this criterion for several simple viscid shear flows and obtained values of the critical $`Ri`$ for linear instability between about 0.05 and 0.11 for large $`R`$. In a numerical simulation at very high resolution (i.e., with a maximum Reynolds number based on the shear layer thickness $`Re_H=24000`$) and moderate stratification, Werne & Fritts werne99  show that the turbulence organizes itself so that $`Ri`$ never exceeds 0.25. In the more complex natural environment, velocity variance and estimates of the vertical mixing efficiency increase rapidly as $`Ri`$ decreases through the range between about 0.5 and 0.0 peters88 . On the other hand, Majda & Shefter majda98  stress the importance of temporal behavior on flow stability by constructing a family of time periodic solutions that are unstable at arbitrarily large $`Ri`$.

In this paper we examine the behavior of stratified turbulence at large $`R`$ values by means of numerical simulations of the Boussinesq Equations with forcing at the larger scales of the computational domain. Some simulations of forced stratified turbulence have been performed previously by Herring and Métais herring89 , but the available resolution did not allow clear conclusions for flows at high $`R`$. Most experiments and simulations for stratified turbulence have been conducted on decaying turbulence, with many focused specifically on the transition from isotropic to stratified turbulence after an initial high-energy excitation event metais89 ; staquet98 ; fincham96 . Because of the large energy dissipation rate in both isotropic and stratified turbulence, this evolutionary path starts with large $`R`$ and $`Fr`$ and only briefly resides in a fully developed regime en route to small $`R`$ and $`Fr`$; this situation therefore provides a limited view of the equilibrium geophysical regime. One of our main purposes here is to analyze the flow regimes of stratified turbulence in terms of $`R`$ and $`Fr`$ varied independently in a controlled fashion.

## II Description of the Calculation

### II.1 Governing Equations

A pseudo-spectral code is used to integrate the Boussinesq Equations on a triply periodic domain vincent91 ; viz.,

$$\{\begin{array}{ccc}_t𝐮+𝐮\mathrm{}𝐮\hfill & =\hfill & \mathrm{}p+\theta 𝐞_3+\nu \mathrm{\Delta }𝐮+𝐅,\hfill \\ _t\theta +𝐮\mathrm{}\theta \hfill & =\hfill & N^2𝐮𝐞_3+\kappa \mathrm{\Delta }\theta ,\hfill \\ \mathrm{}𝐮\hfill & =\hfill & 0.\hfill \end{array}$$
(2)
In these equations, $`𝐮`$ is the three-dimensional velocity, $`p`$ is the pressure divided by $`\rho _o`$, $`\kappa `$ is the conductivity, and $`𝐅`$ is the imposed forcing. In Fourier space the equations for the Fourier components of velocity and the temperature, $`\widehat{𝐮}(𝐤)`$ and $`\mathrm{\Theta }(𝐤)`$, are

$$\{\begin{array}{c}\left(_t+\nu k^2\right)\widehat{u}_i(𝐤,t)P_{i3}(𝐤)\mathrm{\Theta }(𝐤,t)\hfill \\ =ik_lP_{in}(𝐤)_{𝐤+𝐩+𝐪=0}\widehat{u}_n(𝐩,t)\widehat{u}_l(𝐪,t)d^3𝐩+\widehat{F_i}(𝐤,t),\hfill \\ \\ \left(_t+\kappa k^2\right)\mathrm{\Theta }(𝐤,t)+N^2\widehat{u}_3(𝐤,t)\hfill \\ =ik_n_{𝐤+𝐩+𝐪=0}\widehat{u}_n(𝐩,t)\widehat{\mathrm{\Theta }}(𝐪,t)d^3𝐩.\hfill \end{array}$$
(3)
$`P_{ij}=\delta _{ij}k_ik_j/k^2`$ is the projection operator onto the plane orthogonal to $`\widehat{𝐮}(𝐤)`$; $`\delta _{ij}`$ is the Kronecker tensor, repeated indices indicate summation; and $`i^2=1`$ when $`i`$ does not appear as an index.

### II.2 Energy Decomposition

As a simple means of separating turbulence (vortices) and waves, as well as a horizontally uniform shear flow that is neither of these, we use Craya’s decomposition craya58  for the incompressible velocity field in Fourier space into orthogonal components $`\widehat{𝐮}_v`$, $`\widehat{𝐮}_w`$, and $`\widehat{𝐮}_s`$:

$$\begin{array}{cccc}\widehat{𝐮}(𝐤,t)\hfill & =\hfill & \widehat{𝐮}_v(𝐤,t)+\widehat{𝐮}_w(𝐤,t)\hfill & \text{ if}𝐤_h0,\hfill \\ \widehat{𝐮}(𝐤,t)\hfill & =\hfill & \widehat{𝐮}_s(𝐤,t)\hfill & \text{ if}𝐤_h=0,\hfill \end{array}$$
(4)
where

$`\widehat{𝐮}_v(𝐤,t)=\widehat{\varphi }_v(𝐤,t)\phi _v(𝐤),`$ (5)
$`\widehat{𝐮}_w(𝐤,t)=\widehat{\varphi }_w(𝐤,t)\phi _w(𝐤)`$ (6)
and

$`\phi _v(𝐤)`$ $`=`$ $`[(𝐤\times 𝐞_3)]/|(𝐤\times 𝐞_3)|,`$ (7)
$`\phi _w(𝐤)`$ $`=`$ $`[𝐤\times (𝐤\times 𝐞_3))]/|𝐤\times (𝐤\times 𝐞_3)|.`$ (8)
$`𝐤_3=𝐤𝐞_3`$ and $`𝐤_h=𝐤𝐤_3`$ are the components of the wavenumber perpendicular and parallel to gravity. The components $`(\widehat{\varphi }_v,\widehat{\varphi }_w)`$ were previously used by, e.g., Riley et al. riley00  and Lilly lilly65 , and they are usually refered to “vortical” and “wave” components. The emergence of the “shear” component $`\widehat{𝐮}_s`$ was emphasized by Smith and Waleffe smith02 . Associated with $`\widehat{\varphi }_v`$, $`\widehat{\varphi }_w`$ and $`\widehat{𝐮}_s`$, we define the kinetic energy spectra by

$`\mathrm{\Phi }_v(k)`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝐩}{}}\widehat{\varphi }_v^{}(𝐩)\widehat{\varphi }_v(𝐩),`$ (9)
$`\mathrm{\Phi }_w(k)`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝐩,𝐩_h0}{}}\widehat{\varphi }_w^{}(𝐩)\widehat{\varphi }_w(𝐩),`$ (10)
$`\mathrm{\Phi }_s(k)`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝐩,𝐩_h=0}{}}\widehat{𝐮}_s^{}(𝐩)\widehat{𝐮}_s(𝐩),`$ (11)
where the sum $``$ is done over a shell $`k1/2<|𝐩|<k+1/2`$. We further define the “available potential energy” spectrum by

$$\mathrm{\Phi }_p(k)=\frac{1}{2}\underset{𝐩}{}\frac{\widehat{\mathrm{\Theta }}^{}(𝐩)\widehat{\mathrm{\Theta }}(𝐩)}{N^2},$$
(12)
and the “total kinetic energy” spectrum by

$$\mathrm{\Phi }(k)=\frac{1}{2}\underset{𝐩}{}\widehat{u}^{}(𝐩)\widehat{u}(𝐩).$$
(13)
Total component energies ($`E_v`$, $`E_w`$, $`E_s`$, $`E_p`$, and $`E`$) are obtained by summing over all shells $`k`$. In addition to this decomposition, we define the “vertical kinetic energy” $`E_z`$ as half the area-averaged square of the vertical velocity, $`𝐮𝐞_3`$, and $`\mathrm{\Phi }_z`$ as the vertical kinetic energy spectrum.

### II.3 Posing the Problem

Our analysis is based on a single numerical solution (designed after calculating many more exploratory solutions than we wish to admit). An anisotropic grid resolution is used to take advantage of the anisotropy of the flow that arises in response to the stable stratification (i.e., a small aspect ratio). The calculation is performed over a vertical fraction of a cubic domain by imposing a $`2\pi /M`$ vertical periodicity of the velocity ($`M=8`$ in the present case). For a given number of grid points, this increases the achievable $`R`$ value without loss of generality as long as the typical vertical scale is much smaller than the horizontal periodicity length. The level of stratification is controlled by adjusting the spatially uniform value of N in time. The forcing F is defined by $`𝐅(𝐤,t)dt=\beta (k,t)𝐮(𝐤,t)`$, with $`\beta `$ chosen so that the difference $`\mathrm{\Phi }_f(k,t^o)`$ of the energy spectra before and after the forcing (i.e., the energy injection rate) is constant in time:

$`\mathrm{\Phi }_f(k,t^o)`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{𝐩}{}}\left\{|\widehat{𝐮}(𝐩,t)+dt\widehat{F}(𝐩,t)|^2\right\}\mathrm{\Phi }(k,t)`$ (14)
$`=`$ $`\left(1+\beta (k,t)\right)^2\mathrm{\Phi }(k,t).`$
The coefficient $`\beta (k,t)`$ is obtained from eq. (14) as

$$\beta (k,t)=\sqrt{\frac{\mathrm{\Phi }(k,t)+\mathrm{\Phi }_f(k,t^o)}{\mathrm{\Phi }(k,t)}}1.$$
(15)
We choose to force only the first vertical and horizontal modes (i.e., $`\mathrm{\Phi }_f(k,t^o)0`$ for $`k=k_v^o=M`$ and $`k=k_h^o=1`$). In order to reach a high enough $`R`$ value, a hyper-diffusion ($`(1)^p\nu _p\mathrm{\Delta }_h^p`$, with p=4 and a small coefficient of $`\nu _p=10^{12}`$) is added to the Newtonian diffusion in the horizontal direction. Several additional simulations at higher horizontal resolution demonstrate that this modification does not qualitatively affect the results presented here. Since most of the dissipation occurs in association with shear in the vertical direction (about 99.5% in the stable pancake regime; see below), we use ordinary Newtonian diffusion in this direction to have a clean definition of Taylor’s Reynolds number, $`R_\lambda =U_{rms}\lambda /(ϵ/D)=2\sqrt{D}E/ϵ`$, where $`U_{rms}=\sqrt{2E}`$ is the RMS velocity, $`D`$ is the enstrophy (i.e., vorticity variance), $`\lambda =\sqrt{2E/D}`$ is the Taylor scale, and $`ϵ`$ the dissipation rate). The Prandtl number $`\nu /\kappa `$ is set to 1. The bulk Froude number is defined by $`Fr_v=U_{rms}/(HN)`$, where $`H=3\pi /4E(_{k_3}k_3^1\mathrm{\Phi }_v(k_3))`$ is the typical vertical scale.

The primary simulation is adjusted in time to follow a given experimental path in terms of $`R_\lambda `$ and $`Fr_v`$ by adjustment in time of $`N`$ and $`\nu `$. The evolution of these two parameters is shown in Fig. 1.

$`Fr_v`$ is maintained at a small value of 0.08, and $`R_\lambda `$ is changed from 200 to 1000 by steps of 100 after integration periods of 100 turnover times (i.e., $`T=L/U_{rms}`$ with L the integral scale defined by $`L=3\pi /4E(_kk^1\mathrm{\Phi }(k))`$). This period is approximately long enough to adjust to an equilibrium state for each $`R_\lambda `$. This experimental path is designed to expose a sequence of regime transitions with increasing $`R`$.

The equations are solved on a $`2\pi \times 2\pi \times 2\pi /M`$ domain with a spatial grid size of $`256\times 256\times 64`$ for $`R_\lambda <500`$ and $`256\times 256\times 128`$ for higher $`R_\lambda `$. The simulation appear to be slightly under-resolved for the highest Reynolds number in the sense that the dissipation range is not extensive in $`\mathrm{\Phi }(k)`$. The ratios of the highest resolved ($`k_h^m=96`$ and $`k_v^m=341`$) to the corresponding Kolmogorov wavenumbers ($`k_h^\eta =(\nu ^3/ϵ_h)^{1/4}`$ and $`k_v^\eta =(\nu ^3/ϵ_v)^{1/4}`$) are 1.1 and 0.92, respectively, for $`R_\lambda =500`$, and they are 0.4 and 0.2 for $`R_\lambda =1000`$. The under-resolution in the horizontal direction is compensated by the hyper-viscosity. In the vertical direction, the kinetic energy at the resolution scale is much smaller than at the largest scales in the dissipation range (by a factor of $`10^5`$ at the highest $`R_\lambda `$). The Ozmidoz scale ($`Lo=(ϵ/N^3)^{1/2}4.10^4`$ for $`R_\lambda =700`$) is more than one order of magnitude smaller than the smallest resolved vertical scales. This ratio means that all the resolved scales are significantly influenced by stratification.

The simulations were made on one processor of a NEC SX-5. The code uses optimized ASL libraries of Fast Fourier Transforms and requires approximately 4 seconds per time step at the highest resolution. The time step is chosen to sufficiently resolve the fastest wave oscillations with period $`2\pi /N`$. The simulation is integrated over a total of 360,000 time steps and takes about 200 hours.

## III Solution Analysis

The experimental path for the primary solution is demonstrated in Fig. 1 as a function of the non-dimensional time, $`\tau =t/T`$, normalized by the turnover time $`T`$. The corresponding histories of the energy components are shown in Fig. 3. As $`R_\lambda `$ increases, we see a sequence of regime transitions.

At moderate $`R_\lambda `$, less than $`400`$, the pancake motions are stable (i.e., the local $`Ri`$ is everywhere large), and the vortical energy dominates all other energy components at all wavenumbers (Fig. 2).

The first transition occurs for $`R_\lambda 400`$, and it is evident in the significant growth of energy in the shear component, $`E_s`$ (Fig. 3).

The next transition, for $`R_\lambda 500`$, is evident in the intermittent occurrence of regions with small local values of $`Ri`$ below the Kelvin-Helmholtz critical inviscid stability value of 0.25 (Fig. 4).

A further transition, for $`R_\lambda 700`$, is evident in local violations of the inviscid gravitational stability critical value of $`Ri=0.0`$ (Fig. 4). Finally, we see yet another transition for $`R_\lambda 900`$, evident in the growth of vertical kinetic energy, $`E_z`$ (Fig. 3). Interestingly, throughout all these transitions, the principal measures of the internal-wave energy, $`E_w`$ and $`E_p`$, show little change relative to the vortical-mode energy, $`E_v`$. Since $`E_v`$ itself remains reasonably constant with time and its horizontal spectrum $`\mathrm{\Phi }_v(k_h)`$ maintains a similar shape and magnitude at low wavenumbers, we conclude that pancake motions are indeed persistent throughout the $`R_\lambda `$ range we have been able to explore, even though the structure and intensity of the flow changes substantially at high wavenumbers, in the horizontally uniform vertical shear, and in the vertical velocity.

### III.1 Growth of the Vertical Shear Component

In Fig. 3 the vortical energy is nearly steady over the entire simulation. The wave energy is more variable, but on average it is steady as $`R_\lambda `$ increases. However, the shear energy is a growing function of time. It represents an inverse horizontal cascade of kinetic energy into $`k_h=0`$. The intensity of the inverse cascade of shear energy is probably a function of the location of the energy peak in the horizontal direction; in the present case, the forcing is imposed at $`k_h=1`$, and a substantial part of the energy is transformed into pure vertical shear. To assess the degree of equilibration for this inverse cascade, two additional simulations are made. Both start from the primary simulation and thereafter hold $`R_\lambda `$ constant for several hundred turnover times, but their starting $`(\tau ,R_\lambda )`$ values differ. Fig. 5 shows that $`E_s`$ does indeed

equilibrate over a period of less than 100 turnover times at a level that increases systematically with $`R_\lambda `$.

This growth of shear kinetic energy has been seen previously when the Froude number is below a critical value smith02 . For the alternative Froude number defined by $`Fr_s=(ϵk_{v}^{o}{}_{}{}^{2})^{1/3}/N)`$, our simulations have a value of approximately 0.025, more than an order of magnitude below the identified critical value of 0.42. In this previous study, the shear kinetic energy did not equilibrate even after more than 1000 turnover times. This may be due to its reliance on hyper-diffusion in all directions that exerts only a weak damping on the shear component.

### III.2 Onset of Overturning Motions

Overturning occurs when an unstable shear layer rolls up, pulling high-density fluid above low-density fluid. This instability can occur in a fairly localized way. Its occurrence is detected with the local $`Ri`$ defined in eq. (1), and an indication of the overturning instability is a negative $`Ri`$ value. Because of the Miles-Howard condition, we can expect that this Kelvin-Helmholtz instability only occurs in regions where $`Ri`$ is initially less than $`0.25`$. The history of the fraction of the domain with the local $`Ri`$ below 0.25 is shown in Fig. 4. More events with $`Ri<0.25`$ happen as $`R_\lambda `$ increases, although they evidently remain intermittent. The regime of overturning events first appears at $`R_\lambda =700`$ ($`\tau 535`$). Even at the highest $`R`$ value, only a small fraction of the domain is actively overturning at any time, less than 0.7%. The Probability Density Function (PDF) for $`Ri`$ shows that most of the domain remains far away from overturning, with only a small tail in the PDF that extends to small and negative $`Ri`$ values. Because of the intermittency, long averaging periods are required for stable statistics. Nevertheless, we can say that there is a well determined value of $`R`$ for the onset of overturning events. To demonstrate this, the regime just before the first overturning event in the primary simulation ($`R_\lambda =500`$) is integrated over a longer period (250 turnover times), and no overturning occurs despite several events with $`Ri<0.25`$. To characterize more precisely the critical $`Ri`$ for instability, we follow the history of the global minimum in local $`Ri`$ (Fig. 6).

The minimum $`Ri`$ value that does not immediately lead to local overturning is $`Ri0.02`$. This value is a bit smaller but of the same order of magnitude than the values computed by Gage gage71  for simple shear flows.

The spatial distribution of small $`Ri`$ events is organized into thin sheets with large vertical shear in the horizontal velocity. An example of a region with a negative vertical density gradient is shown Fig. 7.

The vertical size of this region is very thin (a few grid cells) even though its horizontal size at this time ($`2\pi /3`$) is not much smaller than to the domain size. An intense vertical velocity is associated with domain of negative vertical density gradient (Fig. 8), but the present simulation has only a

marginally adequate resolution to expose the convective overturning events.

Fig. 9 shows the spectra for the energy components

at $`\tau =521`$, before any overturning occurs. The spectra with respect to horizontal wavenumber are very steep, with a slope close to $`k_h^5`$ for $`\mathrm{\Phi }_v`$, and the shape does not vary much with $`R_\lambda `$ in this stably stratified regime without overturning. The onset of the overturning instability does not seem to affect significantly the overall level of wave and vortical energy (Fig. 3). However, the overturning events are easily identifiable as a peak in the horizontal spectra at $`\tau =741`$ (Fig. 9). The peak is located at the horizontal scale $`L_h2\pi /50`$ that matches the typical vertical scale, $`L_v`$. At this particular time, the instability is localized in a single region of the domain.

The energy at the largest horizontal scales is not affected by the overturning instabilities that are localized in both space and time. In Fig. 10,

time-averaged vortical-energy spectra are compared for four values of $`R_\lambda `$. The horizontal spectra are very similar up to the typical scales of the overturnings. However, at both finer horizontal scales and at all vertical scales finer than the forcing scale, the spectrum amplitude increases systematically with $`R_\lambda `$. At the constant, small $`Fr`$ value in this simulation, the vertical spectrum slope becomes quite shallow as $`R_\lambda `$ increases.

### III.3 Growth of Large-Scale Vertical Motions

The energy histories in Fig. 3 expose another transition at an even larger $`R_\lambda 900`$, viz., the systematic growth of vertical kinetic energy $`E_z`$. Inspection of the vertical energy spectrum reveals that the growth of $`E_z`$ after $`\tau =700`$ occurs principally at $`k_v=0`$ (Fig. 11).

This mode of instability is reminiscent of the “negative-viscosity instability” observed in a Kolmogorov flow dubrulle91b , further investigated by Dubrulle & Frisch dubrulle91a  with a multi-scale analysis. This analysis shows that a parallel flow with a small transverse scale develops a negative-viscosity instability to large-scale perturbations in the transverse direction when the viscosity becomes less than the RMS value of the streamfunction of the primary flow. In our simulation, it is difficult to test precisely this criterion of instability because the streamfunction is ill-defined. Crudely, we can expect an instability of this type when $`\nu <\mathrm{\Phi }_s(\mathrm{}_v)^{1/2}\mathrm{}_v`$, where $`\mathrm{}_v`$ is the scale of the vertical shear and $`\mathrm{\Phi }_s(\mathrm{}_v)`$ is the shear energy at this scale. In our simulation this relation is satisfied on average for $`\tau >700`$ if $`2\pi /\mathrm{}_v>80`$. This scale is comparable in magnitude with the typical vertical wavenumber $`2\pi /L_v50`$. However, due to the complexity of the forced stratified flow, it is difficult to prove the nature of this instability pending more apt stability analyses.

## IV Summary and Discussion

In our simulations of forced, equilibrium, stratified turbulence, we see behaviors somewhat different from many previous studies of decaying stratified turbulence that were not able to sustain a large value of the Reynolds number, $`R`$. Most often the criteria for the occurrence of pancake vortices and suppression of overturning motions (i.e., Kelvin-Helmholtz and gravitational stability) have been linked to the stratification $`N`$ but rarely to $`R`$. Indeed, we find that the stability of a solution is mainly controlled by two parameters with opposite effects on stability: increasing N (decreasing $`Fr`$) leads to a more stable solution and decreasing $`\nu `$ (increasing $`R`$) has the opposite effect. For a fixed low value of $`Fr`$, we follow an experimental path of increasing $`R`$ far enough to detect several regime transitions beyond the familiar one of stable pancake vortices. One transition is to the intermittent occurrence of regions with small or negative $`Ri`$. This refutes previous arguments lilly83 ; mcwilliams85  that stratified turbulence remains stable with uniformly small local values of $`Fr`$ at large $`R`$ and with uniformly cyclostrophic, hydrostatic diagnostic momentum balances. This transition may plausibly be associated with inviscid Kelvin-Helmholtz and ensuing gravitational instabilities of the pancake vortices, although in our simulations the viscous effects on the unstable scales are significant. Nevertheless, the pancake vortices continue to be the energetically dominant component of the turbulence even up to the highest $`R`$ values examined here, and visualizations of the large-scale potential vorticity field (not shown) show little change in spatial structure with $`R_\lambda `$.

Two other transitions to large-scale motions other than pancake vortices do occur: a first one to growth of the shear kinetic energy at zero horizontal wavenumber and a second one to growth of vertical kinetic energy with its spectrum peak at zero vertical wavenumber for large $`R`$. The former has been seen previously in stratified turbulence smith02 , and the latter may be associated with negative-viscosity instability seen previously in unstratified shear flow dubrulle91b . Each of these large-scale transitions may be interpreted as an inverse energy cascade. However, they behavior is strongly constrained by the domain size in our simulations where the forcing is imposed at the gravest finite wavenumbers. We will explore beyond this limitation in future reports.

In this paper we choose to focus on simulations at very small Froude number, and we are able to reach a Reynolds number high enough to destabilize the pancake vortices in several ways. This leads us to advance the following proposition about the nature of equilibrium stratified turbulence: for any Froude number, no matter how small, there are Reynolds numbers large enough so that a sequence of transitions to non-pancake motions will always occur, and, conversely, for any Reynolds number, no matter how large, there are Froude numbers small enough so that these transitions are suppressed. Obviously, this hypothesis warrants further testing, as do our provisional interpretations of the dynamical nature of the transitions.

## Acknowledgments

The primary simulation was calculated on the NEC SX-5 of the Institut du Développement et des Ressources en Informatique Scientifique (IDRIS) and the IBM RS6000/SP of the Centre de Ressource Informatique of the University of Lille was used for additional simulations. JPL and JCM acknowledge support from the Office of Naval Research (grant N00014-98-1-0165).


text:
# Theorem 1

A Nonhereditary Borel-cover $`\gamma `$\- set

Arnold W. Miller111 Thanks to the Fields Institute for Research in Mathematical Sciences at the University of Toronto for their support during the time this paper was written and to Juris Steprans who directed the special program in set theory and analysis. Mathematics Subject Classification 2000: 03E50; 03E17

Abstract

> In this paper we prove that if there is a Borel-cover $`\gamma `$-set of cardinality the continuum, then there is one which is not hereditary.

In this paper we answer some of the questions raised by Bartoszynski and Tsaban  concerning hereditary properties of sets defined by certain Borel covering properties.

Define. An $`\omega `$-cover of a set $`X`$ is a family of sets such that every finite subset of $`X`$ is included in an element of the cover but $`X`$ itself is not in the family.

Define. A $`\gamma `$-cover of a set $`X`$ is an infinite family of sets such that every element of $`X`$ is in all but finitely many elements of the family.

Define. A set $`X`$ is called a Borel-cover $`\gamma `$-set iff every countable $`\omega `$-cover of $`X`$ by Borel sets contains a $`\gamma `$-cover.

These concepts were introduced by Gerlits and Nagy  for open covers.

Being a Borel-cover $`\gamma `$-set is equivalent to saying that for any $`\omega `$-sequence of countable Borel $`\omega `$-covers of $`X`$ we can choose one element from each and get a $`\gamma `$-cover of $`X`$ \- this is denoted $`𝖲_1(_\mathrm{\Omega },_\mathrm{\Gamma })`$. The equivalence was proved by Gerlitz and Nagy  for open covers but the proof works also for Borel covers as was noted in Scheepers and Tsaban :

Let $`_n`$ be Borel $`\omega `$-covers of $`X`$. Since

$$\{UV:U𝒰,V𝒱\}$$

is an $`\omega `$-cover if $`𝒰`$ and $`𝒱`$ are, we may assume that $`_{n+1}`$ refines $`_n`$. Let $`x_n`$ for $`n<\omega `$ be distinct elements of $`X`$ and let

$$=\{A\{x_n\}:n<\omega ,A_n\}$$

It is easy to check that $``$ is an $`\omega `$-cover of $`X`$. Now let $`𝒞`$ be a $`\gamma `$-subcover of $``$. Note that for any fixed $`n`$ at most finitely many of the elements of $`𝒞`$ can be of the form $`A\{x_n\}`$. By refining $`𝒞`$ we may assume at most one thing is taken from each $`_n`$ and since they are refining we can fatten up $`𝒞`$ to take exactly one element of each $`_n`$.

Define. A family of subsets of $`X`$, $`𝒰`$ is a $`\tau `$ cover of $`X`$ iff every element of $`X`$ is in infinitely many elements of $`𝒰`$ and for every $`x,yX`$ at least one of the sets

$$\{U𝒰:xU,yU\}\text{ or }\{U𝒰:xU,yU\}$$

is finite.

Clearly any $`\gamma `$-cover is a $`\tau `$-cover. These covers were introduced in Tsaban .

###### Theorem 1

Suppose there is a Borel-cover $`\gamma `$-set of size the continuum. Then there is a Borel-cover $`\gamma `$-set $`X`$ and subset $`Y`$ of $`X`$ which is not a Borel-cover $`\gamma `$-set. In fact, there is an open $`\omega `$-cover of $`Y`$ with no $`\tau `$-subcover.

Proof

For $`XP(\omega )`$ let

$$\stackrel{~}{X}=\{\omega a:aX\}$$

be the dual of $`X`$, i.e., the set of complements of elements of $`X`$. Let $`P[\omega ]^\omega `$ be a perfect set of independent subsets of $`\omega `$. This means that for every disjoint pair $`F_1,F_2`$ of finite subsets of $`P`$ the set

$$F_1\stackrel{~}{F_2}\text{ is infinite.}$$

Such a set was first constructed by Fichtenholtz, Kantorovich, and Hausdorff, see Kunen . To construct one, let $`Q=\{(n,s):n\omega ,sP(n)\}`$. Define $`A_x=\{(n,s):xns\}`$ for each $`x\omega `$ and

$$P=\{A_x:x\omega \}P(Q)=2^Q.$$

Let $`ZP`$ be a Borel-cover $`\gamma `$-set of cardinality the continuum.

Claim. $`Z\stackrel{~}{Z}`$ is a Borel-cover $`\gamma `$-set.

proof: Let $`\{B_n:n<\omega \}`$ be a Borel $`\omega `$-cover of $`Z\stackrel{~}{Z}`$. Then it is easy to see that $`\{(B_n\stackrel{~}{B_n}):n<\omega \}`$ is an $`\omega `$-cover of $`Z`$. This is because if $`(F\stackrel{~}{F})B_n`$ then $`F(B_n\stackrel{~}{B_n})`$.

Since $`Z`$ is a Borel-cover $`\gamma `$-set there exists an $`a[\omega ]^\omega `$ such that

$$\{(B_n\stackrel{~}{B_n}):na\}$$

is a $`\gamma `$-cover of $`Z`$. But then it is also a $`\gamma `$ cover of $`\stackrel{~}{Z}`$. This proves the Claim.

Let $`X=Z\stackrel{~}{Z}`$ and to pick $`YX`$ as required we will choose for each $`aZ`$ to put either $`aY`$ or $`(\omega a)Y`$ (but not both). Since $`Z`$ was a subset of $`P`$ and $`P`$ was independent we will have that the intersection of any finite subset of $`Y`$ is infinite. In particular,

$$𝒰=\{U_n:n\omega \}\text{ where }U_n=\{a\omega :na\}$$

is an $`\omega `$-cover of $`Y`$. But $`\{U_n:nb\}`$ is a $`\gamma `$-cover of $`Y`$ iff $`b^{}a`$ for every $`aY`$. But this is easy to defeat. Using that $`Z`$ has cardinality the continuum let $`Z=\{a_\alpha :\alpha <𝔠\}`$ and let $`[\omega ]^\omega =\{b_\alpha :\alpha <𝔠\}`$. For each $`\alpha `$ if $`b_\alpha ^{}a_\alpha `$ put $`(\omega a_\alpha )`$ into $`Y`$ and otherwise put $`a_\alpha `$ into $`Y`$.

To construct $`Y`$ so that $`𝒰`$ has no $`\tau `$-subcovers can be done by using two elements $`a_0,a_1`$ of $`Z`$ for each $`b[\omega ]^\omega `$. First note that the set $`\{U_n:nb\}`$ is a $`\tau `$-cover of $`Y`$ iff $`b`$ meets every element of $`Y`$ in an infinite set and for every two elements $`a_0,a_1`$ of $`Y`$ either $`(a_0b)^{}a_1`$ or $`(a_1b)^{}a_0`$.

Notation: $`a^{(0)}=a`$ and $`a^{(1)}=\omega a`$.

Claim. There exists $`i,j`$ in $`\{0,1\}`$ such that

(a) $`ba_i^{(j)}`$ is finite or

(b) both $`ba_0^{(i)}a_1^{(1j)}`$ and $`ba_0^{(1i)}a_1^{(j)}`$ are infinite.

proof: Assume case (a) fails for all $`i,j`$ in $`\{0,1\}`$. The four sets $`a_0^{(i)}a_1^{(j)}`$ partition $`\omega `$ into infinite sets since $`a_0`$ and $`a_1`$ are independent. If all four meet $`b`$ in an infinite set then we are done. So assume that $`ba_0^{(i)}a_1^{(j)}`$ is finite for some $`i,j`$. But since $`ba_0^{(i)}`$ is infinite it must be that $`ba_0^{(i)}a_1^{(1j)}`$ is infinite. A similar argument shows $`ba_0^{(1i)}a_1^{(j)}`$ is infinite. This proves the Claim.

To kill off the possibility of $`b`$ giving a $`\tau `$-subcover we put $`a_i^{(j)}`$ into $`Y`$ in case (a) or put both $`a_0^{(i)},a_1^{(j)}`$ into $`Y`$ in case (b). This proves the Theorem.

QED

Remark. Tsaban points out the following corollary of our result. In Problem 7.9 of Bukovsky, Reclaw, and Repicky  it is asked whether every $`\gamma `$-set of reals which is also a $`\sigma `$-set is a hereditary $`\gamma `$-set. It is shown in Scheepers and Tsaban  that every Borel-cover $`\gamma `$-set (more generally $`𝖲_1(_\mathrm{\Gamma },_\mathrm{\Gamma })`$-set) is a $`\sigma `$-set. Hence the answer to the problem is no.

The following result is due to Brendle . Our proof is a slight modification of a result of Todorcevic - see Theorem 4.1 of Galvin and Miller  and is perhaps simpler.

###### Theorem 2

(Brendle) Assume CH. Then there exists a Borel-cover $`\gamma `$-set of size $`\omega _1`$.

Proof

The idea is to construct an Aronszajn tree $`T\omega ^{<\omega _1}`$ of perfect sets.

We construct perfect subtrees $`p_s2^{<\omega }`$ for $`sT`$ and $`X_s[p_s]`$ countable dense sets such that

1. if $`st`$ then $`p_sp_t`$,
2. if $`s`$ and $`t`$ are incomparable then $`[p_s][p_t]=\mathrm{}`$,
3. if $`\alpha <\beta <\omega _1`$ and $`n<\omega `$ then for every $`sT_\alpha `$ there exists $`tT_\beta `$ with $`st`$ and $`p_s2^n=p_t2^n`$, and
4. for every sequence $`(B_n:n<\omega )`$ of Borel subsets of $`2^\omega `$ there exists $`\alpha <\omega _1`$ such that either for some finite $`F\{X_s:sT_{\alpha +1}\}`$ no $`B_n`$ covers $`F`$ or there exists an $`a[\omega ]^\omega `$ such that $`\{B_n:na\}`$ is a $`\gamma `$-cover of

$$\{[p_s]:sT_{\alpha +1}\}\{X_s:sT_\alpha \}$$

After the construction is completed we will let $`X=\{X_s:sT\}`$. The last item guarantees that $`X`$ will be a Borel-cover $`\gamma `$-set. The first three items are simply to guarantee that our construction can continue at limit levels. To do the last item we use the following Lemma.

Define for any perfect tree $`p`$ and $`sp`$,

$$ps=\{tp:ts\text{ or }st\}$$

###### Lemma 3

Suppose $`p_n:n<\omega `$ are perfect trees and $`(_n:n<\omega )`$ is a sequence of countable Borel $`\omega `$-covers of $`_{n<\omega }[p_n]`$. Then there exists perfect pairwise disjoint subtrees $`q_np_n`$ and $`\{B_n_n:n<\omega \}`$ which is a $`\gamma `$-cover of $`_{n<\omega }[q_n]`$.

Proof

We can begin by refining the $`p_n`$’s so that $`[p_n]`$ are pairwise disjoint. So we may as well assume this to begin with. Also since Borel sets have the (relative) property of Baire with respect to each perfect set, by passing to perfect subsets we may assume that each of our Borel covers is an open cover.

Note that for finite sequences $`(k_i:i<n)`$ and $`(t_ip_{k_i}:i<n)`$, there exists a $`U_n_n`$ and $`r_it_i`$ with $`r_ip_{k_i}`$ such that

$$_{i<n}[p_{k_i}r_i]U_n$$

Using this observation it is easy to construct a fusion sequence which produces the $`q_n`$ and the required $`\gamma `$-cover. This proves the Lemma.

QED

Let $`T_\alpha =T\omega ^\alpha `$.

In our construction of the tree we start by assuming that $`\{_\alpha :\alpha <\omega _1\}`$ is a list containing all countable families of Borel subsets of $`2^\omega `$. At limit ordinals $`\alpha `$, we use the usual fusion arguments to produce $`p_s`$ for $`sT_\alpha `$. We take care of condition (4) as follows.

Suppose by induction we have already constructed: $`(p_s:sT_\alpha )`$ and $`(X_s:sT_{<\alpha })`$.

To obtain condition (4) let $`\{x_n:n<\omega \}=\{X_s:sT_{<\alpha }\}`$, and define

$$_\alpha ^n=\{B:\{x_i:i<n\}B\}$$

If some $`_\alpha ^n`$ is not an $`\omega `$-cover of $`\{[p_s]:sT_\alpha `$, then there exists a finite subset of $`\{x_n:n<\omega \}`$

which is not covered by any $`B_\alpha `$. In this case, we choose $`X_sp_s`$ so that this finite set is included in $`\{X_s:sT_\alpha \}`$. We then choose $`p_{sn}`$ so that $`p_{sn}2^n=p_s2^n`$, $`p_{sn}p_s`$, and $`[p_{sn}]`$ for $`n<\omega `$ pairwise disjoint. We don’t need to worry about $`_\alpha `$ because it cannot be an $`\omega `$-cover of $`X`$.

So we may assume each $`_\alpha ^n`$ is an $`\omega `$-cover of $`\{[p_s]:sT_\alpha \}`$.

Apply the Lemma to the sequence

$$(p_st:sT_\alpha \text{ and }tp_s)$$

Then for each $`sT_\alpha `$ and $`n<\omega `$ let

$$p_{sn}=\{q_{s,t}:t2^np_s\}$$

In this case we can take each $`X_{sn}[p_{sn}]`$ to be an arbitrary countable dense subset.

QED

Theorem 4 is probably known but we include its proof here for completeness.

###### Theorem 4

Suppose that $`M`$ is any countable standard model of ZFC. Then there exists a ccc poset $``$ in $`M`$ of size continuum such if $`G`$ is any $``$-filter generic over $`M`$, then $`X=M2^\omega `$ in $`M`$ is a Borel-cover $`\gamma `$-set in $`M[G]`$. Note that forcing with $``$ does not change the size of the continuum in $`M[G]`$.

Proof

This is really a corollary of result noted by Gerlitz and Nagy  that assuming MA (or even just MA($`\sigma `$-centered)) that every set $`X`$ of size less than continuum is a $`\gamma `$-set.

Let $`\{B_n:n<\omega \}`$ be an $`\omega `$-cover of $`X`$. For each $`xX`$ let

$$a_x=\{n:xB_n\}.$$

The family $`\{a_x:xX\}`$ has the finite intersection property. So there is a well-known ccc poset of size $`|X|`$ (see Kunen ) which adds an infinite $`a[\omega ]^\omega `$ such that $`a^{}a_x`$ for each $`xX`$. Then $`\{B_n:na\}`$ is a $`\gamma `$-cover of $`X`$. To obtain the model $`M[G]`$ simply iterate continuum many times, with the usual dovetailing argument to take care of all sequences of Borel sets in $`M[G]`$.

QED

###### Question 5

Does MA imply there exists a Borel-cover $`\gamma `$-set of size the continuum?

The theorems in this section show that it is consistent that the classes $`𝖲_1(_\mathrm{\Omega },_\mathrm{\Gamma })`$, $`𝖲_1(_\mathrm{\Omega },_\mathrm{T})`$, and $`𝖲_{\mathrm{fin}}(_\mathrm{\Omega },_\mathrm{T})`$ are not hereditary.

I don’t know about the other classes in Bartoszynski and Tsaban , for example:

###### Question 6

Is the class $`𝖲_1(_\mathrm{\Omega },_\mathrm{\Omega })`$ hereditary?

For the definitions of these classes see .

Arnold W. Miller

miller@math.wisc.edu

http://www.math.wisc.edu/$``$miller

University of Wisconsin-Madison

Department of Mathematics, Van Vleck Hall

480 Lincoln Drive

Madison, Wisconsin 53706-1388