Before the first meeting, you should read up to the end of Section 1.2. Section 1.1 introduces basic terminology about partitions, and introduces the pigeon-hole principle, while Section 1.2 introduces basic terminology about graphs.
It is always good to have pen and paper to hand when reading a math book, so that you can work through examples, and verify for yourself claims made by the author. It is also very helpful to do frequent exercises. As you read Section 1.1, you should think about the following exercises, which we will discuss at the first meeting:
- (1) Exercise 1.4. This and the next two exercises are well-known, and you may have seen them before. As you work on them now, try to focus on solutions that make clear the utility of the pigeon-hole principle: identify clearly what your pigeon-holes are, what your pigeons are, and why the conclusion that there must be two pigeons in the same pigeon-hole solves the problem.
- (2) Related to Exercise 1.4: show that whenever \(n+1\) numbers are chosen from \(\{1,…,2n\}\), some two of them must be relatively prime (have no common factors).
- (3) Also related to Exercise 1.4: show that whenever \(n+1\) numbers are chosen from \(\{1,…,2n\}\), some two of them must have the property that one divides the other.
- (4) (Harder) Let \(m\) be an irrational number between \(0\) and \(1\). Let \(n\) be any natural number. Show that there is a rational number \(p/q\) with \(p, q\geq 1\), \(p < q\), and \(p\), \(q\) having no common factors, such that \(\left|m-\frac{p}{q}\right| \leq \frac{1}{qn}\). (Hint: Think about the numbers \(m, 2m, 3m, \ldots, (n+1)m\). These \(n+1\) irrational numbers each have a fractional part that is between \(0\) and \(1\), so some two of them must have fractional parts that are close to each other.)
- (5) (A cute application of (4)): An infinite orchard has trees arranged in a perfect square grid, with one tree at the center removed. Prove that no matter how thin the trees are, if you are standing at the center then no matter which direction you look, your view to infinity will be obstructed by a tree. (If this is a little vague, here’s a more precise formulation: A lattice point is a point in \({\mathbb R}^2\) with integer coordinates. Suppose that centered at every non-zero lattice point in \({\mathbb R}^2\), a disk of radius \(r\) is drawn. Show that no matter the value of \(r\), every ray through the origin eventually meets one of the discs.)
And as you read Section 1.2, you should think about the following exercises:
- (6) Exercise 1.8.
- (7) Show that if G is not connected, then its complement is connected.
- (8) Show that a graph is bipartite if and only if it has no odd-length cycles (this is surprisingly tricky).
- (9) Exercise 1.12.
- (10) Exercise 1.13.