Topics in Combinatorics

(1)

CS 207: Discrete Structures

Lecture 12 – Counting and Combinatorics Pigeon-Hole Principle and its extensions

Feb 21 2018

(2)

Topics in Combinatorics

Basic counting techniques and applications 1. Basic counting techniques, double counting

2. Binomial theorem, permutations and combinations, Estimatingn!

3. Recurrence relations and generating functions

4. Principle of Inclusion-Exclusion (PIE) and its applications.

I Counting the number of surjections on [n].

I Combinatorial proof of PIE

I Number of derangements−>¹_e.

(3)

Topics in Combinatorics

Basic counting techniques and applications 1. Basic counting techniques, double counting

2. Binomial theorem, permutations and combinations, Estimatingn!

3. Recurrence relations and generating functions

4. Principle of Inclusion-Exclusion (PIE) and its applications.

I Counting the number of surjections on [n].

I Combinatorial proof of PIE

I Number of derangements−>¹_e.

(4)

Last lecture

Theorem: Principle of Inclusion-Exclusion (PIE) LetA₁, A₂, . . . , A_n be finite sets. Then,

|A₁∪. . .∪An|= X

1≤i≤n

|A_i| − X

1≤i<j≤n

|A_i∩Aj|

+ X

1≤i<j<k≤n

|A_i∩Aj ∩Ak| −. . .+ (−1)ⁿ⁺¹|A₁∩. . .∩An|

(5)

This lecture

Pigeon-Hole Principle (PHP) and its applications

A simple formulation

Letk∈N. Ifk+ 1 (or more) objects are to be placed ink boxes, then at least one box will have 2 (or more) objects. A simple corollary

I Can a function from a set of k+ 1 or more elements to a set with k elements be injective?

(6)

This lecture

Pigeon-Hole Principle (PHP) and its applications A simple formulation

Letk∈N. Ifk+ 1 (or more) objects are to be placed ink boxes, then at least one box will have 2 (or more) objects.

A simple corollary

(7)

This lecture

Pigeon-Hole Principle (PHP) and its applications A simple formulation

Letk∈N. Ifk+ 1 (or more) objects are to be placed ink boxes, then at least one box will have 2 (or more) objects.

A simple corollary

(8)

Pigeon-Hole Principle (PHP)

Another simple application

For everyn∈Z⁺, there exists a multiple of nwhich can be written with only 0⁰s and 1⁰s(in decimal).

I Consider n+ 1 integers k₁ = 1,k₂= 11, k₃= 111, . . . , k_n+1= 1. . .1 (withn+ 1 1’s).

I When any integer is divided by n, the remainder can be either 0,1, . . . , n−1, i.e.,nchoices.

I So among the n+ 1 integers, by PHP, at least 2 must have the same remainder.

I That is, ∃i, j,k_i =pn+d,k_j =qn+d.

I But then |k_i−k_j|is a multiple of nand (its decimal expansion) only has 0⁰sand 1⁰s.

(9)

Pigeon-Hole Principle (PHP)

I Consider n+ 1 integers k₁ = 1,k₂= 11, k₃= 111, . . . , k_n+1 = 1. . .1 (withn+ 1 1’s).

I When any integer is divided by n, the remainder can be either 0,1, . . . , n−1, i.e.,nchoices.

(10)

Pigeon-Hole Principle (PHP)

I When any integer is divided by n, the remainder can be either 0,1, . . . , n−1, i.e., nchoices.

(11)

Pigeon-Hole Principle (PHP)

(12)

Pigeon-Hole Principle (PHP)

I That is, ∃i, j,ki =pn+d,kj =qn+d.

(13)

A (slightly) more general PHP

Pigeon-Hole Principle (Variant 1)

IfN objects are placed into kboxes then there is at least one box with at leastdN/ke objects.

Suppose not. Then each box has strictly less thanbN/kc objects. Therefore, totally there can be strictly less thanN objects, which is a contradiction.

A simple example

How many cardsmust be selected from a pack of 52 cards so that at least three cards of the same suit are chosen?

I 4 boxes, one for each suit; each selected card is put in one.

I IfN cards are selected then at least 1 box hasdN/4e cards.

I To have ≥3 cards from same suit, suffices dN/4e ≥3.

I Thus,N = 9. But can we do better? No.

(14)

A (slightly) more general PHP

A simple example

(15)

A (slightly) more general PHP

A simple example

(16)

A (slightly) more general PHP

A simple example

(17)

A (slightly) more general PHP

A simple example

I IfN cards are selected then at least 1 box has dN/4e cards.

(18)

A (slightly) more general PHP

A simple example

(19)

A (slightly) more general PHP

A simple example

I Thus,N = 9.

But can we do better? No.

(20)

A (slightly) more general PHP

A simple example

I Thus,N = 9. But can we do better?

No.

(21)

A (slightly) more general PHP

A simple example

(22)

Another application of PHP

Question: Give a sequence of 10 real numbers with no subsequence of length 4 which is increasing or decreasing.

Theorem

Every sequence ofn²+ 1 distinct real numbers contains a subsequence of lengthn+ 1 which is either increasing or decreasing.

