Category Archives: Open problems

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 | 3 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 , | 15 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 , , | 11 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 | 3 Comments

Frankl’s Conjecture for Large Families: Ilan Karpas’ Proof

Posted on March 9, 2018 by

Frankl’s conjecture asserts that a for every finite family of of finite sets that is closed under union, there is an element that belongs to at least half the sets in the family. We mentioned the problem in our very … Continue reading →

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

Ilan Karpas: Frankl’s Conjecture for Large Families

Posted on December 26, 2017 by

Frankl’s conjecture Frankl’s conjecture is the following: Let be a finite family of finite subsets of which is closed under union, namely,  if then also . Then there exists an element which belongs to at least half the sets in . … Continue reading →

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

Third third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Posted on December 20, 2017 by

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome. Dear all, here is the draft of the third third of my … Continue reading →

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

Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics

Posted on December 10, 2017 by

Peter Frankl (right) and Zoltan Furedi The news A new paper by Nathan Keller and Noam Lifshitz settles several open problems in extremal combinatorics for wide range of parameters. Those include the three problems we mention next. Three central open … Continue reading →

Posted in Combinatorics, Open problems, Updates | Tagged , , , , , , , | 1 Comment