Category Archives: Open problems

A Nice Example Related to the Frankl Conjecture

Update: Peter Frankl brought to my attention that the very same example appeared in a paper by Dynkin and Frankl “Extremal sets of subsets satisfying conditions induced by a graph“. The example As a follow up to my previous post … Continue reading

Posted in Combinatorics, Open discussion, Open problems | Tagged , , , , , , , , , , | 7 Comments

Amazing: Justin Gilmer gave a constant lower bound for the union-closed sets conjecture

Frankl’s conjecture (aka the union closed sets conjecture) asserts that if is a family of subsets of [n] (=: ) which is closed under union then there is an element such that Justin Gilmer just proved an amazing weaker form … Continue reading

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

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

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

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

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 | 3 Comments

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

  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

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

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

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

Test your intuition 43: Distribution According to Areas in Top Departments.

  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

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