1. Let a1, . . . , a_n²₊₁ be a sequence of distinct real numbers. 2. For eachk∈ {1. . . n²+ 1},let (i_k, d_k) denote a pair:

ik= length of longest increasing subsequence starting fromak

dk= length of longest decreasing subsequence starting fromak

3. Suppose, there are no increasing/decreasing subsequences of length n+ 1. Then∀k,i_k≤nand d_k ≤n.

4. ∴ by PHP,∃`, m,1≤` < m≤n²+ 1 s.t. (i`, d`) = (im, dm) 5. We will show that this is not possible:

I Case 1: a_`< a_m. Theni_`≥i_m+ 1, a contradiction.

I Case 2: a_`> a_m. Thend_`≥d_m+ 1, a contradiction. 6. All ai’s are distinct so this completes the proof.

(23)

Another application of PHP

Question: Give a sequence of 10 real numbers with no subsequence of length 4 which is increasing or decreasing.

Theorem

1. Let a1, . . . , a_n²₊₁ be a sequence of distinct real numbers. 2. For eachk∈ {1. . . n²+ 1},let (i_k, d_k) denote a pair:

ik= length of longest increasing subsequence starting fromak

dk= length of longest decreasing subsequence starting fromak

4. ∴ by PHP,∃`, m,1≤` < m≤n²+ 1 s.t. (i`, d`) = (im, dm) 5. We will show that this is not possible:

(24)

Another application of PHP

Theorem

1. Let a1, . . . , a_n²₊₁ be a sequence of distinct real numbers.

2. For eachk∈ {1. . . n²+ 1},let (ik, dk) denote a pair: i_k= length of longest increasing subsequence starting froma_k d_k= length of longest decreasing subsequence starting froma_k 3. Suppose, there are no increasing/decreasing subsequences

of length n+ 1. Then∀k,i_k≤nand d_k ≤n.

4. ∴ by PHP,∃`, m,1≤` < m≤n²+ 1 s.t. (i_`, d_`) = (i_m, d_m) 5. We will show that this is not possible:

(25)

Another application of PHP

Theorem

2. For eachk∈ {1. . . n²+ 1},let (ik, dk) denote a pair:

i_k= length of longest increasing subsequence starting froma_k d_k= length of longest decreasing subsequence starting froma_k

4. ∴ by PHP,∃`, m,1≤` < m≤n²+ 1 s.t. (i_`, d_`) = (i_m, d_m) 5. We will show that this is not possible:

(26)

Another application of PHP

Theorem

2. For eachk∈ {1. . . n²+ 1},let (ik, dk) denote a pair:

i_k= length of longest increasing subsequence starting froma_k d_k= length of longest decreasing subsequence starting froma_k 3. Suppose, there are no increasing/decreasing subsequences

of length n+ 1. Then∀k,i_k≤nand d_k ≤n.

4. ∴by PHP, ∃`, m,1≤` < m≤n²+ 1 s.t. (i_`, d_`) = (i_m, d_m) 5. We will show that this is not possible:

I Case 2: a_`> a_m. Thend_`≥d_m+ 1, a contradiction.

6. All ai’s are distinct so this completes the proof.

(27)

Another variant of PHP

Theorem (PHP Variant 2)

