\documentstyle[12pt,epsf]{article}

% DINA4-Format
\oddsidemargin 6pt\evensidemargin 6pt\marginparwidth 48pt\marginparsep 10pt 
\topmargin -18pt\headheight 12pt\headsep 25pt\footheight 12pt\footskip 30pt 
\textheight 625pt\textwidth 431pt\columnsep 10pt\columnseprule 0pt 

\def\R{\hbox{\rm I\kern-2pt R}}
\parskip=1truemm
\long\def\OMIT#1{{}}
\title{``Combinatorial Geometry''\\
Research Group, TU Berlin\\[3truemm]}

\author{
{\Large G\"unter M.~Ziegler}\\
{\Large J\"urgen Richter-Gebert}\\
{\Large Martin Henk}\\
{\Large Eva Maria Feichtner}\\
{\Large Ulrich Hund}\\
{\Large J\"org Rambau}\\[3mm]
Fachbereich Mathematik, MA~6-1\\
Technische Universit\"at Berlin\\
Strasse des 17. Juni 136\\
10623 Berlin, Germany\\[1mm]
Email: {\tt ziegler@math.tu-berlin.de}\\
Tel.: 49 - 30 - 314-25730\\[3truemm]}



\begin{document}
\date{May 21, 1995}
\maketitle

\begin{center}\bf
Supported by the\\
``Algebraic Combinatorics'' network (CHRX-CT93-0400)\\
in the EU Human Capital and Mobility Programme.\\ \rm
\end{center}

Combinatorics is the branch of Mathematics dealing with finite
structures, while Geometry deals with spatial structures. Thus 
Combinatorial Geometry deals with the close interaction of
discrete geometric objects and the combinatorial objects and
data that determine them. 

In this framework, essential aspects of a great variety of
geometric structures can be studied in terms of combinatorial
data (such as the number and incidence structure of the
points, lines, planes etc. involved). At the same time, many
combinatorial objects can be represented by geometric models
(e.g. graphs, complexes, and polytopes), which leads to
additional insight and new methods for their analysis. 

The new methods of combinatorial geometry rely on a systematic
development of the combinatorial models for geometric
structures. Moreover, one uses that the structure,
completeness and complexity of combinatorial objects can be
measured in terms of topological and algebraic invariants \cite{Bj1}.
The evolving systematic theory of combinatorial
structures can be applied in many mathematical situations. For
this the reduction to combinatorial problems is often not new
(see e.g. the method of cell decomposition and stratifications
of topological spaces)  --- the new element in the game is the
(algebraic and topological) theory that is 
available to deal with the combinatorial data generated this way. 



Our research program, supported by 
``Algebraic Combinatorics'' network  
in the EU Human Capital and Mobility Programme,
deals with selected questions that seem to be in the
focus of current interest.
In the following we describe five ranges of topics studied within
our research group, with very brief sketches of the structures
and problems studied, of current research work and some
recent progress and success. We are happy to provide more
information, details and explanations.

\subsection*{1. Polytope Theory.}

   Polytope theory has made rapid, substantial progress in the
   last few years (see Ziegler \cite{Z7}), and has experienced more and more
   interest from ``pure mathematics'', due to its close
   connections to parts of algebraic geometry (e.g. toric
   varieties), optimization (linear programming), commutative
   algebra, and so on. 
   Thus, for example, the construction of the ``permuto-associahedra'' as  
   symmetric, convex polytopes (Reiner \& Ziegler~\cite{RZ})
   was motivated by a problem by Kapranov from Homotopy Theory.
\vspace{-1.0cm}
\[
\def\epsfsize#1#2{0.8#1}
\epsfbox{polyhedron.eps}
\]
\vspace{-1.4cm}     


                      
   A   comprehensive goal in our research on polytopes asks
   to understand more about the algebraic structure of
   polytopes, including diameter questions, rationality,
   decomposition theory, as well as the universal
   constructions within the category of polytopes. 

The {\em realization spaces} of polytopes are
objects of particular importance and interest.
Here one studies the configuration
   space given by all the realizations of some discrete object,
   and asks for the (topological and arithmetic) complexity of this space. A
   class of structures is called {\em universal} if (essentially) all
   semialgebraic sets can appear as configuration spaces of
   objects in the class. Mn\"ev's celebrated ``Universality
   Theorem'' for oriented states that planar line configurations are
   universal in this sense. By now, even a simple proof of a 
   much more powerful ``Universal Partition Theorem'' is available,
   see Richter-Gebert \cite{RG3}.                

   Quite spectacular progress was recently achieved by 
   Richter-Gebert \cite{RG2,RGZ}: a strong Universality Theorem
(and a Universal Partition Theorem)
   for $4$-dimensional polytopes, which has many interesting
   corollaries, among them
\begin{itemize}
\itemsep=-1mm
\item realization spaces of $4$-polytopes can have complicated
      homotopy types,
\item for $4$-polytopes one cannot prescribe the shape of a $2$-face,
      (a Schlegel diagram for 
      the simplest example, a $4$-polytope $\bf X$ with $10$ vertices,
      is indicated below),
 
\vspace{-0.5cm}
\[
\def\epsfsize#1#2{0.3#1}
\epsfbox{12_4face2.eps}
\]
\vspace{-1.4cm}     

\item not every combinatorial type can be realized with rational coordinates,
\item for integral realizations of rational $4$-polytopes, 
      one needs at least doubly exponentially large coordinates.
\end{itemize}
 
After these complete answers for $4$-polytopes, some of the 
open problems about $3$-polytopes need to be reevaluated, and 
studied anew.


\subsection*{2. Homotopy Theory of Finite Structures.}

   Homotopy methods provide essential new tools for problems
   of Algebraic Combinatorics.
   Combinatorial methods here led to elementary proofs for the famous
   homology formulas of Goresky \& MacPherson, and even to
   homotopy formulas (Ziegler \& \v{Z}ivaljevi\'c \cite{ZZ}), with
   applications in complexity theory (Bj\"orner, Lov\'asz \&
   Yao). Surveys of this line of research, which has led to a
   quite complete picture of the topological structure of
   arrangements, are given in Bj\"orner \cite{Bj2} and in 
   Ziegler \cite[Chap.~1]{Z6}. The
   ``homotopy theory techniques'' (in particular, the diagram
   method of Ziegler \& \v{Z}ivaljevi\'c \cite{ZZ}) 
   still have great potential. We are
   working both on the tools and on extending the range of
   applicability.

For this one needs a systematic theory
of {\em diagrams of spaces} and their {\it homotopy limits}.
Substantial progress in this direction is given in Welker, Ziegler \& 
\v{Z}ivaljevi\'c \cite{WZZ}, providing a collection of 
versatile tools for the manipulation and comparison of homotopy limits of
different posets, including  
analogs of the main homotopy comparison results for order complexes, 
in particular of the Quillen Fibration Theorem and the 
Bj\"orner-Walker Complementation Formula.

This makes the diagram construction available in 
much more general contexts. Applications include the topology of
toric varieties, as well as the homotopy types of posets, 
with a new proof of Bj\"orner's \cite{Bj3}
Generalized Homotopy Complementation Formula.
In the future  we will 
test and work out applications to combinatorial, geometric and 
topological situations (esp.\ configurations, tilings, knots, arrangements)
of special interest. A particularly challenging problem here is
the classification of line configurations 
in real or projective $3$-space. 

This research is done in close collaboration with the
Stockholm Group (Prof.~Anders Bj\"orner) 
of the EU network. 

                                      
\subsection*{3. Matroid Theory, and the Grassmannians.}

   Oriented Matroids \cite{BLSWZ} are a versatile and widely applicable
   model for geometric objects. In this model, one can, in
   particular, profitably study realizability and
   embeddability problems. 

The oriented matroid models associated with
(stratifications of) the finite-dimensional real Grassmannians are
important structures that link several topics mentioned above.
Here we investigate the local (inductive resp.\ shelling) structure of
{\it spaces of oriented matroids} resp.\ 
{\it spaces of strings} in polytope theory,
which are discrete models for finite-dimensional Grassmannians.
This is also closely related to the investigations of the
Paris Group (Prof.~Alain Lascoux).

Here our recent research is connected to two most important problems: 
\begin{itemize}
\itemsep=-1mm
\item 
the ``Generalized Baues Conjecture''
of Billera, Kapranov \& Sturmfels, for which we provided 
{\em counterexamples} in Rambau \& Ziegler \cite{RaZ}, and
\item
the cohomology structure of the ``OM-Grassmannian,'' 
see Mn\"ev \& Ziegler \cite{MnZ}. 
Here research is directed towards the key problem of
MacPherson's theory of ``combinatorial differential manifolds.''
This is closely related to 
our work on the geometric 
realization of extension spaces via zonotopal tilings,
via the Bohne-Dress Theorem (see Richter-Gebert \& Ziegler~\cite{RGZ2}).
\item
The structure of the {\em complex matroids} introduced and
studied in Ziegler~\cite{Z5}. Spaces of such complex matroids provide
models for complex Grassmannians, and should eventually lead to the
analogs of Chern classes for complex combinatorial differential manifolds.
\end{itemize}


\subsection*{4. Automatic Theorem Proving.}

   This is a large, important field of
   research, connecting geometry with combinatorics and
   algebra. Here the aim is to design algorithms that can use
   the structural data of hypotheses and conclusions of a
   geometric theorem (incidence properties, angles, etc.) in
   order to automatically generate a proof. New approaches and
   tools \cite{RG} are based on methods of invariant theory (going
   back to Felix Klein's work!), which can be translated into
   effective algorithms. 

\vspace{-1.cm}
\[
\def\epsfsize#1#2{0.8#1}
\epsfbox{pascal.eps}
\]
\vspace{-1.0cm}                              

   In collaboration with H. Crapo (INRIA, Paris) we are
   developing a software package \cite{CRG2,CRG} that provides an interactive,
   graphic interface, linked to a powerful prover, for dealing
   with geometric theorems. 
Here work is still in progress --- but the performance of the
current prototype version is already impressively strong!
 
\begin{small}
\begin{thebibliography}{88}
\itemsep=-.2pt

\bibitem{Bj1}
{A.~Bj\"orner:} 
{Topological Methods,}
{in: {\sl Handbook of Combinatorics} 
(eds.\ R.~Graham, M.~Gr\"otschel, L.~Lov\'asz), North-Holland 1995, to appear.}

\bibitem{Bj2}
{A.~Bj\"orner:} 
{Subspace arrangements,}
{in: Proc.\ of the First European Congress of
Mathematics (Paris 1992), Birkh\"auser 1994.}

\bibitem{Bj3}
{A.~Bj{\"o}rner:}
{A generalized homotopy complementation formula,}
{Preprint 1995.}

\bibitem{BLSWZ}
{A.~Bj\"orner, M.~Las Vergnas, B.~Sturmfels, N.~White \& G.~M.~Ziegler:}
{Oriented Matroids,}
{Encyclopedia of Mathematics {\bf 46}, Cambridge University Press 1993.}

\bibitem{CRG2}
{H. Crapo \& J. Richter-Gebert:}
{Automatic proving of geometric theorems,}
{in: Proc.\ Conference ``Invariant Methods in Discrete and Computational Geometry,'' Williamstadt, Curacao 1994,
Kluwer Academic Publishers, to appear.}

\bibitem{CRG}
{H. Crapo \& J.~Richter-Gebert:}
{CINDERELLA Computer Interactive Drawing Environment,} %% Really ELLegant.
{work in progress.}

\bibitem{MnZ}
{N.~E.~Mn\"ev \& G.~M.~Ziegler:}
{Combinatorial models for the finite-dimensional Grassmannians,}
{Special issue on ``Oriented Matroids'' 
(eds.\ J.~Richter-Gebert, G.~M.\ Ziegler), 
{\sl Discrete \& Computational Geometry} (3) {\bf 10} (1993), 241-250.}

\bibitem{RaZ}
{J.~Rambau \& G.~M.~Ziegler:}
{Projections of polytopes and the Generalized Baues Conjecture,}
{Preprint 429/1995, TU Berlin, February 1995, 28~pages.}

\bibitem{RZ}
{V.~Reiner \& G.~M.~Ziegler:}
{Coxeter-associahedra,}
{{\sl Mathematika} {\bf 41} (1994), 364-393.}

\bibitem{RG}
{J.~Richter-Gebert:}
{Mechanical theorem proving in projective geometry,}
{{\sl Annals of Mathematics and Artificial Intelligence} {\bf 13} (1995), 139-172.}

\bibitem{RG2}
{J.~Richter-Gebert:}
{Realization spaces of $4$-polytopes are universal,}
{Habilitationsschrift, TU Berlin 1995;
Pre\-print 448/1995, TU Berlin 1995, 111~pages.}

\bibitem{RG3}
{J.~Richter-Gebert:}
{Mn\"ev's universality theorem revisited,}
{{\sl S\'eminaire Lotaringien de Combinatoire} 1995, 15~pages.}

\bibitem{RGZ2}
{J.~Richter-Gebert \& G.~M.~Ziegler:}
{Zonotopal tilings and the Bohne-Dress theorem,}
{in: Proc.\ ``Jerusalem Combinatorics '93'' (H.~Barcelo, G.~Kalai, eds.),
{\sl Contemporary Mathematics} {\bf 178}, American Math.\ Society 1994, 
211-232.}

\bibitem{RGZ}
{J.~Richter-Gebert \& G.~M.\ Ziegler:}
{Realization spaces of $4$-polytopes are universal,}
{Preprint 431/1995, TU Berlin 1995, 9~pages;
{\sl Bulletin of the American Mathematical Society} {\bf 32} (1995),
to appear October 1995.}

\bibitem{WZZ}
{V.~Welker, G.~M.~Ziegler \& R.~T.~\v Zivaljevi\'c:}
{Comparison lemmas and applications for diagrams of spaces,}
{Preprint 432/1995, TU Berlin, April 1995, 35~pages.}

\bibitem{ZZ}
{G.~M.~Ziegler \& R.~T.~\v Zivaljevi\'c:}
{Homotopy types of subspace arrangements via diagrams of spaces,}
{{\sl Mathematische Annalen} {\bf 295} (1993), 527-548.}

\bibitem{Z5}
{G.~M.~Ziegler:}
{``What is a complex matroid?''}
{Special issue on ``Oriented Matroids'' 
(eds.\ J.~Richter-Gebert, G.~M.~Ziegler), 
{\sl Discrete \& Computational Geometry} (3) {\bf 10} (1993), 313-348.}

\bibitem{Z6} 
{G.~M.~Ziegler:}
{Combinatorial Models for Subspace Arrangements,}
{Habilitations\-schrift, TU Berlin, April 1992.}

\bibitem{Z7} 
{G.~M.~Ziegler:}
{{Lectures on Polytopes,}}
{{\sl Graduate Texts in Mathematics} {\bf 152}, 
Springer-Verlag New York Berlin Heidelberg 1995.}


\end{thebibliography}
\end{small}
\end{document}