Category Archives: Open problems

New Ramanujan Graphs!

Posted on May 1, 2013 by

Margulis’ paper Ramanujan graphs were constructed independently by Margulis and by Lubotzky, Philips and Sarnak (who also coined the name). The picture above shows Margulis’ paper where the graphs are defined and their girth is studied. (I will come back to the question … Continue reading →

Posted in Algebra and Number Theory, Combinatorics, Open problems | Tagged | 9 Comments

F ≤ 4E

Posted on February 1, 2013 by

1. E ≤ 3V Let G be a simple planar graph with V vertices and E edges. It follows from Euler’s theorem that E ≤ 3V In fact, we have (when V is at least 3,) that E ≤ 3V – 6. … Continue reading →

Posted in Combinatorics, Convex polytopes, Geometry, Open problems | Tagged | 11 Comments

A Few Mathematical Snapshots from India (ICM2010)

Posted on November 17, 2012 by

Can you find Assaf in this picture? (Picture: Guy Kindler.) In my post about ICM 2010 and India I hardly mentioned any mathematics. So here are a couple of mathematical snapshots from India. Not so much from the lectures themselves but … Continue reading →

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

Looking Again at Erdős’ Discrepancy Problem

Posted on August 26, 2012 by

Over Gowers’s blog Tim and I will make an attempt to revisit polymath5. Last Autumn I prepared three posts on the problems and we decided to launch them now. The first post is here. Here is a related MathOverflow question. … Continue reading →

Posted in Combinatorics, Mathematics over the Internet, Open problems | 2 Comments

A Weak Form of Borsuk Conjecture

Posted on July 23, 2012 by

Problem: Let P be a polytope in with n facets. Is it always true that P can be covered by n sets of smaller diameter?   I also asked this question over mathoverflow, with some background and motivation.

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

Satoshi Murai and Eran Nevo proved the Generalized Lower Bound Conjecture.

Posted on March 23, 2012 by

Satoshi Murai and Eran Nevo have just proved the 1971 generalized lower bound conjecture of McMullen and Walkup, in their  paper On the generalized lower bound conjecture for polytopes and spheres . Let me tell you a little about it. … Continue reading →

Posted in Convex polytopes, Open problems | Tagged , , , , | 2 Comments

Cup Sets, Sunflowers, and Matrix Multiplication

Posted on December 9, 2011 by

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

Joe’s 100th MO question

Posted on July 12, 2011 by

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

Posted on July 10, 2011 by

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.

Posted on June 15, 2011 by

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 , , , , | Leave a comment