MATH Seminar

Title: Higher rank antipodality
Seminar: Combinatorics
Speaker: Márton Naszódi of Alfréd Rényi Institute of Mathematics, and Loránd Eötvös University, Budapest
Contact: Liana Yepremyan,
Date: 2024-12-05 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: Motivated by general probability theory, we say that the set $X$ in $\mathbb{R}^d$ is \emph{antipodal of rank $k$}, if for any $k+1$ elements $q_1,\ldots q_{k+1}\in X$, there is an affine map from $\mathrm{conv} X$ to the $k$-dimensional simplex $\Delta_k$ that maps $q_1,\ldots q_{k+1}$ onto the $k+1$ vertices of $\Delta_k$. For $k=1$, it coincides with the well-studied notion of (pairwise) antipodality introduced by Klee.\\ \\ We consider the following natural generalization of Klee's problem on antipodal sets: What is the maximum size of an antipodal set of rank $k$ in $\mathbb{R}^d$? We present a geometric characterization of antipodal sets of rank $k$ and adapting the argument of Danzer and Gr{\"u}nbaum originally developed for the $k=1$ case, we prove an upper bound which is exponential in the dimension. We point out that this problem can be connected to a classical question in computer science on finding \emph{perfect hashes}, and it provides a lower bound on the maximum size, which is also exponential in the dimension. Joint work with Zsombor Szil{\'a}gyi and Mih{\'a}ly Weiner.