Recent Comments

Recent Posts
 Mathematical Gymnastics
 Media Item from “Haaretz” Today: “For the first time ever…”
 Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota’s Conjecture on Matroids
 Media items on David, Amnon, and Nathan
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Happy Birthday Ervin, János, Péter, and Zoli!
 My Mathematical Dialogue with Jürgen Eckhoff
 Test Your Intuition (23): How Many Women?
 Happy Birthday Richard Stanley!
Top Posts & Pages
 Believing that the Earth is Round When it Matters
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 The Ultimate Riddle
 The Intermediate Value Theorem Applied to Football
 Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota's Conjecture on Matroids
 Why Quantum Computers Cannot Work: The Movie!
 Analysis of Boolean Functions
 János Pach: Guth and Katz's Solution of Erdős's Distinct Distances Problem
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
RSS
Category Archives: Combinatorics
Tokyo, Kyoto, and Nagoya
Near Nagoya: Firework festival; Kyoto: with Gunter Ziegler; with Takayuki Hibi, Hibi, Marge Bayer, Curtis Green and Richard Stanly; Tokyo: Peter Frankl; crowded crossing. Added later: Mazi and I at the same restaurant taken by Stanley. I just returned from … Continue reading
Posted in Combinatorics, Conferences, Convex polytopes
Tagged Alternating sign matrices, Convex polytopes, FPSAC, Japan
2 Comments
Celebrations in Sweden and Norway
Celebrations for Endre, Jean and Terry Anders Bjorner presents the 2012 Crafoord Prize in Mathematics I am in Sweden for two weeks to work with colleagues and to take part in two celebrations. Jean Bourgain and Terence Tao are the 2012 laureates … Continue reading
Posted in Academics, Combinatorics, Conferences, Updates
Tagged Endre Szemeredi, Jean Bourgain, Terrence Tao
2 Comments
Galvin’s Proof of Dinitz’s Conjecture
Dinitz’ conjecture The following theorem was conjectured by Jeff Dinitz in 1979 and proved by Fred Galvin in 1994: Theorem: Consider an n by n square table such that in each cell (i,j) you have a set with n or more elements. … Continue reading
Posted in Combinatorics, Games
4 Comments
Fractional SylvesterGallai
Avi Wigderson was in town and gave a beautiful talk about an extension of SylvesterGallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev … Continue reading
Posted in Combinatorics, Computer Science and Optimization, Geometry
Tagged Avi Wigderson, Codes, Greg Kuperberg, SylvesterGallai
4 Comments
Ryan O’Donnell: Analysis of Boolean Function
Ryan O’Donnell has begun writing a book about Fourier analysis of Boolean functions and he serializes it on a blog entiled Analysis of Boolean Function. New sections appear on Mondays, Wednesdays, and Fridays. Besides covering the basic theory, Ryan intends to describe applications … Continue reading
Cup Sets, Sunflowers, and Matrix Multiplication
This post follows a recent paper On sunflowers and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Grouptheoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading
High Dimensional Expanders: Introduction I
Alex Lubotzky and I are running together a year long course at HU on High Dimensional Expanders. High dimensional expanders are simplical (and more general) cell complexes which generalize expander graphs. The course is taking place in Room 110 of the mathematics building on … Continue reading
Posted in Combinatorics, Teaching
4 Comments
Noise Sensitivity and Percolation. Lecture Notes by Christophe Garban and Jeff Steif
Lectures on noise sensitivity and percolation is a new beautiful monograph by Christophe Garban and Jeff Steif. (Some related posts on this blog: 1, 2, 3, 4, 5)
Posted in Combinatorics, Probability
Tagged Christoph Garban, Jeff Steif, Noise, Noisesensitivity, Percolation
Leave a comment
Alantha Newman and Alexandar Nikolov Disprove Beck’s 3Permutations Conjecture
Alantha Newman and Alexandar Nikolov disproved a few months ago one of the most famous and frustrating open problem in discrepancy theory: Beck’s 3permutations conjecture. Their paper A counterexample to Beck’s conjecture on the discrepancy of three permutations is already on … Continue reading
Discrepancy, The BeckFiala Theorem, and the Answer to “Test Your Intuition (14)”
The Question Suppose that you want to send a message so that it will reach all vertices of the discrete dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the … Continue reading