On list chromatic numbers of 2-colorable hypergraphs

A hyporgraph Н is а рай• of sets (V,E ). where V Is finite and E С 2^У: V is called the set of vertices and E the set of edges. A hypergraph is said to be n-uniform if all of its edges have size n (further we call them n-graphs). Note that a graph is a 2-uniform hypergraph.

Given a hypergraph Н = (V, E) and a. vertex v EV. define the degree of the vertex dn (v) as the number of edges of Н that contain v.

A coloring of a hypergraph with r colors is a map / : V ^ {1,..., r}. A coloring J of a hypergraph is said to be proper if each edge е E E contains two vertices v1,v₂ Е e such that

• (с) Черкашин Д. Д., Гордеев A. C., 2022

• (с) Федеральное государственное автономное образовательное учреждение высшего образования «Московский физико-технический институт (национальный исследовательский университет)», 2022

  / (vi) = / (^2)- The minim al number т for which there exists a proper т-coloring of H is called the chromatic number x(H ) of the hypergraph H .

Consider a 2-colorable hypergraph H . Its proper 2-coloring gives a partition of V into two sets A UB = V. A ПВ = 0 such that every edge of H intersects both A and B. Furl her we call such sets A and B parts of H. For a subset of a part T C A define its neighborhood

N h (T)= J e \ A.

eGE, еПТ=0

For convenience define also N h (v) = N h ({v}).

Define a complete 2-colorable hypergraph K^ _m as s-graph with sizes of parts n, m and all possible edges of size s intersecting both parts.

An orientation of a hypergraph H = (V, E ) is a map ф : E ^ V which satisfies ф(е) E e for any e E E. For orientation ф define a degree function d^ on the set of vertices as follows: ^d^^(v) = |y^-1(v)|.

To each vertex v we assign a list L(v) of colors which can be used for v. Given a, map / : V ^ N, we say that a hypergraph H is /-list-colorable (/-choosable) if for any set of lists with lengths |L(v) | = /(v) there exists a proper coloring of H. Hypergraph is fe-choosable if it is /-choosable. where /(v) = fe for each v. The list ehromalic number ch(H) of the hypergraph H is the minimum number fe such that H is fe-choosablc.

List colorings of graphs and hypergraphs were independently introduced by Vizing [12] and by Erdos, Rubin, and Taylor [5]. Clearly, ch(H) >  x(H ), since all lists can be taken equal to {1,..., ch(H)}. At the same time, the chromatic number and the list chromatic number are different, for example, for the complete bipartite graph K3,3, for v^hich ch(K3,3) = 3 (equality is attained at the lists {1,2}, {1, 3}, {2,3} assigned to the vertices of each part).

Sparse case. For a hypergraph H = ( V, E ) denote

|E ‘|

L(H ) =

max ---------

0=E'CE | UeGE’ e|

One of the methods of estimating the list chromatic number of a graph is the Alon-Tarsi method [3]: if there exists an orientation ф of a graph G with certain structural properties, then G is (d^ + 1)-choosable. In the case of bipartite (2-colorable) graphs any orientation has the desired properties, which gives two following theorems.

Теорема 1. Let ф be an orientation of a bipartite graph G = (V, E). Then G is (d_v + 1)- choosable.

Теорема 2 (Theorem 3.2 in [3]). For any bipartite graph G, ch(G) < [L(G)] + 1.

In 2010 Schauz [10] generalized these results to fe-partite fe-uniform hypergraphs, i.e. k- uniform hypergraphs whose set of vertices can be partitioned into fe sets V1,...,Vfe such that each edge has exactly one vertex in each of V) (bipartite graphs correspond to the case fe = 2). We show that in fact the same results hold in even more general case of 2-colorable hypergraphs.

Dense case. Let N (n,r) denote the minimum number of vertices in an n-partite (n-colorable) graph with the list chromatic number larger than т. The following classic theorem express the asymptotics of N (2, т) in terms of the minimal number of edges in an n-uniform hypergraph without a proper 2-coloring. The latter quantity is denoted by m(n).

Теорема 3 (Erdos-Rubin-Taylor [5]). For any т

т(т) <  N (2,т) < 2т(т).

The problem of finding m(n) is well-known, the best current bounds are

I "                            in о In 2 о ~

