The maximal number of geometric permutations for \(n\) disjoint translates of a convex set in \(\mathbb R\) is \(\Omega(n)\) (Q2492643): Difference between revisions

Each non-directed transversal line of a pairwise disjoint family \({\mathcal F}\) of \(n\) convex sets in \({\mathbb R}^d\) intersects the members of \({\mathcal F}\) in an order which can be described by a pair of permutations of \(\{1, 2, \ldots, n\}\) which are reverses of each other. Such a pair is called a geometric permutation. \textit{M. Katchalski, T. Lewis} and \textit{A. Liu} [Discrete Math. 65, 249--259 (1987; Zbl 0619.52002), Discrete Comput. Geom. 7, 197--206 (1992; Zbl 0748.52006)] proved that the maximum number of geometric permutations in families of \(n\) disjoint translates of a convex convex set in \({\mathbb R}^2\) is 3. In their 1992 article, they also conjectured that for each \(d\) there is a constant upper bound on the number of geometric permutations for families of translates in \({\mathbb R}^d\). In this article, the authors disprove this conjecture by showing that for \(d\geq 3\) the maximal number of geometric permutations for such families in \({\mathbb R}^d\) is \(\Omega (n)\).