Namespaces
Variants
Actions

Difference between revisions of "Geometric transversal theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 123 formulas out of 123 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
 
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 123 formulas, 123 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|done}}
 
A theory having its origin in a beautiful theorem of E. Helly in combinatorial geometry and a provocative question by P. Vincensini whose answer turned out to be negative.
 
A theory having its origin in a beautiful theorem of E. Helly in combinatorial geometry and a provocative question by P. Vincensini whose answer turned out to be negative.
  
Helly's theorem states [[#References|[a14]]]: If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300501.png" /> is a collection of compact convex sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300502.png" />, every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300503.png" /> or fewer members of which have a point in common, then there is a point common to all the members of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300504.png" />.
+
Helly's theorem states [[#References|[a14]]]: If $\mathcal{A}$ is a collection of compact convex sets in $\mathbf{R} ^ { d }$, every $d + 1$ or fewer members of which have a point in common, then there is a point common to all the members of $\mathcal{A}$.
  
A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300506.png" />-transversal to a collection of sets is a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300507.png" />-flat (cf. [[Higher-dimensional geometry|Higher-dimensional geometry]]) that meets every set in the collection. With this notion Helly's theorem can be reformulated to assert that if every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300508.png" /> or fewer members of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g1300509.png" /> have a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005010.png" />-transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005011.png" /> has a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005012.png" />-transversal. In 1935, Vincensini [[#References|[a17]]] asked whether there was a corresponding theorem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005013.png" />-transversals to a collection of convex sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005014.png" />: Does there exist an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005015.png" /> such that for every collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005016.png" /> of compact convex sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005017.png" />, if every subcollection of at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005018.png" /> members of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005019.png" /> has a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005020.png" />-transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005021.png" /> has a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005022.png" />-transversal?
+
A $k$-transversal to a collection of sets is a $k$-flat (cf. [[Higher-dimensional geometry|Higher-dimensional geometry]]) that meets every set in the collection. With this notion Helly's theorem can be reformulated to assert that if every $d + 1$ or fewer members of $\mathcal{A}$ have a $0$-transversal, then $\mathcal{A}$ has a $0$-transversal. In 1935, Vincensini [[#References|[a17]]] asked whether there was a corresponding theorem for $k$-transversals to a collection of convex sets in $\mathbf{R} ^ { d }$: Does there exist an $r = r ( k , d )$ such that for every collection $\mathcal{A}$ of compact convex sets in $\mathbf{R} ^ { d }$, if every subcollection of at most $r$ members of $\mathcal{A}$ has a $k$-transversal, then $\mathcal{A}$ has a $k$-transversal?
  
