Recent Comments

Recent Posts
 Gil’s Collegial Quantum Supremacy Skepticism FAQ
 Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectationthresholds
 Starting today: Kazhdan Sunday seminar: “Computation, quantumness, symplectic geometry, and information”
 The story of Poincaré and his friend the baker
 Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures
 Noisy quantum circuits: how do we know that we have robust experimental outcomes at all? (And do we care?)
 Test Your Intuition 40: What Are We Celebrating on Sept, 28, 2019? (And answer to TYI39.)
 Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).
 Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.
Top Posts & Pages
 Gil's Collegial Quantum Supremacy Skepticism FAQ
 Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectationthresholds
 Amazing: Hao Huang Proved the Sensitivity Conjecture!
 Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google).
 TYI 30: Expected number of Dice throws
 Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 The story of Poincaré and his friend the baker
 Amazing: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang made dramatic progress on the Sunflower Conjecture
RSS
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
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
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 Hedetniemi's conjecture, Yaroslav Shitov
15 Comments
Cohen, Haeupler, and Schulman: Explicit Binary TreeCodes & Cancellations
The highdimensional 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
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 Geometric combinatorics, geometric graphs, Graphcoloring
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 Aubrey de Grey, The Hadwiger–Nelson problem
11 Comments
Nathan Rubin Improved the Bound for Planar Weak εNets and Other News From EinGedi
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 EpsilonNets with … Continue reading
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
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 Abigail Raz, Frankl's conjecture, Ilan Karpas, Peter Frankl
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 ICM2018, Quantum computers
3 Comments