^CV inn^{2 — m(n) —(1 +} 4 ⁿ2.

For details see survey [9].

Kostochka extended Theorem 3 in two ways. Let Q(n,r) be the minimal number of edges in an n-uniform n-partite hypergraph with the chromatic number greater than r; m(n, r) be the minimal number of edges in an n-uniform hypergraph with the chromatic number greater than r, and finally p(n, r) be the minimal number of edges in an n-uniform hypergraph without an r-coloring such that every edge meets every color.

Теорема 4 (Kostochka [8]). For every n,r > 2 the following inequalities hold

m(r,n) — Q(n,r) — nm(r, n);

p(r, n) — N(n, r) — np(r, n) .

Upper and lower bounds on the quantities m(n, r) and p(n, r) heavily depend on the relations between n and r . The picture is collected in survey [9] (see also more recent paper [1]).

2.    Sparse case

We give an alternative, more direct proof of the next theorem in the Appendix, since it is rather concise.

Теорема 5. Let p be an orientation of a 2-colorable hypergraph H = (V, E ). Then H is (d^ + 1)- choosable.

Доказательство. Since H is 2-colorable, we can choose a vertex u_e € e in each edge e such that p(e) and u_e belong to different parts of H.

Consider a bipartite graph В on the set of vertices V with the set of edges U_eGE{(p(e), u_e)}-Consider the following orientation of В: p‘((p(e), u_e)) = p(e). Note that d^’(v) = d^(v) for any и € V. Then, by Theorem 1, В is (d^ + 1)-choosable. Since an у proper coloring of В is a proper coloring of H, it follows that H is (d^ + 1)-choosable.                                         □

The following lemma first appeared in [10] (see Lemma 3.2). We give a proof of it here for the sake of completeness.

Лемма 1. For any hypergraph H = ( V, E ) there exists an orientation p of H with d_v — \L(H )].

Доказательство. Consider a bipartite graph G with parts V x {1,..., \L(H )]} and E, in which (v, i) aiid e arc connected if and only if v and e arc incident in H. The statement of lemma is true if and only if there is a matching in G which covers E.

Let 0 = T c E be an arbitrary subset of edges of H. We estimate the size of the neighborhood of T in G:

|NG(T)| = | UeGT e| • [L(H)] > | UeGT e| • ^ТЦ = |T|.

| UeGT e|

By Hall’s marriage theorem it follows that there exists a matching in G which covers E.     □

Theorem 5 and Lemma 1 combined give the following theorem.

Теорема 6. For any 2-colorable hypegraph H, ch(H) — [L(H)] + 1.

The exact value of L(H ) can be difficult to calculate, so we provide a bound in simpler terms. For a liypergrapli H denote the maximum degree of a vertex in H bу A(H) arid the minimum size of an edge in H by s(H ).

Следствие 7. Let H = (V, Е ) be a 2-colorable hypergraph. Then, ....."-1.

Доказательство. For any Е ‘ С Е we have

|Е‘|. s(H ) <  £ |e|<|U_eeE‘ е| • A(H), eEE’

SO

L(H ) <

A(H) s(H ) •

For an arbitrary (not necessarily 2-colorable) hypergraph a weaker bound with an additional factor of 2 holds. The next theorem was essentially proved by Gravin and Karpov [6], though they were not considering their results in the context of list colorings. In fact, the theorem in [6] has the second part in which « + 1» is removed under some assumptions; it can be also generalized on the list chromatic numbers.

Теорема 8. Let H = (V, Е) be a hypergraph. Then,

-“< |2AHH'I'-

Доказательство. Let

k =

Г 2A(H) s(H )

Let G be the incidence graph of H. i.e. a bipartite graph with parts V. Е arid with v Е V. е Е Е connected in G if and only if v and е arc incident in H. We want to delete some edges from G to obtain a graph К with the following conditions on degrees:

dK (е) = 2 for am" е Е Е ; max dK(v) <  k. «ev

If there exists such K, denote N _k (е) = {v_e,n_e} and consider a graph Bona set of vertices V with the set of edges U_eGE{(v_e,n_e)}. One can color vertices of B in any order, each time using any color not yet taken by adjacent vertices, to obtain a bound ch(B) < A(B) + 1 < k + 1. Since any proper coloring of B is a proper coloring of H. it foliows that ch(H) < k + 1.

If there is no К with desired properties, then we choose such К = (V,Е_K ) that d_K (е) = 2 for any е Е Е arid p(K ) = ^Д_еу max(0, dK(v) — k) is as small as possible. Denote by S С V the set of vertices with dK > k. Define an augmenting path as such a sequence of vertices and edges V1,е1,... ,v_m,е_m,v_m+1 th at v_t Е V, е» Е Е, Дуе») Е Ек, (v»+i, е») Е Ек, е» are pairwise distinct, vi Е S. Let U С V be the subset of vertices of V reachable by an augmenting path. Note that:

