Category Archives: Open problems

Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture

Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , | 1 Comment

Ringel Conjecture, Solved! Congratulations to Richard Montgomery, Alexey Pokrovskiy, and Benny Sudakov

Ringel’s conjecture solved (for sufficiently large n) A couple weeks ago and a few days after I heard an excellent lecture about it by Alexey Pokrovskiy in Oberwolfach, the paper A proof of Ringel’s Conjecture by Richard Montgomery, Alexey Pokrovskiy, … Continue reading

Posted in Combinatorics, Open problems, Updates | Tagged , , | 3 Comments

Test your intuition 43: Distribution According to Areas in Top Departments.

  In the community of mamathetitians in a certain country there are mamathetitians in two areas: Anabra (fraction p of the mamathetitians) and Algasis (fraction 1-p of  mamathetitians.) There are ten universities with 50 faculty members in each mamathetics department … Continue reading

Posted in Combinatorics, Open problems, Probability, Test your intuition | Tagged | 9 Comments

Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures

Gérard Cornuéjols Gérard Cornuéjols‘s beautiful (and freely available) book from 2000 Optimization: Packing and Covering is about an important area of combinatorics which is lovely described in the preface to the book The integer programming models known as set packing … Continue reading

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

Richard Ehrenborg’s problem on spanning trees in bipartite graphs

Richard Ehrenborg with a polyhedron In the Problem session last Thursday in Oberwolfach, Steve Klee presented a beautiful problem of Richard Ehrenborg regarding the number of spanning trees in bipartite graphs. Let be a bipartite graph with vertices on one … Continue reading

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

A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture.

Two days ago Nati Linial sent me an email entitled “A sensation in the morning news”. The link was to a new arXived paper by Yaroslav Shitov: Counterexamples to Hedetniemi’s conjecture. Hedetniemi’s 1966 conjecture asserts that if and are two … Continue reading

Posted in Combinatorics, Open problems, Updates | Tagged , | 16 Comments

Cohen, Haeupler, and Schulman: Explicit Binary Tree-Codes & Cancellations

The high-dimensional conference in Jerusalem is running with many exciting talks (and they are videotaped), and today in Tel Aviv there is a conference on Optimization and Discrete Geometry : Theory and Practice. Today in Jerusalem, Leonard Schulman talked (video available!) … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , | 1 Comment

Coloring Problems for Arrangements of Circles (and Pseudocircles)

To supplement and celebrate Aubrey de Grey’s result here are Eight problems on coloring circles A) Consider a finite family of unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are … Continue reading

Posted in Combinatorics, Geometry, Open problems | Tagged , , | 12 Comments

Aubrey de Grey: The chromatic number of the plane is at least 5

  A major progress on an old standing beautiful problem. Aubrey de Grey proved that the chromatic number of the plane is at least 5. (I first heard about it from Alon Amit.) The Hadwiger–Nelson problem asks for the minimum number of … Continue reading

Posted in Combinatorics, Geometry, Open problems, Updates | Tagged , | 11 Comments

Nathan Rubin Improved the Bound for Planar Weak ε-Nets and Other News From Ein-Gedi

I just came back from a splendid visit to Singapore and Vietnam and I will write about it later. While I was away, Nathan Rubin organized a lovely conference on topics closed to my heart  ERC Workshop: Geometric Transversals and Epsilon-Nets with … Continue reading

Posted in Combinatorics, Convexity, Geometry, Open problems | Tagged | 4 Comments