Welcome to the MATH 100-COSC 49/149 Web Page

Math 100---COSC 49/149

Topics in Probability:
THE PROBABILISTIC METHOD in Mathematics and Computer Science

Instructor: Prof. Peter Winkler (peter.winkler at dartmouth.edu)

### News

Your FINAL EXAM will be graded by late Monday Nov 21. Email me to get your exam and course grades.

You can also "visit" your exam, and find out your course grade, on Monday between 4 and 6, Kemeny 229.

An exam score above 50 earns some kind of A, in the 40's a B, in the 30's a C, etc.

### Abstract

One of the great discoveries (attributed, in part, to Paul Erdos and Alfred Renyi) of 20th century mathematics was that probability could help understand and solve problems that seemed not to have any probabilistic content. We will explore this powerful method and apply it to problems in discrete mathematics and the theory of computing.

Example: Proving that a graph with property P exists by showing that a random graph will have property P with positive probability. Or: Estimating the fraction of graphs with property P by repeatedly running a Markov chain on graphs whose stationary distribution is uniform, then observing the fraction of the time that the chain lands on widgets with property P.

Prerequisites: Mathematical background of a senior mathematics major or a beginning graduate student in mathematics or theoretical computer science, including a course in probability (e.g., MATH 20 or Math 60). If in doubt, please see the instructor. Dist: QDS.

Here is a rough weekly compendium of what we covered.

1. The Probabilistic Method: showing that something exists because it has positive probability

2. Application to Ramsey theory

3. Application to Ulam's problem; Erdos-Szekeres theorem

4. Growth of functions, big O, little o; Mumbo-Jumbo

5. Applications to geometry, arithmetic progressions

6. Chebyshev's inequality; the second moment method; thresholds

7. The Lovasz Local Lemma, general and symmetric forms

8. Proof of Moser-Tardos' algorithmic Local Lemma

9. Turan's Theorem via Caro and Wei

### Classes

Room: Kemeny Hall 105
Lectures: "10" slot, in particular: Monday, Wednesday and Friday 10:10 - 11:15.
X-hour: Thursdays (same room) 12:15 pm - 1:05 pm. Will be used only when so announced in class.

### Staff

Instructor:
Peter Winkler -- Kemeny Hall 231
Office Hours: Tu 1:15 - 2:45; Th 10:15 - 11:45.

### Textbook

Noga Alon and Joel Spencer, The Probabilistic Method (4th edition), John Wiley & Sons, 2016.
NOTE: The 3rd edition is accessible online and should be adequate for the course.

Your grade will be based on homework, class participation, two hour exams, and the final exam. The hour exams will be given in class on Monday, Oct 3 and Monday, Oct 24; let me know immediately if you have any possible conflict. The final exam will be in the regular slot for MWF10 courses, namely, Friday Nov 18 at 8am.

### Exams

There may be unannounced in-class quizzes, just to make sure everyone is keeping up.

### Homework

Homework will be assigned at each class period, due at the beginning of the next class.

### Assignments

Due Wednesday Sept 14: Read Sections 1.1 and 1.2 of your text.

Due Friday Sept 16: Prove that R(j,k) is at most R(j-1,k) + R(j,k-1).

Due Monday Sept 19: Design (and draw) a tournament on 7 players in which any two players are beaten by a third.

Due Wednesday Sept 21: In using the probabilistic method to get a lower bound for R(3,4), you want to find as big as possible an n such that a random graph on n vertices with edge-probability p has (with positive probability) neither a clique of size 3 nor an anti-clique of size 4. What value of p should you use? Why?

Due Friday Sept 23: (1) Define the following statements: f(n) = O(e^n); f(n) = e^O(n); f(n) = (1+o(1))e^n; f(n) = e^((1+o(1))n); f(n) = e^(n^(1+o(1))). (2) Order these by strength (statement "A" is stronger than statement "B" if A implies B). (3) Which of the statements do we know to be true if f(n) is the Ramsey number R(n,n)?

Due Monday Sept 26: Read 2.1. Let X be the number of throws of a die you need to get all six numbers. Compute the expectation and variance of X.

