Monthly Archives: May 2019

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 , | 19 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 , , | 10 Comments