Schedule


TimeSpeaker/ Title/ Abstract/ VODLocation
11:00 - 11:15 Welcome remark
CAMP
11:15 - 12:15 1st lecture What is Erdős Magic?
Joel Spencer (New York University),
Loading the live streaming player...
An introduction to the Probabilistic Method. Ramsey Numbers. Tournaments. Easy stuff.
Talk Material 1: /
CAMP
12:30 - 13:30 Lunch
CAMP
13:30 - 14:30 2nd lecture More Erdős Magic
Joel Spencer (New York University),
Loading the live streaming player...
More introduction to the Probabilistic Method. More Ramsey Numbers. Two Coloring. Minor Alterations. Packing Bounds.
Talk Material 1: /
CAMP
14:30 - 17:30 Long break for HW and Team Study
CAMP
17:30 - 18:30 Exercise Session
CAMP
TimeSpeaker/ Title/ Abstract/ VODLocation
09:00 - 09:30 Breakfast
CAMP
09:30 - 10:30 1st lecture Asymptopia
Joel Spencer (New York University),
Loading the live streaming player...
Chernoff Bounds for Large Deviations. Various methods for asymptotic analysis.
Talk Material 1: /
CAMP
11:15 - 12:15 2nd lecture Random Graphs
Joel Spencer (New York University),
Loading the live streaming player...
An overview of the Erdős-Rényi random graph G(n, p). Appearance of subgraphs. Connectivity.
Talk Material 1: /
CAMP
12:30 - 13:30 Lunch
CAMP
13:30 - 16:30 Long break for HW and Team Study
CAMP
16:30 - 17:30 Exercise session
CAMP
TimeSpeaker/ Title/ Abstract/ VODLocation
09:00 - 09:30 Breakfast
CAMP
09:30 - 10:30 1st lecture The Erdős-Rényi Phase Transition
Joel Spencer (New York University),
Loading the live streaming player...
In their great 1960 paper On the Evolution of Random Graphs Paul Erdős and Alfred Rényi expresses a special interest in the behavior of the random graph G(n, p) when p was near n−1. Today we view it through the prism of Percolation Theory. If p = cn−1 and c < 1 the process is subcritical and all components are small and simple. But for c > 1 the process is supercritical and a complex giant component has emerged. We now understand the fine structure: the critical window is parametrized p = n−1 + λn−4/3, with λ → −∞ and λ → +∞ represently the barely subcritical and barely supercritical phases. We discuss the behaviors, the arguments and the many analogies to bond percolation in Mathematical Physics.
Talk Material 1: /
CAMP
11:15 - 12:15 2nd lecture The Erdős-Rényi Phase Transition
Joel Spencer (New York University),
Loading the live streaming player...
In their great 1960 paper On the Evolution of Random Graphs Paul Erdős and Alfred Rényi expresses a special interest in the behavior of the random graph G(n, p) when p was near n−1. Today we view it through the prism of Percolation Theory. If p = cn−1 and c < 1 the process is subcritical and all components are small and simple. But for c > 1 the process is supercritical and a complex giant component has emerged. We now understand the fine structure: the critical window is parametrized p = n−1 + λn−4/3, with λ → −∞ and λ → +∞ represently the barely subcritical and barely supercritical phases. We discuss the behaviors, the arguments and the many analogies to bond percolation in Mathematical Physics.
Talk Material 1: /
CAMP
12:30 - 13:30 Lunch
CAMP
13:30 - 16:30 Long break for HW and Team Study
CAMP
16:30 - 17:30 Exercise session
CAMP
TimeSpeaker/ Title/ Abstract/ VODLocation
09:00 - 09:30 Breakfast
CAMP
09:30 - 10:30 1st lecture Games Mathematicians Play
Loading the live streaming player...
We consider a variety of Paul-Carole games. In one, Paul selects on each round a vector v (under various restrictions) and Carole must add or subtract it from a position vector P, initially 0, with the object of keeping P close to the origin. Here Carole represents an On-Line algorithm and Paul represents Worst Case analysis. Another class are Liar Games. Carole is thinking of a number x ∈ {1, …, n} and Paul may ask q questions. Carole is allowed to lie, though at most k times. Further restrictions might be placed on the nature of the allowable lie. While these games are fully deterministic, the analysis involves consideration of random play by Carole. Thus, we regard these methods as part of the Probabilistic Method as developed by Paul Erdős. Random play leads to a weight function which leads to a good deterministic strategy for Carole and, somewhat surprisingly, a good strategy for Paul as well.
Talk Material 1: /
CAMP
11:15 - 12:15 2nd lecture Needles in Exponential Haystacks
Loading the live streaming player...
The Lovász Local Lemma allows us to show the existence of an object that has no “bad" properties, when the bad properties are “mostly" independent. We give an algorithmic proof, based on the breakthrough ideas of Robin Moser. Six Standard Deviations Suffice was a result of this lecturers, that a two coloring may be found with low discrepancy. We give an algorithmic proof, due to Lovett and Meka, that reaches the coloring with a restricted Brownian motion. In both cases, a random choice would only have exponentially small chance of succeeding.
Talk Material 1: / Talk Material 2: /
CAMP
12:30 - 13:30 Lunch
CAMP
13:30 - 16:30 Long break for HW and Team Study
CAMP
16:30 - 17:30 Exercise session
CAMP
TimeSpeaker/ Title/ Abstract/ VODLocation
09:00 - 09:30 Breakfast
CAMP
09:30 - 10:30 1st lecture Zero-One Laws
Loading the live streaming player...
We examine the random graph $G(n,p)$ from the viewpoint of First Order Logic. The Ehrenfeucht Game, intriguing in its own right, provides a bridge between combinatorics and logic. Fagin and Glebskii et. al. show that for any fixed $p$ and any first order property $A$, $\Pr[A]$ approaches zero or one as $n$ approaches $\infty$. Shelah and the speaker showed that this holds when $p=n^{-\alpha}$ and $\alpha$ is irrational. We describe the Game, give the Fagin/Glebskii argument and outline the Shelah/Spencer argument.
Talk Material 1: /
CAMP
11:15 - 12:15 2nd lecture Gems
Loading the live streaming player...
John Conway once said, “Its a thing that non-mathematicians don’t realize. Mathematics is actually an esthetic subject almost entirely." We give a highly personal selection of esthetically pleasing uses of probabilistic methods. These are arguments that we feel are close to what Paul Erdős called the Book proof.
CAMP
12:30 - 13:30 Lunch
CAMP
13:30 - 15:00 Long break for HW and Team Study
CAMP
15:00 - 16:00 Exercise session
CAMP