Math 1050 : Combinatorics : Homework

Homework 1 -- assigned on Sept 9 -- due Sept 16
1. Section 2.9: Problem 2

2. Section 2.9: Problem 16 (a) and (e)

3. Show that the number of ways to choose a committee with a chair person (for the committee) from a group of $n$ people is equal to: $n 2^{n-1}$ (the size of the committee can be any number from $1$ to $n$).
$~~$ Also, use another way of counting to show that the same number is equal to: $\sum_{k=1}^n k {n \choose k}.$
$~~$ [Hint: To obtain the second formula, pick the committee of size $k$ and then pick a chair in the committee.]

4. Section 2.9: Problem 11
Homework 2 -- assigned on Sept 16 -- due Sept 23
1. Section 2.9: Problem 24

2. Section 2.9: Problem 30
$~~$ [Hint: The answer is in terms of multinomial numbers.]

3. Section 2.9: Problem 32

4. Section 2.9: Problem 33

5. Section 3.11: Problem 2

6. (Bonus problem) As in Example 3.1 consider a collection of $n$ (distinct) lines in the plane such that:
$~~~~~~~~~~~$ (a) any two of them intersect; $~~~$ (b) no three of them pass through the same point.
$~~$ Show that the regions in the plane created by these lines can be colored with two colors B and W such that no two neighboring regions have the same color.
$~~$ We say that two regions are neighboring if they have a line or line segment in common.
$~~$ [Hint: do this recursively.]
Homework 3 -- assigned on Sept 23 -- due Sept 30
1. Section 3.11: Problem 4

2. Section 3.11: Problem 16

3. Section 3.11: Problem 18

4. Section 4.6: Problem 1 (e), (g)

5. (Bonus problem) Section 3.11: Problem 20
Homework 4 -- assigned on Sept 30 -- due Oct 7
1. Section 5.9: Problem 2

2. Section 5.9: Problem 7

3. Section 5.9: Problem 8

4. Section 5.9: Problem 10

5. Section 5.9: Problem 12
$~~$ [Hint: use Theorem 5.5 about Hamiltonian graphs.]
Homework 5 -- assigned on Oct 16 -- due Oct 23
1. Section 5.9: Problem 14

2. Section 5.9: Problem 30

3. Section 5.9: Problem 38

4. Section 5.9: Problem 40

5. Prove that the chromatic number of a tree $T$ (with more than one vertex) is $2$.
Homework 6 -- assigned on Oct 24 -- due Oct 30
1. Section 7.7: Problem 4

2. Section 7.7: Problem 6

3. Section 7.7: Problem 16

4. Section 7.7: Problem 20

5. (Bonus problem) Section 7.7: Problem 22 (a)
Homework 7 -- assigned on Oct 30 -- due Nov 6
1. Section 8.8: Problem 2 (f) and (l)

2. Section 8.8: Problem 4 (b) and (e)

3. Section 8.8: Problem 5

4. Let $a_n$ be the number of ways that a number $n$ can be written as a sum of integers: $n = x_1 + x_2 + x_3 + x_4$, where $x_1 \geq 0, ~x_2 \geq 0, ~ x_3 \geq 1$ and $0 \leq x_4 \leq 1$.
$~~$ Write the generating function for $(a_n)$ in closed form. Find a formula for $a_n$ in terms of $n$.

5. Let $(b_i)$ be the sequence defined recursively by: $b_{i+2} = b_{i+1} + 2b_i$ and $b_0 = 1,~ b_1 = 1$.
$~~$ Find the generating function for this sequence.
Homework 8 -- assigned on Nov 9 -- due Nov 16

1. (a) In the proof of Ramsey's theorem, we in fact showed that: $R(m, n) < R(m-1, n) + R(m, n-1)$.
$~~$ Using this inequality and material/examples discussed in class, show that $R(3, 4)$ is at most 9.

$~~$ (b) (Bonus problem) To show that $R(3, 4)$ is exactly 9 we need show that $R(3, 4) > 8$.
$~~$ To do this, we need to color the edges of the complete graph $K_8$ by two colors Red and Blue such that, there is no Red triangle and there is no $K_4$ subgraph which is Blue.
$~~$ Can you find such a coloring of edges of $K_8$?
$~~~~~~$ [Hint: the graph of Red edges is an $8$-gon with all its main diagonals, i.e. connect each vertex by Red to vertices before and after it as well as the vertex exactly opposite to it.]

2. One can define Ramsey numbers for more than two colors.
$~~$ The Ramsey number $R(n_1, ..., n_s)$ is the smallest number $r>0$ such that if we color the edges of a complete graph $K_r$ with $s$ colors $C_1, \ldots, C_s$ then there exists:
$~~~~$ * $~$ either a complete subgraph $K_{n_1}$ colored $C_1$,
$~~~~$ * $~$ or a complete subgraph $K_{n_2}$ colored $C_2$,
$~~~~$ * $~$ or ...
$~~~~$ * $~$ or a complete subgroup $K_{n_s}$ colored $C_s$.
$~~$ The generalized Ramsey theorem says that for any integers $n_1, \ldots, n_s$ such a number $r = R(n_1, ..., n_s)$ exists.

$~~$ Use the generalized Ramsey theorem to prove the following:
$~~$ For any $s \geq 2$, there is $r > 3$ such that for any coloring of the numbers $1,2,\ldots,r$ with $s$ colors, there are three integers $1 \leq x, y, z \leq r$ of the same color such that $x + y = z$.

$~~$ [Hint: let $n$ be the Ramsey number $R(3, 3, \ldots , 3)$ where $3$ is repeated $s$ times.
$~~$ Recall that $r = R(3,3,\ldots,3)$ has the property that if the edges of a complete graph $K_r$ are colored with $s$ colors then there is a triangle in $K_r$ all whose edges have the same color.
$~~$ Color the edges $(i, j)$ of $K_r$ as follows: assume $j>i$ then color the edge by the color $j-i$.]
Homework 9 -- assigned on Nov 20 -- due Nov 30

1. Section 12.6: Problem 10: Prove that if no two weights are equal in a weighted simple graph, then there is a unique minimum weight spanning tree.

2. Section 12.6: Problem 11

3. Section 13.7: Problem 2
Homework 10 -- assigned on Dec 4 -- due Dec 11

The three last problems of the semester