Suppose there aren≥1 +r(`−1) objects which are colored withr different colors. Then there exist `objects all with the same color.

Proof: (H.W)

I Is this coloring optimal?

I That is, if fewer than 1 +r(`−1) objects are given, is there a way of coloring them such that no `have the same color?

(28)

Another variant of PHP

Proof: (H.W)

(29)

Another variant of PHP

Proof: (H.W)

(30)

Another variant of PHP

Proof: (H.W)

I That is, if fewer than 1 +r(`−1) objects are given, is there a way of coloring them such that no` have the same color?

(31)

Back to the coloring game

The coloring game

I There are six points on board and two colored chalks.

I Divide class into 2 groups. Group 1 draws white lines and Group 2 draws blue lines between points.

I You lose if you are first to draw a triangle of your color.

I Can you ever have a draw?

We will now show that this is impossible. That is, Lemma

Any 2-coloring of edges of a graph on 6 nodes has a monochromatic triangle.

I 2-coloring of edges: coloring all edges of the graph using atmost 2 colors.

I monochromatic (triangle): all edges have the same color.

(32)

Back to the coloring game

The coloring game

(33)

Back to the coloring game

The coloring game

(34)

Back to the coloring game

The coloring game

(35)

Back to the coloring game

The coloring game

We will now show that this is impossible. That is,

Lemma

(36)

Back to the coloring game

The coloring game

(37)

Back to the coloring game

Lemma

Proof:

I Let 1, . . . ,6 be the points, and red/blue the colors.

I Consider the edges 16,26,36,46,56.

I By PHP at least 3 of them must be same color, say 16,26,36 are red.

I Now there are two possibilities:

I Either one of 12,23,31 is red (then we have a red triangle).

I Else none of them are red, implies 123 is a blue triangle.

I What if there were 5 or lesser nodes?

(38)

Back to the coloring game

Lemma

Proof:

(39)

Back to the coloring game

Lemma

Proof:

(40)

Back to the coloring game

Lemma

Proof:

(41)

Back to the coloring game

Lemma

Proof:

(42)

Back to the coloring game

Lemma

Proof:

(43)

Back to the coloring game

Lemma

Proof:

(44)

Another coloring problem...

Theorem

Any 2-coloring (say red and blue) of a graph on 10 nodes has either ared triangleor a blue complete graph on 4 nodes.

I complete: all pairs of edges are present.

I How do you prove this? Any ideas?

I How is this different from the previous problem?

(45)

Another coloring problem...

Theorem

Proof:

x a

b c

d

x a

b c

d e

f

I Consider all edges from some nodex.

I By PHP, either 4 edges have redcolor or6 have blue.

(46)

Another coloring problem...

Theorem

Proof:

x a

b c

d

I Case 1: 4 red edges

I Either one of edges betweena, b, c, dis red or all are blue.

So, we are done.

(47)

Another coloring problem...

Theorem

Proof:

x a

b c

d e

f

I Case 2: 6 blue edges

I But this means that there are 6 nodesa, . . . f.

(48)

Another coloring problem...

Theorem

Proof:

x a

b c

d e

f

I Any 2-coloring on 6 vertices has a red or blue triangle.

I Thus we are done again.

(49)

Another coloring problem...

Theorem

Proof:

x a

b c

d e

f

I Any 2-coloring on 6 vertices has a red or blue triangle.

I Thus we are done again.

I And this completes the proof.

(50)

Another coloring problem...

Thus, we have showed...

Theorem

I But, is this optimal?

I That is, does this fail for a graph on 9 nodes?

I Can you find 2-coloring on a graph of 9 nodes such that the statement above does NOT hold?

Answer: No! In fact, it does hold on 9 nodes! Theorem

Any 2-coloring (say red and blue) of a graph on9 nodes has either ared triangleor a blue complete graph on 4 nodes.

(51)

Another coloring problem...

Theorem

(52)

Another coloring problem...

Theorem

(53)

Another coloring problem...

Theorem

Answer: No! In fact, it does hold on 9 nodes!

Theorem

(54)

Another coloring problem...

Theorem

Answer: No! In fact, it does hold on 9 nodes!

Theorem

(55)

Yet another coloring problem...

Theorem

Proof:

I Try the same proof as above?

I The only new case, where the previous proof does not work, is if all nodes have 3 red edges and 5 blue edges. (Why?)

I But is this case possible?

I Recall the Handshake lemma!

I In any graph, the number of nodes having odd degree is even.

I Thus, this case is impossible and we are done.

(56)

Yet another coloring problem...

Theorem

Proof:

(57)

Yet another coloring problem...

Theorem

Proof:

(58)

Yet another coloring problem...

Theorem

Proof:

(59)

Yet another coloring problem...

Theorem

Proof:

(60)

Can we generalize the above?

In general,

How many nodes should a (complete) graph have so that any 2 coloring of its edges has

I either, a k-sized complete graph with all red edges

I or, a`-sized complete graph with all blue edges

I The minimal such number is denotedR(k, `) and is called Ramsey number.

I We have seen that R(3,3) = 6.

I Also R(3,4) = 9 (not quite...). What aboutR(k, `) in general?

(61)

Can we generalize the above?

In general,

I Also R(3,4) = 9 (not quite...). What aboutR(k, `) in general?

(62)

Can we generalize the above?

In general,

I Also R(3,4) =

9 (not quite...). What aboutR(k, `) in general?

(63)

Can we generalize the above?

In general,

I Also R(3,4) = 9 (not quite...).

What aboutR(k, `) in general?

(64)

Can we generalize the above?

In general,

I Also R(3,4) = 9 (not quite...).

What aboutR(k, `) in general?

(65)

Ramsey’s theorem

Figure:Frank Plumpton Ramsey (1903-1930)

Ramsey’s theorem (simplified version)

For anyk, `∈N, there existsR(k, `)∈Nsuch that any 2-coloring of a (complete) graph onR(k, `) nodes has

I or, a`-sized complete graph with all blue edges Moreover, we have

R(k, `)≤

k+`−2 k−1

(66)

Edge coloring problems

Summary of results till now

1. Any 2-coloring of a graph on 6 nodes has either ared triangleor a blue triangle.

I 6 is the optimal such number. Thus,R(3,3) = 6.

2. Any 2-coloring of a graph on 10 nodes has either ared triangleor a blue complete graph on 4 nodes.

I Is 9 the optimal such number? R(3,4)≤9.

I (H.W?)Prove thatR(3,4) = 9!

I (H.W) Prove that any 2-coloring of a graph on 18 nodes has a monochromatic complete graph on 4 nodes. (hint: you may use any of the above results)

(67)

Edge coloring problems

(68)

Edge coloring problems

(69)

Edge coloring problems

I (H.W) Prove that any 2-coloring of a graph on 18 nodes has a monochromatic complete graph on 4 nodes.

(hint: you may use any of the above results)