Category Archives: Open problems

Open problem session of HUJI-COMBSEM: Problem #5, Gil Kalai – the 3ᵈ problem

Posted on January 10, 2021 by Gil Kalai

This post continues to describe problems presented at our open problems session back in November 2020. Here is the first post in the series.  Today’s problem was presented by me, and it was an old 1989 conjecture of mine. A … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Geometry, Open problems | 5 Comments

Open problem session of HUJI-COMBSEM: Problem #1, Nati Linial – Turan type theorems for simplicial complexes.

Posted on November 25, 2020 by Gil Kalai

On November, 2020  we had a very nice open problem session in our weekly combinatorics seminar at HUJI.  So I thought to have a series of posts to describe you the problems presented there.  This is the first post in … Continue reading →

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

Péter Pál Pach and Richárd Palincza: a Glimpse Beyond the Horizon

Posted on November 20, 2020 by Gil Kalai

  Prologue Consider the following problems: P3: What is the maximum density of a set A in without a 3-term AP? (AP=arithmetic progression.) This is the celebrated Cap Set problem and we reported here in 2016 the breakthrough results by … Continue reading →

Posted in Combinatorics, Geometry, Number theory, Open problems | Tagged , | 9 Comments

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

Posted on March 22, 2020 by Gil Kalai

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

Posted on January 27, 2020 by Gil Kalai

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 Gil Kalai

  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 Gil Kalai

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 Gil Kalai

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 Gil Kalai

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 , | 17 Comments

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

Posted on April 24, 2018 by Gil Kalai

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