Due Wednesday Sept 28: Read as far as you dare in Chapter 2, and do 2.7 Exercise 1 (top p. 23, 3rd ed.; p. 27, 4th). That is: Let H=(V,E) be a k-uniform hypergraph with 4^{k-1} edges. Show there is a 4-coloring of V with no monochromatic edge. (Don't forget: X-hour Thursday this week, followed by Prosser Lecture at 7pm in Oopik!)

Due Thursday Sept 29: Look up Joel Spencer's famous paper Six Standard Deviations Suffice and write down, in your own words, one of the formulations of the main theorem.

Due Wednesday Oct 5: 200 students take a 6-question exam, and each question is answered correctly by at least 120 students. Prove that there must be some pair of students with the property that every question was answered correctly by at least one of them.

Due Friday Oct 7: No written assignment. Go over your exam and make sure you understand what you missed!

Due Monday Oct 10: Prove that you can 4-color the numbers from 1 to 2000 in such a way that there is no monochromatic arithmetic progression of length 10.

Due Wednesday Oct 12: Let P be the (random) poset obtained by ordering n random points in the unit cube coordinatewise; alternatively, by intersecting the indentity permutation of {1,...,n} with two independently chosen uniformly random permutations. Prove that the expected value of the height of P is at most (1+o(1))en^{1/3}.

Due Friday Oct 14: Let F(n,k) be the number of permutations of {1,2,...,n} that have exactly k fixed points. Prove that the sum over all k (from 0 to n) of kF(n,k) is n!.

Due Monday Oct 17: The canvas of an applique portrait of Donald Trump is half-covered by swatches of each of the colors orange, yellow, red, pink and purple. Prove that there are two colors that overlap in at least 1/5 of the portrait. And: read President Hanlon's latest blog entry at http://sites.dartmouth.edu/president.

Due Wednesday Oct 19: Prove that given any 650 points in a disk of radius 16, at least 10 can be covered by an annulus with small radius 2 and big radius 3.

Due Friday Oct 21: Let f be a uniformly random function from {1,...,n} to {1,...,m}; equivalently, f(i) is a uniformly random number between 1 and m, chosen independently for each i. A collision is a pair i,j of distinct numbers in {1,...,n} for which f(i)=f(j). Let X be the number of collisions; what is the variance of X?

Due Monday Oct 24: Read 4.1, 4.3 and 4.4.

Due Wednesday Oct 26: An isolated point is a vertex incident to no edges, i.e., a vertex of degree 0. Find a function f(n) that is a threshold function for the property P that Gn,p has no isolated point. Then show that if p(n) = (1+ε)f(n), then Gn,p(n) almost always has property P.

Due Friday Oct 28: Find a threshold function f(n) for the property "G contains a triangle" and prove that it works---i.e., prove that if p(n) << f(n), then Gn,p(n) almost never has a triangle, but when p(n) >> f(n), Gn,p(n) almost always has a triangle.

Due Monday Oct 31: Read 4.6 (Distinct Sums). Find a number n and a subset S of {1,...,n} that has distinct sums, and which is bigger (in number of elements) than the set of powers of 2 in {1,...,n}.

Due Wednesday Nov 2: A code (for us) is a set of binary strings ("codewords") none of which is an initial segment of another. Prove that the sum over all codewords of 1/2|c|, where |c| is the length of the codeword c, is at most 1. For one point extra credit, use the first part to show that the average length of the codewords in an n-word code is at least the log base 2 of n.

Due Friday Nov 4: Prove that for any positive integer n, (1 - 1/n)n < 1/e < (1 - 1/n)n-1, by using the Taylor expansion log(1-x) = - x - x2/2 - x3/3 - x4/4 - ... .

Due Monday Nov 7: Let H be a k-uniform, k-regular hypergraph, with its vertices colored red or green uniformly at random. (a) Show that if edges S and T overlap in just one element, the events "S is monochromatic" and "T is monochromatic" are independent. (b) Show that the number of edges that intersect S in more than one vertex is at most k(k-1)/2. (c) Does this enable you to improve our class result (that H is 2-colorable when k is at least 9)?

Due Wednesday Nov 9: The nodes of a Moser tree are labeled with edges of H in such a way that the label of a child always intersects the label of its parent, but labels of siblings are disjoint. Suppose there are just three edges with α intersecting β and β intersecting γ, but α and γ are disjoint. (Of course, every edge intersects itself.) Find all Moser trees of depth at most 3.

Due Friday Nov 11: Suppose that w(1), w(2), ... is a sequence of positive reals with w(1) = p such that w(i) ≤ p(1+w(i-1))d+1 for each i. Show that if the real number x ≥ p satisfies x ≥ p(1+x)d+1, then w(i) ≤ x for all i.

Due Monday Nov 14: Suppose positive integers s1,...,sn sum to a fixed number s. Show that the sum of their reciprocals is minimized when the si's are as close together as possible; that is, when |si-sj| ≤ 1 for every i and j.

### Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

### Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.