Solutions

Probabilistic Method in Combinatorics
Instructor: Benny Sudakov
Solutions to assignment 3
Problem 1: Let G = (V, E) be a simple graph, and suppose each v ∈ V is associated with
a list S(v) of colours of size at least 10d, where d ≥ 1. Suppose further that for each v ∈ V
and c ∈ S(v), there are at most d neighbours u of v such that c ∈ S(u). Prove that there is a
proper colouring of G assigning each vertex v a colour from its list S(v).
Solution: Note that the condition given to us is a local condition, as we have a bound on the
number of times a colour in S(v) can appear in the lists of neighbours of v. This suggests that
we should colour the vertices at random and try to apply the Local Lemma.
We will choose for each vertex a colour from its list, and hope to find a proper colouring of
the graph. The events we wish to avoid, then, are having edges with both endpoints receiving
the same colour. Note that this can only happen for the edge e = {u, v} if there is some colour
c ∈ S(u) ∩ S(v). Let us denote by E{u,v},c , {u, v} ∈ E(G) and c ∈ S(u) ∩ S(v), the event that
the edge {u, v} has both its endpoints coloured c.
Note that E{u,v},c depends only on the colours assigned to u and v, and is thus independent
of E{u0 ,v0 },c0 if {u0 , v 0 } ∩ {u, v} = ∅. Hence E{u,v},c may only depend on other edges involving
u or v. Note that u has |S(u)| colours in its list S(u), each of which is shared by at most d
neighbouring vertices. Hence there are at most d |S(u)| events of the form E{u,v0 },c0 .
Without an upper bound on |S(u)|, this means the degrees in the dependency digraph are
unbounded, making it impossible to apply the symmetric version of the Local Lemma. While
we might try to use the asymmetric version, it is easier to bound the sets S(u), as we shall do
below.
For each vertex v, form a shorter list S 0 (v) ⊂ S(v) consisting of exactly 10d colours (which
may be chosen arbitrarily). When sampling a random colouring χ : V → ∪v S(v), choose for
each vertex v one of the 10d colours in S 0 (v). We define the events E{u,v},c as before, except that
we now require c ∈ S 0 (u) ∩ S 0 (v). By our above discussion, it follows that there are at most
d |S 0 (u)| = 10d2 events involving u, and at most 10d2 events involving v, and hence E{u,v},c is
independent of all but at most 20d2 − 2 other events (the 10d2 counted the event E{u,v},c itself).
Moreover, note that P(E{u,v},c ) = P(χ(u) = χ(v) = c) = P(χ(u) = c)P(χ(v) = c) =
(1/10d)2 = 1/100d2 . Since e · (1/100d2 ) · (20d2 − 1) < 1, it follows from the symmetric version
of the Local Lemma that P ∩E{u,v},c > 0, and hence a proper list-colouring exists.
1
Problem 2: A simple path of even length P = v1 v2 . . . v2k in a graph G = (V, E) with a vertex
colouring f : V → [r] is periodic if f (vj ) = f (vj+k ) for all j, 1 ≤ j ≤ k. Prove that there is a
constant r such that every graph G with maximum degree 5 admits a vertex colouring with r
colours in which no path of even length is periodic.
Solution: We sample a uniformly random colouring χ : V → [r], where r will be chosen
later. For every even path P , we have the event EP that P is periodically coloured; that is, if
P = v1 v2 . . . v2k , then χ(vi+k ) = χ(vi ) for 1 ≤ i ≤ k. Note that we have P(EP ) = r−k , since the
colours of the last k vertices have to match those of the first k.
Note that EP is independent of the event EP 0 if P ∩P 0 = ∅, since they depend on independent
random variables. Thus EP only depends on the events corresponding to paths P 0 that meet
P . The number of such paths depends on the lengths of P and P 0 . Suppose P has 2k vertices.
We now bound the number of paths P 0 with 2` vertices that intersect P . First, we choose a
common vertex - there are at most 2k choices from the vertices in P . Next, we have to decide
which vertex in the path P 0 this is - there are 2` such possibilities. Finally, we have to choose
the remaining vertices in P 0 . Since G has maximum degree 5, there are 5 choices for the first
additional vertex, and then 4 choices for each of the remaining 2` − 2 vertices. Thus there are
at most 20k`42`−2 = 1.25k`16` paths P 0 of length 2` meeting P .
This term is unbounded (in fact, exponentially increasing in `), and so we cannot hope to
find a uniform bound on the degrees in the dependency digraph. However, the probabilities
of the events EP are also exponentially small, so we may hope to apply the asymmetric local
lemma. (Note that we must use the Local Lemma, and not just a union bound, since the number
of events (paths) grows with the number of vertices, while the probability is independent of n.)
Q
We thus seek real numbers xP such that P(EP ) ≤ xP P 0 ∼P (1 − xP 0 ). By symmetry, we
may assume that xP should only depend on the length of P . Moreover, since the other terms
are exponential, it makes sense to try xP = αk , where P is a path of length 2k.
We would then have
!k
∞
∞
∞
Y
Y
Y
Y
Y
`
`
1.25k`16
xP
(1 − xP 0 ) = αk
(1 − α` ) ≥ αk
1 − α`
= α (1 − α` )1.25`16
.
P 0 ∼P
`=1 |P 0 |=2`
P 0 ∩P 6=∅
l=1
`=1
(1)
Now `≥1 (1−α )
≥ 1−1.25 `≥1 `(16α) . If 16α < 1, then `≥1 `(16α) = 16α/(1−
Q
`
2
16α) < 0.4 for α = 0.01. Thus `≥1 (1 − α` )1.25`16 ≥ 0.5, and so the right-hand side of (1) is
at least 0.005k .
On the other hand, we have P(EP ) = r−k < 0.005k if r ≥ 200. Hence, by the Local Lemma,
with positive probability our random colouring produces a non-periodic colouring when r = 200,
and thus such a colouring exists.
Q
` 1.25`16`
`
P
2
P
`
Problem 3: Let G be a graph with m edges, and let S be a random set of vertices of G
obtained by picking each vertex independently with probability 1/2. Prove that the probability
that S is an independent set in G is at least (3/4)m .
Solution: For each edge e, let Ee be the event that e 6⊂ S. We have P(Ee ) = 1 − P(e ⊂ S) =
1 − (1/2)2 = 3/4. Note that Ee is monotone decreasing with respect to S, as if S 0 ⊂ S and
e 6⊂ S, then e 6⊂ S 0 . Hence these events are positively correlated, and so we have
Y
P(S is independent ) = P(∩e Ee ) ≥
P(Ee ) = (3/4)m .
e
Problem 4: Show that the probability of the random graph G(2k, 1/2) having maximum
degree at most k − 1 is at least 1/4k .
Solution:
For a vertex v, let Ev be the event that the degree of v is at most k − 1. Note that the
degree of v is distributed as Bin(2k − 1, 1/2), and so
X 2k − 1
1−2k
P(Ev ) = P(Bin(2k − 1, 1/2) ≤ k − 1) = 2
= 1/2.
i
i≤k−1
Now the events Ev are monotone decreasing in the edge-set E = E(G(2k, 1/2)), as if
degE (v) ≤ k − 1, and E 0 ⊂ E, then degE 0 (v) ≤ degE (v) ≤ k − 1. Thus the events Ev are
positively correlated, and
Y
P(∆(G(2k, 1/2)) ≤ k − 1) = P(∩v Ev ) ≥
P(Ev ) = (1/2)2k = 1/4k .
v
Problem 5: A family of subsets F is called intersecting if F1 ∩ F2 6= ∅ for all F1 , F2 ∈ F. Let
F1 , F2 , . . . , Fk be k intersecting families of subsets of {1, 2, . . . , n}. Prove that
k
∪i=1 Fi ≤ 2n − 2n−k .
Is this bound best possible?
Solution: Without loss of generality, we may assume that each intersecting family Fi is an
up-set; that is, if F ∈ Fi and F ⊂ F 0 , then F 0 ∈ Fi (clearly Fi remains an intersecting family).
We also know that |Fi | ≤ 2n−1 .
By taking complements, we wish to show ∩ki=1 Fic ≥ 2n−k . This is equivalent to showing
that for a uniformly random subset F ⊂ [n], P(F ∈ ∩ki=1 Fic ) = P(∩ki=1 Ei ) ≥ 2−k , where
Ei = {F ∈ Fic }.
3
We have P(Ei ) = |Fic | /2n = 1 − |Fi | /2n ≥ 1/2.
Note that if Fi is an up-set, then Fic is a down-set (so if F ∈ Fic and F 0 ⊂ F then F 0 ∈ Fic ).
Hence it follows that Ei is monotone decreasing in F for each i, and so the events Ei are positively
correlated. Thus
k
Y
k
P(∩i=1 Ei ) ≥
P(Ei ) ≥ 1/2k ,
i=1
as desired.
This bound is tight. Let Fi = {F ⊂ [n] : i ∈ F }. Then ∪ki=1 Fi = {F : F ∩ [i] 6= ∅}, and
k
∪i=1 Fi = 2n − 2n−k .
Problem 6: Given a set family F = {F1 , F2 , . . . , Fm } of subsets of [n], we ‘colour’ the elements
P
of [n] by a map χ : [n] → {−1, +1}. For a set Fi , define χ(Fi ) = j∈Fi χ(j). We then define
the discrepancy of the colouring χ as disc(F, χ) = maxi |χ(Fi )|, and the overall discrepancy of
F as the smallest possible discrepancy:
disc(F) = min disc(F, χ).
χ
p
(a) Show the random colouring gives the bound disc(F) ≤ 2n ln(2m).
p
(b) For n even, improve the bound to disc(F) ≤ n ln(2m) by coupling the colours of the
vertices, so that χ i + n2 = −χ(i).
(c) Can you improve the bound further?
[Hint: sriap modnar otni secitrev eht elpuoc ,gniruoloc nehW]
P
Solution: In what follows, let Sn = ni=1 Xi , where Xi is uniformly distributed over {−1, +1}.
2
By our Chernoff bounds, we have P(|Sn | > a) < 2e−a /(2n) .
p
(a) Let Ei = {|χ(Fi )| > 2n ln(2m)}. Since χ(Fi ) ∼ S|Fi | , it follows that
P(Ei ) < 2e−2n ln(2m)/(2|Fi |) ≤ 2e− ln(2m) = 1/m.
We now apply a union bound to obtain
X
p
P disc(F, χ) > 2n ln(2m) = P(∪i Ei ) ≤
P(Ei ) < 1,
i
p
and there exists some colouring χ with disc(F, χ) ≤ 2n ln(2m). This gives the desired upper
bound on disc(F) ≤ disc(F, χ).
(b) We have now paired the vertices so that they come with opposite colours. Note that if
a set Fi contains some pair {j, j + n/2}, then those terms cancel out, so that pair contributes
4
nothing to χ(Fi ). Let U (Fi ) ⊂ Fi be the unpaired elements in Fi , and let u(Fi ) = |U (Fi )|. Note
that we have u(Fi ) ≤ n/2, χ(Fi ) = χ(U (Fi )), and χ(U (Fi )) ∼ Su(Fi ) .
p
Let Ei = {|χ(Fi )| > n ln(2m)}. By the Chernoff bounds, we have
p
P(Ei ) = P Su(Fi ) > n ln(2m) < 2e−n ln(2m)/(2u(Fi )) ≤ 2e− ln(2m) = 1/m,
p
and thus the union bound again gives P disc(F, χ) > n ln(2m) < 1. Hence we have
p
disc(F) ≤ n ln(2m), as required.
(c) [Left open for now.]
5

Download Report