It is six in the morning. The house
is asleep.
Nice music is playing. I prove and
conjecture.
Paul Erdos, in a letter to
Vera Sos
Course:
Math 290-40, CRN 49746
Title:
Reading Seminar "The
Probabilistic Method in Combinatorics"
When: Tuesday 9-10 am
Where: Kerr 693
Instructor: Roman Vershynin
Office: 671 Kerr
Email: vershynin_at_math.ucdavis.edu
Office Hours: Tue 10:10-12 am, and by appointment
Organizational meeting:
Friday, October 1 at
4pm in Kerr 593
We will read and discuss some key
texts on the celebrated Probabilistic Method, which had a strong impact
on
the development of Mathematics in the 20th century. One is often not
able to construct an object he needs (such as a graph with certain nice
properties). Then one tries to make a random
construction, when an
object is taken at random from a large pool (such as two nodes of a
graph are connected by an edge with probability 1/2). The Probabilistic
Method
proves -- and here's the beauty -- that with positive probability, such a
randomly chosen object does have the nice properties. Therefore, it
exists!
The texts we will
read are:
- "The probabilistic
method" by N.Alon and J.Spencer (see bottom of this page)
- some recent
papers related to computer science
- Further suggestions are welcome!
The tentative schedule is at the
bottom of this page.
Students who attend regularly can register for
one credit; students who
present a topic can register for
three
credits.
Completion of a graduate course in probability theory is
not a prerequisite for this
seminar.
In addition to this, there will be a
280
course "Probability and
Convexity"
How
to choose and prepare your presentation
If you have never done it before, you may want to choose a presentation
from the book
[AS] (bottom of this page
has a link to it)
which is very nicely written for a
beginner. Pick a chapter that most appeals to you (see the schedule
below). From that chapter, select theorems that you like (and which
do not scare you away). In the schedule, I emphasized results that I
think are most important in each chapter, and which should be covered
if possible.
Papers with applications (November 15, 22, 29, December 6) are really
beautiful, you won't regret studying and presenting them.
If you have questions, contact me.
Tentative Schedule
October 1
|
|
Orgainzational meeting at 4pm in
Kerr 593
|
October 5
|
Roman Vershynin,
Damien Pitman
|
I will recall basic concepts of
graph theory and probability. Then
Damien will start his talk on the basic Probabilistic Method. Chapter 1
of [AS] and "the Probabilistic Lens"
|
October 12
|
Damien Pitman
|
continuation
|
October 19
|
John Steinberger
|
Methods based on the linearity
of expectation methods. Especially: splitting graphs, balancing
vectors. Chapter 2 of [AS] |
October 26
|
Momar Dieng
|
The second moment method.
Especially applications to number theory and distinct sums. Chapter 4
of [AS] |
November 2
|
Professor Martin Zerner
|
The Local Lemma.
Chapter 5 of [AS] |
| November 9 |
Deanna Needell
|
Correlation inequalities and
applications, especially to monotone properties (Kleitman's lemma).
Chapter 6 of [AS] |
November 16
|
free |
Applications to computer
science: satisfying boolean formulae, reducing probability spaces.
Lectures 1 and 3 from "Randomized
methods in computation" by Goldreich |
| November 23 |
Ram Puri |
Applications
to computational
geometry: "Sampling
lattice points" by Kannan and Vempala |
| November 30 |
Professor Eric Rains |
Applications to information
theory: Shannon's theorem, error correcting codes |
December 7
|
Jaideep Mulherkar
|
Applications
to computational number theory: primality testing. Lecture 11 from "Randomized
methods in computation" by Goldreich |
|
free |
One more paper available (to be
moved to whatever date remains free). Applications to signal
processing: "Robust
uncertainty principles: Exact signal reconstruction from highly
incomplete frequency information”by Candes, Romberg and Tao
|
[AS]
Noga Alon, Joel Spencer, The
probabilistic Method, Wiley-Interscience, 2000
This links to some chapters that are available
online. Note that the schedule refers to the numbering of chapters in
the printed edition.
I will keep a copy of this book in my mailbox; feel
free to have a look at it. When you are preparing the presentation, you
may borrow it, but please 1) put a note with your
name in my mailbox; 2) return the book to my mailbox at
the end of the day.
Web:
http://www.math.ucdavis.edu/~vershynin/teaching/RFG04/Reading-fall.html