Recent Comments
Category Archives: Open problems
Is Backgammon in P?
The Complexity of Zero-Sum Stochastic Games with Perfect Information Is there a polynomial time algorithm for chess? Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is … Continue reading
Polynomial Hirsch Conjecture 5: Abstractions and Counterexamples.
This is the 5th research thread of polymath3 studying the polynomial Hirsch conjecture. As you may remember, we are mainly interested in an abstract form of the problem about families of sets. (And a related version about families of multisets.) The … 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 Mittag-Leffler 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 Heath-Brown, 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 Jean-Pierre Tillich’s Octonion-based 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 Simonovits-Sos 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
Polymath 3: The Polynomial Hirsch Conjecture 2
Here we start the second research thread about the polynomial Hirsch conjecture. I hope that people will feel as comfortable as possible to offer ideas about the problem. The combinatorial problem looks simple and also everything that we know about it is rather simple: … Continue reading
Posted in Convex polytopes, Open discussion, Open problems, Polymath3
Tagged Hirsch conjecture, Polymath3
104 Comments
Polymath 3: Polynomial Hirsch Conjecture
I would like to start here a research thread of the long-promised Polymath3 on the polynomial Hirsch conjecture. I propose to try to solve the following purely combinatorial problem. Consider t disjoint families of subsets of {1,2,…,n}, . Suppose that … Continue reading
Posted in Convex polytopes, Open discussion, Open problems, Polymath3
Tagged Hirsch conjecture, Polymath3
117 Comments
