Category Archives: Combinatorics

Nostalgia corner: John Riordan’s referee report of my first paper

Posted on February 19, 2021 by Gil Kalai

In 1971/1972 academic year, I was an undergraduate student at the Hebrew University of Jerusalem and toward the end of the year I wrote a paper about Abel’s sums. I sent it to John Riordan the author of the books  … Continue reading →

Posted in Combinatorics, personal | Tagged , , , | 7 Comments

To cheer you up in difficult times 20: Ben Green presents super-polynomial lower bounds for off-diagonal van der Waerden numbers W(3,k)

Posted on February 8, 2021 by Gil Kalai

What will be the next polymath project? click here for our post about it.  New lower bounds for van der Waerden numbers by Ben Green Abstract: We show that there is a red-blue colouring of [N] with no blue 3-term … Continue reading →

Posted in Combinatorics, Number theory | Tagged , | 2 Comments

To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger corner-free sets from better numbers-on-the-forehead protocols

Posted on February 3, 2021 by Gil Kalai

What will be the next polymath project? click here for our previous post.  Number on the forehead, communication complexity, and additive combinatorics Larger Corner-Free Sets from Better NOF Exactly-N Protocols, by Nati Linial and Adi Shraibman Abstract: A subset of … Continue reading →

Posted in Combinatorics, Computer Science and Optimization | Tagged , | 3 Comments

Possible future Polymath projects (2009, 2021)

Posted on January 29, 2021 by Gil Kalai

What will be our next polymath project? A polymath project (Wikipedia) is a collaboration among mathematicians to solve important and difficult mathematical problems by coordinating many mathematicians to communicate with each other on finding the best route to the solution. … Continue reading →

Posted in Combinatorics, Mathematics over the Internet, Open discussion | Tagged , , | 22 Comments

Amazing: Simpler and more general proofs for the g-theorem by Stavros Argyrios Papadakis and Vasiliki Petrotou, and by Karim Adiprasito, Stavros Argyrios Papadakis, and Vasiliki Petrotou.

Posted on January 21, 2021 by Gil Kalai

Stavros Argyrios Papadakis, Vasiliki Petrotou, and Karim Adiprasito In 2018, I reported here about Karim Adiprasito’s proof of the g-conjecture for simplicial spheres.  This conjecture by McMullen from 1970 was considered a holy grail of algebraic combinatorics and it resisted … Continue reading →

Posted in Algebra, Combinatorics, Geometry | Tagged , , , , | 4 Comments

Igor Pak: What if they are all wrong?

Posted on January 19, 2021 by Gil Kalai

Originally posted on Igor Pak's blog:
Conjectures are a staple of mathematics. They are everywhere, permeating every area, subarea and subsubarea. They are diverse enough to avoid a single general adjective. They come in al shapes and sizes. Some…

Posted in Combinatorics, Computer Science and Optimization, Geometry, What is Mathematics | Tagged | 6 Comments

To cheer you up in difficult times 17: Amazing! The Erdős-Faber-Lovász conjecture (for large n) was proved by Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus!

Posted on January 14, 2021 by Gil Kalai

Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus have just uploaded a paper to the arXive, A proof of the Erdős-Faber-Lovász conjecture. (I am thankful to Nati Linial and Ryan Alweiss for telling me about it.) … Continue reading →

Posted in Combinatorics, Updates | Tagged , , , , , | 2 Comments

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

The Argument Against Quantum Computers – A Very Short Introduction

Posted on December 29, 2020 by Gil Kalai

Left: Gowers’s book Mathematics a very short introduction. Right C. elegans; Boson Sampling can be seen as the C. elegans of quantum computing. (See, this paper.) Update (January 6, 2021): Tomorrow January, 7, 8:30 AM Israel time, I give a … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Physics, Probability, Quantum | Tagged , | 7 Comments

Open problem session of HUJI-COMBSEM: Problem #4, Eitan Bachmat: Weighted Statistics for Permutations

Posted on December 26, 2020 by Gil Kalai

This is a continuation of our series of posts on the HUJI seminar 2020 open problems. This time the post was kindly written by Eitan Bachmat who proposed the problem.  My summary: understanding of the distribution of largest increasing subsequences … Continue reading →

Posted in Combinatorics, Guest blogger, Probability | Tagged | 4 Comments