Recent Comments

Recent Posts
 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
 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?
Top Posts & Pages
 In And Around Combinatorics: The 18th Midrasha Mathematicae. Jerusalem, JANUARY 1831
 Believing that the Earth is Round When it Matters
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 In how many ways you can chose a committee of three students from a class of ten students?
 János Pach: Guth and Katz's Solution of Erdős's Distinct Distances Problem
 Polymath 8  a Success!
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 The Intermediate Value Theorem Applied to Football
 About
RSS
Category Archives: Combinatorics
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
Polymath3 : Polynomial Hirsch Conjecture 3
Here is the third research thread for the polynomial Hirsch conjecture. I hope that people will feel as comfortable as possible to offer ideas about the problem we discuss. Even more important, to think about the problem either in the directions suggested by … Continue reading
Posted in Combinatorics, Convex polytopes, Open discussion, Open problems, Polymath3
Tagged Polymath3
102 Comments