Recent Comments

Recent Posts
 Test your intuition 24: Which of the following three groups is trivial
 School Starts at HUJI
 A lecture by Noga
 Ehud Friedgut: Blissful ignorance and the KahnemanTversky paradox
 In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 1831
 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
Top Posts & Pages
 Test your intuition 24: Which of the following three groups is trivial
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Believing that the Earth is Round When it Matters
 Why Quantum Computers Cannot Work: The Movie!
 The Intermediate Value Theorem Applied to Football
 Polymath 8  a Success!
 יופיה של המתמטיקה
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 Amazing: Peter Keevash Constructed General Steiner Systems and Designs
RSS
Category Archives: Combinatorics
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
Test Your Intuition (14): A Discrete Transmission Problem
Recall that the dimensional discrete cube is the set of all binary vectors ( vectors) of length n. We say that two binary vectors are adjacent if they differ in precisely one coordinate. (In other words, their Hamming distance is 1.) This … Continue reading
A Couple Updates on the AdvancesinCombinatorics Updates
In a recent post I mentioned quite a few remarkable recent developments in combinatorics. Let me mention a couple more. Independent sets in regular graphs A challenging conjecture by Noga Alon and Jeff Kahn in graph theory was about the number of … Continue reading
Posted in Combinatorics, Open problems, Updates
Tagged Independent sets in graphs, Roth's theorem
4 Comments
Around Borsuk’s Conjecture 1: Some Problems
Greetings to all! Karol Borsuk conjectured in 1933 that every bounded set in can be covered by sets of smaller diameter. In a previous post I described the counterexample found by Jeff Kahn and me. I will devote a few posts … Continue reading
The Combinatorics of Cocycles and Borsuk’s Problem.
Cocycles Definition: A cocycle is a collection of subsets such that every set contains an even number of sets in the collection. Alternative definition: Start with a collection of sets and consider all sets that contain an odd number of members … Continue reading
Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier
Click here for the most recent polymath3 research thread. I missed Tom by a few minutes at MittagLeffler Institute a year and a half ago Suppose that is a subset of of maximum cardinality not containing an arithmetic progression of length 3. Let . … Continue reading
Posted in Combinatorics, Open problems
Tagged Endre Szemeredi, Jean Bourgain, Klaus Roth, Roger HeathBrown, Roth's theorem, Tom Sanders
9 Comments
János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem
Click here for the most recent polymath3 research thread. Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach. This post is authored by János Pach A … Continue reading
Posted in Combinatorics, Geometry, Guest blogger, Open problems
Tagged Larry Guth, Nets Hawk Katz
13 Comments
Octonions to the Rescue
Xavier Dahan and JeanPierre Tillich’s Octonionbased Ramanujan Graphs with High Girth. Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect. Update: There is more to … Continue reading
The SimonovitsSos Conjecture was Proved by Ellis, Filmus and Friedgut
Simonovits and Sos asked: Let be a family of graphs with N={1,2,…,n} as the set of vertices. Suppose that every two graphs in the family have a triangle in common. How large can be? (We talked about it in this post.) … Continue reading
Posted in Combinatorics, Open problems
10 Comments
Polymath3: Polynomial Hirsch Conjecture 4
So where are we? I guess we are trying all sorts of things, and perhaps we should try even more things. I find it very difficult to choose the more promising ideas, directions and comments as Tim Gowers and Terry Tao did so … Continue reading
Posted in Combinatorics, Convex polytopes, Open discussion, Open problems, Polymath3
Tagged Hirsch conjecture, Polymath3
73 Comments