Abstract

Consider 4 grasshoppers sitting at the vertices of a square. In a "legal move'', any one of them can jump over another, and land on its other side at exactly the same distance. After a finite number of legal moves, can the grasshoppers end up at the vertices of a larger square? This is a well known puzzle, and the answer is no. Using a linear algebraic approach, Gábor Tardos and I answered the question of Florestan Brunck: What happens if the grasshoppers originally sit at the vertices of a regular $n$-gon ($n>4$) ? Given $n$ sets $X_1,..., X_n$, we call the elements of $S=X_1\times...\times X_n$ strings. A nonempty set of strings $W \subseteq S$ is said to be "well-connected'' if for every $v \in W$and for every i, there is another element $v' \in W$ which differs from $v$ only in its $i$-th coordinate. Peter Frankl and I used the Linear Algebra Method to prove a conjecture of Yaokun Wu and Yanzhen Xiong by showing that every set of more than $$\prod_{i=1}^n|X_i|-\prod_{i=1}^n(|X_i|-1)$$ strings has a well-connected subset. This bound is tight.

Speaker Intro

János Pach is Research Adviser at Rényi Institute, Budapest. His main fields of interest are discrete and computational geometry, convexity, and combinatorics. He wrote more than 300 research papers. His books, “Research Problems in Discrete Geometry” (with Brass and Moser) and “Combinatorial Geometry” (with Agarwal) were translated into Japanese, Russian, and Chinese. He is co-editor-in-chief of Discrete & Computational Geometry and serves on the editorial boards of ten other professional journals. He was elected ACM Fellow (2011), member of Academia Europeae (2014), Hungarian Academy of Sciences (2022), and AMS Fellow (2015). He was invited speaker at the International Congress of Mathematicians in Seoul (2014), and was Plenary Speaker at the European Congress of Mathematics in Portorož (2021).