2023/07/31 by Naszódi, Márton, Szilágyi, Zsombor, Weiner, Mihály
#52C17 #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Information Theory (cs.IT) #Metric Geometry (math.MG) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2307.16857
Motivated by general probability theory, we say that the set S in ℝd is antipodal of rank k, if for any k+1 elements q1,… qk+1∈ S, there is an affine map from conv(S) to the k-dimensional simplex Δk that maps q1,… qk+1 bijectively onto the k+1 vertices of Δ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 ℝd? We present a geometric characterization of antipodal sets of rank k and adapting the argument of Danzer and Grünbaum originally developed for the k=1 case, we prove an upper bound which is exponential in the dimension. We show that this problem can be connected to a classical question in computer science on finding perfect hashes, and it provides a lower bound on the maximum size, which is also exponential in the dimension. By connecting rank-k antipodality to k-neighborly polytopes, we obtain another upper bound when k>d/2.