טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentAndrei Asinowski
SubjectGeometric Permutations in the Plane and in
Euclidean Spaces of Higher Dimension
DepartmentDepartment of Mathematics
Supervisor Professor Emeritus Katchalski Meir


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.