Ph.D Thesis


Ph.D StudentAsinowski Andrei
SubjectGeometric Permutations in the Plane and in
Euclidean Spaces of Higher Dimension
DepartmentDepartment of Mathematics
Supervisor PROFESSOR EMERITUS Meir Katchalski


Abstract

Let A={A1, A2, …, An} be a family of disjoint convex sets in Euclidean space Rd. A straight line l is a transversal of A if it intersects every set in A. Each transversal intersects the members of A in an order which can be described by a pair of permutations of {1, 2, …, n} which are reverses of each other. Such a pair is called a geometric permutation of A.

            It is known that a family of any number of disjoint translates of a convex set in the plane R2 has no more than 3 geometric permutations. It was conjectured that constant bounds exist in higher dimensions. We give a construction in R3 that refutes this conjecture: a family of 2n disjoint translates of a convex set in R3, with n+1 geometric permutations.

            It is known that certain collections of permutations cannot be geometric permutations of the same planar family. We extend this observation to higher dimensions, proving that: (1) for each natural k, each family of k permutations is realizable in R2k-1 (and therefore in higher dimensions); (2) for each natural k, there is a family of k permutations which is non-realizable (forbidden) in R2k-2 (and therefore in lower dimensions as well).

Finally, we study realizable and forbidden families of geometric permutations in R2. We prove two necessary and sufficient conditions for realizability of a family {p, q} of two permutations as geometric permutations of a planar family. Regarding families of more than two permutations, we give two necessary conditions for realizability in R2, and show by an example that they are not sufficient.