Category Archives: Combinatorics

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

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

IPAM Workshop – Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

  Workshop at IPAM: January 18 – 21, 2011 Here is the link to the IPAM conference. 

Posted in Combinatorics, Computer Science and Optimization, Conferences, Convex polytopes | Leave a comment

The Polynomial Hirsch Conjecture: The Crux of the Matter.

 Consider t disjoint families of subsets of {1,2,…,n}, .   Suppose that (*) For every , and every and , there is  which contains .  The basic question is: How large can t  be???   Let’s call the answer f(n).   … Continue reading

Posted in Combinatorics, Convex polytopes, Open problems, Polymath3 | 5 Comments

Midrasha Talks are Now Online

Itai Benjamini listening to Gadi Kozma There are 41 lectures from the Midrasha on Probability and Geometry: The Mathematics of Oded Schramm which are now online. Joram Lindenstrauss’s concluding lecture (click on the picture to see) Laci Lovasz More pictures … Continue reading

Posted in Combinatorics, Conferences, Probability | Tagged , , | 4 Comments

Noise Stability and Threshold Circuits

The purpose of this post is to describe an old conjecture (or guesses, see this post) by Itai Benjamini, Oded Schramm and myself (taken from this paper) on noise stability of threshold functions. I will start by formulating the conjectures and … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged , , , , | 11 Comments

A Discrepancy Problem for Planar Configurations

Yaacov Kupitz and Micha A. Perles asked: What is the smallest number C such that for every configuration of n points in the plane there is a line containing two or more points from the configuration for which the difference between the … Continue reading

Posted in Combinatorics | Tagged , | Leave a comment