Vincensini gave an incorrect proof that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005023.png" />. Subsequently, several examples showed that no finite <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005024.png" /> exists, even if it is assumed that the sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005025.png" /> are pairwise disjoint. It is perhaps counterintuitive that the existence of such a number should depend on whether the sets are pairwise disjoint; however, L. Danzer [[#References|[a4]]] pointed out that although families of disjoint unit discs in the plane admit such a number (see below), there are examples, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005026.png" /> arbitrarily large, of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005027.png" /> unit discs in the plane (not disjoint) that do not have a line transversal even though any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005028.png" /> of them do. He also gave examples of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005029.png" /> disjoint unit balls in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005030.png" /> that have no plane transversal even though any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005031.png" /> of them do, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005032.png" /> arbitrarily large.
+
Vincensini gave an incorrect proof that $r ( 1,2 ) = 6$. Subsequently, several examples showed that no finite $r ( 1,2 )$ exists, even if it is assumed that the sets of $\mathcal{A}$ are pairwise disjoint. It is perhaps counterintuitive that the existence of such a number should depend on whether the sets are pairwise disjoint; however, L. Danzer [[#References|[a4]]] pointed out that although families of disjoint unit discs in the plane admit such a number (see below), there are examples, with $m$ arbitrarily large, of $m + 1$ unit discs in the plane (not disjoint) that do not have a line transversal even though any $m$ of them do. He also gave examples of $m + 1$ disjoint unit balls in $\mathbf{R} ^ { 3 }$ that have no plane transversal even though any $m$ of them do, for $m$ arbitrarily large.
  
With hopes dashed for a generalization of Helly's theorem in the form proposed by Vincensini, other Helly-type transversal theorems were found, where the elements of the collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005033.png" /> were subject to significant restrictions on either their shape or their relative position. Some noteworthy examples of such theorems are as follows.
+
With hopes dashed for a generalization of Helly's theorem in the form proposed by Vincensini, other Helly-type transversal theorems were found, where the elements of the collection $\mathcal{A}$ were subject to significant restrictions on either their shape or their relative position. Some noteworthy examples of such theorems are as follows.
  
 
===Santaló's theorem.===
 
===Santaló's theorem.===
([[#References|[a15]]]) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005034.png" /> be a collection of parallel rectangles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005035.png" />. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005036.png" /> or fewer elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005037.png" /> admit a line transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005038.png" /> admits a line transversal. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005039.png" /> cannot be reduced in general.
+
([[#References|[a15]]]) Let $\mathcal{A}$ be a collection of parallel rectangles in $\mathbf{R} ^ { 2 }$. If every $6$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ admits a line transversal. The number $6$ cannot be reduced in general.
  
 
This generalizes in two directions to:
 
This generalizes in two directions to:
  
a) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005040.png" /> be a collection of parallelotopes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005041.png" /> with edges parallel to the coordinate axes. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005042.png" /> or fewer elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005043.png" /> admit a line transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005044.png" /> admits a line transversal.
+
a) Let $\mathcal{A}$ be a collection of parallelotopes in $\mathbf{R} ^ { d }$ with edges parallel to the coordinate axes. If every $2 ^ { d - 1 } ( 2 d - 1 )$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ admits a line transversal.
  
b) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005045.png" /> be a collection of parallelotopes in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005046.png" /> with edges parallel to the coordinate axes. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005047.png" /> or fewer elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005048.png" /> admit a hyperplane transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005049.png" /> admits a hyperplane transversal.
+
b) Let $\mathcal{A}$ be a collection of parallelotopes in $\mathbf{R} ^ { d }$ with edges parallel to the coordinate axes. If every $2 ^ { d - 1 } ( d + 1 )$ or fewer elements of $\mathcal{A}$ admit a hyperplane transversal, then $\mathcal{A}$ admits a hyperplane transversal.
  
 
===Hadwiger's theorem.===
 
===Hadwiger's theorem.===
([[#References|[a11]]], [[#References|[a5]]]) Suppose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005050.png" /> is a collection of compact convex sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005051.png" /> whose union is unbounded, each having diameter bounded by a constant. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005052.png" /> or fewer sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005053.png" /> have a line transversal, then all the sets do.
+
([[#References|[a11]]], [[#References|[a5]]]) Suppose $\mathcal{A}$ is a collection of compact convex sets in $\mathbf{R} ^ { d }$ whose union is unbounded, each having diameter bounded by a constant. If every $d + 1$ or fewer sets of $\mathcal{A}$ have a line transversal, then all the sets do.
  
 
===Grünbaum's theorem.===
 
===Grünbaum's theorem.===
 
([[#References|[a6]]], [[#References|[a10]]])
 
([[#References|[a6]]], [[#References|[a10]]])
  
a) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005054.png" /> be a collection of compact convex sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005055.png" />, each lying in one of a collection of parallel hyperplanes. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005056.png" /> or fewer sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005057.png" /> have a line transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005058.png" /> has a line transversal.
+
a) Let $\mathcal{A}$ be a collection of compact convex sets in $\mathbf{R} ^ { d }$, each lying in one of a collection of parallel hyperplanes. If every $2 d - 1$ or fewer sets of $\mathcal{A}$ have a line transversal, then $\mathcal{A}$ has a line transversal.
  
b) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005059.png" /> be a collection of pairwise disjoint translates of a parallelogram. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005060.png" /> or fewer elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005061.png" /> admit a line transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005062.png" /> has a line transversal.
+
b) Let $\mathcal{A}$ be a collection of pairwise disjoint translates of a parallelogram. If every $5$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.
  
 
===Danzer's theorem.===
 
===Danzer's theorem.===
([[#References|[a4]]]) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005063.png" /> be a collection of pairwise disjoint unit discs in the plane. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005064.png" /> or fewer elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005065.png" /> admit a line transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005066.png" /> has a line transversal.
+
([[#References|[a4]]]) Let $\mathcal{A}$ be a collection of pairwise disjoint unit discs in the plane. If every $5$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.
  
 
==Grünbaum conjecture.==
 
==Grünbaum conjecture.==
In view of these last two theorems, it was natural for B. Grünbaum to conjecture, in 1958 [[#References|[a6]]], that for a collection of disjoint translates of a convex set, if every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005067.png" /> or fewer sets of the collection admit a line transversal, then the entire collection has a line transversal.
+
In view of these last two theorems, it was natural for B. Grünbaum to conjecture, in 1958 [[#References|[a6]]], that for a collection of disjoint translates of a convex set, if every $5$ or fewer sets of the collection admit a line transversal, then the entire collection has a line transversal.
  
 
This conjecture remained open for over 30 years and its eventual solution involved an idea that had first appeared in a theorem of H. Hadwiger. The key observation is that while, without additional assumptions, a Helly-type theorem does not hold for arbitrary convex sets in the plane, by imposing a consistency condition on the order in which triples of a collection of convex sets are met by a line, one can recover the Helly property:
 
This conjecture remained open for over 30 years and its eventual solution involved an idea that had first appeared in a theorem of H. Hadwiger. The key observation is that while, without additional assumptions, a Helly-type theorem does not hold for arbitrary convex sets in the plane, by imposing a consistency condition on the order in which triples of a collection of convex sets are met by a line, one can recover the Helly property:
  
 
===Hadwiger's transversal theorem.===
 
===Hadwiger's transversal theorem.===
([[#References|[a12]]]) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005068.png" /> be a finite collection of pairwise disjoint convex sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005069.png" />. If there exists a linear ordering of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005070.png" /> such that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005071.png" /> members of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005072.png" /> are met by a directed line in the corresponding order, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005073.png" /> has a line transversal.
+
([[#References|[a12]]]) Let $\mathcal{A}$ be a finite collection of pairwise disjoint convex sets in $\mathbf{R} ^ { 2 }$. If there exists a linear ordering of $\mathcal{A}$ such that every $3$ members of $\mathcal{A}$ are met by a directed line in the corresponding order, then $\mathcal{A}$ has a line transversal.
  
 
A line transversal to any collection of disjoint convex sets meets the sets in a given order or its reverse, depending on the direction of the transversal. This pair of orders (permutations) is called a geometric permutation. Building on the fact that disjoint translates admit only few geometric permutations, H. Tverberg was able to prove Grünbaum's conjecture.
 
A line transversal to any collection of disjoint convex sets meets the sets in a given order or its reverse, depending on the direction of the transversal. This pair of orders (permutations) is called a geometric permutation. Building on the fact that disjoint translates admit only few geometric permutations, H. Tverberg was able to prove Grünbaum's conjecture.
  
 
===Tverberg's theorem.===
 
===Tverberg's theorem.===
([[#References|[a16]]]) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005074.png" /> be a collection of disjoint translates of a convex set in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005075.png" />. If every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005076.png" /> or fewer members of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005077.png" /> admit a line transversal, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005078.png" /> has a line transversal.
+
([[#References|[a16]]]) Let $\mathcal{A}$ be a collection of disjoint translates of a convex set in $\mathbf{R} ^ { 2 }$. If every $5$ or fewer members of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.
  
 
==Hyperplane transversals.==
 
==Hyperplane transversals.==
Hadwiger's transversal theorem restored the generality and simplicity of Helly's theorem to the situation of Vincensini's problem. While it has been shown that no theorem of Hadwiger type holds for line transversals in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005079.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005080.png" />, it turns out nevertheless that Hadwiger's theorem does generalize to hyperplane transversals in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005081.png" />. This requires a notion of order for finite point sets in higher dimensions.
+
Hadwiger's transversal theorem restored the generality and simplicity of Helly's theorem to the situation of Vincensini's problem. While it has been shown that no theorem of Hadwiger type holds for line transversals in $\mathbf{R} ^ { d }$ for $d \geq 3$, it turns out nevertheless that Hadwiger's theorem does generalize to hyperplane transversals in $\mathbf{R} ^ { d }$. This requires a notion of order for finite point sets in higher dimensions.
  
By the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005083.png" />-order type of a numbered set of points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005084.png" /> is meant the family of orientations of its <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005085.png" />-tuples, i.e., the collection
+
By the $k$-order type of a numbered set of points $P = \{ p _ { 1 } , \dots , p _ { n } \} \subset \mathbf{R} ^ { k }$ is meant the family of orientations of its $( k + 1 )$-tuples, i.e., the collection
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005086.png" /></td> </tr></table>
+
\begin{equation*} \left( \text{sign det} \left( \begin{array} { c c c c } { 1 } &amp; { p _ { i_0 } ^ { 1 } } &amp; { \dots } &amp; { p _ { i_0 } ^ { k } } \\ { \vdots } &amp; { \vdots } &amp; { \ddots } &amp; { \vdots } \\ { 1 } &amp; { p _ { i_k } ^ { 1 } } &amp; { \cdots } &amp; { p _ { i_ k } ^ { k } } \end{array} \right) \right) _ { 1 \leq i _ { 0 } &lt; \ldots &lt; i _ { k } \leq n } . \end{equation*}
  
This order type is simple if the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005088.png" /> lies in [[General position|general position]] in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005089.png" />, i.e., if every determinant is non-zero.
+
This order type is simple if the set $P$ lies in [[General position|general position]] in $\mathbf{R} ^ { k }$, i.e., if every determinant is non-zero.
  
A generalization of disjointness is also needed. Just as every directed line transversal to a collection of convex sets meets the sets in a unique, well-defined order if and only if the sets are disjoint, every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005090.png" />-transversal will meet them in a unique, simple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005091.png" />-ordering if and only if no <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005092.png" /> sets of the collection admit a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005093.png" />-transversal; such a collection is said to be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005095.png" />-separated. Thus, a collection is pairwise disjoint if and only if it is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005096.png" />-separated.
+
A generalization of disjointness is also needed. Just as every directed line transversal to a collection of convex sets meets the sets in a unique, well-defined order if and only if the sets are disjoint, every $k$-transversal will meet them in a unique, simple $k$-ordering if and only if no $k + 1$ sets of the collection admit a $( k - 1 )$-transversal; such a collection is said to be $( k - 1 )$-separated. Thus, a collection is pairwise disjoint if and only if it is $0$-separated.
  
 
With these definitions, J.E. Goodman and R. Pollack proved the following generalization of Hadwiger's transversal theorem in arbitrary dimension.
 
With these definitions, J.E. Goodman and R. Pollack proved the following generalization of Hadwiger's transversal theorem in arbitrary dimension.
  
 
===Goodman–Pollack theorem.===
 
===Goodman–Pollack theorem.===
([[#References|[a7]]]) A <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005097.png" />-separated collection <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005098.png" /> of compact convex sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g13005099.png" /> has a hyperplane transversal if and only if there is a one-to-one correspondence between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050100.png" /> and a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050101.png" /> of points in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050102.png" /> such that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050103.png" /> sets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050104.png" /> are met by an oriented hyperplane consistently with the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050105.png" />-ordering induced on the corresponding points of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050106.png" />.
+
([[#References|[a7]]]) A $( d - 2 )$-separated collection $\mathcal{A}$ of compact convex sets in $\mathbf{R} ^ { d }$ has a hyperplane transversal if and only if there is a one-to-one correspondence between $\mathcal{A}$ and a set $S$ of points in $\mathbf{R} ^ { d-1 } $ such that every $d + 1$ sets of $\mathcal{A}$ are met by an oriented hyperplane consistently with the $( d - 1 )$-ordering induced on the corresponding points of $S$.
  
For this to hold, moreover, it is sufficient to find an acyclic rank-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050107.png" /> oriented [[Matroid|matroid]] structure on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050108.png" /> whose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050109.png" />-tuples satisfy the consistency condition of the theorem. (For the notion of oriented matroid, which can be thought of as a  "locally realizable"  generalization of the order type of a set of points, see also [[#References|[a3]]].)
+
For this to hold, moreover, it is sufficient to find an acyclic rank-$d$ oriented [[Matroid|matroid]] structure on $\mathcal{A}$ whose $( d + 1 )$-tuples satisfy the consistency condition of the theorem. (For the notion of oriented matroid, which can be thought of as a  "locally realizable"  generalization of the order type of a set of points, see also [[#References|[a3]]].)
  
 
This theorem was subsequently generalized in several directions, the most comprehensive statement (which subsumes intermediate results of M. Katchalski and of Pollack and R. Wenger) being:
 
This theorem was subsequently generalized in several directions, the most comprehensive statement (which subsumes intermediate results of M. Katchalski and of Pollack and R. Wenger) being:
  
 
===Anderson–Wenger theorem.===
 
===Anderson–Wenger theorem.===
([[#References|[a2]]]) Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050110.png" /> be a finite collection of connected sets in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050111.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050112.png" /> has a hyperplane transversal if and only if for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050113.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050114.png" />, there exists a rank-<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050115.png" /> acyclic oriented matroid structure on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050116.png" /> such that every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050117.png" /> members of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050118.png" /> are met by an oriented <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050119.png" />-flat consistently with that oriented matroid structure.
+
([[#References|[a2]]]) Let $\mathcal{A}$ be a finite collection of connected sets in $\mathbf{R} ^ { d }$. $\mathcal{A}$ has a hyperplane transversal if and only if for some $k$, $0 \leq k &lt; d$, there exists a rank-$( k + 1 )$ acyclic oriented matroid structure on $\mathcal{A}$ such that every $k + 2$ members of $\mathcal{A}$ are met by an oriented $k$-flat consistently with that oriented matroid structure.
  
 
==Other directions.==
 
==Other directions.==
An effort to understand intermediate-dimensional transversals leads to considering the set of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050120.png" />-transversals to a collection of convex sets. While there are as yet (2000) very few non-trivial results about transversals of dimensions between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050121.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050122.png" />, there is a good deal known about the structure of these complete sets of transversals to collections of convex sets. It turns out that these subsets of the  "affine Grassmannian"  themselves behave very much like convex point sets. Although they need not be connected, they nevertheless share many properties with convex sets, such as being defined by a convex hull operator satisfying the anti-exchange property that commutes with non-singular affine transformations, and satisfying the Krein–Mil'man theorem [[#References|[a8]]] (cf. also [[Locally convex space|Locally convex space]]).
+
An effort to understand intermediate-dimensional transversals leads to considering the set of all $k$-transversals to a collection of convex sets. While there are as yet (2000) very few non-trivial results about transversals of dimensions between $1$ and $d - 1$, there is a good deal known about the structure of these complete sets of transversals to collections of convex sets. It turns out that these subsets of the  "affine Grassmannian"  themselves behave very much like convex point sets. Although they need not be connected, they nevertheless share many properties with convex sets, such as being defined by a convex hull operator satisfying the anti-exchange property that commutes with non-singular affine transformations, and satisfying the Krein–Mil'man theorem [[#References|[a8]]] (cf. also [[Locally convex space|Locally convex space]]).
  
 
Other streams in geometric transversal theory include:
 
Other streams in geometric transversal theory include:
Line 74: Line 82:
 
Gallai-type theorems, in which a Helly-type hypothesis leads to the conclusion that several transversals cover the entire collection (see [[#References|[a1]]], [[#References|[a18]]]);
 
Gallai-type theorems, in which a Helly-type hypothesis leads to the conclusion that several transversals cover the entire collection (see [[#References|[a1]]], [[#References|[a18]]]);
  
the more general theorems of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050124.png" /> type, in which a hypothesis of the form  "for every choice of p sets from the collection, some q have a common transversal"  leads to a Gallai-type conclusion (see [[#References|[a1]]], [[#References|[a18]]]);
+
the more general theorems of $( p , q )$ type, in which a hypothesis of the form  "for every choice of p sets from the collection, some q have a common transversal"  leads to a Gallai-type conclusion (see [[#References|[a1]]], [[#References|[a18]]]);
  
 
generalizations from transversal flats to transversal curves and surfaces (see [[#References|[a9]]]);
 
generalizations from transversal flats to transversal curves and surfaces (see [[#References|[a9]]]);
Line 80: Line 88:
 
ongoing work of L. Montejano on a topological generalization of Hadwiger's transversal theorem and on the related notion of a  "separoid" ;
 
ongoing work of L. Montejano on a topological generalization of Hadwiger's transversal theorem and on the related notion of a  "separoid" ;
  
the problem of bounding the number of geometric permutations of a collection of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050125.png" /> convex bodies in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050126.png" />, and its generalization (via order types) to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050127.png" />-transversals (see [[#References|[a19]]]);
+
the problem of bounding the number of geometric permutations of a collection of $n$ convex bodies in $\mathbf{R} ^ { d }$, and its generalization (via order types) to $k$-transversals (see [[#References|[a19]]]);
  
 
algorithmic geometric transversal theory, a branch of [[Computational geometry|computational geometry]] (see [[#References|[a19]]]).
 
algorithmic geometric transversal theory, a branch of [[Computational geometry|computational geometry]] (see [[#References|[a19]]]).
Line 87: Line 95:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Eckhoff,  "Helly, Radon, and Carathéodory type theorems"  P.M. Gruber (ed.)  J.M. Wills (ed.) , ''Handbook of Convex Geometry'' , North-Holland  (1993)  pp. 389–448</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. Anderson,  R. Wenger,  "Oriented matroids and hyperplane transversals"  ''Adv. Math.'' , '''119'''  (1996)  pp. 117–125</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Björner,  M. Las Vergnas,  N. White,  B. Sturmfels,  G.M. Ziegler,  "Oriented matroids" , Cambridge Univ. Press  (1993)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  L. Danzer,  "Über ein Problem aus der kombinatorischen Geometrie"  ''Archiv Math.'' , '''8'''  (1957)  pp. 347–351</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  L. Danzer,  B. Grünbaum,  V. Klee,  "Helly's theorem and its relatives"  V. Klee (ed.) , ''Convexity'' , ''Proc. Symp. Pure Math.'' , '''7''' , Amer. Math. Soc.  (1963)  pp. 101–180</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  B. Grünbaum,  "On common transversals."  ''Archiv Math.'' , '''9'''  (1958)  pp. 465–469</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  J.E. Goodman,  R. Pollack,  "Hadwiger's transversal theorem in higher dimensions"  ''J. Amer. Math. Soc.'' , '''1'''  (1988)  pp. 301–309</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  J.E. Goodman,  R. Pollack,  "Foundations of a theory of convexity on affine Grassmann manifolds"  ''Mathematika'' , '''42'''  (1995)  pp. 305–328</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  J.E. Goodman,  R. Pollack,  R. Wenger,  "Geometric transversal theory"  J. Pach (ed.) , ''New Trends in Discrete and Computational Geometry'' , '''10: Algorithms and Combinatorics''' , Springer  (1993)  pp. 163–198</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  B. Grünbaum,  "Common transversals for families of sets."  ''J. London Math. Soc.'' , '''35'''  (1960)  pp. 408–416</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  H. Hadwiger,  "Über einen Satz Hellyscher Art."  ''Archiv Math.'' , '''7'''  (1956)  pp. 377–379</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  H. Hadwiger,  "Über Eibereiche mit gemeinsamer Treffgeraden"  ''Portugal. Math.'' , '''16'''  (1957)  pp. 23–29</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  H. Hadwiger,  H. Debrunner,  V. Klee,  "Combinatorial geometry in the plane" , Holt, Rinehart &amp; Winston  (1964)</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  E. Helly,  "Über Mengen konvexen Körper mit gemeinschaftlichen Punkten"  ''Jahresber. Deutsch. Math. Verein.'' , '''32'''  (1923)  pp. 175–176</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top">  L. Santaló,  "Un teorema sobre conjuntos de paralelepipedos de aristas paralelas"  ''Publ. Inst. Mat. Univ. Nac. Litoral'' , '''2'''  (1940)  pp. 49–60</TD></TR><TR><TD valign="top">[a16]</TD> <TD valign="top">  H. Tverberg,  "Proof of Grünbaum's conjecture on common transversals for translates"  ''Discr. Comput. Geom.'' , '''4'''  (1989)  pp. 191–203</TD></TR><TR><TD valign="top">[a17]</TD> <TD valign="top">  P. Vincensini,  "Figures convexes et variétés linéaires de l'espace euclidien à <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g130/g130050/g130050128.png" /> dimensions"  ''Bull. Sci. Math.'' , '''59'''  (1935)  pp. 163–174</TD></TR><TR><TD valign="top">[a18]</TD> <TD valign="top">  R. Wenger,  "Helly-type theorems and geometric transversals"  J.E. Goodman (ed.)  J.O'Rourke (ed.) , ''Handbook of Discrete and Computational Geometry'' , CRC  (1997)  pp. 63–82 (Chap. 4)</TD></TR><TR><TD valign="top">[a19]</TD> <TD valign="top">  R. Wenger,  "Progress in geometric transversal theory"  B. Chazelle (ed.)  J.E. Goodman (ed.)  R. Pollack (ed.) , ''Advances in Discrete and Computational Geometry'' , ''Contemp. Math.'' , '''223''' , Amer. Math. Soc.  (1999)  pp. 375–393</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  J. Eckhoff,  "Helly, Radon, and Carathéodory type theorems"  P.M. Gruber (ed.)  J.M. Wills (ed.) , ''Handbook of Convex Geometry'' , North-Holland  (1993)  pp. 389–448</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  L. Anderson,  R. Wenger,  "Oriented matroids and hyperplane transversals"  ''Adv. Math.'' , '''119'''  (1996)  pp. 117–125</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  A. Björner,  M. Las Vergnas,  N. White,  B. Sturmfels,  G.M. Ziegler,  "Oriented matroids" , Cambridge Univ. Press  (1993)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  L. Danzer,  "Über ein Problem aus der kombinatorischen Geometrie"  ''Archiv Math.'' , '''8'''  (1957)  pp. 347–351</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  L. Danzer,  B. Grünbaum,  V. Klee,  "Helly's theorem and its relatives"  V. Klee (ed.) , ''Convexity'' , ''Proc. Symp. Pure Math.'' , '''7''' , Amer. Math. Soc.  (1963)  pp. 101–180</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  B. Grünbaum,  "On common transversals."  ''Archiv Math.'' , '''9'''  (1958)  pp. 465–469</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  J.E. Goodman,  R. Pollack,  "Hadwiger's transversal theorem in higher dimensions"  ''J. Amer. Math. Soc.'' , '''1'''  (1988)  pp. 301–309</td></tr><tr><td valign="top">[a8]</td> <td valign="top">  J.E. Goodman,  R. Pollack,  "Foundations of a theory of convexity on affine Grassmann manifolds"  ''Mathematika'' , '''42'''  (1995)  pp. 305–328</td></tr><tr><td valign="top">[a9]</td> <td valign="top">  J.E. Goodman,  R. Pollack,  R. Wenger,  "Geometric transversal theory"  J. Pach (ed.) , ''New Trends in Discrete and Computational Geometry'' , '''10: Algorithms and Combinatorics''' , Springer  (1993)  pp. 163–198</td></tr><tr><td valign="top">[a10]</td> <td valign="top">  B. Grünbaum,  "Common transversals for families of sets."  ''J. London Math. Soc.'' , '''35'''  (1960)  pp. 408–416</td></tr><tr><td valign="top">[a11]</td> <td valign="top">  H. Hadwiger,  "Über einen Satz Hellyscher Art."  ''Archiv Math.'' , '''7'''  (1956)  pp. 377–379</td></tr><tr><td valign="top">[a12]</td> <td valign="top">  H. Hadwiger,  "Über Eibereiche mit gemeinsamer Treffgeraden"  ''Portugal. Math.'' , '''16'''  (1957)  pp. 23–29</td></tr><tr><td valign="top">[a13]</td> <td valign="top">  H. Hadwiger,  H. Debrunner,  V. Klee,  "Combinatorial geometry in the plane" , Holt, Rinehart &amp; Winston  (1964)</td></tr><tr><td valign="top">[a14]</td> <td valign="top">  E. Helly,  "Über Mengen konvexen Körper mit gemeinschaftlichen Punkten"  ''Jahresber. Deutsch. Math. Verein.'' , '''32'''  (1923)  pp. 175–176</td></tr><tr><td valign="top">[a15]</td> <td valign="top">  L. Santaló,  "Un teorema sobre conjuntos de paralelepipedos de aristas paralelas"  ''Publ. Inst. Mat. Univ. Nac. Litoral'' , '''2'''  (1940)  pp. 49–60</td></tr><tr><td valign="top">[a16]</td> <td valign="top">  H. Tverberg,  "Proof of Grünbaum's conjecture on common transversals for translates"  ''Discr. Comput. Geom.'' , '''4'''  (1989)  pp. 191–203</td></tr><tr><td valign="top">[a17]</td> <td valign="top">  P. Vincensini,  "Figures convexes et variétés linéaires de l'espace euclidien à $n$ dimensions"  ''Bull. Sci. Math.'' , '''59'''  (1935)  pp. 163–174</td></tr><tr><td valign="top">[a18]</td> <td valign="top">  R. Wenger,  "Helly-type theorems and geometric transversals"  J.E. Goodman (ed.)  J.O'Rourke (ed.) , ''Handbook of Discrete and Computational Geometry'' , CRC  (1997)  pp. 63–82 (Chap. 4)</td></tr><tr><td valign="top">[a19]</td> <td valign="top">  R. Wenger,  "Progress in geometric transversal theory"  B. Chazelle (ed.)  J.E. Goodman (ed.)  R. Pollack (ed.) , ''Advances in Discrete and Computational Geometry'' , ''Contemp. Math.'' , '''223''' , Amer. Math. Soc.  (1999)  pp. 375–393</td></tr></table>

Latest revision as of 17:00, 1 July 2020

A theory having its origin in a beautiful theorem of E. Helly in combinatorial geometry and a provocative question by P. Vincensini whose answer turned out to be negative.

Helly's theorem states [a14]: If $\mathcal{A}$ is a collection of compact convex sets in $\mathbf{R} ^ { d }$, every $d + 1$ or fewer members of which have a point in common, then there is a point common to all the members of $\mathcal{A}$.

A $k$-transversal to a collection of sets is a $k$-flat (cf. Higher-dimensional geometry) that meets every set in the collection. With this notion Helly's theorem can be reformulated to assert that if every $d + 1$ or fewer members of $\mathcal{A}$ have a $0$-transversal, then $\mathcal{A}$ has a $0$-transversal. In 1935, Vincensini [a17] asked whether there was a corresponding theorem for $k$-transversals to a collection of convex sets in $\mathbf{R} ^ { d }$: Does there exist an $r = r ( k , d )$ such that for every collection $\mathcal{A}$ of compact convex sets in $\mathbf{R} ^ { d }$, if every subcollection of at most $r$ members of $\mathcal{A}$ has a $k$-transversal, then $\mathcal{A}$ has a $k$-transversal?

Vincensini gave an incorrect proof that $r ( 1,2 ) = 6$. Subsequently, several examples showed that no finite $r ( 1,2 )$ exists, even if it is assumed that the sets of $\mathcal{A}$ are pairwise disjoint. It is perhaps counterintuitive that the existence of such a number should depend on whether the sets are pairwise disjoint; however, L. Danzer [a4] pointed out that although families of disjoint unit discs in the plane admit such a number (see below), there are examples, with $m$ arbitrarily large, of $m + 1$ unit discs in the plane (not disjoint) that do not have a line transversal even though any $m$ of them do. He also gave examples of $m + 1$ disjoint unit balls in $\mathbf{R} ^ { 3 }$ that have no plane transversal even though any $m$ of them do, for $m$ arbitrarily large.

With hopes dashed for a generalization of Helly's theorem in the form proposed by Vincensini, other Helly-type transversal theorems were found, where the elements of the collection $\mathcal{A}$ were subject to significant restrictions on either their shape or their relative position. Some noteworthy examples of such theorems are as follows.

Santaló's theorem.

([a15]) Let $\mathcal{A}$ be a collection of parallel rectangles in $\mathbf{R} ^ { 2 }$. If every $6$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ admits a line transversal. The number $6$ cannot be reduced in general.

This generalizes in two directions to:

a) Let $\mathcal{A}$ be a collection of parallelotopes in $\mathbf{R} ^ { d }$ with edges parallel to the coordinate axes. If every $2 ^ { d - 1 } ( 2 d - 1 )$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ admits a line transversal.

b) Let $\mathcal{A}$ be a collection of parallelotopes in $\mathbf{R} ^ { d }$ with edges parallel to the coordinate axes. If every $2 ^ { d - 1 } ( d + 1 )$ or fewer elements of $\mathcal{A}$ admit a hyperplane transversal, then $\mathcal{A}$ admits a hyperplane transversal.

Hadwiger's theorem.

([a11], [a5]) Suppose $\mathcal{A}$ is a collection of compact convex sets in $\mathbf{R} ^ { d }$ whose union is unbounded, each having diameter bounded by a constant. If every $d + 1$ or fewer sets of $\mathcal{A}$ have a line transversal, then all the sets do.

Grünbaum's theorem.

([a6], [a10])

a) Let $\mathcal{A}$ be a collection of compact convex sets in $\mathbf{R} ^ { d }$, each lying in one of a collection of parallel hyperplanes. If every $2 d - 1$ or fewer sets of $\mathcal{A}$ have a line transversal, then $\mathcal{A}$ has a line transversal.

b) Let $\mathcal{A}$ be a collection of pairwise disjoint translates of a parallelogram. If every $5$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.

Danzer's theorem.

([a4]) Let $\mathcal{A}$ be a collection of pairwise disjoint unit discs in the plane. If every $5$ or fewer elements of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.

Grünbaum conjecture.

In view of these last two theorems, it was natural for B. Grünbaum to conjecture, in 1958 [a6], that for a collection of disjoint translates of a convex set, if every $5$ or fewer sets of the collection admit a line transversal, then the entire collection has a line transversal.

This conjecture remained open for over 30 years and its eventual solution involved an idea that had first appeared in a theorem of H. Hadwiger. The key observation is that while, without additional assumptions, a Helly-type theorem does not hold for arbitrary convex sets in the plane, by imposing a consistency condition on the order in which triples of a collection of convex sets are met by a line, one can recover the Helly property:

Hadwiger's transversal theorem.

([a12]) Let $\mathcal{A}$ be a finite collection of pairwise disjoint convex sets in $\mathbf{R} ^ { 2 }$. If there exists a linear ordering of $\mathcal{A}$ such that every $3$ members of $\mathcal{A}$ are met by a directed line in the corresponding order, then $\mathcal{A}$ has a line transversal.

A line transversal to any collection of disjoint convex sets meets the sets in a given order or its reverse, depending on the direction of the transversal. This pair of orders (permutations) is called a geometric permutation. Building on the fact that disjoint translates admit only few geometric permutations, H. Tverberg was able to prove Grünbaum's conjecture.

Tverberg's theorem.

([a16]) Let $\mathcal{A}$ be a collection of disjoint translates of a convex set in $\mathbf{R} ^ { 2 }$. If every $5$ or fewer members of $\mathcal{A}$ admit a line transversal, then $\mathcal{A}$ has a line transversal.

Hyperplane transversals.

Hadwiger's transversal theorem restored the generality and simplicity of Helly's theorem to the situation of Vincensini's problem. While it has been shown that no theorem of Hadwiger type holds for line transversals in $\mathbf{R} ^ { d }$ for $d \geq 3$, it turns out nevertheless that Hadwiger's theorem does generalize to hyperplane transversals in $\mathbf{R} ^ { d }$. This requires a notion of order for finite point sets in higher dimensions.

By the $k$-order type of a numbered set of points $P = \{ p _ { 1 } , \dots , p _ { n } \} \subset \mathbf{R} ^ { k }$ is meant the family of orientations of its $( k + 1 )$-tuples, i.e., the collection

\begin{equation*} \left( \text{sign det} \left( \begin{array} { c c c c } { 1 } & { p _ { i_0 } ^ { 1 } } & { \dots } & { p _ { i_0 } ^ { k } } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { 1 } & { p _ { i_k } ^ { 1 } } & { \cdots } & { p _ { i_ k } ^ { k } } \end{array} \right) \right) _ { 1 \leq i _ { 0 } < \ldots < i _ { k } \leq n } . \end{equation*}

This order type is simple if the set $P$ lies in general position in $\mathbf{R} ^ { k }$, i.e., if every determinant is non-zero.

A generalization of disjointness is also needed. Just as every directed line transversal to a collection of convex sets meets the sets in a unique, well-defined order if and only if the sets are disjoint, every $k$-transversal will meet them in a unique, simple $k$-ordering if and only if no $k + 1$ sets of the collection admit a $( k - 1 )$-transversal; such a collection is said to be $( k - 1 )$-separated. Thus, a collection is pairwise disjoint if and only if it is $0$-separated.

With these definitions, J.E. Goodman and R. Pollack proved the following generalization of Hadwiger's transversal theorem in arbitrary dimension.

Goodman–Pollack theorem.

([a7]) A $( d - 2 )$-separated collection $\mathcal{A}$ of compact convex sets in $\mathbf{R} ^ { d }$ has a hyperplane transversal if and only if there is a one-to-one correspondence between $\mathcal{A}$ and a set $S$ of points in $\mathbf{R} ^ { d-1 } $ such that every $d + 1$ sets of $\mathcal{A}$ are met by an oriented hyperplane consistently with the $( d - 1 )$-ordering induced on the corresponding points of $S$.

For this to hold, moreover, it is sufficient to find an acyclic rank-$d$ oriented matroid structure on $\mathcal{A}$ whose $( d + 1 )$-tuples satisfy the consistency condition of the theorem. (For the notion of oriented matroid, which can be thought of as a "locally realizable" generalization of the order type of a set of points, see also [a3].)

This theorem was subsequently generalized in several directions, the most comprehensive statement (which subsumes intermediate results of M. Katchalski and of Pollack and R. Wenger) being:

Anderson–Wenger theorem.

([a2]) Let $\mathcal{A}$ be a finite collection of connected sets in $\mathbf{R} ^ { d }$. $\mathcal{A}$ has a hyperplane transversal if and only if for some $k$, $0 \leq k < d$, there exists a rank-$( k + 1 )$ acyclic oriented matroid structure on $\mathcal{A}$ such that every $k + 2$ members of $\mathcal{A}$ are met by an oriented $k$-flat consistently with that oriented matroid structure.

Other directions.

An effort to understand intermediate-dimensional transversals leads to considering the set of all $k$-transversals to a collection of convex sets. While there are as yet (2000) very few non-trivial results about transversals of dimensions between $1$ and $d - 1$, there is a good deal known about the structure of these complete sets of transversals to collections of convex sets. It turns out that these subsets of the "affine Grassmannian" themselves behave very much like convex point sets. Although they need not be connected, they nevertheless share many properties with convex sets, such as being defined by a convex hull operator satisfying the anti-exchange property that commutes with non-singular affine transformations, and satisfying the Krein–Mil'man theorem [a8] (cf. also Locally convex space).

Other streams in geometric transversal theory include:

Gallai-type theorems, in which a Helly-type hypothesis leads to the conclusion that several transversals cover the entire collection (see [a1], [a18]);

the more general theorems of $( p , q )$ type, in which a hypothesis of the form "for every choice of p sets from the collection, some q have a common transversal" leads to a Gallai-type conclusion (see [a1], [a18]);

generalizations from transversal flats to transversal curves and surfaces (see [a9]);

ongoing work of L. Montejano on a topological generalization of Hadwiger's transversal theorem and on the related notion of a "separoid" ;

the problem of bounding the number of geometric permutations of a collection of $n$ convex bodies in $\mathbf{R} ^ { d }$, and its generalization (via order types) to $k$-transversals (see [a19]);

algorithmic geometric transversal theory, a branch of computational geometry (see [a19]).

Surveys include [a5], [a1], [a9], [a13], [a18], [a19], where many other references can be found.

References

[a1] J. Eckhoff, "Helly, Radon, and Carathéodory type theorems" P.M. Gruber (ed.) J.M. Wills (ed.) , Handbook of Convex Geometry , North-Holland (1993) pp. 389–448
[a2] L. Anderson, R. Wenger, "Oriented matroids and hyperplane transversals" Adv. Math. , 119 (1996) pp. 117–125
[a3] A. Björner, M. Las Vergnas, N. White, B. Sturmfels, G.M. Ziegler, "Oriented matroids" , Cambridge Univ. Press (1993)
[a4] L. Danzer, "Über ein Problem aus der kombinatorischen Geometrie" Archiv Math. , 8 (1957) pp. 347–351
[a5] L. Danzer, B. Grünbaum, V. Klee, "Helly's theorem and its relatives" V. Klee (ed.) , Convexity , Proc. Symp. Pure Math. , 7 , Amer. Math. Soc. (1963) pp. 101–180
[a6] B. Grünbaum, "On common transversals." Archiv Math. , 9 (1958) pp. 465–469
[a7] J.E. Goodman, R. Pollack, "Hadwiger's transversal theorem in higher dimensions" J. Amer. Math. Soc. , 1 (1988) pp. 301–309
[a8] J.E. Goodman, R. Pollack, "Foundations of a theory of convexity on affine Grassmann manifolds" Mathematika , 42 (1995) pp. 305–328
[a9] J.E. Goodman, R. Pollack, R. Wenger, "Geometric transversal theory" J. Pach (ed.) , New Trends in Discrete and Computational Geometry , 10: Algorithms and Combinatorics , Springer (1993) pp. 163–198
[a10] B. Grünbaum, "Common transversals for families of sets." J. London Math. Soc. , 35 (1960) pp. 408–416
[a11] H. Hadwiger, "Über einen Satz Hellyscher Art." Archiv Math. , 7 (1956) pp. 377–379
[a12] H. Hadwiger, "Über Eibereiche mit gemeinsamer Treffgeraden" Portugal. Math. , 16 (1957) pp. 23–29
[a13] H. Hadwiger, H. Debrunner, V. Klee, "Combinatorial geometry in the plane" , Holt, Rinehart & Winston (1964)
[a14] E. Helly, "Über Mengen konvexen Körper mit gemeinschaftlichen Punkten" Jahresber. Deutsch. Math. Verein. , 32 (1923) pp. 175–176
[a15] L. Santaló, "Un teorema sobre conjuntos de paralelepipedos de aristas paralelas" Publ. Inst. Mat. Univ. Nac. Litoral , 2 (1940) pp. 49–60
[a16] H. Tverberg, "Proof of Grünbaum's conjecture on common transversals for translates" Discr. Comput. Geom. , 4 (1989) pp. 191–203
[a17] P. Vincensini, "Figures convexes et variétés linéaires de l'espace euclidien à $n$ dimensions" Bull. Sci. Math. , 59 (1935) pp. 163–174
[a18] R. Wenger, "Helly-type theorems and geometric transversals" J.E. Goodman (ed.) J.O'Rourke (ed.) , Handbook of Discrete and Computational Geometry , CRC (1997) pp. 63–82 (Chap. 4)
[a19] R. Wenger, "Progress in geometric transversal theory" B. Chazelle (ed.) J.E. Goodman (ed.) R. Pollack (ed.) , Advances in Discrete and Computational Geometry , Contemp. Math. , 223 , Amer. Math. Soc. (1999) pp. 375–393
How to Cite This Entry:
Geometric transversal theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Geometric_transversal_theory&oldid=18437
This article was adapted from an original article by Jacob E. GoodmanRichard Pollack (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article