Category Archives: Open problems

Cap 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 Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , , , | 6 Comments

Joe’s 100th MO question

MathOverflow is a remarkable recent platform for research level questions and answers in mathematics. Joe O’Rourke have asked over MO wonderful questions. (Here is a link to the questions) Many of those questions can be the starting point of a research … Continue reading

Posted in Mathematics over the Internet, Open problems | Tagged , , | 4 Comments

A Couple Updates on the Advances-in-Combinatorics 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 , | 4 Comments

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

Posted in Combinatorics, Convexity, Open problems | Tagged , , , , | 2 Comments

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

Posted in Computer Science and Optimization, Games, Open problems, Probability | 9 Comments

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

Posted in Open discussion, Open problems, Polymath3 | Tagged , | 60 Comments

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

Posted in Algebra and Number Theory, Combinatorics, Computer Science and Optimization, Open problems, Physics | Tagged , , , | 11 Comments

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