A NOTE ON TWO-COLORABILITY OF NONUNIFORM
HYPERGRAPHS

arXiv:1803.03060v1 [math.CO] 8 Mar 2018

LECH DURAJ, GRZEGORZ GUTOWSKI, AND JAKUB KOZIK
Abstract. For a hypergraph H, let q(H) denote the expected number of
monochromatic edges when the color of each vertex in H is sampled uniformly
at random from the set of size 2. Let smin (H) denote the minimum size of an
edge in H. Erdős asked in 1963 whether there exists an unbounded function
g(k) such that any hypergraph H with smin (H) > k and q(H) 6 g(k) is
two colorable. Beck in 1978 answered this question in the affirmative for a
function g(k) = Θ(log∗ k). We improve this result by showing that, for an
absolute constant δ > 0, a version of random greedy coloring procedure is
likely to find a proper two coloring for any hypergraph H with smin (H) > k
and q(H) 6 δ · log k.

1. Introduction
A hypergraph H = (V, E) is a finite set of vertices V and a set of edges E where
each edge is a set of at least two vertices. A two coloring of H is an assignment
of color blue or red to each vertex in H. A coloring is proper if each edge in H
contains both a vertex colored blue and a vertex colored red. We say that H is
two colorable if it admits a proper two coloring. Hypergraph H is k-uniform if
every edge in H has size exactly k – we also say that H is a k-graph. For every
n ∈ N, the set {1, . . . , n} is denoted by [n]. We use standard O-notation to describe
asymptotic properties of various functions.
One of the most classical problems in the extremal combinatorics is to find the
minimum number of edges m(k) in a k-uniform hypergraph that is not two colorable.
The research on this problem has been started in the 60s by Erdős and Hajnal
[EH61], who used the term Property B for two colorability. Today, by the result of
Radhakrishnan and Srinivasan [RS00], we know that m(k) = Ω((k/ log k)1/2 ) · 2k .
The best known upper bound, proved by Erdős [Erd64] in 1964, is m(k) = O(k 2 )·2k .
This upper bound follows from the fact that a random k-graph with k 2 vertices
and O(k 2 ) · 2k edges is very unlikely to be two colorable. Interestingly, known
deterministic constructions require much larger structures – the best one is by
2/3
Gebauer [Geb13] and gives a not two colorable k-graph with roughly 2k+k edges.
Lovász [Lov73] proved that for k > 3, the problem of deciding if a given k-graph is
two colorable is NP-complete. For k-graphs with the number of edges smaller than
m(k) the decission problem is trivial – by the definition they are all two colorable.
Nevertheless, constructing a two coloring of such k-graphs is not necessarily an
easy task. Luckily, the known lower bounds for m(k) are constructive. In fact, the
bound of [RS00] is proved by showing that some randomized coloring procedure
succeeds with high probability for the considered hypergraphs. Cherkashin and
Kozik [CK15] showed that the same bound is obtained by the analysis of a random
1991 Mathematics Subject Classification. G.2.1 Combinatorics, G.2.2 Graph Theory, G.3 Probability and Statistics, F.2.2 Nonnumerical Algorithms and Problems.
Key words and phrases. Property B, Nonuniform Hypergraphs, Hypergraph Coloring, Random
Greedy Coloring.
This work was partially supported by Polish National Science Center (2016/21/B/ST6/02165).
1

2

LECH DURAJ, GRZEGORZ GUTOWSKI, AND JAKUB KOZIK

