Category Archives: Combinatorics

Analysis of Boolean Functions – Week 7

Lecture 11 The Cap Set problem We presented Meshulam’s  bound for the maximum number of elements in a subset A of not containing a triple x,y,x of distinct elements whose sum is 0. The theorem is analogous to Roth’s theorem … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Teaching | Tagged , , | Leave a comment

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 n-dimensional space. (Other graphs were considered later as … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , | Leave a comment

Analysis of Boolean Functions – week 4

Lecture 6 Last week we discussed two applications of the Fourier-Walsh plus hypercontractivity method and in this lecture we will discuss one additional application: The lecture was based on a 5-pages paper by Ehud Friedgut and Jeff Kahn: On the number … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Teaching | Tagged | Leave a comment

Analysis of Boolean Functions – Week 3

Lecture 4 In the third week we moved directly to the course’s “punchline” – the use of Fourier-Walsh expansion of Boolean functions and the use of Hypercontractivity. Before that we  started with  a very nice discrete isoperimetric question on a … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability, Teaching | Tagged , , | Leave a comment

Richard Stanley: How the Proof of the Upper Bound Theorem (for spheres) was Found

The upper bound theorem asserts that among all d-dimensional polytopes with n vertices, the cyclic polytope maximizes the number of facets (and k-faces for every k). It was proved by McMullen for polytopes in 1970, and by Stanley for general triangulations … Continue reading

Posted in Combinatorics, Convex polytopes | Tagged , | 2 Comments

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 Ben-Or 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 , | 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

Posted in Combinatorics, Convexity, Geometry, Open problems | Tagged , , , | Leave a comment

Analysis of Boolean Functions – week 1

Home page of the course. In the first lecture I defined the discrete n-dimensional 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

Posted in Combinatorics, Computer Science and Optimization, Teaching | Tagged , , , | 1 Comment

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 , | Leave a comment

Lawler-Kozdron-Richards-Stroock’s combined Proof for the Matrix-Tree 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 Kirchho ff and Wilson via Kozdron and Stroock. The lecture is based on … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged , , | 4 Comments