Welcome to the Math 100 Web Page

Math 100

Percolation (Topics in Probability)

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

Abstract | Classes | Tutorials | Staff | Textbook | Grading | News and current assignment | Past assignments | Exams | Honor Code


News

Following are the papers---an absolutely wonderful collection---written as projects for Math 100 in Winter 2010:

A Sketch of Menshikov's Theorem, by Thomas Bao

Percolation on the Oriented Square Grid, by Amir Barghi

Proof of Reimer's Theorem, by Dan Crytser

Renormalization: An Attack on Critical Exponents, by Zebediah Engberg

The Complex Analysis Behind Smirnov's Theorem, by Elizabeth Gillaspy

Sharp Thresholds, by Zachary Hamaker

The Aizenman-Kesten-Newman Theorem, by Natasha Komarov

Critical Probabilities on the Triangular and Hexagonal Lattices, by Pat Schooley

Lilypad Percolation, by Enrique Trevino

Abstract

This course studies a mathematical model for flow through a porous material. Though simple and elegant, the model exhibits fascinating behavior and makes use of a panorama of mathematical techniques from probability, geometry, analysis and combinatorics. The material is suitable for an advanced undergraduate math major or any level of graduate student; no particular prerequisite (although the equivalent of Math 20 would be helpful).

Here is the course syllabus.

1. Introduction to the model; motivation; basic results
Week 1, B/R Chapter 1.

2. Tools from probability
Week 2, B/R Chapter 2.

3. Bond percolation on the square grid
Week 3, B/R Chapter 3.

4. Exponential decay
Week 4, B/R Chapter 4.

5. The infinite open cluster
Week 5, B/R Chapter 5.

6. Critical probabilities
Week 6, B/R Chapter 6.

7. Percolation variants: continuum and coordinate percolation
Weeks 7 and 8, B/R Chapter 8 and supplementary materials

8. Conformal invariance
Weeks 9 and 10, B/R Chapter 7.

Classes

Room: Kemeny Hall 004
Lectures: "2A" slot, in particular: Tuesdays 2-3:50 (with a break), and Thursdays 2-3:30.
X-hour: Wednesdays 4:15 pm--5:20pm

Tutorials

There may be occasional meetings, usually optional, during our X-period, Wednesdays, 4:15 PM - 5:20 PM, in our classroom.

Staff

Instructor:
Peter Winkler -- Kemeny Hall 231 / Tel. 6-3468
Office Hours: Tuesday, Wednesday and Thursday 10:30 am--11:30 am, and by appointment.
Homework grader:
To be determined.

Textbook

Bela Bollobas and Oliver Riordan
Percolation, Cambridge University Press, 2006.
(required)

This book is available from Wheelock Books and elsewhere.

Grading

Your grade will be based on homework, class participation, and a project (different for each student) which entails a half-hour presentation and, at the end of the term, a short paper.

Homework

Homework will be assigned at each class period, due at the beginning of the next class. In some cases nothing written will be due, but any student may be called upon to present his or her homework to the class.

Past assignments

Due Tuesday 1/12: Compute the critical probabilities p_H and p_T for bond percolation on the 2-branching lozenge tree.

Due Thursday 1/14: Compute the theta-function for a 3-regular Bethe lattice (that is, a tree in which every vertex has degree 3).

Due Tuesday 1/19: Prove Harris' Lemma (constant p will do), showing explicit justification for "the second inequality following from (6)" (middle of p. 40 of your text).

Due Thursday 1/21: Prove that Bridg-It cannot end in a draw. Make use of the technology of our Peierls argument!

Due Tuesday 1/26: Let G be the Shannon Switching Game played on the graph with vertices s, t, a and b, and edges sa, sb, at, bt and ab. (a) Who wins G, playing alternating moves: Short, Cut or first player? (b) With what probability does Short win the random-turn version of G? (c) Up do what amount should Short be willing to offer Cut for the privilege of first move, if each starts with $1 in the Richman version of G?

Due Thursday 1/28: use our Harris' Theorem argument to prove that at p = 1/2, the probability that the radius of the open cluster containing (0,0) exceeds n is bounded by n^{-c}, for some positive constant c.

Due Tuesday 2/2: Find the "right" increasing function g(n) such that when A is the event "at least half the coordinates are 1s" in Q^n, then the derivative of P_p(A) at p = 1/2 is at least t(1-t)g(n), where t = P_{1/2}(A).

Due Thursday 2/4: Use Cayley's Theorem (and hints from class) to show that the number of size-n trees rooted at v in a lattice of max degree D is at most (eD)^n.

Due Tuesday 2/9: Show that a random variable N of range {1,2,...,n} and expectation cn must have probability at least c/2 of exceeding cn/2.

Due Thursday 2/11: Can there be more than one infinite open cluster in independent percolation on the square grid, when p > p_c?

Due Tuesday 2/16: You are given a large amount of material with which to make a screen from sticks of length 1 mm and cross-sectional area t square microns, for any t you want. Such a stick breaks with probability 1/2^t. What lattice and what value of t should you use, to maximize the size of your screen while assuring that it won't fall apart?

Due Tuesday 2/23: Let K be any nonempty subset of the discrete hypercube Q_n, and for x, y in K put x adjacent to y iff no other element of K belongs to the subcube [x,y]. Prove that the resulting graph is connected.

Due Thursday 2/25: Let H be the hex grid on a discrete domain with boundary arcs A_1, A_2 and A_3. Pick any site of H with neighboring cells x_1, x_2, x_3 labeled in the same (counter-clockwise) order as the boundary arcs. Let B_i be the event that x_i and A_i are connected by an open path, W_i by a closed path, assuming critical face percolation on H. Letting # represent the disjoint "box" product, which is more likely, B_1 # B_2 # B_3 or W_1 # B_2 # B_3?

Due Tuesday 3/2: For a binary string x in the uniform discrete hypercube Q_n, let x' denote the result of flipping all the bits in x, and for any set S let S' := {x'|x in S} so that P(S)=P(S'). Let A and B be two up-events in Q_n. Find an example where P(A # B) < P(A and B), or one where P(A # B) > P(A and B), or both (if possible).

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 Coordinator, Nancy Pompian, can be reached at 6-2014 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.