Spring 2014 LOM 215, MW 2.30-3.45; Office hour: M: 10am-11.30am.
TA: Oanh Nguyen MW 7-8.30pm, Lounge, Dunham 4th floor.
This is an advanced, proof based, class, close to grad level. A set of HW will be assigned (and due) every 2 weeks . Students are also encouraged to read a short paper and present in class. Grades will be given based on the HWs and presentations.
Prerequisites: 244 or equivalent, basic knowledge of probability (such as random variables, distributions, mean and variance); 222 or 225.
We will start with Chapter 1 from Alon-Spencer book (The probabilistic method). This book has many editions; I will use the latest, but there is no difference in the first few chapters (which we discuss). I will bring copies of the material to class.
First week: Jan 15, 17 (notice we have WF this week):
Basic notations: graphs, random variables, mean and variance, linearity of expectations. The main idea of “probabilistic proofs”. Ramsey numbers. Small dominating sets in graphs. Hypergraphs and Property “B”.
Second week: Jan 22.
Continue on Chapter 1: Random permutation and (k,l) system; Sum-free sets; Codes.
Math345-HW1 (due Feb 5)
Third week: Jan 27, 29.
Chapter 2: Tournaments, Max-cuts, Balancing vectors and Unbalancing lights.
Fourth week: Feb 3,5.
Chapter 2: Choice of distributions: Theorem 2.2.3; Random permutation and Bregman’s theorem.
Math345-HW02(due Feb 19)
Fifth week: Feb 10, 12.
Chapter 3: Ramsey number revisited, Independent sets, Geometry, Coloring.
Sixth week: Feb 17, 19.
Chapter 3: Girth and Chromatic number
Chapter 4: Variance, Chebysev inequality. Hardy-Ramanujan theorem. Random graphs and subgraph count.
Math345-HW (due March 5)
Seventh week: Feb 24, 26.
More inequalities on variance. The central limit theorem (this will be outside Alon-Spencer book).
Eighth week: March 3, 5.
Chapter 5: The Local Lemma. Finding a needle in a haystack.
Selection of project due before break.
Ninth and tenth weeks: March 24, 26, 31, April 2.
Inequalities in Probability and applications. (We will touch parts of Chapters 6,7,8 and will also use material from elsewhere.)
Presentations will be scheduled for the last 2 weeks. Long ones would take about 35-40′ (even longer is possible upon request); short one would take 15-20 minutes.