Author Archives: Gil Kalai

Itai Benjamini and Jeremie Brieussel: Noise Sensitivity Meets Group Theory

The final  version of my ICM 2018 paper Three puzzles on mathematics computation and games is available for some time. (This proceeding’s version unlike the arXived version has a full list of references.)  In this post I would like to … Continue reading

Posted in Algebra, Combinatorics, Probability | Tagged , , | Leave a comment

Imre Bárány: Limit shape

Limit shapes are fascinating objects in the interface between probability and geometry and between the discrete and the continuous. This post is kindly contributed by Imre Bárány. What is a limit shape? There are finitely many convex lattice polygons contained … Continue reading

Posted in Combinatorics, Convexity, Geometry, Guest blogger, Probability | Tagged , | 2 Comments

Amazing: Hao Huang Proved the Sensitivity Conjecture!

Today’s arXived amazing paper by Hao Huang’s Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture Contains an amazingly short and beautiful proof of a famous open problem from the theory of computing – the sensitivity conjecture posed … Continue reading

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

Another sensation – Annika Heckel: Non-concentration of the chromatic number of a random graph

Annika Heckel Sorry for the long period of non blogging. There are a lot of things to report and  various other plans for posts and I hope to come back to it soon. But it is nice to break the … Continue reading

Posted in Combinatorics | Tagged | Leave a comment

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

Answer to TYI 37: Arithmetic Progressions in 3D Brownian Motion

Consider a Brownian motion in three dimensional space. We asked (TYI 37) What is the largest number of points on the path described by the motion which form an arithmetic progression? (Namely, , so that all are equal.) Here is … Continue reading

Posted in Combinatorics, Open discussion, Probability | Tagged , , | 1 Comment

The last paper of Catherine Rényi and Alfréd Rényi: Counting k-Trees

A k-tree is a graph obtained as follows: A clique with k vertices is a k-tree. A k-tree with n+1 vertices is obtained from a k-tree with n-vertices by adding a new vertex and connecting it to all vertices of a … Continue reading

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

Are Natural Mathematical Problems Bad Problems?

One unique aspect of the conference “Visions in Mathematics Towards 2000” (see the previous post) was that there were several discussion sessions where speakers and other participants presented some thoughts about mathematics (or some specific areas), discussed and argued.  In … Continue reading

Posted in Combinatorics, Conferences, Open discussion, What is Mathematics | Tagged | 1 Comment

An Invitation to a Conference: Visions in Mathematics towards 2000

Let me invite you to a conference. The conference took place in 1999 but only recently the 57 videos of the lectures and the discussion sessions are publicly available. (I thank Vitali Milman for telling me about it.) One novel … Continue reading

Posted in Combinatorics, Conferences, What is Mathematics | Tagged | Leave a comment

The (Random) Matrix and more

Three pictures, and a few related links. Van Vu Spoiler: In one of the most intense scenes, the protagonist, with his bare hands and against all odds, took care of the mighty Wigner semi-circle law in two different ways. (From … Continue reading

Posted in Combinatorics, People, What is Mathematics | Tagged , , , , , , | 1 Comment