Category Archives: Open problems

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

Posted on March 22, 2020 by

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

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

Posted on January 27, 2020 by

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.

Posted on January 24, 2020 by

  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

Posted on October 13, 2019 by

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

Posted on September 1, 2019 by

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.

Posted on May 10, 2019 by

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

Posted on April 24, 2018 by

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)

Posted on April 13, 2018 by

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

Posted on April 10, 2018 by

  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

Posted on April 5, 2018 by

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