Author Archives: Gil Kalai

Test Your Intuition about the Alon-Tarsi Conjecture

On the occasion of Polymath 12 devoted to the Rota basis conjecture let me remind you about the Alon-Tarsi conjecture and test your intuition concerning a strong form of the conjecture. The sign of a Latin square is the product … Continue reading

Posted in Combinatorics, Open problems, Test your intuition | Tagged , | Leave a comment

Thilo Weinert: Transfinite Ramsey Numbers

This is first of three posts kindly written by Thilo Weinert Recently Gil asked me whether I would like to contribute to his blog and I am happy to do so. I enjoy both finite and infinite combinatorics and it … Continue reading

Posted in Combinatorics, Guest post, Logic and set theory | Tagged | 3 Comments

Timothy Chow Launched Polymath12 on Rota Basis Conjecture and Other News

Polymath12 Timothy Chow launched polymath12 devoted to the Rota Basis conjecture on the polymathblog. A classic paper on the subject is the 1989 paper by Rosa Huang and Gian Carlo-Rota. Let me mention a strong version of Rota’s conjecture (Conjecture … Continue reading

Posted in Combinatorics, Mathematics over the Internet, Movies, Music, Sport, Updates | Tagged | Leave a comment

Proof By Lice!

From camels to lice. (A proof promised here.) Theorem (Hopf and Pannwitz, 1934): Let be a set of points in the plane  in general position (no three points on a line) and consider line segments whose endpoints are in .  Then … Continue reading

Posted in Combinatorics, What is Mathematics | Tagged | 5 Comments

The seventeen camels riddle, and Noga Alon’s camel proof and algorithms

Three children inherited 17 camels. The will gave one half to one child, one third to a second child and one ninth to the third. The children did not know what to do and  a neighbor offered to lend them … Continue reading

Posted in Combinatorics | Tagged | 4 Comments

Edmund Landau and the Early Days of the Hebrew University of Jerusalem

Some personal/historical remarks in  first minutes of my lecture at 7ECM on July 2016… German-Jewish mathematicians in the early days of the Hebrew University of Jerusalem Being invited to give a plenary lecture at the 7ECM was a great honor … Continue reading

Posted in Academics, Combinatorics, personal | Tagged | 4 Comments

Boolean Functions: Influence, Threshold, and Noise

Here is the written version of my address at the 7ECM last July in Berlin. Boolean functions, Influence, threshold, and Noise Trying to follow an example of a 1925 lecture by Landau (mentioned in the lecture), the writing style is very … Continue reading

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

Laci Babai Visits Israel!

  I am sure that every one of the readers of this blog heard about Laci Babai’s quasi-polynomial algorithm for graph isomorphism and also the recent drama about it: A mistake pointed out by Harald Helfgott,  a new sub-exponential but … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , | 2 Comments

Polymath10 conclusion

The Polymath10 project on the Erdos-Rado Delta-System conjecture took place over this blog from November 2015 to May 2016. I aimed for an easy-going project that people could participate calmly aside from their main research efforts and  the duration of … Continue reading

Posted in Combinatorics, Open problems, Polymath10 | Tagged , | 4 Comments

Is Heads-Up Poker in P?

Five years ago I wrote a post entitled Is Backgammon in P? It was based on conversations with Peter Bro Miltersen and Uri Zwick (shown together in the above picture) about the computational complexity of computing the values (and equilibrium … Continue reading

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