### x n-1

```Colorings of graphs and
Ramsey’s theorem
•A proper coloring of a graph G is a function from the vertices
to a set C of colors such that the ends of every edge have
distinct colors. If |C|=k, then we say G is k-colored.
•The Chromatic number (G) of a graph G is the minimal number
of colors such that G is colorable.
If (G) = 2, then G is a bipartite graph, which has no odd cycle.
• “Four Color Theorem” (Appel and Haken, 1977) states that if
G is planar, then (G) ≤
 4.
Applications of graph coloring:




Scheduling Final Exams: How can the final exams at
a university be scheduled so that no student has two
exams at the same time?
Frequency Assignments: Suppose no two TV stations
can operate within 220km on the same channel.
How can the assignment of channels be modeled by
graph coloring?
Index Register: In efficient compilers the execution
of loops is speeded up when frequently used
variables are stored temporarily in index registers in
the CPU, instead of regular memory. For a given
loop, how many index registers are needed?
........
p2.
Thm 3.1.(Brooks’s Theorem) Let d  3 and let G be a graph where all
vertices have degree ≤ d such that Kd+1 is not a subgraph of G.
Then (G) ≤ d.
Pf: We prove by contradiction and with the re-coloring technique.
Let G be a counterexample with the minimum number of vertices. Let
x be a vertex with neighbors x1,…, xl, l 
≤ d. Let H= G – {x}. Then
H has a d-coloring, since G is a minimal graph without d-coloring.
Let 1,…, d be the colors. If one of the colors is not used in x’s
neighbors, then we’re done. Why? Thus l=d and assume xi has
color i.
Let Hij be a subgraph of H with colors i and j.
xi and xj must be in the same connected component of Hij (say Cij).
Why?
p3.
Can the first i have 2 neighbors with j?
H=G-{x}
1
1
2
2
<= d-2
l l<=d?
d
x
i
i
j
j
i
j
j
i Is it possible?
p4.
j
k
i
i
k
k
j
i
Moreover, the component is a simple path from xi to xj in
Hij. Since if 2 neighbors of xi in H had the same color j,
then the other neighbors of xi in H would have at most
d-2 different colors. Then we could recolor xi, which is
impossible. Why?
Suppose y is the first vertex on the path from xi to xj in
Cij with deg  3. Then the neighbors of y in H use at
most d-2 colors, so we can recolor y such that xi and xj
are not connected in Hij, which is impossible. Why?
Thus no such y exists and Cij is a path.
Suppose z is in Cij and Cik but it is not xi. Then z has two
neighbors with color j and two with color k. Again the
neighbor of z in H use at most d-2 colors. Re-coloring z,
we have another contradiction. So Cij  Cik ={xi}.
p5.
By the assumption that G has no Kd+1 as subgraph,
there are 2 neighbors of x, say x1 and x2, that are
not adjacent. Let a be the neighbor of x1 with color
2. Interchange the colors
1 and 3 on C13. Thus a is in
x1 C13
C’23 and is also in C’12.
x3
Thus C’12  C’23  {x2}.
a
x
C23
C12
x2
p6.
Proof 2 of Brooks Theorem:


Problem 3A: Fix d≥ 3. Let H be a simple graph with all
degree ≤ d which cannot be d-colored and which is
minimal subject to these properties. (1) Show that H is
connected after deleting a vertex. (2) Then show that if
partition V(H) into sets X and Y with |Y| ≥ 3, then there
are at least 3 vertices a, b, c in Y each of which is
adjacent to at least one vertex in X.
Proof 2: Let d and H as in Problem 3A. If H is not
complete, there are vertices x1,xn-1,xn so that x1 is
adjacent to xn-1 and xn but the last two are not adjacent.
x1
xn-1
xn
Number the rest n-3 vertices such that each xk, k>1
is adjacent to at least one of xi with i< k.
I.e. when x1,...,xk have been chosen k< n-2, choose
xk+1 to be any vertex other than xn-1 or xn
adjacent to one of x1,..xk. Why possible?
p7.
Proof 2 of Brooks Theorem:

Once the above is done, d-color the vertices starting
at the end of the sequence– assigning xn and xn-1 the
same color.
x1
x2
xk
xk+1
xn-1
xn
Inductively and finally, there is one color available
If x ,..., xn have been colored properly, then xk
for x1. Why?k+1
connects to at most d-1 of them.
p8.
Thm 3.2. If the edges of Kn are colored red or blue, and ri,
i=1,…, n, denotes the number of red edges with vertex i
as an endpoint, and if T is the number of monochromatic
triangles, then
n 1 n

T=

r ( n  1  r ).
 
3 
Pf:

2
i
i 1
i
..
ri red edges
Corollary:
n
T  
3 
n

2
 n 1 2 
( 2 )   .


i
Ramsey number N( p, q; 2):至少需要幾人，其中才會有
p個人彼此都認識或有q個人彼此都不認識?
N( 3, 2; 2) =3.
N( 3, 3; 2) =6. Why?
Ramsey number N( p, q; 2):至少需要幾人，其中才會有
p個人彼此都認識或有q個人彼此都不認識?
Claim: N(p,q;2) ≤ N(p-1,q; 2) + N(p,q-1; 2).
Proof:
•Let n = N(p-1,q; 2) + N(p,q-1; 2). Consider a graph
with n vertices and v be one of the vertices.
•Color the edges of the graph with red and blue colors
By induction the red neighbors has p vertices with
in an arbitrary way.
blue edges only or q-1 vertices with red edges only.
Red neighbors >= N(p,q-1;2).
v
or
Similarly, by induction, the blue neighbors has p-1 vertices
with blue edges only or q vertices with red edges only.
Blue neighbors >= N(p-1,q;2).
Ramsey number N( p, q; 2):至少需要幾人，其中才會有p個人

•By observing the binomial coefficients C(n,k), we know
C(n,k)= C(n-1,k) + C(n-1, k-1).
•By the claim, we have N(p,q;2) ≤ N(p-1,q; 2) + N(p,q-1; 2).
•We prove Thm 3.4. N(p,q;2)
≤
C(p+q-2, q-1). By induction,
assume N(p-1,q; 2)
≤
C(p+q-3, q-1) and
N(p,q-1; 2)
≤
C(p+q-3, q-2).
•Then N(p,q;2) ≤ N(p-1,q; 2) + N(p,q-1; 2)
≤
C(p+q-3, q-1) + C(p+q-3, q-2)
= C(p+q-2, q-1)
What is the value of N(p,q:2) in general?
N(3,4;2) ≤ 9, by Thm 3.4 and Problem 3C.
To show the equality holds, we find a coloring on K8
0
without red K3 and blue K4.
7
• Similarly, we have (Problem 3D)
N(4,4;2)=18, N(3,5;2)=14.
6
2
3
5
• With a lot more work, it is known that:
N(3,6;2)=18, N(3,7;2)=23, N(3,8; 2)=28
N(3,9;2)=36, N(4,5;2)=25. There is no other
larger N(p,q;2) value known!
1
4
"Imagine an alien force, vastly more
powerful than us landing on Earth
and demanding the value of
N(5, 5;2) or they will destroy our
planet. In that case, we should
marshal all our computers and all
our mathematicians and attempt
to find the value. But suppose,
N(6, 6;2), we should attempt to
destroy the aliens".
- Paul Erdős
p14.
p, 1 2
q
3
4
5
6
7
8
9
10

1
1 1
1
1
1
1
1
1
1
1
2
1 2
3
4
5
6
7
8
9
10
3
1 3
6
9
14
18
23
28
36
40–43
4
1 4
9
18
25
35–41
49–61
56–84
73–115
92–149
5
1 5
14
25
43–49
58–87
80–143
101–216
125–316
143–442
6
1 6
18
35–41
58–87
102–165
113–298
127–495
169–780
179–1171
7
1 7
23
49–61
80–143
113–298
205–540
216–
1031
233–1713
289–2826
8
1 8
28
56–84
101–
216
127–495
216–
1031
282–
1870
317–3583
≤ 6090
9
1 9
36
73–
115
125–
316
169–780
233–
1713
317–
3583
565–6588
580–
12677
1
0
1 1
0
40–
43
92–
149
143–
442
179–1171 289–
2826
≤ 6090
580–12677 798–
23556
p15.
By Thm 3.4 we know N(p,p:2) ≤ 22p-2.
Thm3.5. N(p,p;2)  2p/2.
Kp
Pf: Randomly color a Kn. There are 2 C(n,2) different ways of
coloring the edges blue or red.
C(n,2)-C(p,2)+1 colorings for which
 Fix a subgraph Kp. There are 2
Kp is monochromatic.
C(n,2)-C(p,2)+1 colorings that some K
 There are at most C(n, p) 2
p
is monochromatic. If this number is less than the total number
of colorings, then there exist colorings with no monochromatic
Kp.
p
p/2, then
 Since C(n,p) < n /p!, if n< 2
C(n, p) 2 C(n,2)-C(p,2)+1 < 2C(n,2) .
-C(p,2)+1< (np/p!) 2-C(p,2)+1
 Because C(n, p) 2
< (2p*p/p!) 2-C(p,2)+1 < 1.
Thm 3.6. (Lovász Local lemma) Let G be some dependency
graph for the events A1,…, An. Suppose that Pr[Ai] ≤ p,
i=1,…,n and that every vertex of G has degree ≤ d. If 4dp <
1, then
A i  0.
Pf: First show that for every subset {i 1 , ..., i m },
P r[A i1 | A i 2 ...A i m ] 
1
2d
. For convenience take i j = j.
It is trivial for m = 1 and for m = 2 w e have:
P r[A 1 | A 2 ] 
p
1-p

1 / 4d
1  1 / 4d

1
4d  1

1
.
2d
p17.
P r[A 2 ...A q | A q+ 1 ...A m ]  1  P r[A 2  ...  A q | A q+ 1 ...A m ]
W e proceed by induc tion
on m .
q
 1  toP2,3,...,
r[A i | Aqq+ 1only.
...A m ]  1 
i= 2
W e have P r[A 1 | A 2 ...A m ] 
P r[A 1 ...A n ] 
P r[A 1 ]
1

q 1
 1 / 2.
2d
P r[A 1 A 2 ...A q | A q+ 1 .. .A m ]
.
P r1[A
...A1 ...A
P r[A
A 2 2A...A
+ 1r[A
m ] n]
3 ] q | A qP

 ... 
P r[A 1 ]
P r[A 1 A 2 ]
P r [ A 1 ...A n-1 ] 1
P r[A 1 A 2 ]
T he num erat or is at m ost P r[A 1 | A q+ 1 . ..A m ]  P r[A 1 ] 
.
 P r[A 1 ]  P r[A 2 | A 1 ]  P r[A 3 | A 1 A 2 ]  ...  P r[ A n | A 14d
...A n-1 ]
B y i nduction hypothesis, the denom inator is at least
q
1-  P r[A i | A q+ 1 ...A m ]  1 
i= 2
q 1
 1 / 2.
2d
T hus w e p rove the claim .
n
N ow P r[A 1 ...A n ] 

i= 1
P r[A i | A 1 ...A i-1 ]  (1 
1
2d
)  0.
n
Thm 3.7. N(p,p;2)c p 2p/2, where c is a constant.
Pf. Consider Kn and color the edges randomly.
 For any set S of k vertices let AS be the event that the
subgraph on S is monochromatic. Pr[ AS ] = 21-C(k,2).
 Let T be another k-set. AS and AT are dependent iff |S 
T|  2, i.e. the subgraphs on S and T share at least one
common edge.
 The degree d is at most C(k,2) C(n, k-2).
1-C(k,2)C(k,2)C(n, k-2)<1, then none of A will
 If 4 2
S
happen.
k/2.
 By some calculation, we have n < c k 2
This means we will need larger n to have any AS
happen. Let k=p. we prove the Thm. □
p19.
F. R. Ramsey (1902-1928) a logician
Thm 3.3. (Ramsey’s theorem 1930) Let r  1 and qi  r,
i=1,2,…,s be given. There exists a minimal positive
number N(q1,…,qs; r) such that:
 Let S be a set with n elements.
 Suppose that all C(n,r) r-subsets of S are divided into s
mutually exclusive families T1,…, Ts (colors).
 Then if n  N(q1,…,qs; r) there is an i  [s] and some
qi-subset of S for which every r-subset of these qi is in
Ti.
We will show the case when s=2.
(a) N(p,q;1)= p+q-1, Why?
(b) N( p, r; r)=p and N( r, q; r)=q, for p, q  r.
p20.
Proof of Thm 3.3.
By induction on r, we assume it is true for up to r-1.
Use induction on p+q, using (b).
Define p1=N( p-1, q; r) and q1=N( p, q-1; r).

Let S be a set with n elements, where
n  1+ N(p1, q1; r-1).

Let the r-subsets of S be colored with red and blue colors.
Let a be an arbitrary element of S and S’=S-{a}.

Define a coloring of the (r-1)-subsets of S’ by giving any (r1)-subset X  S’ the same color as X  {a}.

By ind hyp, S’ either has a subset A of size p1 such that all its
(r-1)-subsets are red or a subset B of size q1 with all its (r-1)subsets colored blue. WLOG, suppose the first case happens.
Then A has N(p-1, q;r) elements.
p21.
A has N(p-1, q; r) elements. There are two possibilities.
(1) A has a subset of q elements with all its r-subsets blue, in
which we are done.
(2) A has a subset A’ of size p-1 with all its r-subsets red.
The set A’  {a} also has this property, since A’  A. This
proves the theorem and we have:
N(p, q; r) ≤ N( p1, q1; r-1) +1
= N( N(p-1, q; r) , N(p, q-1; r) ; r-1) +1.
□
Taking r=2, we can obtain
N(p, q; 2) ≤ N(p-1, q; 2) + N(p, q-1; 2).

N(p, q; r) ≤ N( N(p-1, q; r), N(p, q-1; r); r-1) +1.
r-1
N(p-1, q; r) elements.
a
r-1

N(p,q-1;r) elements.
N(p, q; 2) ≤ N(p-1, q; 2) + N(p, q-1; 2).
p-1
q-1
Problem 3C: The equality cannot hold, if
the right hand side are both even.
q
p
deg=N(p-1,q;2)+N(p,q-1;2)-1
p23.
An application of Ramsey’s Theorem

Theorem 3.8: For a given n, there is an integer N(n) such that
any collection of N> N(n) points in the plane, no three on a line,
has a subset of n points forming a convex n-gon.
Proof: (1) 觀察平面上n個點，其中任何三點不共線。這n點

(2)令N(n)=N(n,n;3) 。然後將這N(n)個點由1

2
1
7
3
1
5
p24.




b

c
d

a

p25.
```