Recent Comments

Recent Posts
 Polymath10, Post 2: Homological Approach
 Polymath10: The Erdos Rado Delta System Conjecture
 Convex Polytopes: Seperation, Expansion, Chordality, and Approximations of Smooth Bodies
 Igor Pak’s collection of combinatorics videos
 EDP Reflections and Celebrations
 Séminaire N. Bourbaki – Designs Exist (after Peter Keevash) – the paper
 Important formulas in Combinatorics
 Updates and plans III.
 NogaFest, NogaFormulas, and Amazing Cash Prizes
Top Posts & Pages
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Polymath10, Post 2: Homological Approach
 Polymath10: The Erdos Rado Delta System Conjecture
 New Ramanujan Graphs!
 The Mystery PianoPlayer at the MittagLeffler Institute
 Extremal Combinatorics III: Some Basic Theorems
 'Gina Says'
 Why Quantum Computers Cannot Work: The Movie!
 Four Derandomization Problems
RSS
Category Archives: Combinatorics
Analysis of Boolean Functions week 5 and 6
Lecture 7 First passage percolation 1) Models of percolation. We talked about percolation introduced by Broadbent and Hammersley in 1957. The basic model is a model of random subgraphs of a grid in ndimensional space. (Other graphs were considered later as … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching
Tagged Arrow's theorem, Percolation
Leave a comment
Analysis of Boolean Functions – week 4
Lecture 6 Last week we discussed two applications of the FourierWalsh plus hypercontractivity method and in this lecture we will discuss one additional application: The lecture was based on a 5pages paper by Ehud Friedgut and Jeff Kahn: On the number … Continue reading
Analysis of Boolean Functions – Week 3
Lecture 4 In the third week we moved directly to the course’s “punchline” – the use of FourierWalsh expansion of Boolean functions and the use of Hypercontractivity. Before that we started with a very nice discrete isoperimetric question on a … Continue reading
Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found
The upper bound theorem asserts that among all ddimensional polytopes with n vertices, the cyclic polytope maximizes the number of facets (and kfaces for every k). It was proved by McMullen for polytopes in 1970, and by Stanley for general triangulations … Continue reading
Analysis of Boolean functions – week 2
Post on week 1; home page of the course analysis of Boolean functions Lecture II: We discussed two important examples that were introduced by BenOr and Linial: Recursive majority and tribes. Recursive majority (RM): is a Boolean function with variables … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching
Tagged Boolean functions, Tribes
Leave a comment
Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture
Borsuk asked in 1933 if every bounded set K of diameter 1 in can be covered by d+1 sets of smaller diameter. A positive answer was referred to as the “Borsuk Conjecture,” and it was disproved by Jeff Kahn and me in 1993. … Continue reading
Analysis of Boolean Functions – week 1
Home page of the course. In the first lecture I defined the discrete ndimensional cube and Boolean functions. Then I moved to discuss five problems in extremal combinatorics dealing with intersecting families of sets. 1) The largest possible intersecting family … Continue reading
Poznań: Random Structures and Algorithms 2013
Michal Karonski (left) who built Poland’s probabilistic combinatorics group at Poznań, and a sculpture honoring the Polish mathematicians who first broke the Enigma machine (right, with David Conlon, picture taken by Jacob Fox). I am visiting now Poznań for the 16th … Continue reading
Posted in Combinatorics, Conferences, Open problems, Philosophy, Probability
Tagged Poznan, RSA
2 Comments
LawlerKozdronRichardsStroock’s combined Proof for the MatrixTree theorem and Wilson’s Theorem
David Wilson and a cover of Shlomo’s recent book “Curvature in mathematics and physics” A few weeks ago, in David Kazhdan’s basic notion seminar, Shlomo Sternberg gave a lovely presentation Kirchhoff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Probability
Tagged David Wilson, Gustav Kirchhoff, Trees
4 Comments
Some old and new problems in combinatorics and geometry
Paul Erdős in Jerusalem, 1933 1993 Update: Here is a link to a draft of a paper* based on the first part of this lecture. Some old and new problems in combinatorial geometry I: Around Borsuk’s problem. I just came back from … Continue reading