• •    For any v Е U the inequality dK (v) >  k holds (otherwise we could flip the status of edges on the corresponding augmenting path and decrease p(K )).

• •    For any е Е Е if Nk (е)П U = 0 thcri | Ng ( c ) \ U | 6 1. Indeed, suppose that v Е N k (е)П U. then any w Е Ng^) \ N k (е) must lie in U, because there is an augmenting path ending in w: it follows that the only vertex of Ng ( c ) which can possibly not lie in U is the unique vertex from N k (е) \ {v}.

Let Т С N _k (U ) be a set of е Е N _k (U ) such that |No(e) \ U | = 1. Si nee d_K (v) >  к for any v Е U and dK (v) >  к for any v Е S, we get the inequality

| Nk (U ) \ Т | >^kl^ULJ^T|.

Now we obtain the lower bound on the sum of degrees do over vertices of U by summing up |N^(e) П U | otvr е Е N _k (U ):

-

^} >  A(H )|U|.

£ d_G(v) > IT^s(H ) - 1) + ^{k | U 1 | T 1} s(H ) > A(H) | U| + |T| ^(H) - 1 «eu

It follows that there exists such v Е U with do(v) >  A(H ), which is a contradiction.        □

3.    Dense case

Теорема 9. Let H ^c an s-uniform 2-colomble hypergraph on t vertices and t< 4(1 + W')'.

Then ch(H) < I.

Доказательство. Consider the set of lists as a hypergraph F. Then t = |E(F )|; we still refer to edges of F as lists to avoid the confusion with edges of H. We split the palette V (F) randomly into three parts: blue colors, red colors and neutral colors in the following way. Every vertex of V(F) is red or blue uniformly and iiidependently with probability ^1—2. so with probability p it is neutral; the value of p will be defined later. Then the expectation of monochromatic lists is equal to

A = 2 (^1-2 У ^|E(F )!•

We call a list dangerous, if it has no blue or no red vertices. The expectation of dangerous lists equals to

B = ² (Цт) I^E (F)|.

In Ilie case A <  1/2 arid B < s/2 Markov inequality implies that with positive probability F has no monochromatic edges and the number of dangerous lists is smaller than s. Recall that H is 2-colorable; under the assumption one can color vertices of one part of H in blue or neutral colors, vertices of another part of H in red or neutral colors, in such a way that vertices of H corresponding to dangerous lists have neutral colors. Since we have less than s dangerous lists, arid every other edge of H lias a red arid a blue vertex. we construct a proper coloring of H.

Now we show that the following choice of p satisfies the desired inequalities. Put

s1/' - 1     ,      B     1+ p\1 p =1 + ,1/' ’  "'^ A = U - p) = ‘' On the other hand, (^)'=(1+^ Summing up, A = ^E (F )|  =    2t    < 1 (1 + s1/')    (1 + s1/')    2 ’ hence B = A (^)' = A,

Obviously, ch(KS/_2t/₂)< ch(K_t²/_2t/₂) = (1 + o(1))log₂t by Erdos-Rubin-Taylor theorem.

Note that for s = t“, where a is a constant, the bound in Theorem 9 is constant times better.

Теорема 10. Suppose that t = И ((log s + log I) • 12(1 + s1/1)1^ .

Then ch(Kt/2,t/2) > Z.

Доказательство. Denote H = K®/_{2 t}/₂. Put v = Z² and consider a set of random (independent and uniform) lists with size I over the left part of H, and its copy over the right part. Let F be the resulting random hypergraph of colors; we refer to its edges as lists to avoid the confusion with the edges of H.

Suppose the contrary: in particular it means that for every F hypergraph H = K_t^s/_{2 t}/₂ has proper coloring in colors of F. Consider an arbitrary such proper coloring ph- We call a color (a vertex of F) poor, if it appears in both parts of H. so a poor color appears at most s — 1 times. Define a coloring p_p on vertices of F as follows: if a color appears only in the left part of H then the corresponding vertex of F is blue, if a color appears only in the right part of H then the corresponding vertex of F is red, finally if a color is poor then the corresponding vertex has no color. Note that pp contains no monochromatic lists; indeed if a list is blue then one cannot choose a color from a copy of this list over the vertex in the right part of H, which contradicts with the existence of ph- We show that with positive probability such a coloring pp cannot exist.

Consider an arbitrary vertex coloring p of F in two colors in which some vertices remain colorless. We call a list dangerous if it has no blue or no red vertices. It turns out that with positive probability every p has a monochromatic list or greater than vg(s — 1) dangerous lists, where vo is the number of colorless vertices. Hence pp (and also ph) cannot exist, which gives the desired contradiction. Below we provide an upper bound on the probability of every p to have no monochromatic list and no more than vo(s — 1) dangerous lists.

Let c = ^ l>e the ratio of colork'ss vertices, denote by p1 = p1(p) the probability that a random list is monochromatic and by p₂ = p₂(p) the probability that it is dangerous. By definition

P1 = 2 (^)'   P^ = 2 (^)'

Then the probability that we have at most (s — 1)cv dangerous lists is smaller than the probability that there are at most sZ2 dangerous lists. The latter is evaluated by

E ^{7 2} a 1 — P2)^t/2-i< E (^)"е-*-* " = 1    ^% ’                        "=1       '

< E (т у

"=1 x 7

_g-P2 (t/2-si'²)

Consider the following substitution c = ^+1 and put T =

ДЖ+1Ғ Wc got

^p2 = 2 (^У =2 ()^l

2s

(s1/1 + 1)i.

Then ^tp2 = sT and

E (^tp2У

"=1  '     7

_e^-_P2^(t/2-si2) < sz² (^

si2

_g^-P2 ^(t/2-si2)

.

One has

g ^p2^{(t/2 si}2) < g ^(p2^{t/2 si}2) = g^-sT+^si2

Also

' 2

.

si² (^)   = (sT + o(1))^s/2 = e^{(1+o(1)) log(sT)st}

Summing up, under the conditions of theorem

(1 + o(1))i²s log(sT) — sT + si²< 0

and the event that the number of dangerous lists is smaller than si² has probability smaller than

1                                                                                                      "                                                                                                                          '

2'

On the other hand

t

(1 — py)¹/²< _e^-pit/2< е (і+т^/г)^г = e

^T< 2 •

So for c = ^/;₊1 a random i-graph of lists with positive probability has both a monochromatic list and at least si² dangerous lists in every 2-coloring. From a combinatorial argument for smaller c a random i-graph of lists with positive probability has a monochromatic list in every 2-coloring. and for bigger c with positive probability has at least si² dangerous lists in every 2-coloring.

□

4.    Applications and discussion

• 1)    A hypergraph is к-гсциіаг if the degree of every vertex is equal l,о к. It is known that a к-uniform к-regular hypergraph is 2-colorable for к > 4 [7,11]. Thus Theorem 6 gives that such graph has the list chromatic number 2. So к-uniform k-regular hypergraphs are chromatic-choosable for к > 4.

• 2)    It turns out that there is a large gap between the bounds in dense and sparse cases; the same holds even for 2-graphs. As far as we are aware, the best known general bounds on the choice number of d-regular bipartite graph G are the following (see [4])

(2—°(1))iogd

Note that Erdos-Rubin-Taylor theorem gives a tight bound for a complete bipartite graph ^сһ^(КІі) = ^{(1 +} o^(1))log t.

• 3)    Theorems 9 and 10 can be extended for r-colorable hypergraphs (r > 2 is a constant) in a direct way.

Acknowledgments. The research of Danila Cherkashin is supported by «Native towns», a social investment program of PJSC «Gazprom Neft». The research of Alexey Gordeev was funded by RFBR, project number 19-31-90081.

Appendix. Alternative proof of Theorem 5

Denote parts of H as A, В eV: every edge of H intersects both A and B. For each edge e of H choose a spanning tree T_e on its set of vertices such that each edge of T_e connects a vertex from part A with a vertex from part B. Consider the following polynomial on variables {х_а}_аЕд, ^{Уь^}ьев-

^ҒН/Л Ц I ^2 ^(жа^— Уь) J .

eEE y(a,b)GT_e           /

Note that if Ғң(x,y) — 0 then the values of x,y form a proper coloring of H (the reverse is not necessarily true). By Combinatorial Nullstellensatz (see [2]), if the coefficient

Г п x   n yt^A Ғн—о,

LaeA       ьев      J then H is (d^ + 1)-choosable. Consider now

^ҒН^(x,^{y) — Ғ}н^(x, -у) — I ⁽x_a + уь) I . eEE \(a,b) ET_e           /

Note that n ■ n yt-(ь)

.aEA       bEB

Ғн — ± n x^t-(a)П yt^-(b . aEA       bEB

ҒН,

hence one can study coefficients of ҒҢ instead of Ғң. The coefficient of ҒҢ in question is nonzero, because no summands will cancel out after opening the brackets, and orientation p corresponds to at least one summand with the desired coefficient.