Category Archives: Open problems

Polymath4 – Finding Primes Deterministically – is On Its Way

  After two long and interesting discussion threads polymath4, devoted to finding deterministically large prime numbers, is on its way on the polymath blog.

Posted in Open problems | Tagged | Leave a comment

The Polynomial Hirsch Conjecture – How to Improve the Upper Bounds.

I can see three main avenues toward making progress on the Polynomial Hirsch conjecture. One direction is trying to improve the upper bounds, for example,  by looking at the current proof and trying to see if it is wasteful and if so where … Continue reading

Posted in Convex polytopes, Open discussion, Open problems | Tagged , | 14 Comments

The Polynomial Hirsch Conjecture, a Proposal for Polymath3 (Cont.)

The Abstract Polynomial Hirsch Conjecture A convex polytope is the convex hull of a finite set of points in a real vector space. A polytope can be described as the intersection of a finite number of closed halfspaces. Polytopes have … Continue reading

Posted in Convex polytopes, Open discussion, Open problems | Tagged , | 5 Comments

The Polynomial Hirsch Conjecture: A proposal for Polymath3

This post is continued here.  Eddie Kim and Francisco Santos have just uploaded a survey article on the Hirsch Conjecture. The Hirsch conjecture: The graph of a d-polytope with n vertices  facets has diameter at most n-d. We devoted several … Continue reading

Posted in Convex polytopes, Open discussion, Open problems | Tagged , , , | 38 Comments

Raigorodskii’s Theorem: Follow Up on Subsets of the Sphere without a Pair of Orthogonal Vectors

Andrei Raigorodskii (This post follows an email by Aicke Hinrichs.) In a previous post we discussed the following problem: Problem: Let be a measurable subset of the -dimensional sphere . Suppose that does not contain two orthogonal vectors. How large … Continue reading

Posted in Convexity, Open problems | Tagged , | 1 Comment

How Large can a Spherical Set Without Two Orthogonal Vectors Be?

The problem Witsenhausen’s Problem (1974): Let be a measurable subset of the -dimensional sphere . Suppose that does not contain two orthogonal vectors. How large can the -dimensional volume of be?   A Conjecture Conjecture: The maximum volume is attained … Continue reading

Posted in Open problems | 4 Comments

The Cap-Set Problem and Frankl-Rodl Theorem (C)

Update: This is a third of three posts (part I, part II) proposing some extensions of the cap set problem and some connections with the Frankl Rodl theorem. Here is a post presenting the problem on Terry Tao’s blog (March 2007). Here … Continue reading

Posted in Combinatorics, Open problems | Tagged , , | Leave a comment

Around the Cap-Set problem (B)

Part B: Finding special cap sets This is a second part in a 3-part series about variations on the cap set problem that I studied with Roy Meshulam. (The first post is here.)  I will use here a different notation than in part … Continue reading

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

A Problem on Planar Percolation

Conjecture (Gady Kozma):  Prove that the critical probability for planar percolation on a Cayley graph of the group is always an algebraic number. Gady  mentioned this conjecture in his talk here about percolation on infinite Cayley graphs.  (Update April 30: Today Gady mentioned … Continue reading

Posted in Open problems, Probability | Tagged , | 1 Comment

(Eran Nevo) The g-Conjecture II: The Commutative Algebra Connection

Richard Stanley This post is authored by Eran Nevo. (It is the second in a series of five posts.) The g-conjecture: the commutative algebra connection Let be a triangulation of a -dimensional sphere. Stanley’s idea was to associate with a ring … Continue reading

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