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.

Math345-HW

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.)

Math345-HW

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.