greedy algorithm (i.e., a procedure that colors the vertices of a hypergraph in a
random order and assigns color blue to each vertex unless it is the last vertex of a
monochromatic blue edge – only then color red is assigned).
For a hypergraph H = (V, E), let q(H) denote the expected number of monochromatic edges when the color of each vertex is sampled uniformly at random. Clearly,
for a k-graph H, we have q(H) = |E| · 2−k+1 , and determining the value of
m(k) is equivalent to finding a not two colorable k-graph H with the minimal
possible value of q(H). This formulation allows for a neat generalization of the
question to hypergraphs with edges of arbitrary sizes (i.e., nonuniform hypergraphs). ForPa hypergraph H = (V, E), let smin (H) = mine∈E |e| and observe
that q(H) = e∈E 2−|e|+1 . Erdős [Erd63, EL75] asked whether there exists an unbounded function g such that any hypergraph H with smin (H) > k and q(H) 6 g(k)
is two colorable. A positive answer has been given in 1978 by Beck [Bec78] who
proved the result for g(k) = Θ(log∗ (k)). This has not been improved since then.
(In 2008 L. Lu announced a proof of a bound Ω(log(k)/ log log(k) but it turned out
to work only for√simple hypergraphs. Shabanov in [Sha15] improved the bound for
this class to Ω( k).) In this paper we prove the same result for g(k) = Θ(log(k)).
The random construction of a not two colorable k-graph by Erdős [Erd64] shows
that the best possible g is O(k 2 ), even when restricted to uniform hypergraphs. Interestingly, there are no better nonuniform constructions known. Our main result
is the following.
Theorem 1.1. There exists a constant δ > 0 such that for all sufficiently large k,
any hypergraph H = (V, E) with smin (H) > k and q(H) 6 δ · log k is two colorable.
Moreover, we prove the theorem by showing that a version of a random greedy
coloring procedure succeeds with positive probability for these hypergraphs.
2. Basic notions and the coloring procedure
2.1. Tools. We start with a simple lemma on convex functions of random variables.
Lemma 2.1. Let X be a nonnegative random variable such that 0 6 X 6 M and
E[X] 6 λM for some M > 0, and 0 6 λ 6 1. Then, for any convex function
f : [0, M ] → [0, ∞) with f (M ) > f (0), the following inequality holds
E[f (X)] 6 λf (M ) + (1 − λ)f (0).
Proof. Consider another random variable Y :=
convexity of f we have f (X) 6 Y . Therefore

X
M f (M )

+ (1 −

X
M )f (0).

From the

E[X]
E[X]
E[X]
·f (M )+f (0)−
·f (0) 6 f (0)+(f (M )−f (0))·
6 λf (M )+(1−λ)f (0),
M
M
M
as desired.

E[f (X)] 6

2.2. Preliminaries. Let H = (V, E) be a hypergraph and let k denote the minimum size of an edge in H. For any j > k we define
X
2−j+1 ,
qj :=
e∈E,|e|=j

which is the expected number of monochromatic edges of size j when the color
of each
P vertex is sampled uniformly at random. Let q := q(H) and observe that
q = j>k qj .
We aim to prove that if q = O(log k) then the hypergraph is two colorable.
In order to do that, we describe a random coloring procedure and with a careful
analysis we bound the probability that a fixed edge is monochromatic after the

A NOTE ON TWO-COLORABILITY OF NONUNIFORM HYPERGRAPHS

3

procedure finishes. The obtained bound allows us to conclude that the expected
number of monochromatic edges after the procedure finishes is smaller than one.
Thus, the hypergraph is two colorable.
2.3. The coloring procedure. Our algorithm is based on the random greedy coloring and it works in two phases:
(1) Initial coloring
We start by independently sampling, for every vertex v, the following
two values:
• ic(v) – the initial color of v: blue or red, each with probability 21 ,
• w(v) – the weight of v, sampled uniformly at random from the real
interval (0, 1).
The edge in which all vertices get the same initial color is called initially
monochromatic. We assume that no two vertices have the same weight –
we discuss this in Section 3.1. For an edge e, the heaviest vertex in e is the
one with maximum weight among vertices in e. We define the weight w(e)
of e to be the weight of the heaviest vertex in e (i.e., w(e) = maxv∈e w(v)).
(2) Recoloring
We iterate over all vertices in the order of increasing weight and for each
vertex v, we define c(v) – the color of v. Once the color is assigned, it is
never changed. We say that a vertex v is recolored if c(v) is already defined
and it is different than ic(v). Our goal is to recolor at least one vertex
in each initially monochromatic edge. If v is the heaviest vertex in some
initially monochromatic edge e, then the color of every other vertex in e is
already defined. If none of the vertices in e is recolored, we define c(v) to be
the color other than ic(v) (i.e., we recolor v), and we say that e is a reason
to recolor v. Note that there may be more than one reason to recolor v. If
there is no reason to recolor v (i.e., no initially monochromatic edge with
no recolored vertex and heaviest vertex v) we simply assign c(v) = ic(v).
Observe that eventually every initially monochromatic edge gets one of the
vertices recolored.
2.4. Main result. For a better exposition of the argument, we first prove a statement slightly weaker than Theorem 1.1. In Section 3.3 we give a proof of the
following result about the coloring procedure.
Proposition 2.2. If q = O( logloglogk k ) then, for any edge e, the probability that all
1
vertices in e are colored red does not exceed 3q2|e|−1
.
This immediately
implies that the expected number of monochromatic edges is
P
at most 2 · e∈E 3·q·21|e|−1 = 23 and thus, not only H is two colorable but also
that our coloring procedure succeeds with probability at least 31 . In Section 3.4 we
introduce more technical details to the argument and improve the bound.
Proposition 2.3. If q = O(log k) then, for any edge e, the probability that all
1
vertices in e are colored red does not exceed 3q2|e|−1
.
This immediately implies Theorem 1.1.
3. Analysis
3.1. Bad events. The proof focuses on bounding the probability that one, fixed
edge becomes monochromatic red. Nevertheless, we want to first exclude some
problematic but unlikely events from happening. The simplest example is that we
don’t want two different vertices to receive the same weight. The probability of this
event is zero and we want to simply assume that it doesn’t happen. To be more

4

LECH DURAJ, GRZEGORZ GUTOWSKI, AND JAKUB KOZIK

precise, we allow our coloring procedure to fail during the initial phase of coloring.
We give a few different reasons to fail and we argue that the probability that any
of those bad events happens is small. Then, for the rest of the proof, we assume
that none of the bad events happens.
3.1.1. Event A – too many initially monochromatic edges. The expected number
of initially monochromatic edges is q. For a constant αA (to be fixed later) let A
denote the event that there are more than αA · q initially monochromatic edges.
Markov inequality gives that Pr[A] < 1/αA .
3.1.2. Event B – a light monochromatic edge. For a constant αB (to be fixed later)
and every j we define
ln(αB q)
.
pj :=
j
An edge e of size j is light if it is initially monochromatic and the weight of every
vertex in e is smaller than 1 − pj . The expected number of light monochromatic
edges of size j is
qj
qj 2j−1 · (1 − pj )j · 2−j+1 < qj · j · exp(−pj ) =
.
αB q
Therefore, the expected total number of light edges (of any size) is at most 1/αB .
Let B denote the event that there is a light monochromatic edge. Clearly Pr[B] <
1/αB .
3.1.3. Event C – too many almost monochromatic edges. An edge e is almost monochromatic if there is a vertex v ∈ f such that all vertices in f − v have the same initial
color (in particular, an initially monochromatic edge is also an almost monochromatic edge). With every almost monochromatic edge f we can injectively associate
a certifying pair (f, v) ∈ E ×V for which v ∈ f and f −v is initially monochromatic.
Let Qj be a random variable that denotes the number of almost monochromatic
edges of size j. Since the number of such edges cannot exceed the number of
certifying pairs associated with edges of size j, we get E[Qj ] 6 qj 2j−1 · j · 2−j+2 =
2j · qj . We define random variable
X Qj
,
Y :=
j
j
and get that E[Y ] 6 2q. Let C denote the event that Y > αC q. Markov inequality
gives Pr[C] < 2/αC .
For any fixed ε > 0 we can choose constants αA , αB , αC so that 1/αA + 1/αB +
2/αC < ε. Denote by G the intersection A ∩ B ∩ C and observe that Pr[G] > 1 − ε.
That is, with arbitrarily high probability none of the bad events happens. For
any event V, we denote Pr[V ∩ G] by PrG [V] and similarily by PrG [V|C] we mean
Pr[V ∩ G|C].
3.2. e-focused coloring. For the rest of this section and the next section we fix
an arbitrary edge e in E. Let s denote the size of e. The event “e becomes red ”
denotes the situation that all vertices in e are colored red by the coloring procedure.
First observation is that if e is initially monochromatic red, then at least one vertex
in e gets recolored and e can’t become red in the end. Thus, if e becomes red then e
contains some initially blue vertices and each of them gets recolored. In particular,
every initially blue vertex in e is the heaviest vertex in some initially monochromatic
blue edge. Additionally, it needs to happen that none of the initially red vertices
in e gets recolored, but this condition seems impossible to use.

A NOTE ON TWO-COLORABILITY OF NONUNIFORM HYPERGRAPHS

5

Taking into account the bad events we aim to prove that for a proper q we have:
1
1
PrG [e becomes red] < · s−1 .
3 q2
3.2.1. The threat hypergraph. In what follows we try to understand better which
initially blue vertices in e are recolored to red. The important observation is that
if edges f and e have more than one vertex in common and f is a reason to recolor
any of the common vertices, then e does not become red. To see that, let v be the
heaviest vertex in f , and let w be any vertex in f ∩ e other than v. If f is a reason
to recolor v then f is initially monochromatic blue and w is not recolored. Thus,
w retains the initial blue color, and edge e does not become red.
This motivates the following construction of the threat hypergraph He . We define
the vertex set of He to be V \ e. For each edge f in E that has exactly one common
vertex with e (i.e., |f ∩ e| = 1), let fe = f \ e. We define the edge set of He to be
{fe : f ∈ E, |f ∩ e| = 1}. Observe that for different edges f 6= f ′ in E it might
happen that fe = fe′ . Thus, He is a multihypergraph. For each edge fe of He we
call f to be the extension edge of fe and we call the only vertex in f ∩ e to be the
extension vertex of fe .
For the sake of our analysis, we reveal the outcomes of the random experiments
used in the coloring procedure in four steps. In the first step we reveal the initial
colors of the vertices in He . In the second step, we reveal the initial colors of the
vertices in e. Then, we reveal the weights of vertices in He . Finally, we reveal the
weights of the vertices in e. It is crucial to understand that this does not influence
the coloring procedure in any way.
After the first step, some edges in He are monochromatic blue. For every such an
edge fe , let v be the extension vertex of fe , and we say that v is endangered by fe .
Observe that if e is to become red, then among vertices in e, only the endangered
ones can be recolored from blue to red. For every endangered vertex v in e we define
the severity of v to be the minimum size |f | of an edge such that v is endangered
by fe . We define Rej to be the set of all vertices in e that are endangered and with
severity j. Let Rje := |Rej |. Note that both Rje and Rej are random variables which
are determined after the first step (i.e., by the initial colors of the vertices in He ).
Thus, a necessary condition for e to become red is that in the second step only
the endangered vertices get initial color blue. Consider an endangered vertex with
severity j which is initially blue and which is to become red. There is an edge fe
that endangers v, and v becomes the heaviest vertex in the extension of fe . In
particular, since the size of f is at least j, the weight of v (revealed in the fourth
step) has to be at least 1 − pj . Otherwise, the edge f is a light monochromatic edge
and bad event B happens.
Observe that there are no more vertices recolored than there are initially monochromatic edges. As we assume that bad event A does not happen, there are at most
αA q vertices recolored in total. Let us sum up the observed necessary conditions
for the edge e to become red:
(1) at least one and at most αA q vertices in e are initially blue,
(2) every initially blue vertex v in e is endangered. If severity of v is j then
w(v) > 1 − pj .
We use these conditions to obtain an upper bound on the probability of e becoming
red.
3.3. Simple bound. We define, mainly for technical convenience, a random variable
X
Rje · pj .
X :=
j

6

LECH DURAJ, GRZEGORZ GUTOWSKI, AND JAKUB KOZIK

Observe that X is determined after the first step and that X takes only a finite
number of possible values. For the rest of this section whenever we condition on
event X = x we always assume that the value x is such that Pr[X = x] > 0. The
bound will follow from the following result:
Proposition 3.1.
PrG [e becomes red |X = x] <

exp(x) − 1
.
2s

Proof. Assume that we are after the first step and the values of variables Rej , Rje ,
and X are determined. For each j > k, let rj := Rje . With this assumption, we
compute the probability of e becoming red. We claim that
X
Y rj   pj cj  1 rj −cj
1
.
PrG [e becomes red |the first step] 6 s−P r
j j
cj
2
2
2
j
16ck +ck+1 +...6αA q

The first factor corresponds to the not endangered vertices in e – each of them
needs to be initially colored red. The sum spans over the values ck , ck+1 , . . ., where
e
cP
j corresponds to the number of initially blue vertices in Rj . There are exactly
j cj initially blue elements and we know that this number is at least 1 and at
most αA q.

Once the number of initially blue elements in each Rej is fixed, there are rcjj
possibilities to choose these elements from Rej . Finally, all the chosen elements have
to be initially colored blue and their weight has to be at least 1 − pj . The remaining
elements of Rej have to be initially colored red.
Observe that the expression depends not on a particular result of the first phase,
 r cj
but rather only on the values of Rje . We use the fact that rcjj 6 cjj ! , rearrange the
terms, and obtain:
αA q
X
Y rj  c
1 X
pj
PrG [e becomes red |(Rje = rj )j>k ] 6 s
2 c=1 c +c +...=c j cj j
k
k+1
c

α
Aq
X
X
1
1
6 s
rj · pj  .
2 c=1 c!
j
P e
P
Let x :=
j Rj · pj , and observe that the last
j rj · pj , recall that X =
expression depends not on the particular values of Rje , but rather only on the value
of X.
αA q
1 X xc
PrG [e becomes red |X = x] 6 s
(1)
2 c=1 c!
(2)

<

exp(x) − 1
.
2s


Proof of Proposition 2.2. Recall that the random variable Qj denotes the number
of almost monochromatic edges of size j, while Rje is the number of endangered
vertices in e with severity j. For every such a vertex v we have an initially blue
edge f in He for which v is the extension vertex. Since the extension edge of f is
almost blue we obtain that Rje 6 Qj . This implies:
(3)

X=

X
j

Rje · pj = ln(αB q) ·

X Rje
j

j

6 ln(αB q) ·

X Qj
j

j

= ln(αB q) · Y .

A NOTE ON TWO-COLORABILITY OF NONUNIFORM HYPERGRAPHS

7

Therefore X 6 ln(αB q) · αC q unless bad event C happens. We now have:
X
Pr[X = x] · PrG [e becomes red |X = x]
PrG [e becomes red] =
x6ln(αB q)·αC q

<

X

x6ln(αB q)·αC q

6
Inequality (3) also yields

Pr[X = x] ·

exp(x) − 1
2s

h
i
1
· E exp(X) − 1 X 6 ln(αB q) · αC q .
s
2

E[X] 6

X
j

qj · pj 6

q ln(αB q)
.
k

We apply Lemma 2.1 for f (x) = exp(x) − 1, M = αC q ln(αB q) and λ =
obtain:
exp(ln(αB q) · αC q)
E[exp(X) − 1] 6
.
αC k
Hence
1 exp(ln(αB q) · αC q)
.
PrG [e becomes red] < s ·
2
αC k
Let α > max{αB , αC }. Now, suppose that:

1
αC k ,

and

ln k
1
·
.
α ln ln k
For k large enough, ln(αB q) 6 ln ln(k) which yields:


exp(ln(αB q) · αC q)
αC ln k
1
k (αC /α)−1
.
6
· exp
· ln ln k 6
αC k
αC k
α ln ln k
αC
q6

For k large enough, the last term is less than

1
6q ,

PrG [e becomes red] <
and completes the proof.

which implies:

1
3q · 2s−1



An astute reader may have realised that we did not use bad event A in any
essential way. Currently, the only reason to introduce A is that it makes the proof
slightly easier. We could, however, use A to improve bound (2) for the values of x
log k
greater than q, leading to a slightly better condition q = O( log log
log k ). We do not
elaborate on that since the argument in Section 3.4 already gives an even better
result.
3.4. Improved bound. In order to obtain an improved bound we introduce one
more bad event.
3.4.1. Event D – large second weight deficit. For every edge f in E which is initially
monochromatic, we define its second weight deficit as d2 (f ) := (|f |+ 1)·(1 − w2(f )),
where w2 (f ) is the weight of the second heaviest vertex in f . For an edge f that is
not initially monochromatic, d2 (f ) is defined to be 0.
Note that, conditioned on f being initially monochromatic, the variable 1 −
2
. In particular E[d2 (f )| f is monochromatic] = 2 and hence
w2 (f ) has mean |f |+1
P
2
E[d2 (f )] = 2|f |−1 . Let D2 := f ∈E d2 (f ) and observe that we have
X
2qj = 2q.
E[D2 ] =
j

8

LECH DURAJ, GRZEGORZ GUTOWSKI, AND JAKUB KOZIK

Event D is defined as D2 > αD q. By Markov inequality, we get Pr[D] < 2/αD and
we can chose αD so that this probability is arbitrarily small.
3.4.2. Analysis. In the first step of e-focused coloring we reveal the initial colors
of all the vertices from V \ e. This step determines the endangered vertices in e –
we denote their set by R. For every value of c = 1, 2, . . . αA q and every c-subset
S = {v1 , . . . , vc } of R we consider an event that S contains exactly the vertices in e
which become recolored. Thus, these are the only initially blue vertices in e. Once
we fix the subset S, the probability that S is the set of initially blue vertices in e is
precisely 2−s . This event is determined after the second step of e-focused coloring
– when the initial colors of vertices in e are revealed. In order to be recolored,
every vertex vj must receive a weight that makes it heavier than some edge that
endangers it. Let us reveal the weights of the vertices in V \ e (third step of efocused coloring). The vertex vj is endangered by some edges fv1j , . . . , fvtj of He ,
and let fvj be the lightest of these edges (i.e. the edge whose heaviest vertex is
the lightest among the heaviest vertices of fv1j , . . . , fvtj ). Clearly in order for vertex
vj to be recolored, it has to get a weight greater than w(fvj ) – this happens with
probability 1 − w(fvj ). We choose a parametrization that takes into account the
δ
size of fvj and denote the value 1 − w(fvj ) by |fv j|+2 . Now, conditioned on the
j

result of the first three steps, the probability that all vertices {v1 , . . . , vc } are heavy
enough is
c
c
Y
Y
δj
δj
<
.
(4)
|
+
2
|f
|f
vj
vj | + 1
j=1
j=1

The edge fvj together with vj forms an edge of H, which we denote by hvj . Although the value of d2 (hvj ) is not determined until we reveal the weight of vj (in
the fourth step), we already know at this point that δj 6 d2 (hvj ) (it becomes an
equality when vj becomesP
the heaviest vertex in hvj ). Assuming the bad event D
c
does not happen, we have j=1 δj 6 αD q. Using the AM-GM inequality we deduce

Qc
c
that j=1 δj 6 αDc q , which bounds the value of (4):
c

c
Y

 α q c Y
1
δj
D
6
.
|fvj | + 1
c
|f
v
j| + 1
j=1

j=1

Summing over all c-subsets of R we get that the probability that some c-subset
contains all initially blue vertices in e and they are all recolored does not exceed
!c
X 1  αD q c Y
1  αD q c 1 X
1
1
.
6 s
2s
c
|fv | + 1
2
c
c!
|fv | + 1
R
v∈S
v∈R
S∈( c )
Define random variable
Ye :=

X

fe in He , fe is blue

1
,
|fe | + 1

which gets determined after the first step of e-focused coloring. For each endangered
vertex v in e, all the edges, including the lightest one, that P
endanger v are blue
and thus are taken into the sum defining Ye . Therefore, Ye > v∈R |fv1|+1 . On the
other hand, the extension edge of every blue edge in He is an almost monochromatic
edge in H. As Y counts the number of almost monochromatic edges in H, we get
Ye 6 Y 6 αC q unless bad event C happens. We can also bound the expected value
of Ye :
X 2−|f |
1 X −|f ′ |+1
q
<
2
= .
E[Ye ] =
|f | + 1
k ′
k
f ∈He

f ∈H

A NOTE ON TWO-COLORABILITY OF NONUNIFORM HYPERGRAPHS

9

Note that Ye takes only a finite number of possible values. For any value y such
that Pr[Ye = y] > 0, we get the following bound:
αA q
1 X  αD q c y c
PrG [e becomes red |Ye = y] 6 s
2 c=1
c
c!
6

6
c

c!·(2c)
as (2c)!
= c!·cc . For any x, we have
2c 6
2c
Therefore

PrG [e becomes red |Ye = y] 6
and



αA q
1 X (αD qy)c
2s c=1 c! · cc

αA q
1 X (2αD qy)c
2s c=1 (2c)!

x2c
c=0 (2c)!

P∞

=

exp(x)+exp(−x)
2

= cosh(x).


p
1
qy
− 1),
(cosh
2α
D
2s



p
1
PrG [e becomes red] 6 E s (cosh
2αD qYe − 1) Ye 6 αC q .
2
√
convex and
Observe that for any a > 0, the function cosh (a x) is √
 increasing in
[0, ∞). Therefore, we apply Lemma 2.1 for f (x) = cosh 2αD qx − 1, M = αC q
and λ = α1C k , and obtain:

p

√
1
1 1
(cosh
exp 2αD αC · q .
PrG [e becomes red] 6 s
2αD αC qq − 1) 6
s
2 αC k
αC k2
1
3q2s−1

whenever

√
3q exp 2αD αC · q
6 1.
2αC k

The obtained value is smaller than

The last inequality is easily seen to hold for q 6
k.

√ 0.9
2αD αC

ln k and all large enough

4. Remarks
4.1. Bounded maximal size. We can derive better bounds when the size of the
maximum edge is not much larger than k. Suppose that maxe∈E |e| 6 K. We apply
the proof strategy from [CK15] and analyze the random greedy coloring procedure
(i.e. we arrange the vertices in random order and color consecutive vertices blue
if this does not create a monochromatic edge, otherwise we color it red). As a
technical convenience, instead of sampling a random ordering of the vertices, for
every vertex we choose uniformly a weight from the real interval (0, 1). We color
vertices greedily in the order of increasing weights. We choose (with foresight)
parameter p := ln(4q)/k. An edge is called light if the weight of its heaviest vertex
is at most (1 − p)/2. Similarly an edge f is heavy if every verex in f has weight
at least (1 + p)/2. The probability that there exists a light edge is bounded by the
expected number of such:
X  1 − p |f |
6 (1 − p)k · q.
2
f ∈E

The same bound holds for heavy edges. It is easy to see that in order for the
procedure to fail there must exist a pair of edges f1 , f2 such that the heaviest vertex
of f1 is the lightest vertex of f2 . Such a pair is called conflicting. Therefore for the
procedure to fail it is necessary that either there exists a conflicting pair f1 , f2 for
which the weight of the unique common vertex belongs to ((1 − p)/2, (1 + p)/2) or

10

LECH DURAJ, GRZEGORZ GUTOWSKI, AND JAKUB KOZIK

there exists a light or heavy edge. The expected number of such conflicting pairs
is at most
|f1 |−1 
|f2 |−1
X Z p/2  1
1
+x
−x
dx
2
2
f1 ,f2 ∈E −p/2
X
6
2−|f1 |−|f2 |+2 · p ·
max
(1 + 2x)|f1 |−1 (1 − 2x)|f2 |−1
x∈(−p/2,p/2)

f1 ,f2 ∈E

6p·
=p·

X

f1 ,f2 ∈E

X

f1 ,f2 ∈E

2−|f1 |−|f2 |+2 ·

max

x∈(−p/2,p/2)

(1 + 2x)|f1 |−|f2 |

2−|f1 |−|f2 |+2 · (1 + p)|f1 |−|f2 |

6 p · (1 + p)K−k

X

2−|f1 |−|f2 |+2 = p(1 + p)K−k q 2 .

f1 ,f2 ∈E

Altogether the probability of failure is at most
p(1 + p)K−k q 2 + 2(1 − p)k q ∼ pq 2 exp(p(K − k)) + 2q exp(−pk).
Plugging in the value of p we get
ln(4q)q 2 (4q)K/k−1
ln(k)(4q)K/k+1
+ 1/2 6
+ 1/2
k
k
where we additionally assumed that q 6 k. As long as this value is below 1 we can
be sure that random greedy coloring strategy succeeds with positive probability.
For k = K we recover the result of [CK15]. When K is bounded by a linear
function of k, e.g. K 6 αk it is sufficient that q does not exceed
1

 α+1
k
1
5 ln(k)
The resulting bound for q starts to be worse than the one from Theorem 1.1 when
K is roughly of the order k log(k).
4.2. Uniform case. It is instructive to observe how our analysis works for uniform
hypergraphs. We focus on modifications in the proof of our simple bound, since
the ideas used for the improved bound do not help in the uniform case. Using an
obvious bound Rke 6 k, we improve inequality (3) to X 6 ln(αB q). Then we apply
Lemma 2.1 with M = ln(αB q) and λ = kq obtaining
q
q 1+αB
exp(ln(αB q)) = 2−k
.
k
k
Since in this case the only bad event that we use is B, we can afford to set αB = 1+ε,
ε
.
for any small ε > 0. We get that B does not happen with probability at least 1+ε
Then
q 2+ε
PrG [e becomes red] < 2−k
k
ε
and in order for this value to be at most 2k1q · 1+ε
it suffices that
PrG [e becomes red] < 2−k

q6k

1
3+ε

·



ε
1+ε

1
 3+ε

.

This way we obtain a result analogous to that of Beck from [Bec78] (i.e. m(k) >
k 1/3−o(1) 2k ). Incorporating
the ideas from [RS00] or [CK15] that allowed to derive
p
a bound m(k) = Ω( k/ log(k)) · 2k does not bring any significant improvement of
our main result.

A NOTE ON TWO-COLORABILITY OF NONUNIFORM HYPERGRAPHS

11

4.3. Hypergraphs with random-like characteristics. The weakest points of
our analysis are the places where we apply Lemma 2.1. The lemma works for any
bounded non-negative random variable X. It is clear from the bound that the
worst case distribution of X is the one that assumes only values 0 and M . The
variables for which we apply the lemma are related to the numbers of initially
monochromatic edges in hypergraphs He . If these variables exhibit sufficiently
strong concentration around their mean (like in the case of random hypergraphs)
we may get much stronger bound than the one of Lemma 2.1 and obtain results
that are much closer to the case of uniform hypergaphs.
References
[Bec78] J. Beck. On 3-chromatic hypergraphs. Discrete Math., 24(2):127–137, 1978.
[CK15] Danila D. Cherkashin and Jakub Kozik. A note on random greedy coloring of uniform
hypergraphs. Random Structures Algorithms, 47(3):407–413, 2015.
[EH61] P. Erdős and A. Hajnal. On a property of families of sets. Acta Math. Acad. Sci. Hungar,
12:87–123, 1961.
[EL75] P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some
related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P.
Erdős on his 60th birthday), Vol. II, pages 609–627. Colloq. Math. Soc. János Bolyai,
Vol. 10. North-Holland, Amsterdam, 1975.
[Erd63] P. Erdős. On a combinatorial problem. Nordisk Mat. Tidskr., 11:5–10, 40, 1963.
[Erd64] P. Erdős. On a combinatorial problem. II. Acta Math. Acad. Sci. Hungar, 15:445–447,
1964.
[Geb13] Heidi Gebauer. On the construction of 3-chromatic hypergraphs with few edges. J. Combin. Theory Ser. A, 120(7):1483–1490, 2013.
[Lov73] L. Lovász. Coverings and coloring of hypergraphs. In Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic
Univ., Boca Raton, Fla., 1973), pages 3–12. Utilitas Math., Winnipeg, Man., 1973.
[RS00] Jaikumar Radhakrishnan and Aravind Srinivasan. Improved bounds and algorithms for
hypergraph 2-coloring. Random Structures Algorithms, 16(1):4–32, 2000.
[Sha15] Dmitry A. Shabanov. Around Erdős-Lovász problem on colorings of non-uniform hypergraphs. Discrete Math., 338(11):1976–1981, 2015.
Theoretical Computer Science Department, Faculty of Mathematics and Computer
Science, Jagiellonian University, Kraków, Poland
E-mail address: {Lech.Duraj, Grzegorz.Gutowski, Jakub.Kozik}@uj.edu.pl

