Category Archives: Open problems

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

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

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

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

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