New Bounds on the Katchalski—Lewis Transversal Problem

   Abstract. In 1980 Katchalski and Lewis showed the following: if each three members of a family of disjoint translates in the plane are met by a line, then there exists a line meeting all but at most k members of F, where k is some positive constant independent of the family. They also showed that k can be taken to be less than 603, and conjectured that k=2 is a universal bound for all such families. In 1990 Tverberg improved the upper bound by showing that k≤ 108 holds. We make further improvements on the upper bound of k , showing that k≤ 22 . Finally, we give a construction of a family of disjoint translates of a parallelogram, each three being met by a line, but where any line misses at least four members. This provides a counterexample to the Katchalski—Lewis conjecture.     

The Katchalski-Lewis Transversal Problem in R<Superscript>n</Superscript>

Let F be a family of disjoint translates of a compact convex set in the plane. In 1980 Katchalski and Lewis showed that there exists a constant k, independent of F, such that if each three members of F are met by a line, then a "large" subfamily G ⊂ F, with |F\G| ≤ k, is met by a line. In this paper we obtain a higher-dimensional analogue containing the Katchalski-Lewis result. Also we give two constructions of families of pairwise disjoint translates of the unit ball in R³ which answer some related questions.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

   Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

Proof of the Katchalski-Lewis Transversal Conjecture for T(3)-Families of Congruent Discs

A family of disjoint closed congruent discs is said to have property T(3) if to every triple of discs there exists a common line transversal. Katchalski and Lewis [10] proved the existence of a constant m_disc such that to every family of disjoint closed congruent discs with property T(3) a straight line can be found meeting all but at most m_disc of the members of the family. They conjectured that this is true even with m_disc = 2. On one hand Bezdek [1] proved m_disc ≥ 2 in 1991 and on the other hand Kaiser [9] showed m_disc ≤ 12 in a recent paper. The present work is devoted to proving this conjecture showing that m_disc ≤ 2.     

A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets

Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P _k (n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P ₃ (n) < 16 ⁿ . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p437.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received March 27, 1997, and in revised form July 10, 1997.     

Categoricity,amalgamation, and tameness

Theorem: For each 2 ≤ k < ω there is an -sentence ϕ_k such that (1) ϕ_k is categorical in μ if μ≤ℵ_k−2; (2) ϕ_k is not ℵ_k−2-Galois stable (3) ϕ_k is not categorical in any μ with μ>ℵ_k−2; (4) ϕ_k has the disjoint amalgamation property (5) For k > 2 (a) ϕ_k is (ℵ₀, ℵ_k−3)-tame; indeed, syntactic first-order types determine Galois types over models of cardinality at most ℵ_k−3; (b) ϕ_k is ℵ_m-Galois stable for m ≤ k − 3 (c) ϕ_k is not (ℵ_k−3, ℵ_k−2). The first author is partially supported by NSF grant DMS-0500841.     

Polytopes in Arrangements

Consider an arrangement of n hyperplanes in \real ^d . Families of convex polytopes whose boundaries are contained in the union of the hyperplanes are the subject of this paper. We aim to bound their maximum combinatorial complexity. Exact asymptotic bounds were known for the case where the polytopes are cells of the arrangement. Situations where the polytopes are pairwise openly disjoint have also been considered in the past. However, no nontrivial bound was known for the general case where the polytopes may have overlapping interiors, for d>2 . We analyze families of polytopes that do not share vertices. In \real ³ we show an O(k ^1/3 n ² ) bound on the number of faces of k such polytopes. We also discuss worst-case lower bounds and higher-dimensional versions of the problem. Among other results, we show that the maximum number of facets of k pairwise vertex-disjoint polytopes in \real ^d is Ω(k ^1/2 n ^d/2 ) which is a factor of away from the best known upper bound in the range n ^d-2 ≤ k ≤ n ^d . The case where 1≤ k ≤ n ^d-2 is completely resolved as a known Θ(kn) bound for cells applies here. Received September 20, 1999, and in revised form March 10, 2000. Online publication September 22, 2000.     

Line Transversals to Unit Disks

Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.     

Line Transversals to Unit Disks

   Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.