\documentclass{jams-l}

\usepackage{epsf}

\title{      A point set whose space of triangulations is disconnected}
\author{     Francisco Santos}
\address{    Departamento de Matem\'aticas, Estad\'{\i}stica y Computaci\'on\\
             Universidad de Cantabria, E-39005, Santander, SPAIN.}

\email{santos@matesco.unican.es
%, http://matsun1.matesco.unican.es/\~{}santos
}

\thanks{This research was partially supported by grant
PB97--0358 of the Spanish  Direcci\'on General de Ense\~nanza 
Superior e Investigaci\'on Cient\'{\i}fica}

\date{August 2, 1999 and, in revised form, January 17, 2000.}
\subjclass{Primary 52B11; Secondary 52B20}
\keywords{Triangulation, point configuration,
  bistellar flip, polyhedral subdivision, Baues problem}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{defi}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}

\newcommand{\starskip}{\smallskip\centerline{$\ast$}\smallskip}

%\newcommand{\naturals}{{\mathbb N}}
\newcommand{\integers}{{\mathbb Z}}
\newcommand{\reals}{{\mathbb R}}
%\newcommand{\rationals}{{\mathbb Q}}
%\newcommand{\complexes}{{\mathbb C}}

\newcommand{\invlim}{\varprojlim}
\newcommand{\Mom}{{\hbox{\rm Mom}}}
\newcommand{\conv}{{\hbox{\rm conv}}}
\newcommand{\aff}{{\hbox{\rm aff}}}
%\newcommand{\dim}{{\hbox{\rm dim}}}
\newcommand{\link}{{\hbox{\rm link}}}
\newcommand{\st}{{\hbox{\rm star}}}
\newcommand{\stair}{{\hbox{\rm stair}}}

%Caligraphic letters
\newcommand{\A}{{\mathcal A}}
\newcommand{\T}{{\mathcal T}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\M}{{\mathcal M}}

%Extra greek letters:
\newcommand{\Alpha}{\hbox{A}}
\newcommand{\Beta}{\hbox{B}}
\newcommand{\Epsilon}{\hbox{E}}
\newcommand{\Zeta}{\hbox{Z}}
\newcommand{\Eta}{\hbox{H}}
\newcommand{\Iota}{\hbox{I}}
\newcommand{\Kappa}{\hbox{K}}
\newcommand{\Mu}{\hbox{M}}
\newcommand{\Nu}{\hbox{N}}
\newcommand{\Omicron}{\hbox{O}}
\newcommand{\omicron}{\hbox{\it o}}
\newcommand{\Rho}{\hbox{P}}
\newcommand{\Tau}{\hbox{T}}
\newcommand{\Chi}{\hbox{X}}


% GRAPHICS
\def\picture #1 by #2 (#3) {
  \centerline {\vbox to #2{
    \hrule width #1 height 0pt depth 0pt
    \vskip #2
    \special{picture #3} % this is the low-level interface
    }}
  \nobreak
 }

\def\scaledpicture #1 by #2 (#3 scaled #4) {
	\dimen1=#1 \dimen2=#2
  \divide\dimen1 by 1000 \multiply\dimen1 by #4
  \divide\dimen2 by 1000 \multiply\dimen2 by #4
  \centerline {\vbox to \dimen2{
    \hrule width \dimen1 height 0pt depth 0pt
    \vskip \dimen2
    \special{picture #3 scaled #4} % this is the low-level interface
    }}
  \nobreak
  }




\begin{document}

\begin{abstract}
By the ``space of triangulations" of a finite point configuration 
$\A$ we mean either of the following two objects: the {\em graph of
triangulations} of $\A$, whose vertices are the triangulations
of $\A$ and whose edges are the geometric bistellar operations between them
or the partially ordered set ({\em poset}) of all polyhedral
subdivisions of $\A$ ordered by {\em coherent refinement}. The latter
is a modification of the more known {\em Baues poset} of $\A$ and is of
of special interest in the theory of algebraic toric varieties.

We construct an integer point configuration in dimension 6 and a
triangulation  of it which admits no geometric bistellar
operations. This triangulation is an isolated point in both the graph
and the poset, which proves for the first time that these two
objects can be not connected.
\end{abstract}

\maketitle



\section*{\bf Introduction}
\addcontentsline{toc}{section}{Introduction}
\label{intro}


In this paper we construct explicitly a triangulation of a
6-dimensio\-nal point configuration with 324 vertices
which admits no {\em geometric bistellar operations} (or {\em flips}, for
short). This triangulation is an isolated element 
in the {\em graph of triangulations}
of the point configuration. It has been a central open question in polytope
combinatorics in the last decade whether point configurations exist for which
this graph is not connected (see, e.g. \cite[Question 1.2]{Reiner-survey}
and \cite[Challenge 3]{Ziegler-recent}). 

Our construction is likely to have an impact in algebraic
geometry too, via the connections between lattice polytopes and toric
varieties \cite{GKZbook,IteRoy,Oda,Sturmfels-book}. For example, in
\cite[Section 2]{Alexeev} and \cite[Section 4]{KaStZe} 
the different authors study algebraic schemes based on the 
poset of subdivisions of an integer point configuration. The connectivity
of these schemes and of the graph of triangulations are equivalent.
See Section \ref{sub.alexeev}, in
particular Corollary \ref{coro.alexeev}.
%Question 6 in
%\cite[Section 6]{Alexeev} asks whether the scheme is connected. In our
%example this is not the case.

The graph of triangulations is also related to the 
Baues poset, which  appears as an important object in {\em oriented matroid
theory}, {\em zonotopal tilings} and  {\em hyperplane
arrangements}, so our
result has implications in these areas. 

%We will come back to this
%particular point at the end of the introduction.

\starskip

Let $\A$ be a finite point set in the real affine space $\reals^k$. 
A {\em polyhedral subdivision} of $\A$ is a geometric polyhedral complex
with vertices in $\A$ which covers the convex hull of $\A$. If all the
cells are simplices then it is a {\em triangulation}. More
combinatorial definitions are convenient if $\A$ is not in {\em convex
position}, i.e. if some element of $\A$ is not a vertex of the convex hull.
See Definitions
\ref{defi.subdivision} and \ref{defi.triang} for details, and also
\cite{BiFiSt}, \cite[Chapter 7]{GKZbook}, 
\cite{RamZie}, or \cite[Chapter 9]{Ziegler}.

There are at least the following three ways to give a structure to the
collection of all triangulations of a point configuration $\A$:

(A) {\em Flips.}
Geometric bistellar operations, or flips, are the minimal changes which 
can be made in a triangulation of $\A$ 
to produce a new one. See Definition \ref{defi.flips}.
A particular case is the familiar {\em diagonal edge flip} in two-dimensional
triangulations, of frequent use in computational geometry and geometric
combinatorics.

The {\em graph of triangulations of $\A$} has 
the triangulations of $\A$ as vertices and the flips between them
as edges. Graphs of triangulations in dimension two are known to be
connected  since the early days of computational geometry \cite{Lawson}. 
For the vertex set of a convex 
polygon, the graph is a classical object in combinatorics,
first studied by Stasheff and Tamari \cite{Tamari,Stasheff} and
related to associativity structures and to binary trees 
\cite{Lee,SlTaTh}. It is disturbing that in dimension three,
and  even assuming convex position, we do not know whether the graph is
always connected or not. 

The graph of triangulations of $\A$
contains as an induced subgraph the 1-skeleton of the {\em secondary 
polytope} of $\A$ introduced by Gel'fand et al.~\cite{GeKaZe}. This is a
polytope of dimension $\vert\A\vert -\dim(\A)-1$ whose vertices  are in
bijection with the {\em regular} (or {\em coherent}) triangulations of $\A$;
see \cite{BiFiSt,GKZbook,Lee-survey,Ziegler} and also Section
\ref{sub.coherent}. Triangulations with less than
$\vert\A\vert -\dim(\A)-1$ geometric bistellar operations 
are called {\em flip-deficient}. Flip-deficiency
cannot occur either in dimension two or in convex position in
dimension three \cite{LoSaUr}. In non-convex position in
dimension three there are triangulations 
with more than $n^2$ vertices and less than 
$4n$ flips for arbitrarily large $n$ \cite[Section 2]{Santos-fewflips}. 
In dimension four there are
triangulations with arbitrarily many vertices and bounded number of flips 
\cite[Sections 3 and 4]{Santos-fewflips}.
The precise statement of our main result is:

\medskip
\noindent
{\bf Theorem 1} 
{\em
There is a triangulation without geometric bistellar neighbors of an integer
point configuration $\A_1\times \A_2$ of dimension 6 with 324 popints.
$\A_1\times \A_2$ is the product of 
two point configurations $\A_1\subset\reals^4$ and
$\A_2\subset\reals^2$ with 81 and four
points respectively. The
triangulation has $9\times 64\times 3\times {6\choose 2}$ maximal simplices.
}
\medskip

J\"org Rambau has double-checked, 
with his computer program {\tt TOPCOM} \cite{topcom}, that 
our six dimensional triangulation with the
integer coordinates described in Section \ref{sub.integer} is in fact a
triangulation and has no flips. The current release of {\tt TOPCOM}
includes files which generate the triangulation and
carry out this checking.
 
Connectivity of the graph of triangulations is an important question 
in computational geometry, where flips are used to 
enumerate triangulations or to search for optimal ones
\cite{deLoera,EdeSha}. But it is also relevant theoretically: if the
graph is connected, properties which hold for a particular triangulation
and are preserved under flips must hold for any other one.
Our negative result contrasts the
following two 
positive results in more algebraic-geometric and topological
settings: 

 Morelli's factorization theorem of toric
birational maps \cite{AbMaRa,Morelli} has as an implication that any
two triangulations of a rational point configuration are connected
by geometric bistellar operations
if we allow the use of arbitrarily many additional
rational vertices in the intermediate steps. (Geometric bistellar
flips in triangulations with rational vertices correspond to pairs
blow-up/blow-down in toric varieties).

 Pachner \cite{Pachner2} has shown that any two
PL-homeomorphic combinatorial manifolds can be connected by a sequence
of the (non-geometric) bistellar operations used in combinatorial
topology \cite{BjoLut,Ewald}.

\medskip

(B) {\em The refinement poset of subdivisions (Baues poset).}
The {\em polyhedral subdivisions} of $\A$ form a partially
ordered set ({\em poset}) 
whose minimal elements are the triangulations.
We denote it $\Omega(\A)$.
It is usually referred to as the {\em Baues poset} of $\A$ and its study is the
{\em generalized Baues problem}. We call {\em strict Baues poset} the
one obtained removing from $\Omega(\A)$ its unique maximal element,
the trivial subdivision.

To be precise, Baues posets were introduced 
implicitly in \cite{BilStu} and explicitly in \cite{BiKaSt} in a 
more general situation where one has an affine 
projection $\pi$ from the vertex set of a polytope $P$ to $\A$.
The {\em Baues poset of $\pi$} is the poset of subdivisions of $\A$ which are 
{\em induced} by $\pi$, meaning that only projections of faces of $P$
are allowed as cells in the subdivisions. (A more careful
definition is needed in degenerate cases).
When $P$ is a simplex (hence of dimension 
$\vert\A\vert -1$) all subdivisions of $\A$ are $\pi$-induced and this is
the case of interest to us. When $P$ is a cube its projection is a {\em
zonotope} and the $\pi$-induced subdivisions are its {\em zonotopal tilings}
\cite{Ziegler}. 
%When 
%$\dim(\A)=1$, the $\pi$-induced subdivisions 
%are {\em cellular strings} \cite{BiKaSt} (a generalization of
%{\em monotone paths}) on the polytope $P$. 
See \cite{Reiner-survey} for a
very complete account of the different contexts in which Baues posets appear.

The {\em Baues complex} of $\A$ is the {\em order complex} \cite{Bjorner}
of the strict Baues
poset. That is to say, the abstract simplicial complex whose simplices are
the chains in the poset. Billera et al.~\cite{BiKaSt} proved that if
$\dim(\A)=1$, then the Baues complex of any projection 
$\pi:\hbox{vert}(P)\to \A$ is homotopy equivalent to a $(\dim(P)-2)$-sphere.
This resolved a conjecture of Baues \cite{Baues}. Their conjecture that in 
general the Baues complex is homotopy equivalent to a
$(\dim(P)-\dim(\A)-1)$-sphere was since called the {\em generalized Baues
conjecture}, or GBC. It was inspired by the fact that the {\em fiber polytope}
\cite{BilStu} of the projection (a generalization of the secondary
polytope) has dimension $\dim(P)-\dim(\A)$ and its face lattice is
naturallly embedded in the Baues poset. Rambau and Ziegler 
\cite{RamZie} found a counterexample to the GBC, but the particularly
interesting cases of $P$ being a simplex or a cube remain open
starting in $\dim(\A)=3$ or $\dim(P)-\dim(\A)=4$.

%Baues complexes are also known to be homotopy equivalent to spheres of
%the  appropriate dimensions in the cases when 
%$\dim(P)-\dim(\A)\le 2$ \cite{RamZie}, when $P$ is a cube or a simplex
%and either $\dim(\A)= 2$ or $\dim(P)-\dim(\A)= 3$
%\cite{Azaola,EdeRei,StuZie} and when
%$\pi$ is the canonical projection between two cyclic polytopes
%\cite{RamSan,AtRaSa}.

Triangulations of $\A$ and bistellar flips between them are precisely
the minimal and next-to-minimal elements in the Baues poset (Lemma
\ref{lemma.baues}). In particular,
connectivity of the graph of triangulations implies connectivity of
the Baues complex, but the converse is only (almost) true if $\A$ is
in general position (Corollary \ref{coro.baues}).
In the case of our triangulation without flips we can only say that it
is an isolated element in the poset of proper refinements of any
minimal element among the subdivisions of $\A$ refined by it.
But the strict Baues poset is probably connected.

\medskip

(C) {\em The coherent poset of subdivisions.}
In Section \ref{sub.coherent} we introduce a
modified Baues poset $\Omega_{c}(\A)$. It again contains all the
polyhedral subdivisions of $\A$, but a subdivision $\Pi'$
refining another one $\Pi$ is considered smaller only if the
refinement is coherent in a certain sense, first studied by Alexeev
\cite[Definition 2.12.10]{Alexeev}.

The poset $\Omega_{c}(\A)$ is nicer than the Baues poset in the
following respects:
\begin{itemize}

\item It is the right poset in order to study the algebraic schemes
introduced in \cite[Section 2]{Alexeev} and \cite[Section
4]{KaStZe}. In particular, (the order complex of)
$\Omega_{c}(\A)$ is connected if and only if the
schemes are connected (Corollary \ref{coro.alexeev}). 
%This is also partially true also for the
%{\em toric Hilbert scheme} of Peeva and Stillman \cite{PeeSti} (see
%also \cite{MacTho}).

\item The topology of the whole poset is much more related to
that of its lower ideals in the case of $\Omega_{c}(\A)$ than in 
$\Omega(\A)$
(compare Lemma \ref{lemma.connected} and Corollary \ref{coro.baues}).
In particular, $\Omega_{c}(\A)$ is connected 
if and only if the graph of triangulations is
connected (Corollary \ref{coro.connected}), 
and this is true regardless of whether the trivial
subdivision is considered an element of the poset or not. 
\end{itemize}

%Hence:
%\medskip
%\noindent
%{\bf Theorem 1}
%{\em
%For the six-dimensional point configuration of Theorem 1, both the
%inverse limit of toric GIT-quotients of the projective space of
%dimension $|\A|-1$ modulo the algebraic torus induced by $\A$ 
%\cite[Section 4]{KaStZe} and
%the moduli space of stable semiabelic toric pairs of type $\le
%\conv(\A)$ \cite[Section 2]{Alexeev} are disconnected.
%}
%\medskip



\starskip

The structure of the paper is as follows.
Section \ref{sec.prelim} contains preliminaries on triangulations and
geometric bistellar operations. The rest of
the paper is divided into Sections \ref{sec.stair}, \ref{sec.dim4}
and \ref{sec.posets} which can be read independently. The
first two combine to produce our main result.

In Section \ref{sub.refine} we study the relation between the
flips in triangulations $\T_1$ and $\T_2$ and the flips in any
triangulation which refines the product $\T_1\times\T_2$. In Section
\ref{sub.stair} we introduce a particular  way of refining such a
product based on the {\em staircase triangulation} of the
product of two simplices.
In Section \ref{sub.noflips} we prove that this refinement has no flips 
when $\T_1$ is any triangulation satisfying certain hypotheses and $\T_2$ is
a very simple triangulation of dimension two (Corollary \ref{coro.noflips2}).

In Section \ref{sub.triang} we describe a triangulation of a four-dimensional
point  configuration with 81 points. Then, we
compute its flips (Section \ref{sub.flips}) and introduce a {\em locally
acyclic  orientation} of its 1-skeleton (Section \ref{sub.orient}). 
This construction is based in the one which appeared in Section 4 of
\cite{Santos-fewflips}, a connection detailed in Remark
\ref{rem.fewflips}.  The triangulation 
satisfies the requirements needed in Corollary
\ref{coro.noflips2}. Although in its original form the point
configuration is not rational, 
in Section \ref{sub.integer} we modify it
so that it becomes integer, loosing part of its symmetry but none of
its special properties. This gives Theorem 1.

Sections \ref{sub.baues} and \ref{sub.coherent}
deal with the relation between the
graph of triangulations and the posets $\Omega(\A)$ and $\Omega_{c}(\A)$.
The latter is explicitly introduced here for the first
time, although it is implicit in \cite[Section 2.12]{Alexeev}.
Section \ref{sub.alexeev} shows the connections of $\Omega_{c}(\A)$
and the afore mentioned algebraic schemes.

\starskip

It would be desirable to improve our construction of a  triangulation
without flips in any of the following ways, in case this is possible:

\medskip\noindent{\bf Smaller dimension:}
Connectivity of the graph of triangulations and the Baues poset
is open starting in dimension three.
Theorem \ref{thm.noflips1} cannot provide a triangulation without
flips in
dimension less than five: every locally acyclic orientation of the
graph of a planar triangulation has reversible edges \cite[Remark
9]{Santos-fewflips} and a 1-dimensional triangulation always
contains sinks, sources and ``sandwich edges''.
In dimension three, we know triangulations which admit
locally acyclic orientations without  reversible edges, sinks or sources
(Remark \ref{rem.fewflips}). But we have not obtained one whose flippable
circuits are ``sandwich circuits'', as required in Corollary
\ref{coro.noflips2}.

\medskip\noindent{\bf Small codimension:} By this we mean the
dimension $|\A|-d-1$ of the secondary polytope. The fact that 
the GBC is false already for the projection of
a 5-dimensional polytope onto a point 
configuration with 10 points in dimension 2 
indicates that the simplex case should also be false in relatively small
codimension.

\medskip\noindent{\bf Convex position:}
Our triangulation has 324 vertices, of which only 96 are {\em extremal},
i.e. vertices in the convex hull.
The general procedure described in
\cite[Section 4.4]{Santos-OMtri} and \cite[Proposition 3.3]{LoSaUr}
substitutes any element of a point configuration
by two extremal points, increasing the dimension by one and preserving
the graph of triangulations and poset of subdivisions.
Applying it 228 times to our triangulation one obtains a triangulation
without flips and with vertices in convex position, with dimension 234 and 552
vertices. But flip-deficiency occurs in convex position starting in dimension
four \cite{LoSaUr}.

\medskip\noindent{\bf General position:}
A point configuration of dimension $d$ 
is said to be in {\em general position} if every $d+1$
points are affinely independent. 
%Then every circuit affinely spans
%$\A$ and the Definition \ref{defi.flips} of geometric bistellar 
%operation is much simpler: part (ii)  is
%superfluous, since the link mentioned in it is empty.

Flip-deficient triangulations in general position exist 
starting in dimension three \cite{LoSaUr}. A triangulation without
flips of a point configuration $\A$
in general position would disprove the GBC for projections from simplices
(Corollary \ref{coro.baues}).
The techniques in this paper cannot be adapted to general position
in any obvious way, since they are based on taking products. Actually,
we have reasons to believe that any perturbation of our triangulation
into general position creates flips.

\medskip\noindent{\bf Primitiveness:} By this we mean
that $\A=\conv(\A)\cap \integers^k$. This is 
of interest in the algebraic-geometric context. See Corollary
\ref{coro.alexeev}, part (iv).

\medskip\noindent{\bf
Unimodular configurations and $\A$-gradad ideals:}
Let $\A\subset (\integers_{\ge 0})^k$ be a nonnegative, integer point
configuration.  Sturmfels \cite[Chapter 10]{Sturmfels-book} has shown
that the radical of every {\em monomial $\A$-graded ideal} ({\em
mono-$\A$-GI} for short) equals the Stanley ideal of some
triangulation of $\A$. The converse is not always true: the Stanley
ideal of a triangulation may not be the radical of any mono-$\A$-GI.
We do not know whether our triangulation without flips has this
property. 

He also defines a parameter space of all $\A$-graded ideals
\cite[Section 5]{Sturmfels-agraded}, which turns out to be the reduced
scheme of the toric Hilbert scheme recently introduced by Peeva and
Stillman \cite{PeeSti}. This is pointed out by MacLagan
and Thomas \cite{MacTho}, who also show that
a triangulation without flips whose Stanley
ideal equals the radical of some mono-$\A$-GI
would imply that Sturmfels' parameter space and the toric Hilbert
scheme are not connected.

Specially interesting in this context is the case when $\A$ is
{\em unimodular}, meaning that all
its affine bases have the same determinant, up to a sign. 
Then the Stanley ideal of any triangulation of $\A$ is a mono-$\A$-GI
and every mono-$\A$-GI is radical
\cite[Lemma 10.14]{Sturmfels-book}. Our point
configuration is not unimodular.

\medskip\noindent{\bf
Lifting triangulations and Lawrence polytopes; relation to
zonotopal tilings and oriented matroids:}
Let $\A$ be a point configuration, let $\A^*$ denote a Gale
transform of $\A$ and let $\M(\A^*)$ be
the {\em oriented matroid} of affine dependences in $\A^*$
(roughly speaking, its set of circuits).
Every generic one-element extension of $\M(\A^*)$ induces
a triangulation of $\A$. The triangulations which
can be obtained in this way are called {\em lifting
triangulations} (see \cite[Section 9.6]{OMbook}
or \cite[Section 4]{Santos-OMtri}). 
It can be easily proved that our triangulation is not lifting.

Specially interesting in this context is the case 
when the Gale transform $\A^*$ is centrally symmetric, i.e when 
$\A$ is the vertex set of a {\em Lawrence polytope}
\cite{OMbook,Ziegler}. Then all its triangulations are lifting
(see \cite[Section 4.3]{Santos-OMtri} or
\cite[Section 4]{HuRaSa}). Moreover, the poset of subdivisions 
of a Lawrence polytope is isomorphic to the poset of zonotopal tilings
of a certain zonotope, and viceversa. 

A lifting triangulation without flips 
would imply the existence of a zonotopal tiling without cubical flips,
thus answering question 1.3 in \cite{Reiner-survey}.
If, moreover, the vertices of the triangulation are in general
position, this would disprove the GBC for projections from cubes,
which by the above mentioned results is equivalent to the 
GBC for the projections from simplices to Lawrence polytopes.

Via the Bohne-Dress Theorem \cite{OMbook,Ziegler}, these two cases
of the GBC are also equivalent to the 
{\em extension space conjecture}
of oriented matroid theory \cite[pp. 295--296]{OMbook}, stating that
the poset of one-element extensions of a realizable oriented
matroid of rank $r$ is homotopy equivalent to an $(r-1)$-sphere.

Finally, the extension space conjecture is the case
$k=d-1$ of the following far-reaching conjecture by MacPherson, Mn\"ev and
Ziegler \cite[Conjecture 11]{Reiner-survey}: that the poset of all
strong images of rank $k$ of any  realizable oriented matroid $\M$ of rank
$d$ (the {\em OM-Grassmannian of rank $k$} of $\M$)
is homotopy equivalent to the real Grassmannian 
$G^k(\reals^d)$. This conjecture is relevant to
matroid bundle theory \cite{Anderson} and the 
{\em combinatorial differential geometry} introduced by MacPherson
\cite{MacPherson}.

\section{Triangulations and flips}
\label{sec.prelim}

Let $\A$ be a finite subset of the real affine space $\reals^k$
and let $d$ denote the dimension of the affine subspace 
$\aff(\A)$ spanned by $\A$. 
This is what we call a {\it point configuration of dimension $d$}.

\begin{defi}
\label{defi.triang}
A {\em triangulation} of $\A$ is any  collection $\T$ of affinely independent
subsets of $\A$ with the following  properties: 
(i) if $S$ is in $\T$, then every subset of $S$ is in $\T$, i.e. $\T$ is an
abstract simplicial complex; 
(ii) if $S$ and $S'$ are in $\T$, then
$\conv(S)\cap\conv(S')$ is a face of both $\conv(S)$ and $\conv(S')$, i.e.
$\T$ induces a geometric simplicial complex in $\reals^k$; (iii) $\cup_{S\in
\T}\conv(S)=\conv(\A)$, i.e. $\T$ covers the convex hull of $\A$.
\end{defi}

We will call {\em simplices} of $\T$ all its elements, 
{\em  maximal simplices} of $\T$ the elements of dimension
$d$ and {\em facets} of $\T$ the facets of the maximal simplices, i.e. the
simplices of dimension $d-1$. This deviates from standard use in simplicial
complexes, where the facets are the maximal simplices. With our conventions,
every facet of $\conv(\A)$ is triangulated by facets of
$\T$. A facet is {\em interior} if its convex hull intersects the interior of
$\conv(\A)$ and is a {\em boundary facet} otherwise. 

It has some combinatorial advantages to consider elements of $\T$
only the maximal simplices, as is done in \cite{BiFiSt,LoHoSaSt,GKZbook}.
Here (but not in Section \ref{sec.posets}) 
we prefer to use the convention that
lower dimensional ones are also elements, to work more easily with the
links and stars of simplices, defined as follows. If $S\in \T$, then
$
\st_{\T}(S)=\{S'\in\T:S\cup S'\in \T\}
$
and
$
\link_{\T}(S)=\{S'\in\T:S\cup S'\in \T, S\cap S'=\emptyset \}.
$
 
\begin{lemma}[\cite{LoHoSaSt}]
\label{lemma.pseudomanifold}
Let $\A$ be a point configuration and let
$\T$ be an abstract simplicial complex of pure dimension $\dim(\A)$ with
vertices contained in $\A$ and containing only affinely independent subsets.
$\T$ is a triangulation of $\A$ if and only if:
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item The link of every interior facet $S$ of $\T$ has exactly two elements, 
which lie on opposite sides of the hyperplane of $\aff(\A)$ spanned by $S$.
\item There exists a point in $\conv(\A)$ which lies in the convex hull of exactly one maximal simplex of $\T$.
\qed
\end{enumerate}
\end{lemma}

Geometric bistellar operations arose in the following terms
in the work of Gel'fand, Kapranov and Zelevinsky~\cite{GeKaZe} 
\cite[Chapter 7]{GKZbook}, who called them {\em modifications}.

Following the terminology of matroid theory, we call a minimal affinely
dependent subset of $\A$ a {\it circuit} (see \cite{OMbook} or \cite{Ziegler}
for details). The {\em Radon partition} of a circuit $Z$ is the unique
partition $Z=Z_+\cup Z_-$ such that the convex hulls of the two parts
intersect. Equivalently, $Z_+$ and $Z_-$  contain respectively the elements
with positive and negative coefficient in the unique (up to a scalar multiple)
affine dependence equation on $Z$. The pair $(Z_+,Z_-)$ is called an {\it
oriented circuit}; of course, if
$(Z_+,Z_-)$ is an oriented circuit, then so is
$(Z_-,Z_+)$, and the two of them are the only orientations of $Z=Z_{+}
\cup Z_{-}$. Since our interest will always be in oriented circuits we will use
the word circuits for the pairs $(Z_+,Z_-)$ and will call the underlying
unoriented circuit the {\it support} of $(Z_+,Z_-)$.

The support $Z$ of a circuit $(Z_+,Z_-)$ admits exactly
two triangulations $\T_+(Z)$ and $\T_-(Z)$, which have $Z_+$ and
$Z_-$ as their unique minimal non-faces. I.e:
$$
\T_{+}(Z):=\{ S\subset Z : Z_+\not\subset S\},
\qquad
\T_{-}(Z):=\{ S\subset Z : Z_-\not\subset S\}.
$$  

\begin{defi}
\label{defi.flips}
Let $\T$ be a triangulation of $\A$ and let $(Z_+,Z_-) \subset \A$ be a circuit of $\A$.
Suppose that the following conditions are satisfied:
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item 
  The triangulation $\T_{+}(Z)$ is a subcomplex of $\T$. 
\item 
  All the maximal simplices of
$\T_{+}(Z)$ have the same link $L$ in $\T$. In particular,
$\T_{+}(Z)*L$ is a subcomplex of $\T$. 
Here $A*B:=\{S\cup T: S\in A, T\in B\}$.

\end{enumerate}
Then, we can obtain a new triangulation $\T'$ of $\A$ by
replacing the subcomplex $\T_{+}(Z)*L$ of $\T$ by the complex $\T_{-}(Z)*L$.
This operation of changing the triangulation is called a {\em geometric bistellar
operation}, {\em geometric bistellar flip} (or a {\it flip}, for short) supported on the circuit $(Z_+,Z_-)$. 
We call $(Z_+,Z_-)$ a {\em flippable circuit} and we
say that $\T$ and $\T'$ are {\it geometric bistellar neighbors}. 
\end{defi}

\begin{figure}[tb]
\begin{center}
        \epsfxsize=2.73 in\leavevmode\epsfbox{flipfacet.eps}
%  \scaledpicture 5.46 in by 1.50 in (flipfacet scaled 500)
\end{center}
\caption{\label{fig.flipfacet}A flip supported on the circuit
$(\{a,c\},\{e\})$. It has two flippable facets, $\{b,e\}$ and $\{d,e\}$.}
\end{figure}

Our definition of flip supported on a circuit explicitly assumes that
the circuit is oriented so that the star of the {\it negative part} 
is ``flipped out" and the star of the {\it positive part} is ``flipped in".
This convention is not made by other authors (see \cite[page 231]{GKZbook})
and will be relevant in our exposition.
See \cite{Santos-refine} for a generalization
of the concept of flip in the framework of Baues posets and fiber
polytopes.

It is sometimes more convenient to focus on {\em flippable facets},
which we now introduce, 
instead of {\em flippable circuits}. Let 
$S$ be the common facet of two maximal simplices $S\cup\{a_1\}$ and $S\cup
\{a_2\}$ of  a triangulation $\T$.
The $d+2$ elements of $S\cup \{a_1,a_2\}$ affinely span
$\aff(\A)$. Hence, there is a unique circuit
$(Z_+,Z_-)$ with support contained in them. This circuit can be oriented so
that $a_1,a_2\in Z_+$. We call $(Z_+,Z_-)$ the circuit {\it supported on
$S$}. We say that $S$ is a {\it flippable facet of $\T$} if
there is a flip supported on $(Z_+,Z_-)$. See an example in Figure
\ref{fig.flipfacet}.

In the following statement, if $(Z_+\cup Z_-)$ is full-dimensional, then the
link $L$ of $\T_+(Z)$ has one maximal simplex: the empty set.

\begin{lemma}
\label{lemma.flippable}
Let $\T$ be a triangulation of a point configuration $\A$ of dimension $d$.
Let $(Z_+,Z_-)$ be a flippable circuit, with $\vert Z_+\vert  = k $.
Let $l$ be the number of maximal simplices in the common link  $L$ of
$\T_{+}(Z)$ in $\T$. Then, $(Z_+,Z_-)$ is supported on $l{k\choose
2}$ facets of $\T$. In particular:
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item If $\T$ uses all the elements of $\A$ as vertices, then every flippable
circuit is supported on at least one flippable facet.
\item If $\conv(Z_+\cup Z_-)$ has dimension $d'$ and intersects the
interior of $\conv(\A)$, then $(Z_+,Z_-)$
 is supported on  at least $(d+1-d'){k\choose 2}$ flippable facets.
\end{enumerate}
\end{lemma}

\begin{proof}
The flippable facets of $\T$ on which the circuit $(Z_+,Z_-)$ is supported
are those of the form $S*T$ where $S$ is an interior facet of  $\T_{+}(Z)$
and $T$ is a maximal simplex in $L$.
The triangulation $\T_{+}(Z)$ has $k$ maximal simplices and every pair of
them are adjacent. Hence it has ${k\choose 2}$ interior facets.

Every proper subset of $Z_+$ is a simplex in $\T_+(Z)\subset \T$.
If every element of $\A$ is a vertex in $\T$, then
$Z_+$ has at least two elements, which implies part (i).

If $\conv(Z_+\cup Z_-)$ intersects the interior of $\conv(\A)$,
then $L$ is a triangulation of a $(d-d')$-sphere and, hence, it has at least 
$d+1-d'$ maximal simplices.
\end{proof}


\section{Refining the product of two triangulations}
\label{sec.stair}

Throughout this section, let $\T_1$ and $\T_2$ be  
triangulations using all the elements of respective point configurations
$\A_1$ of dimension $d_1$ and $\A_2$ of dimension $d_2$. 
Their product $\T_1\times \T_2$ is the polyhedral subdivision of $\A_1\times
\A_2$ into products $S_1\times S_2$ of simplices
$S_1\in\T_1$ and $S_2\in \T_2$. Clearly, $\T_1\times \T_2$ uses all the
elements of $\A_1\times \A_2$.

\subsection{Flippable circuits in refinements of $\T_1\times \T_2$}
\label{sub.refine}

Here we let $\T$ be any triangulation of $\A_1\times \A_2$  refining
$\T_1\times \T_2$.
We are going to study the relation between the flips in $\T$ and the flips in
$\T_1$ and $\T_2$. 
We consider the two natural projections $\pi_1:\A_1\times \A_2\to\A_1$ and $\pi_2:\A_1\times \A_2\to\A_2$
and will often use the following properties.

\begin{lemma}
\label{lemma.projectsimplices}
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item  $\T_1=\{\pi_1(S) : S\in \T\}$ and  $\T_2=\{\pi_2(S) : S\in \T\}$.
\item For every simplex $S\in \T$ and for $i\in \{1,2\}$:
$$
\st_{\T_i}(\pi_i(S))=\pi_i(\st_{\T}(S)) \quad\hbox{ and }\quad
\link_{\T_i}(\pi_i(S))\subset \pi_i(\link_{\T}(S)).\quad
\qed
$$
\end{enumerate}
\end{lemma}

By an {\em affine equality} on a point configuration $\A$ we mean a valid
expression of the
form $\sum_{a\in{Z}_+} \lambda_a a = \sum_{b\in{Z}_-} \mu_b b$, in which
$Z_+$ and $Z_-$ are disjoint subsets of $\A$, all the
coefficients $\lambda_a$ and $\mu_b$
are strictly positive reals, and $\sum_a \lambda_a=\sum_b \mu_b$. For example, there is a unique affine equality
(up to  a scalar multiple) associated to any circuit $(Z_+,Z_-)$ of $\A$.

Any affine equality $C$ on $\A_1\times \A_2$ is projected to affine
equalities on $\A_i$, that we denote $\pi_i(C)$
($i\in\{1,2\}$), in the following natural way: substitute every point
$(a_1,a_2)\in \A_1\times \A_2$ which appears in the equality by its projection
$a_i$ and combine the coefficients of points which at the end appear more than
once. One or both of the projected equalities
might result in a trivial equality $0=0$. This happens, for example,
for the equality $(a,a')+(b,b')=(a,b')+(b,a')$ 
for any given points $a,b\in\A_1$ and $a',b'\in\A_2$. 

We are interested in the affine equalities on $\A_1\times \A_2$ associated to
the flippable circuits  of $\T$. It
is more convenient to look at flippable facets of $\T$ instead, which can be
done by part (i) of Lemma \ref{lemma.flippable}. Interior facets of $\T$ 
fall into the following three categories:

\begin{itemize}
\item[(A)] {\em Facets which are interior to a maximal 
cell $S_1\times S_2$ of $\T_1\times \T_2$.}
The points involved in the equality are contained in $S_1\times S_2$, whose
two projections are affinely independent. Hence, the projected equalities are
trivial.

\item[(B$_1$)] {\em Facets common to two maximal cells $S_1\times S_2$ and 
$S'_1\times S_2$ of $\T_1\times \T_2$ with the same second factor.}
Now the points involved in the equality are contained in $(S_1\cup S_1')\times S_2$.
The second projection has to be a trivial equality as in the previous case.
The first projection
could in principle be trivial or can be the equality associated to the circuit
contained in $S_1\cup S_1'$. Lemmas \ref{lemma.projectcircuits} and
\ref{lemma.projectflips} below show that the second is always the case and that
the circuit in question  is flippable in $\T_1$, if the original facet is
flippable in $\T$. See Figure \ref{fig.projectcircuit}.

\item[(B$_2$)] {\em Facets common to two maximal cells $S_1\times S_2$ and 
$S_1\times S'_2$ of $\T_1\times \T_2$ with the same first factor.}
This case is analogous to (B$_1$).
\end{itemize}

\begin{lemma}
\label{lemma.projectcircuits}
Let $S$ be an interior facet common to two maximal cells $S_1\times S_2$ and 
$S'_1\times S_2$ of $\T_1\times \T_2$ with the same second factor. Let
$(Z_+,Z_-)$ be the circuit supported on that facet of $\T$
and let $C$ denote the affine equality associated to the circuit. Then,
$\pi_1(C)$ is the affine equality on a circuit $(Z'_+,Z'_-)$ of
$\A_1$, with
$Z'_+\subset \pi_1(Z_+)$ and $Z'_-\subset \pi_1(Z_-)$.
\end{lemma}

\begin{figure}[htb]
\begin{center}
        \epsfxsize=3.34 in\leavevmode\epsfbox{projectcircuit.eps}
%  \scaledpicture 5.56 in by 2.35 in (projectcircuit scaled 600)
\end{center}
\caption{\label{fig.projectcircuit}
The circuit $(\{a,d\},\{b,c\})$ of $\T$ 
projects to the circuit $(\{e,g\},\{f\})$ of $\T_1$. Here $S_1=\{e,f\}$, $S'_1=\{f,g\}$ 
and $S_2=\{h,i\}$.}
\end{figure}


\begin{proof}
Let $Z'_+$ and $Z'_-$ be the sets of points on one and the other side of the
projected equality $\pi_1(C)$. The conditions $Z'_+\subset \pi_1(Z_+)$ and
$Z'_-\subset
\pi_1(Z_-)$ are obvious. Let $(a,b)$ and $(a',b')$ be the two points in
$\link_\T(S)$. Clearly $a \ne a'$ and they are not in
$\pi_1(S)$. Hence, $a$ and $a'$ appear in $\pi_1(C)$ and $\pi_1(C)$ is not 
trivial. Since $Z'_+\cup Z'_-\subset \pi_1(Z_+\cup Z_-)$ is contained in the
union of two adjacent simplices of $\T_1$,
$(Z'_+,Z'_-)$ must be a circuit.
\end{proof}

\begin{lemma}
\label{lemma.projectflips} 
In the conditions of Lemma \ref{lemma.projectcircuits}, if $(Z_+,Z_-)$
supports a flip of $\T$, then:
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item For any $a\in \pi_1(Z_+)$ there is a unique $b\in \A_2$ such that
$(a,b)\in Z_+$ and there is no $b\in\A_2$ such that $(a,b)\in Z_-$.
\item  $Z'_+=\pi_1(Z_+)$ and $Z'_- = \pi_1(Z_-)$.
\item $(Z'_+,Z'_-)$ supports a flip of $\T_1$.
\item There is no pair of elements $a\in Z'_+$ and $b\in \A_2$ such that $(a,b)$ is
in the common link in $\T$ of the positive triangulation of $(Z_+,Z_-)$.
\item $\pi_2(Z_+)= \pi_2(Z_-)$.
\end{enumerate}
\end{lemma}

\begin{proof}
We denote $Z=Z_+\cup Z_-$ and $Z'=Z'_+\cup Z'_-$.

Let $a\in \pi_1(Z_+)$. Let $b\in \A_2$ with $(a,b)\in Z_+$. 
Since $(Z_+,Z_-)$ is flippable, $Z\setminus(a,b)$ is a simplex of $\T$ and hence projects to a simplex of
$\T_1$. On the other hand, $Z$ projects to a dependent set.
This implies that no other point $(a,b'')$ is contained in $Z$ because
otherwise $\pi_1(Z)=\pi_1(Z\setminus (a,b))$. This finishes part (i).

The containments $Z'_+\subset \pi_1(Z_+)$ and $Z'_-\subset \pi_1(Z_-)$ 
appear in the statement of Lemma \ref{lemma.projectcircuits}. Their converses
hold because any element in $\pi_1(Z_+)\setminus Z'_+$ or in
$\pi_1(Z_-)\setminus Z'_-$ must appear as the first coordinate of points both
in $Z_+$ and $Z_-$, contradicting part (i). This proves part (ii).

Let us now see part (iii).
By parts (i) and (ii), for any $a\in Z'_+$ there is a 
$b\in \A_2$ with $(a,b)\in Z_+$ and with
$Z'\setminus a= \pi_1(Z\setminus(a,b))$. Since $(Z_+,Z_-)$ is
flippable in $\T$, $Z'\setminus a$ is in $\T_1$.
Hence, $\T_1$ contains as a subcomplex the positive triangulation of $Z'$. 

Let $a$ and $a'$ be two different elements in $Z'_+$. We have to prove
that $\link_{\T_1}(Z'\setminus a)
= \link_{\T_1}(Z'\setminus a')$, for which we check only one of the two
containments.
Let $b,b'\in \A_2$ with $(a,b),(a',b')\in Z_+$, as before.
We have 
$\link_{\T_1}(Z'\setminus
a) = \link_{\T_1}(\pi_1(Z\setminus(a,b)))\subset \pi_1(\link_{\T}( Z\setminus (a,b)))
=\pi_1(\link_{\T}( Z\setminus (a',b')))
$, 
where the first equality holds by part (ii) of the statement, the containment
in the middle by 
part (ii) of Lemma \ref{lemma.projectsimplices} and the last equality
because $(Z_+,Z_-)$ is flippable. With similar arguments
$\pi_1(\link_{\T}( Z\setminus (a',b')))\subset \st_{\T_1}(\pi_1(Z\setminus
(a',b'))) =\st_{\T_1}(Z'\setminus a')$.
In conclusion, $\link_{\T_1}(Z'\setminus a)\subset \st_{\T_1}(Z'\setminus a')$.
Since no element of $Z'\setminus a'$ can appear in $\link_{\T_1}(Z'\setminus
a)$, we have $\link_{\T_1}(Z'\setminus a)\subset \link_{\T_1}(Z'\setminus
a')$.

For part (iv), if $(a,b')$ is a point in the common link of the positive
triangulation of $(Z_+,Z_-)$ with $a\in Z'_+=\pi_1(Z_+)$, then let $(a,b)\in
Z_+$ as before. We have that  $Z\cup (a,b')\setminus (a,b)$ is a simplex
in $\T$. But $Z'= \pi_1(Z)= \pi_1(Z\cup (a,b')\setminus (a,b))$. This is
impossible since $Z'$ is dependent in $\A_1$.

Part (v) is trivial: the second projection
$\pi_2(C)$  of the affine equality on the circuit $(Z_+,Z_-)$ is the trivial
equality. This implies that every element in $\pi_2(Z)$ is the second
coordinate of points in both $Z_+$ and $Z_-$.
\end{proof}

\subsection{The staircase refinement of $\T_1\times \T_2$}
\label{sub.stair}

We first recall what the staircase triangulation of the product of two
simplices is. Let $S_1$ and $S_2$ be two simplices of dimensions $d_1$ and
$d_2$, and suppose that their vertices are given in a specific order. The
total order in the  vertices of $S_1$ and $S_2$ induces the following partial
order in the vertices of the product $S_1\times S_2$: $(a,b)\le(a',b')$ if and
only if $a\le a'$ and $b\le b'$. Every chain in this partial order is an
affinely
independent subset of $S_1\times S_2$. The collection of all such chains is a
triangulation of $S_1\times S_2$, described for example in
\cite[Section 7.3.D]{GKZbook} and \cite[p. 282]{Lee-survey} and
used also in algebraic topology.

All the maximal simplices contain the vertices
$(a_{min},b_{min})$ and
$(a_{max},b_{max})$, where $a_{min}$ and $a_{max}$ (respectively $b_{min}$
and $b_{max}$) are the minimum and maximum vertices of $S_1$ (respectively of
$S_2$). More visually, if we arrange the vertices of
$S_1\times S_2$ in a $(d_1+1)\times (d_2+1)$ rectangular grid, then the maximal
simplices of our triangulation are the monotone staircases from
$(a_{min},b_{min})$ to $(a_{max},b_{max})$. For this reason it is called
the {\it staircase triangulation} of $S_1\times S_2$ and we denote it
$\stair(S_1\times S_2)$. We will encounter an example of a staircase
triangulation in Remark
\ref{rem.fewflips}.

Any pair of adjacent maximal simplices in $\stair(S_1\times S_2)$ differ in
the replacement of a point
$(a,b')$ by a point $(a',b)$, for consecutive pairs of vertices $a<a'$ and
$b<b'$ in the total orderings of $S_1$ and $S_2$. In particular, every flip of
$\stair(S_1\times S_2)$ is supported on a circuit
$(\{(a,b'),(a',b)\},\{(a,b),(a',b')\})$, for consecutive pairs of vertices
$a<a'$ and
$b<b'$. The converse is also true although we do not need it: $\stair(S_1\times
S_2)$ has exactly $d_1\times d_2$ flips, supported on the circuits of that
form. 

For the sequel, it is convenient to reformulate the construction of 
the staircase triangulation as follows: We will express the ordering of the
vertices of $S_1$ and $S_2$ by giving an acyclic orientation to their
respective 1-skeletons. Then, the circuits which produce flips are those of
the form $(\{(a,b'),(a',b)\},\{(a,b),(a',b')\})$ where $\{a,a'\}$ and
$\{b,b'\}$ are edges of $S_1$ and $S_2$ whose reversal produces no directed
cycle. We call such edges {\em reversible edges}.

\medskip

Suppose now that we have two triangulations $\T_1$ and $\T_2$ of two point configurations $\A_1$ and
$\A_2$ as in Section \ref{sub.refine}, and that we 
are given respective {\em locally acyclic} orientations of the 1-skeletons of 
$\T_1$ and $\T_2$. By this we mean orientations which are acyclic on every
simplex. Then, refining each product $S_1\times S_2\in \T_1\times \T_2$ in its
staircase way (according to the given locally acyclic orientations)
produces a triangulation of $\A_1\times \A_2$. That this is indeed a triangulation follows from the
fact that in the staircase triangulation of the product of two simplices $S_1\times S_2$, each face
$F_1\times F_2$ is triangulated according to the staircase triangulation corresponding to the
restrictions of the orderings of $S_1$ to $F_1$ and of $S_2$ to $F_2$. 

We call this triangulation the {\it staircase refinement} of $\T_1\times
\T_2$ and denote it
$\stair(\T_1\times \T_2)$. Observe that the staircase refinement depends on
the orientations of the 1-skeletons of $\T_1$ and $\T_2$. In our notation,
$\T_1$ and $\T_2$ will implicitly denote not only the triangulations but also
specific locally acyclic orientations of their 1-skeletons. 
In  \cite[p. 67]{EilSte}, a simplicial complex together with a locally acyclic
orientation is called an {\em ordered simplicial complex} and the 
(combinatorial) staircase refinement of two ordered simplicial complexes
is just called the {\em cartesian product} of them. It is used 
as the standard way to give a structure
of simplicial complex to the product of (the underlying spaces of) two simplicial complexes.

The analysis of flippable circuits carried out in Section
\ref{sub.refine} gives the following:


\begin{lemma}
\label{lemma.stair}
If the locally acyclic orientation of at least one of
$\T_1$ or $\T_2$ does not have any reversible edge, then every flippable
circuit of
$\stair(\T_1\times \T_2)$ projects, in the sense of Lemmas
\ref{lemma.projectcircuits} and \ref{lemma.projectflips}, 
either to a  flippable circuit of $\T_1$ or to a flippable circuit of $\T_2$.
\end{lemma}

\begin{proof} Recall the three types (A), (B$_1$) and (B$_2$) of possible interior
facets in a refinement of $\T_1\times \T_2$ that we mentioned before Lemma
\ref{lemma.projectcircuits}. Those of type (B$_1$) are in the conditions of
Lemma \ref{lemma.projectcircuits} and by Lemma
\ref{lemma.projectflips} they project to a flippable circuit of $\T_1$.
Analogous lemmas for the second instead of
the first projection deal with facets of type (B$_2$).

Hence, we only need to deal with facets of type (A), i.e. facets interior to a
cell $S_1\times S_2$ of $\T_1\times \T_2$. A flip
in one of these facets will be in particular a flip in the staircase triangulation
of $S_1\times S_2$. Such a  flip is supported in a circuit of the form
$(\{(a,b'),$ $(a',b)\},\{(a,b),(a',b')\})$
where $\{a,a'\}$ is a reversible edge in the orientation of $S_1$ and
$\{b,b'\}$ a reversible edge in the orientation of $S_2$. For this
circuit to be flippable it is clearly
necessary (and sufficient, although we do not need it) that both edges
$\{a,a'\}$ and $\{b,b'\}$ be reversible in {\em in every simplex} of $\T_1$
and $\T_2$  in which they appear. Our hypotheses forbid the existence of at
least one of these edges.
\end{proof}

\subsection{Towards a triangulation without flips}
\label{sub.noflips}

Let $\T$ be a triangulation of a point configuration $\A$, with its
1-skeleton oriented locally acyclically. A {\em source} (resp. a {\em
sink}) of $\T$ is a vertex which is the source (resp. the sink) of
every simplex incident to it.
An edge of $\T$  will be called a {\em sandwich edge}
if its source and sink are the source and sink, respectively, of every simplex
containing the edge.

Let $(Z_+,Z_-)$
be a flippable circuit of $\T$ and suppose that $Z_+$ has at least two
elements (this is automatic if all the points of $\A$ are vertices
in $\T$). Then, every pair $\{a_+,a_-\}$ with
$a_+\in Z_+$ and $a_-\in Z_-$ is an edge in $\T$. 

\begin{defi}
\label{defi.sandwich}
In the above conditions, we say that an element $a_+\in Z_+$ is a {\em
source} (respectively, a {\em sink}) in $(Z_+,Z_-)$ if it is the source
(respectively the sink) in all the edges $\{a_+,a_-\}$ with $a_-\in
Z_-$. We say that
\begin{itemize}
\item $(Z_+,Z_-)$ is a {\em source circuit} (resp. {\em a sink
circuit}) if every $a_+\in Z_+$ is a source (resp. a sink) in the circuit.
\item $(Z_+,Z_-)$ is a {\em sandwich circuit} if every
$a_+\in Z_+$ is either a source or a sink in the circuit 
and there is at least one of each.
\end{itemize}
\end{defi}



\begin{theorem}
\label{thm.noflips1}
Let $\T_1$ and $\T_2$ be triangulations with their 1-skeletons
oriented in locally acyclic ways. Let $(Z_+,Z_-)$ be a circuit which
supports a flip in $\stair(\T_1\times \T_2)$ and suppose that it
projects onto a flippable circuit $(Z'_+,Z'_-)$ of $\T_1$, in the
sense of Lemmas \ref{lemma.projectcircuits} and
\ref{lemma.projectflips}.
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item If $(Z'_+,Z'_-)$ is a sink circuit, then $\pi_2(Z_+)$
is a sink vertex of $\T_2$.
\item If $(Z'_+,Z'_-)$ is a source circuit, then $\pi_2(Z_+)$
is a source vertex of $\T_2$.
\item If $(Z'_+,Z'_-)$ is a sandwich circuit, then $\pi_2(Z_+)$
is a sandwich edge of $\T_2$.
%\item In case (iii), $Z'_+$ has exactly two elements, one source and
%one sink of the circuit.
\end{enumerate}
\end{theorem}

\begin{proof}
Let $S_2$ be any simplex in $\T_2$ containing $\pi_2(Z_+)$.
For any $a\in Z'_+$ there is a unique point $b\in \pi_2(Z_+)$ 
with $(a,b)\in Z_+$,
by part (i) of Lemma \ref{lemma.projectflips}). 
We will prove that if $a$ is a source in $(Z'_+,Z'_-)$
then $b$ is the source of $S_2$. This and the analog statement when
$a$ is a sink imply parts (i), (ii) and (iii).

Let $b_0$ be the source of $S_2$. Let $a'\in Z'_+\setminus\{a\}$, so
that $S_1:=Z'_+\cup Z'_-\setminus\{a'\}$, 
is a simplex in $\T_1$. Let $b'$ be such that $(a',b')\in Z_+$.
Since the staircase triangulation of
$S_1\times S_2$ is a subcomplex of $\stair(\T_1\times \T_2)$ and since
$(Z_+,Z_-)$ is flippable, there is a
maximal staircase $S$ in $S_1\times S_2$ containing $Z_+\cup
Z_-\setminus \{(a',b')\}$. 

Taking into account that the 
sources of $(Z'_+,Z'_-)$ contained in $S_1$ form an initial segment of
$S_1$, and that in each of their columns there is only one element of
$S$ (by parts (i) and (iv) of Lemma \ref{lemma.projectflips}) we
conclude that for any source $a''$ of $(Z'_+,Z'_-)$ contained in $S_1$ (in
particular for $a$), $(a'',b_0)$ is in $Z_+$. Hence $b=b_0$.
\end{proof}


\begin{corollary}
\label{coro.noflips2}
Let $\T_1$ be a triangulation using all the points of a point configuration
$\A_1$ and whose 1-skeleton has been oriented in a locally acyclic way,
without  global sinks or reversible edges, and with the property that all its
flippable circuits are sandwich circuits.

Let $\A_2=\{o,p,q,r\}\in\integers^2$ with $o=(0,0)$, 
$p=(1,0)$, $q=(0,1)$ and $r=(-1,-1)$.  Let
$\T_2$ be the triangulation of $\A$ whose maximal simplices are 
$\{o, p,q\}$, $\{o, p,r\}$, and $\{o,q,r\}$ with its 1-skeleton
oriented by $o\to p$, $o\to q$, $o\to r$ and  $p\to q\to r\to p$.

Then, the staircase refinement $\stair(\T_1\times \T_2)$ of $\T_1\times \T_2$
does not have any flips.
\end{corollary}


\begin{proof}
By Lemma \ref{lemma.stair}, and
since $\T_1$ has no reversible edges, 
every flippable circuit of $\stair(\T_1\times
\T_2)$ projects in the sense of Lemmas \ref{lemma.projectcircuits} and
\ref{lemma.projectflips}
either to a flippable circuit of $\T_1$, which is a sandwich circuit, 
or to the unique flippable circuit of
$\T_2$, which is a sink circuit. Both cases are forbidden by Theorem
\ref{thm.noflips1}, since $\T_1$ has no sinks and $\T_2$ has no
sandwich edges.
\end{proof}



\section{A construction in dimension four}
\label{sec.dim4}

This section is devoted to describing a triangulation in dimension four which
satisfies the hypotheses of the $\T_1$ of Corollary \ref{coro.noflips2}. 

\subsection{Description of the triangulation}
\label{sub.triang}

Throughout Section \ref{sec.dim4}, let $\A$ be the following point
configuration in $\reals^4$, with 81 elements. Indices are regarded modulo 8:
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}

\item The origin $O=(0,0,0,0)$.

\item The 8 points $v_{j}:=\left(0,0,
\cos\left({\pi \over 4}j\right), 
\sin\left({\pi \over 4}j\right) \right)$, for $j=0,\dots,7$.

\item The 8 points $h_i:=\left(
\cos\left({\pi \over 4}i\right), 
\sin\left({\pi \over 4}i\right),0,0 \right)$, for $i=0,\dots,7$.

\item The 32 points $t_{i,j}:=h_i + v_j =
\left(
\cos\left({\pi \over 4}i\right), \sin\left({\pi \over 4}i\right), 
\cos\left({\pi \over 4}j\right), \sin\left({\pi \over 4}j\right) \right)$, for
all values of $i,j\in\{0,\dots,7\}$ with $i+j$ odd.

\item The 32 points $s_{i+{1\over 2},j+{1\over 2}}=(t_{i,j+1}+t_{i+1,j})/ 2$, for
all values of $i,j\in\{0,\dots,7\}$ with $i+j$ even.

\end{enumerate}

The convex hull of $\A$ is a
4-polytope whose vertices are the 32 points $t_{i,j}$ and with the following 48
facets: 
\begin{itemize}
\item Eight square anti-prisms $P_{k+{1\over 2}}$ $(k=0,\dots, 7)$ whose eight
vertices are the points $t_{i,j}$ with $j\in \{k,k+1\}$, 
\item Another eight 
square anti-prisms $P'_{k+{1\over 2}}$ $(k=0,\dots, 7)$ whose
eight vertices are the points $t_{i,j}$ with $i\in \{k,k+1\}$, and
\item 32 tetrahedra $T_{i,j}$
$(i,j\in\{0,\dots, 7\},  i+j$ even) having as vertices $t_{i-1,j}$, $t_{i+1,j}$,
$t_{i,j-1}$ and 
$t_{i,j+1}$.
\end{itemize}

The two series of 8 anti-prisms form two solid tori in the three-dimensional
topological sphere
$\partial(\conv(\A))$ which are glued to one another along edges, leaving some
spaces for the 32 tetrahedra
$T_{i,j}$. The point $s_{i+{1\over 2},j+{1\over 2}}$ lies in an edge incident
to the tetrahedra
$T_{i,j}$ and $T_{i+1,j+1}$ and to the anti-prisms $P_{j+{1\over 2}}$ and
$P'_{i+{1\over 2}}$. The point $v_j$ (respectively $h_i$)
lies in the square between the two anti-prisms 
$P_{j-{1\over 2}}$ and $P_{j+{1\over 2}}$ 
(respectively $P'_{i-{1\over 2}}$ and $P'_{i+{1\over 2}}$).

The affine symmetry group of $\A$ has 128 elements, since any of the 16
anti-prisms can be sent to any other one in eight ways. We will be interested
in the following subgroup $G$ with 64 elements. 
Let $g_h$ and $g_v$ denote the rotations of angle $\pi/4$ on the first two and
on the last two coordinates respectively, and let $g_t$ be the exchange of the
first two and last two coordinates. Then, $G$ is generated by 
$g_1:={g_h}^2$, $g_2:={g_v}^2$, $g_3:={g_h\circ g_v}={g_v\circ g_h}$, and
$g_4:=g_t$. Either of the 
first two is redundant. All these isometries fix the origin $O$. Table
\ref{tab.symmetries} shows the permutations induced on the other
points of $\A$.
\begin{table}[htb]
\small
$$
\begin{array}{lllllllll}
g_1:&(
  h_i\mapsto  h_{i+2};&
  v_j\mapsto v_{j};&t_{i,j}\mapsto t_{i+2,j};&
  s_{i+{1\over 2},j+{1\over 2}}\mapsto s_{i+{5\over 2},j+{1\over 2}}\ ) \cr
g_2:&(
  h_i\mapsto  h_{i};&
  v_j\mapsto v_{j+2};&t_{i,j}\mapsto t_{i,j+2};&
  s_{i+{1\over 2},j+{1\over 2}}\mapsto s_{i+{1\over 2},j+{5\over 2}}\ ) \cr
g_3:&(
  h_i\mapsto  h_{i+1};&
  v_j\mapsto v_{j+1};&t_{i,j}\mapsto t_{i+1,j+1};&
  s_{i+{1\over 2},j+{1\over 2}}\mapsto s_{i+{3\over 2},j+{3\over 2}}\ )\cr
g_4:&(
  h_i\mapsto  v_{i};&
  v_j\mapsto h_{j};&t_{i,j}\mapsto t_{j,i};&
  s_{i+{1\over 2},j+{1\over 2}}\mapsto s_{j+{1\over 2},i+{1\over 2}}\ ) \cr
\end{array}
$$
\caption{\label{tab.symmetries} The affine symmetries of the triangulation
$\T$.}
\end{table}

We now define a triangulation $\T$ of $\A$ which has $G$ as its symmetry
group. For this, we give in Table \ref{tab.simplices} a representative of each of the nine 
orbits of maximal simplices in $\T$. 
We name the orbits with the first nine letters of the capital Greek alphabet.
The indices $i$ and $j$ in Table \ref{tab.simplices}
range over all the possibilities modulo 8 with $i+j$ even. This produces
32 simplices in each orbit. The other 32 are obtained by applying the
transformation $g_4$ and we name them as follows: 
$\Alpha'_{j,i}:=g_4(\Alpha_{i,j})$, $\Beta'_{j,i}:=g_4(\Beta_{i,j})$,
$\Gamma'_{j,i}:=g_4(\Gamma_{i,j})$, 
$\Delta'_{j,i}:=g_4(\Delta_{i,j})$, $\Epsilon'_{j,i}:=g_4(\Epsilon_{i,j})$,
$\Zeta'_{j,i}:=g_4(\Zeta_{i,j})$, 
$\Eta'_{j,i}:=g_4(\Eta_{i,j})$, $\Theta'_{j,i}:=g_4(\Theta_{i,j})$, and
$\Iota'_{j,i}:=g_4(\Iota_{i,j})$. That these $9\times 64$ simplices  of
dimension four are indeed the maximal simplices of a triangulation of 
$\A$ will be proved afterwards. Remark \ref{rem.fewflips} at the end of Section
\ref{sub.orient} may help to clarify this construction and its genesis.

\begin{table}[htb]
\small
$$
\begin{array}{ccccccccccc}

\Alpha_{i,j}:=\{O&,&v_{j+1}&,&t_{i,j+1}&,&s_{i-{1\over 2},j-{1\over 2}}&,
   &s_{i+{1\over 2},j+{1\over 2}}\}\cr 

\Beta_{i,j}:=\{O&,&v_{j+1}&,&t_{i+1,j}&,&s_{i-{1\over
2},j-{1\over 2}}&,
   &s_{i+{1\over 2},j+{1\over 2}}\}\cr 

\Gamma_{i,j}:=\{O&,&v_{j+1}&,&t_{i+1,j}&,&t_{i+2,j+1}&,&s_{i+{1\over 2},j+{1\over 2}}\}\cr 

\Delta_{i,j}:=\{O&,&v_{j+1}&,&t_{i-1,j}&,&t_{i,j+1}&,&s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\Epsilon_{i,j}:=\{O&,&v_{j+1}&,&v_j&,&t_{i+1,j}&,&s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\Zeta_{i,j}:=\{O&,&v_{j+1}&,&v_j&,&t_{i-1,j}&,&s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\Eta_{i,j}:=\{v_{j+1}&,& v_{j}&,&t_{i-1,j}&,
   & t_{i+1,j}&,& s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\Theta_{i,j}:=\{v_{j+1}&,&t_{i-1,j}&,& t_{i+1,j}&,
   & s_{i-{1\over 2},j-{1\over 2}}&,&s_{i+{1\over 2},j+{1\over 2}}\}\cr 

\Iota_{i,j}:=\{v_{j+1}&,&t_{i,j+1}&,&t_{i-1,j}&,
   & s_{i-{1\over 2},j-{1\over 2}}&,&s_{i+{1\over 2},j+{1\over 2}}\}\cr 

\end{array}
$$
\caption{\label{tab.simplices} Representatives for the nine orbits of
maximal simplices in $\T$.}
\end{table}


There are 7 orbits of boundary facets in $\T$, with representatives given in
Table \ref{tab.boundary}. The first five orbits triangulate the 16 square
anti-prisms. The last two orbits triangulate the 32 tetrahedra
$T_{i,j}$. For example,
$T_{0,0}$ is triangulated with $\Theta_{0,0}\setminus v_{1}$,
$\Theta'_{0,0}\setminus h_{1}$,
$\Iota_{0,0}\setminus v_{1}$ and
$\Iota'_{0,0}\setminus h_{1}$. Each of the four 3-simplices joins 
the two points
$s_{-{1\over 2},-{1\over 2}}$ and $s_{i+{1\over 2},j+{1\over 2}}$, which lie
in two opposite edges of $T_{0,0}$ to one of the remaining four edges of
$T_{0,0}$.

\begin{table}[htb]
\small
$$
\begin{array}{lcccl}
\Gamma_{i,j}\setminus O&=&
  \{v_{j+1},\ t_{i+1,j},\ t_{i+2,j+1},\ s_{i+{1\over 2},j+{1\over 2}}\} & 
  \subset & P_{j+{1\over 2}}  \cr
\Eta_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2}}&=&
  \{v_{j+1},\  v_{j},\ t_{i-1,j},\ t_{i+1,j}\} &
  \subset & P_{j+{1\over 2}} \cr
\Eta_{i+1,j+1}\setminus v_{j+2}&=&
  \{v_{j+1},\ t_{i,j+1},\ t_{i+2,j+1},\ s_{i+{1\over 2},j+{1\over 2}}\} & 
  \subset & P_{j+{1\over 2}}  \cr
\Theta_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2} }&=&
  \{v_{j+1},\ t_{i-1,j},\ t_{i+1,j},\ s_{i+{1\over 2},j+{1\over 2}}\} & 
  \subset & P_{j+{1\over 2}}  \cr
\Iota_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2} }&=&
  \{v_{j+1},\ t_{i-1,j},\ t_{i,j+1},\ s_{i+{1\over 2},j+{1\over 2}}\} & 
  \subset & P_{j+{1\over 2}}  \cr
\Theta_{i,j}\setminus v_{j+1} &=&
  \{t_{i-1,j},\  t_{i+1,j},\ s_{i-{1\over 2},j-{1\over 2}},\ s_{i+{1\over 2},j+{1\over 2}}\} &
  \subset & T_{i,j} \cr 
\Iota_{i,j}\setminus v_{j+1} &=& 
  \{ t_{i,j+1},\ t_{i-1,j},\  s_{i-{1\over 2},j-{1\over 2}},\ s_{i+{1\over 2},j+{1\over 2}}\} & 
  \subset  & T_{i,j} \cr 
\end{array}
$$
\caption{\label{tab.boundary} Representatives for the seven orbits of
boundary facets in $\T$.}
\end{table}


There are 19 orbits of interior facets in the triangulation $\T$, with
representatives given in Table \ref{tab.interior}.
For each one we write its two representations as the complement of
a vertex in a maximal simplex of $\T$ followed by its four vertices. As
before, the indices $i$ and $j$ range over all the possibilities modulo 8 and
with $i+j$ even. This gives 32 elements of each orbit and the other 32 are
obtained applying the transformation $g_4$ to them.

\begin{table}[htb]
\small
$$
\begin{array}{ll}

\alpha_{i,j}:=
\Alpha_{i,j}\setminus O  = & 
\Iota_{i,j}\setminus  t_{i-1,j}= \hfill\ 
\{v_{j+1},\ t_{i,j+1},\ s_{i+{1\over 2},j+{1\over 2}},\  s_{i-{1\over 2},j-{1\over 2}}\}\cr

\beta_{i,j}:=
\Alpha_{i,j}\setminus v_{j+1} = &
\Beta'_{j,i}\setminus h_{i+1} = \hfill\ 
\{O,\ t_{i,j+1},\  s_{i-{1\over 2},j-{1\over 2}},\ s_{i+{1\over 2},j+{1\over 2}}\}\cr

\gamma_{i,j}:=
\Alpha_{i,j}\setminus t_{i,j+1} = & 
\Beta_{i,j}\setminus t_{i+1,j} = \hfill\ 
\{O,\ v_{j+1},\  s_{i-{1\over 2},j-{1\over 2}},\ s_{i+{1\over 2},j+{1\over 2}}\}\cr

\delta_{i,j}:=
\Alpha_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2}} = & 
\Zeta_{i+1,j+1}\setminus v_{j+2} = \hfill\ 
\{O,\ v_{j+1},\ t_{i,j+1},\ s_{i+{1\over 2},j+{1\over 2}}\}\cr

\epsilon_{i,j}:=
\Alpha_{i,j}\setminus s_{i+{1\over 2},j+{1\over 2}} = & 
\Delta_{i,j}\setminus t_{i-1,j} = \hfill\ 
\{O,\ v_{j+1},\ t_{i,j+1},\  s_{i-{1\over 2},j-{1\over 2}}\}\cr

\zeta_{i,j}:=
\Beta_{i,j}\setminus O  = & 
\Theta_{i,j}\setminus t_{i-1,j}  = \hfill\ 
\{v_{j+1},\ t_{i+1,j},\ s_{i-{1\over 2},j-{1\over 2}},\  s_{i+{1\over 2},j+{1\over 2}}\}\cr 

\eta_{i,j}:=
\Beta_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2}} = & 
\Gamma_{i,j}\setminus t_{i+2,j+1} = \hfill\ 
\{O,\ v_{j+1},\ t_{i+1,j},\ s_{i+{1\over 2},j+{1\over 2}}\}\cr 

\theta_{i,j}:=
\Beta_{i,j}\setminus s_{i+{1\over 2},j+{1\over 2}}  = & 
\Epsilon_{i,j}\setminus v_{j} = \hfill\ 
\{O,\ v_{j+1},\ t_{i+1,j},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\iota_{i,j}:=
\Gamma_{i-1,j-1}\setminus v_{j} = & 
\Delta'_{j,i}\setminus h_{i+1} = \hfill\ 
\{O,\ t_{i,j-1},\ t_{i+1,j},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\kappa_{i,j}:=
\Gamma_{i-1,j-1}\setminus t_{i,j-1}  = & 
\Epsilon_{i,j}\setminus v_{j+1}  = \hfill\ 
\{O,\ v_{j},\ t_{i+1,j},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\multicolumn{2}{l}{
\lambda_{i,j}:=
\Gamma_{i-1,j-1}\setminus s_{i-{1\over 2},j-{1\over 2}} = 
\Delta_{i+1,j-1}\setminus s_{i+{1\over 2},j-{3\over 2}} = \hfill\ 
\{O,\ v_{j},\ t_{i,j-1},\ t_{i+1,j}\}}\cr 

\mu_{i,j}:=
\Delta_{i,j}\setminus O  = & 
\Iota_{i,j}\setminus s_{i+{1\over 2},j+{1\over 2}} =\hfill\ 
\{v_{j+1},\ t_{i-1,j},\ t_{i,j+1},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\nu_{i,j}:=
\Delta_{i,j}\setminus t_{i,j+1} = & 
\Zeta_{i,j}\setminus v_{j} = \hfill\ 
\{O,\ v_{j+1},\ t_{i-1,j},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\xi_{i,j}:=
\Epsilon_{i,j}\setminus O  = &
\Eta_{i,j}\setminus t_{i-1,j}  = \hfill\ 
\{v_{j+1},\ v_j,\ t_{i+1,j},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\omicron_{i,j}:=
\Epsilon_{i,j}\setminus t_{i+1,j}  = &
\Zeta_{i,j}\setminus t_{i-1,j}  = \hfill\ 
\{O,\ v_{j+1},\ v_j,\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\pi_{i,j}:=
\Epsilon_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2}} = &
\Zeta_{i+2,j}\setminus s_{i+{3\over 2},j-{1\over 2}}  = \hfill\ 
\{O,\ v_{j+1},\ v_j,\ t_{i+1,j}\}\cr 

\rho_{i,j}:=
\Zeta_{i,j}\setminus O  = & 
\Eta_{i,j}\setminus t_{i+1,j} = \hfill\ 
\{v_{j+1},\ v_j,\ t_{i-1,j},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\sigma_{i,j}:=
\Eta_{i,j}\setminus v_j  = & 
\Theta_{i,j}\setminus s_{i+{1\over 2},j+{1\over 2}}  = \hfill\ 
\{v_{j+1},\ t_{i-1,j},\ t_{i+1,j},\ s_{i-{1\over 2},j-{1\over 2}}\}\cr 

\tau_{i,j}:=
\Theta_{i,j}\setminus t_{i+1,j}  = & 
\Iota_{i,j}\setminus t_{i,j+1} = \hfill\ 
\{v_{j+1},\ t_{i-1,j},\ s_{i+{1\over 2},j+{1\over 2}},\  s_{i-{1\over 2},j-{1\over 2}}\}\cr
\end{array}
$$
\caption{\label{tab.interior} Representatives for the nineteen orbits of
interior facets in  $\T$.}
\end{table}


\subsection{$\T$ is a triangulation, with two orbits of flips}
\label{sub.flips}

In order to prove that $\T$ is a triangulation and compute its flips, 
in Table \ref{tab.circuits} we display a list of affine equalities valid on
$\A$. Each equality involves only the points of $\A$ in or joined to one
representative  of one of the 19 orbits of interior facets in $\T$, although
different  orbits may produce the same equality. In other words, the points
on the left  and right part of each equality are the positive and negative
parts of the circuit supported on the corresponding interior facet of $\T$.
The group $G$ acts freely over the circuits
supported on facets except for those of types $\gamma$ (same circuit as
$\tau$), $\iota$ and $\lambda$, in which the stabilizer has exactly two
elements, as indicated in Table \ref{tab.circuits}.


The reader can check the equalities with 
a symbolic computation program or can verify them by hand in the following
way:  first check that in every equation the sum of coefficients is
equal on both sides; second,
forget the appearances of the point $O$ and perform the following
substitutions: $t_{k,l}= h_k + v_l$,
$s_{k+{1\over2}, l+{1\over 2}}= (h_k + h_{k+1} + v_l + v_{l+1})/2$,
$h_{k+1}+h_{k-1} = \sqrt{2} h_k$, and $v_{l+1}+v_{l-1} =\sqrt{2} v_l$. After
this is done all terms should cancel out in all the equations.

\begin{table}[t]
\small
$
C(\alpha_{0,0}),C(\epsilon_{0,0}),C(\mu_{0,0}):    
\hfill
(\sqrt{2}-1) O  + {1+\sqrt{2}\over 2}  t_{-1,0} + s_{{1\over 2},{1\over 2}} 
={\sqrt{2}\over 2} v_{1} + {1\over 2} t_{0,1} + \sqrt{2} s_{-{1\over 2},-{1\over 2}} 
$
\medskip\noindent \\
$
C(\beta_{0,0}):                                    \hfill
({\sqrt{2}\over 2}+1) v_{1} + ({\sqrt{2}\over 2}+1) h_{1} + s_{-{1\over 2},-{1\over 2}}  
=2 O  + (1+\sqrt{2} ) s_{{1\over 2},{1\over 2}}
$
\medskip\noindent \\
$
C(\gamma_{0,0})=C(\gamma'_{0,0}),C(\tau_{0,0})=C(\tau'_{0,0}):                      \hfill
 t_{1,0} + t_{0,1}
=2  s_{{1\over 2},{1\over 2}}
$
\medskip\noindent \\
$
C(\delta_{0,0}):                                  \hfill
s_{-{1\over 2},-{1\over 2}} + (1 + {\sqrt{2}\over 2}) v_{2}  + s_{{1\over 2},{1\over 2}} 
= (2-{\sqrt{2}\over 2}) O + {\sqrt{2}\over 2} v_{1} + (1+{\sqrt{2}\over 2}) t_{0,1}
$
\medskip\noindent \\
$
C(\zeta_{0,0}),C(\xi_{0,0}),C(\omicron_{0,0}),C(\rho_{0,0}):
\hfill
(2-\sqrt{2}) O  + {\sqrt{2}\over 2} t_{1,0} + (1+{\sqrt{2}\over 2}) t_{-1,0} 
=v_{1} + 2 s_{-{1\over 2},-{1\over 2}}
$
\medskip\noindent \\
$
C(\eta_{0,0}):\hfill 
2 s_{-{1\over 2},-{1\over 2}} + (1+\sqrt{2}) t_{2,1}  
=(2-\sqrt{2}) O + \sqrt{2} v_{1} + (1+ \sqrt{2}) t_{1,0} 
$
\medskip\noindent \\
$
C(\theta_{0,0}):\hfill 
\sqrt{2} s_{{1\over 2},{1\over 2}} + v_{0} + (3-2\sqrt{2}) O 
= v_{1} + t_{1,0} + (2-\sqrt{2}) s_{-{1\over 2},-{1\over 2}}
$
\medskip\noindent \\
$
C(\iota_{0,0})=C(\iota'_{1,-1}):\hfill 
 v_{0} + h_{1}  
=O + t_{1,0}
$
\medskip\noindent \\
$
C(\kappa_{0,0}):\hfill 
(1+\sqrt{2}) t_{0,-1} + \sqrt{2} v_{1}  
=(2\sqrt{2}-2) O + t_{1,0} + 2 s_{-{1\over 2},-{1\over 2}}
$
\medskip\noindent \\
$
C(\lambda_{0,0})=C(\lambda'_{1,-1}):\hfill 
\sqrt{2} s_{-{1\over 2},-{1\over 2}} +\sqrt{2}  s_{{1\over 2},-{3\over 2}} 
=(\sqrt{2} -1) O + (\sqrt{2} +1) t_{0,-1}
$
\medskip\noindent \\
$
C(\nu_{0,0}): \hfill
\ t_{0,1} + \sqrt{2} v_{0} + (2-\sqrt{2}) O + t_{-1,0}
=2 v_{1} + 2 s_{-{1\over 2},-{1\over 2}}
$
\medskip\noindent \\
$ C(\pi_{0,0}):                        \hfill
s_{-{1\over 2},-{1\over 2}} + (1+\sqrt{2}) s_{{3\over 2},-{1\over 2}} +(1+{\sqrt{2}\over 2}) 
v_{1} 
=O + (1+{\sqrt{2}\over 2}) v_0 + (1+\sqrt{2}) t_{1,0}
$
\medskip\noindent   \\
$
C(\sigma_{0,0}):\hfill 
\sqrt{2} v_0  + 2 s_{{1\over 2},{1\over 2}}  
=v_{1} + {\sqrt{2}\over 2} t_{-1,0} + {1+\sqrt{2}\over 2} t_{1,0}
$
\caption{\label{tab.circuits} Affine equalities for the circuits
supported on interior facets of $\T$.}
\end{table}


\begin{lemma}
\label{lemma.triang}
$\T$ is a triangulation of $\A$.
\end{lemma}

\begin{proof}
We first check that $A_{i,j}$ is affinely independent. For this we compute the
determinant of the points $O$, $v_0$, $t_{0,0}$, $s_{-{1\over 2},-{3 \over 2}}$, and 
$s_{{1\over 2},-{1 \over 2}}$ (we are taking $i=0$ and $j=-1$):
$$
  \left| 
   \begin{matrix}
 0 & 0 & 1 & {1\over 2} + {\sqrt{2}\over 4}  & {1\over 2} + {\sqrt{2}\over 4} \cr
 0 & 0 & 0 & - {\sqrt{2}\over 4}             & {\sqrt{2}\over 4} \cr
 0 & 1 & 1 &  {\sqrt{2}\over 4}              & {1\over 2} + {\sqrt{2}\over 4} \cr
 0 & 0 & 0 & -{1\over 2} + {\sqrt{2}\over 4} & - {\sqrt{2}\over 4} \cr
 1 & 1 & 1 & 1 & 1 \cr
   \end{matrix}
  \right|
=\left| 
   \begin{matrix}
 - {\sqrt{2}\over 4}             & {\sqrt{2}\over 4} \cr
 -{1\over 2} + {\sqrt{2}\over 4} & - {\sqrt{2}\over 4} \cr
\end{matrix}
\right|
={\sqrt{2}\over8}.
$$

Since $A_{i,j}$ is an affine basis, for any point $a\in\A\setminus
\Alpha_{i,j}$ and $b\in A_{i,j}$, if $a$ and $b$ have non-zero
coefficient in the unique affine equality supported on
$A_{i,j}\cup\{a\}$, then
$A_{i,j}\cup\{a\}\setminus \{b\}$ is again a basis. Hence, the affine
equalities $C(\alpha_{i,j})$,
$C(\gamma_{i,j})$, $C(\delta_{i,j})$, and $C(\epsilon_{i,j})$ imply, 
respectively, that $\Iota_{i,j}$, $\Beta_{i,j}$,
$\Zeta_{i+1,j+1}$, and $\Delta_{i,j}$ are also bases. Using the same argument
and the other equalities we conclude that $\Gamma_{i,j}$, $\Epsilon_{i,j}$,
$\Eta_{i,j}$, and $\Theta_{i,j}$ are bases too. Thus, $\T$ consists only
of independent subsets of $\A$ and we can apply Lemma
\ref{lemma.pseudomanifold} to it.

The lists of boundary and interior facets of $\T$ given in Tables
\ref{tab.boundary} and \ref{tab.interior} are complete and non-redundant in
the sense that exactly one representative of each of the five facets of each
of the nine orbits of 4-simplices appears exactly once  in them. 
Moreover, in each of
$C(\alpha_{i,j}),\dots,C(\tau_{i,j})$ the two vertices joined to the
interior facet in question appear both on the left-hand side of the equality.
This implies that these two points are in opposite sides of the interior
facet. With this and Lemma
\ref{lemma.pseudomanifold} we only have
to check that some point of $\conv(\A)$ lies in the
convex hull of exactly one simplex of $\T$. For a generic point in the
interior of
$\conv(\A)$ but sufficiently  close to a facet of $\conv(\A)$, 
this follows from the fact that $\T$ induces a triangulation on that facet.
\end{proof}

\begin{lemma}  
\label{lemma.flips}
$\T$ has two orbits of flips under the action of its symmetry group $G$,
with representatives
supported on the circuits 
$$(\{O, t_{i-1,j},s_{i+{1\over 2}, j+{1\over 2}}\}, 
\{v_{j+1},t_{i, j+1},s_{i-{1\over 2}, j-{1\over 2}}\}) \hbox{ and}$$
$$(\{v_{j},s_{i+{1\over 2}, j+{1\over
2}}\},\{v_{j+1},t_{i-1, j},t_{i+1,j}\}).$$
\end{lemma}

\begin{proof}
That $(\{O, t_{i-1,j},s_{i+{1\over 2}, j+{1\over
2}}\},\{v_{j+1},t_{i, j+1},s_{i-{1\over 2}, j-{1\over 2}}\})$ and
$(\{v_{j},s_{i+{1\over 2}, j+{1\over 2}}\},$ $\{v_{j+1},t_{i-1,
j},t_{i+1,j}\})$ are circuits follows respectively from the equalities
$C(\alpha_{0,0})$ and $C(\sigma_{0,0})$ of Table \ref{tab.circuits}.

The first circuit spans $\conv(\A)$ and the maximal simplices
in its positive triangulation are $\Alpha_{i,j}$, $\Delta_{i,j}$, and
$\Iota_{i,j}$.
The second circuit spans the anti-prism facet $P_{j+{1\over 2}}$ of
$\conv(\A)$.  
The maximal simplices in its positive triangulation are
$\Eta_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2}}$ and
$\Theta_{i,j}\setminus s_{i-{1\over 2},j-{1\over 2}}$. In other words, $\T$
contains its positive triangulation and all the maximal simplices in it have
the same link. Hence, both circuits are flippable.

We now check that the other 15 orbits of interior facets are not flippable,
using Lemma \ref{lemma.flippable} for this. 
In the first place, if a flippable circuit has more than two positive
elements, then it must be supported on at least $3\choose 2$ facets of $\T$.
This implies that the circuits supported on the facets of types $\beta$,
$\delta$, $\theta$, $\nu$, and $\pi$ are not flippable, because they are
supported only on one facet of $\T$ each and their positive parts have at
least three elements.

The circuits supported on facets of types $\zeta$ (same circuit as $\xi$,
$\omicron$, and $\rho$), $\eta$, $\iota$, $\kappa$, and $\lambda$ all contain
the element
$O$ and hence we can apply part (ii) of Lemma \ref{lemma.flippable} to them.
According to it we would need at least $2\cdot 3$, 
$2\cdot 1$, $3\cdot 1$, $2\cdot 1$,  and $3\cdot 1$ flippable facets for 
them respectively, but they are supported in only 4, 1, 2, 1, and 2 facets.

Only the facets of types $\gamma$ and $\tau$ remain to be checked.
$\gamma_{0,0}$ and $\tau_{0,0}$ are  both supported on the circuit
$(\{t_{1,0},t_{0,1}\},\{s_{{1\over 2},{1\over 2}}\})$.This circuit is
not flippable since the link of $\{t_{1,0},s_{{1\over 2},{1\over 2}}\}$
in $\T$ contains
$\{O,v_{1},v_{2}\}$ (simplex $\Zeta_{1,1}$), the link of
$\{t_{0,1},s_{{1\over 2},{1\over 2}}\}$ contains
$\{O,v_{1},t_{2,1}\}$ (simplex $\Gamma_{0,0}$) and the points $v_{2}$
and
$t_{2,1}$ lie both on the same side of the hyperplane spanned by
$\{O,v_{1},t_{1,0},t_{0,1},s_{{1\over 2},{1\over 2}}\}$
(equation $C(\kappa_{1,1})$).
\end{proof}

\subsection{A locally acyclic orientation of the edges of $\T$}
\label{sub.orient}

We now introduce an orientation of the 1-skeleton of the triangulation $\T$.
There are 14 orbits of edges. In Table \ref{tab.orientedges} below we show a 
representative for each orbit, and a particular maximal simplex containing it. 
We orient the representatives from
the vertex which appears first to the second and let each orbit be oriented
by the action of the symmetry group $G$.


\begin{table}[htb]
\small
$$
\begin{array}{lllllll}
\{O,v_j\}\in \Alpha_{i,j+1} &\qquad
\{v_j,v_{j+1}\}\in \Epsilon_{i,j} \cr
\{O,t_{i,j+1}\}\in \Alpha_{i,j} &\qquad
\{O,s_{i+{1\over 2,},j+{1\over 2}}\}\in \Alpha_{i,j} \cr
\{v_j,t_{i+1,j}\}\in \Gamma_{i+1,j+1} &\qquad
\{t_{i,j-1},v_j\}\in \Delta_{i+1,j-1} \cr
\{v_j,s_{i-{1\over 2,},j-{1\over 2}}\}\in \Alpha_{i-1,j-1} &\qquad
\{s_{i+{1\over 2,},j-{3\over 2}},v_j\}\in \Epsilon_{i+1,j-1} \cr
\{t_{i-1,j},t_{i+1,j}\}\in \Eta_{i,j} & \qquad
\{t_{i,j-1},t_{i+1,j}\}\in \Gamma_{i-1,j-1} \cr
\{s_{i-{1\over 2,},j-{1\over 2}},t_{i,j+1}\}\in \Alpha_{i,j} &\qquad
\{s_{i-{1\over 2,},j-{1\over 2}},s_{i+{1\over 2,},j+{1\over 2}}\}\in \Alpha_{i,j} \cr
\{t_{i-1,j},s_{i+{1\over 2,},j+{1\over 2}}\}\in \Theta_{i,j} &\qquad
\{t_{i,j-1},s_{i-{1\over 2,},j-{1\over 2}}\}\in \Beta_{i-1,j-1} \cr
\end{array}
$$
\caption{\label{tab.orientedges} The fourteen orbits of edges in $\T$.}
\end{table}


That this orientation {\em is locally acyclic} can be seen in Table \ref{tab.orientsimplices}, where the
total order induced on the vertices of each maximal representative simplex is 
shown. It {\em has no reversible edges} since the reversal of any
edge produces a cycle in the simplex included after it
in Table \ref{tab.orientedges}.
The only vertices which are sinks of some maximal simplex in
Table \ref{tab.orientsimplices} are 
$v_{j+1}$, $t_{i,j+1}$ and $s_{i+{1\over 2},j+{1\over 2}}$, but the first two
are not sinks in
$\Alpha_{i,j}$ and the last one is not a sink in $\Gamma_{i,j}$.
Hence, the orientation {\it has no sinks}.

\begin{table}[htb]
\small
$$
\begin{array}{ccccccccccc}

\Alpha_{i,j}:&\{O&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to & v_{j+1}&
\to & t_{i,j+1}&
\to & s_{i+{1\over 2},j+{1\over 2}}
\}\cr 

\Beta_{i,j}:&\{O&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to & t_{i+1,j}&
\to & v_{j+1}&
\to & s_{i+{1\over 2},j+{1\over 2}}
\}\cr 

\Gamma_{i,j}:&\{O&
\to & t_{i+1,j}&
\to & v_{j+1}&
\to & s_{i+{1\over 2},j+{1\over 2}}&
\to & t_{i+2,j+1}
\}\cr 

\Delta_{i,j}:&\{O&
\to & t_{i-1,j}&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to & v_{j+1}&
\to & t_{i,j+1}
\}\cr 

\Epsilon_{i,j}:&\{O&
\to & v_j&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to & t_{i+1,j}&
\to & v_{j+1}
\}\cr 

\Zeta_{i,j}:&\{O&
\to & v_j&
\to & t_{i-1,j}&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to & v_{j+1}
\}\cr 

\Eta_{i,j}:&\{
v_{j}&
\to & t_{i-1,j}&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to & t_{i+1,j}&
\to &v_{j+1}
\}\cr 

\Theta_{i,j}:&\{
 t_{i-1,j}&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to & t_{i+1,j}&
\to &v_{j+1}&
\to & s_{i+{1\over 2},j+{1\over 2}}
\}\cr

\Iota_{i,j}:&\{
 t_{i-1,j}&
\to & s_{i-{1\over 2},j-{1\over 2}}&
\to &v_{j+1}&
\to & t_{i,j+1}&
\to & s_{i+{1\over 2},j+{1\over 2}}
\}\cr 
\end{array}
$$
\caption{\label{tab.orientsimplices} The orientation of the
1-skeleton of $\T$ is locally acyclic.}
\end{table}

Finally, let us see that the two types of flippable circuits of $\T$ 
(see Lemma \ref{lemma.flips}) are
{\em sandwich circuits}, in the terms of Definition 
\ref{defi.sandwich}. This holds since 
the orientation of the 1-skeleton of $\T$ is
compatible only with the following total order on the supports
of the circuits:
$$
\stackrel{+}{O}\to 
\stackrel{+}{t_{i-1,j}} \to
\stackrel{-}{s_{i-{1\over 2}, j-{1\over 2}}}\to 
\stackrel{-}{v_{j+1}}\to 
\stackrel{-}{t_{i, j+1}} \to 
\stackrel{+}{s_{i+{1\over 2}, j+{1\over 2}}},
$$
$$
\stackrel{+}{v_{j}} \to 
\stackrel{-}{t_{i-1, j}} 
\to \stackrel{-}{t_{i+1,j}} \to 
\stackrel{-}{v_{j+1}} \to 
\stackrel{+}{s_{i+{1\over 2}, j+{1\over 2}}}.
$$

The following statement sums up the key facts on $\T$ proved throughout this
section:

\begin{theorem}
\label{thm.dim4}
$\T$ is a triangulation of the point configuration $\A\subset \reals^4$.
With the locally acyclic orientation we
have given to its edges it has no global sinks, it has no reversible
edges and every flippable circuit is a sandwich circuit.

Hence, the staircase refinement $\stair(\T\times \T_2)$,
does not have any flips, where $\T_2$
is the 2-dimensional triangulation of Corollary
\ref{coro.noflips2} 
\qed
\end{theorem}



\begin{remark}
\label{rem.fewflips}
The triangulation $\T$ described in the last pages is based on the construction
in Section 4 of \cite{Santos-fewflips}. We show here this connection
because understanding that (simpler) triangulation will help to understand this
one.

Let $n\ge 3$ be an integer. Let $\A_n\subset \reals^4$ consist of the following
$(n+1)^2$ points: $O:=(0,0,0,0)$, $v_{j}:=\left(0,0,\cos\left({\pi \over
4}j\right), 
\sin\left({\pi \over 4}j\right) \right)$, $h_i:=\left(
\cos\left({\pi \over 4}i\right), 
\sin\left({\pi \over 4}i\right),0,0 \right)$, and $t_{i,j}:=h_i + v_j - O =
\left(
\cos\left({\pi \over 4}i\right), \sin\left({\pi \over 4}i\right), 
\cos\left({\pi \over 4}j\right), \sin\left({\pi \over 4}j\right) \right)$.
The indices $i$ and $j$ range over all the possibilities modulo $n$.
Let $\T_n$ be the triangulation having the
following $6n^2$ maximal simplices. For each
$i,j=0,\dots, n-1$:
$$
\begin{array}{ll}
\Phi_{i,j}:=
\{O,v_{j},t_{i,j+1},t_{i,j},t_{i+1,j+1}\},\qquad&
\Phi'_{i,j}:=
\{O,h_{i},t_{i+1,j},t_{i,j},t_{i+1,j+1}\},\cr 
\Psi_{i,j}:=
\{O,v_{j},t_{i+1,j},t_{i,j},t_{i+1,j+1}\},\qquad&
\Psi'_{i,j}:=
\{O,h_{i},t_{i,j+1},t_{i,j},t_{i+1,j+1}\},\cr
\Omega_{i,j}:=
\{O,v_{j+1},v_{j},t_{i+1,j+1},t_{i,j+1}\},\qquad&
\Omega'_{i,j}:=
\{O,h_{i+1},h_{i},t_{i+1,j+1},t_{i+1,j}\}. 
\end{array}
$$

The configuration $\A_n$ is the product with itself of the two-dimensional
point configuration
$\B_n$ consisting of the vertices and the centroid of a regular $n$-gon. The
triangulation $\T_n$ described above equals the staircase triangulation
$\stair({\mathcal S}_n\times {\mathcal S}_n)$, where ${\mathcal S}_n$ is the radial
triangulation of ${\B}_n$, with the following locally acyclic orientation:
orient all interior edges from the center to the boundary and orient the
boundary in the direction of positive angles. The six 4-simplices in
the list above  are the monotone staircases in the following
grid:
$$
\begin{array}{|c|c|c|}
\hline
v_{j+1} & t_{i,j+1} & t_{i+1,j+1} \cr
\hline
v_j & t_{i,j} & t_{i+1,j} \cr
\hline
O & h_i & h_{i+1} \cr
\hline
\end{array}
$$
 A different description of $\T_n$ is as
follows: let $P=\conv(\A)$, which equals the product of two $n$-gons. Each of the 
$2n$ facets of $P$ is a prism over a regular $n$-gon (the facets form two
cycles with $n$ prisms each; each cycle is a solid torus and the two solid 
tori are glued along their boundaries). If we divide each of the $2n$ prisms into
$n$-triangular prisms by its medial axis, we have the boundary of $P$ decomposed
into $2n^2$ equal triangular prisms. In $\T_n$, the cone of each such prism to 
the centroid $O$ of $P$ is triangulated with three 4-simplices, one from each of the three
orbits $\Phi$, $\Psi$ and $\Omega$. 

To go from the triangulation $\T_8$ to our
triangulation $\T$ proceed as follows:
In the point configuration $\A_8$, perform a positive
rotation of order 8 to the octagons containing the points $h_i$ and $v_j$ (but
leaving the
$t_{i,j}$'s fixed) and substitute each point $t_{i,j}$ with $i+j$ even by
the point $s_{i-{1\over 2},j-{1\over 2}}$. This gives the point configuration
$\A$. The triangulation $\T_8$ becomes
a geometric simplicial complex with non-convex boundary but whose
simplices still intersect properly. Each of the three orbits of 4-simplices
in $\T_8$ divides into two orbits of simplices present in $\T$: the
orbits $\Alpha$ and $\Gamma$ for $\Phi$,
$\Beta$ and $\Delta$ for $\Psi$, and $\Epsilon$ and $\Zeta$ for $\Omega$.
The other three orbits $\Eta$, $\Theta$ and $\Iota$ of $\T$ 
fill in the convex hull of $\A$.

The above modification on $\T_n$ is in principle possible for any 
even $n$. But with $n=4$ bad intersections occur between
simplices and with $n=6$ the modification works but some of the flippable
circuits are not sandwich circuits.


When considered in $\T_8$ (or in any other $\T_n$),
the orientation of the 1-skeleton described in Section \ref{sub.orient} is
still locally acyclic and has no reversible edges or sinks.
With $n=3$ this is exactly the triangulation and orientation which
appeared in \cite[Section 4]{Santos-fewflips}.
It is interesting that the triangulation induced by
$\T_n$ in the Schlegel diagram of $\conv(\A_n)$ with respect to any of its
facets has dimension three and its 1-skeleton oriented in a
locally acyclic way, without reversible edges, sinks or sources
(but with non-sandwich circuits). This might
be a step towards a triangulation without flips in dimension five.



\end{remark}

\subsection{Integer coordinates}
\label{sub.integer}
\label{sub.fewflips}


\begin{table}[ht]
\small
$
C(\alpha_{0,0}),C(\epsilon_{0,0}),C(\mu_{0,0}):      \hfill
2 O  + 5  t_{-1,0} + 4 s_{{1\over 2},{1\over 2}}
= 3  v_{1} + 2 t_{0,1} + 6 s_{-{1\over 2},-{1\over 2}}
$
\smallskip\noindent   \\
$
C(\alpha'_{0,0}),C(\epsilon'_{0,0}),C(\mu'_{0,0}):      \hfill
2 O  + 7  t_{0,-1} + 6 s_{{1\over 2},{1\over 2}}
= 4  h_{1} + 3 t_{1,0} + 8 s_{-{1\over 2},-{1\over 2}} 
$
\medskip\noindent \\
$
C(\beta_{0,0}):                                    \hfill
21 v_{1} + 20 h_{1} + 12 s_{-{1\over 2},-{1\over 2}} 
=t_{1,0} + 24 O  + 28 s_{{1\over 2},{1\over 2}}
$
\smallskip\noindent   \\
$
C(\beta'_{0,0}):                                    \hfill
20 h_{1} + 21 v_{1} + 12 s_{-{1\over 2},-{1\over 2}} + t_{0,1}
=24 O  + 30 s_{{1\over 2},{1\over 2}}
$
\medskip\noindent \\
$
C(\gamma_{0,0})=C(\gamma'_{0,0}),C(\tau_{0,0})=C(\tau'_{0,0}):                      \hfill
 t_{1,0} + t_{0,1} 
=2  s_{{1\over 2},{1\over 2}}
$
\medskip\noindent \\
$
C(\delta_{0,0}):                                  \hfill
12 s_{-{1\over 2},-{1\over 2}} + 20 v_{2}  +  12 s_{{1\over 2},{1\over 2}}
= 14 O + 9 v_{1} + 21 t_{0,1}
$
\smallskip\noindent   \\
$
C(\delta'_{0,0}):                                  \hfill
12 s_{-{1\over 2},-{1\over 2}} + 21 h_{2}  +  12 s_{{1\over 2},{1\over 2}}
= 17 O + 8 h_{1} + 20 t_{1,0}
$
\medskip\noindent \\
$
C(\zeta_{0,0}),C(\xi_{0,0}),C(\omicron_{0,0}),C(\rho_{0,0}): \hfill
2 O  + 5 t_{1,0} + 2 t_{-1,0} 
= 3 v_{1} + 6 s_{-{1\over 2},-{1\over 2}}
$
\smallskip\noindent   \\
$
C(\zeta'_{0,0}),C(\xi'_{0,0}),C(\omicron'_{0,0}),C(\rho'_{0,0}): \hfill
2 O  + 7 t_{0,1} + 3 t_{0,-1} 
= 4 h_{1} + 8 s_{-{1\over 2},-{1\over 2}}
$
\medskip\noindent \\
$
C(\eta_{0,0}):\hfill 
12 s_{-{1\over 2},-{1\over 2}} + 15 t_{2,1}
= 4 O + 9 v_{1} + 14 t_{1,0} 
$
\smallskip\noindent   \\
$
C(\eta'_{0,0}):\hfill 
12 s_{-{1\over 2},-{1\over 2}} + 14 t_{1,2} 
= 3 O + 8 h_{1} + 15 t_{0,1}  
$
\medskip\noindent \\
$
C(\theta_{0,0}):\hfill 
30 s_{{1\over 2},{1\over 2}} + 20 v_{0} + 4 O 
=  21 v_{1} +  21 t_{1,0} + 12 s_{-{1\over 2},-{1\over 2}}
$
\smallskip\noindent   \\
$
C(\theta'_{0,0}):\hfill 
28 s_{{1\over 2},{1\over 2}} + 21 h_{0} + 3 O 
=  20 h_{1} +  20 t_{0,1} + 12 s_{-{1\over 2},-{1\over 2}} 
$
\medskip\noindent \\
$
C(\iota_{0,0})=C(\iota'_{1,-1}):\hfill 
 v_{0} + h_{1}
=O + t_{1,0}
$
\smallskip\noindent \\
$
C(\iota'_{0,0})=C(\iota_{-1,1}):\hfill 
 h_{0} + v_{1} 
=O + t_{0,1}
$
\medskip\noindent \\
$
C(\kappa_{0,0}):\hfill 
5 t_{0,-1} + 3 v_{1} 
=2 O +  2 t_{1,0} + 4 s_{-{1\over 2},-{1\over 2}}
$
\smallskip\noindent   \\
$
C(\kappa'_{0,0}):\hfill 
7 t_{-1,0} + 4 h_{1}  
=2 O +  3 t_{0,1} + 6 s_{-{1\over 2},-{1\over 2}}
$
\medskip\noindent \\
$
C(\lambda_{0,0})=C(\lambda'_{1,-1}):\hfill 
4 s_{-{1\over 2},-{1\over 2}} + 4  s_{{1\over 2},-{3\over 2}} 
 = O + 7 t_{0,-1}
$
\smallskip\noindent \\
$
C(\lambda'_{0,0})=C(\lambda_{-1,1}):\hfill 
3 s_{-{1\over 2},-{1\over 2}} + 3  s_{{-3\over 2},{1\over 2}}
= O + 5 t_{-1,0}
$
\medskip\noindent \\
$
C(\nu_{0,0}): \hfill
3 t_{0,1} + 4 v_{0} + 2 O +  3 t_{-1,0}
=6 v_{1} + 6 s_{-{1\over 2},-{1\over 2}}
$
\smallskip\noindent   \\
$
C(\nu'_{0,0}): \hfill
2 t_{1,0} + 3 h_{0} + O +  2 t_{0,-1}
=4 h_{1} + 4 s_{-{1\over 2},-{1\over 2}}
$
\medskip\noindent \\
$ C(\pi_{0,0}):                        \hfill
12 s_{-{1\over 2},-{1\over 2}} + 30 s_{{3\over 2},-{1\over 2}} + 21 v_{1} 
= 14 O + 20 v_0 + 29 t_{1,0}
$
\smallskip\noindent   \\
$ 
C(\pi'_{0,0}):                        \hfill
12 s_{-{1\over 2},-{1\over 2}} + 28 s_{-{1\over 2},{3\over 2}} + 20 h_{1} 
= 10 O + 21 h_0 + 29 t_{0,1}
$
\medskip\noindent   \\
$
C(\sigma_{0,0}):\hfill 
4 v_0  + 6 s_{{1\over 2},{1\over 2}}  
= 3 v_{1} + 2 t_{-1,0} + 5 t_{1,0}
$
\smallskip\noindent   \\
$
C(\sigma'_{0,0}):\hfill 
6 h_0  + 8 s_{{1\over 2},{1\over 2}}  
= 4 h_{1} + 3 t_{0,-1} + 7 t_{0,1}
$
\caption{\label{tab.integer} Affine equalities for the circuits
supported on interior facets of $\T_{{\rm int}}$.}
\end{table}



Consider the following sixteen points in $\reals^4$:
{\small$$
\begin{array}{llll}
h_0:=(4,-4,0,0), & h_1:=(6,0,0,0),  & h_2:=(4,4,0,0),  & h_3:=(0,6,0,0), \cr
h_4:=(-4,4,0,0), & h_5:=(-6,0,0,0), & h_6:=(-4,-4,0,0),& h_7:=(0,-6,0,0),\cr
v_0:=(0,0,6,0),  & v_1:=(0,0,4,4),  & v_2:=(0,0,0,6),  & v_3:=(0,0,-4,4),\cr
v_4:=(0,0,-6,0), & v_5:=(0,0,-4,-4),& v_6:=(0,0,0,-6), & v_7:=(0,0,4,-4).\cr
\end{array}
$$}
Let $\A_{{\rm int}}$ be the point configuration 
consisting of them, together with the origin $O=(0,0,0,0)$, the 32 points
$t_{i,j}:=h_i + v_j - O$ for all values of $i,j\in\{0,\dots,7\}$ with $i+j$
odd, and the 32 points $s_{i+{1\over 2},j+{1\over 2}}=(t_{i,j+1}+t_{i+1,j})/
2$ for all values of $i,j\in\{0,\dots,7\}$ with $i+j$ even. Indices are 
regarded modulo 8. The essential difference between  $ \A_{{\rm int}}$ and
the point configuration $\A$ of the previous sections is that the regular
octagons in the first two and last two coordinate planes have been modified
to have integer coordinates (using the approximation $\sqrt{2}\simeq 4/3$)
and hence they are not regular anymore. But, for
example,
$\conv(\A)$ and $\conv( \A_{{\rm int}})$ are combinatorially equivalent
polytopes. We construct a triangulation $ \T_{{\rm int}}$ of $
\A_{{\rm int}}$ following word by word the description in Section
\ref{sub.triang}, except that the symmetries displayed in Table
\ref{tab.symmetries} are only combinatorial. With the notation of Section
\ref{sub.triang}, the affine symmetry group of $ \T_{{\rm int}}$
is a subgroup of $G$ of index 2, generated by 
${g_h}^2$, ${g_v}^2$, and ${g_t \circ g_h\circ g_v}$.

The only other thing to be modified with respect to what we 
said in Sections \ref{sub.triang}, \ref{sub.flips} and
\ref{sub.orient} are the affine equalities displayed on Table
\ref{tab.circuits}. Each orbit of
interior facets of $\T$, say
$\alpha$,  breaks into two orbits in $ \T_{{\rm int}}$ having as
representatives
$\alpha_{0,0}$ and $\alpha'_{0,0}$. These two orbits may produce different
equalities, and all of them are displayed in  Table \ref{tab.integer}.
They can be verified as follows: first check that in every equation the sum
of coefficients is equal on both sides; second,
forget the appearances of the point $O$ and perform the following
substitutions:
$$ 
\begin{array}{l}
t_{k,l}= h_k + v_l, \qquad
s_{k+{1\over2}, l+{1\over 2}}= (h_k + h_{k+1} + v_l + v_{l+1})/2 \qquad 
\forall k,l\in\{0,\dots,7\}; \cr
2 h_{k+1} + 2 h_{k-1} = 3 h_k 
\qquad \hbox{and}\qquad
3 v_{k+1} + 3 v_{k-1} = 4 v_k
\qquad\hbox{if $k$ is even;}
\cr 
3 h_{k+1} + 3 h_{k-1} = 4 h_k 
\qquad \hbox{and}\qquad
2 v_{k+1} + 2 v_{k-1} = 3 v_k
\qquad\hbox{if $k$ is odd.}
\end{array}
$$

Comparing Tables \ref{tab.circuits} and \ref{tab.integer} we see that the 
only circuits that change are those supported on facets of type $\beta$.
But, since  $C(\beta_{0,0})$ and $C(\beta'_{0,0})$  in Table
\ref{tab.integer} have both at least three  
elements in their positive parts and are supported in only one facet of
$\T_{{\rm int}}$ each, Lemma
\ref{lemma.flippable} implies that they are still not flippable.
Hence, in Theorem \ref{thm.dim4} we can take $ \T_{{\rm int}}$ and
$\A_{{\rm int}}$ instead of $ \T$ and $\A$.






\section{The graph of triangulations versus the poset of subdivisions}
\label{sec.posets}


\subsection{The Baues poset}
\label{sub.baues}
Let $\A\subset \reals^k$ be a point configuration of dimension $d$. 
A {\em cell} of $\A$ is any
spanning subset $B$ of $\A$. A {\em face} of a cell $B$ is the intersection
$F\cap B$ of $B$ with any face $F$ of the convex hull of $B$.

\begin{defi}
\label{defi.subdivision}
A {\em (polyhedral) subdivision} of $\A$ is any family $\Pi$ of cells of
$\A$ such that $\cup_{B\in \Pi} \conv(B) =
\conv(\A)$ and for any $B_1,B_2\in \Pi$ one has 
$\conv(B_1)\cap\conv(B_2) = \conv(B_1\cap B_2)$ and 
$B_1\cap B_2$ is a (possibly empty) face of $B_1$ and $B_2$.
\end{defi}

The subdivisions of $\A$ are partially ordered by the following {\em
refinement} relation:
$$
\Pi \le \Pi' \qquad \Longleftrightarrow \qquad
\forall B\in\Pi \quad \exists B'\in \Pi' : B\subseteq B'.
$$
The partially ordered set 
(poset) so obtained is the {\em Baues poset} of $\A$, which we
denote $\Omega(\A)$. We call {\em strict Baues poset} the
Baues poset without the trivial subdivision $\{\A\}$.
A lower ideal in a poset $X$ is any
subposet $Y$ with the property that $x\in Y$ and $y < x$ imply $y\in Y$.
For any $x\in X$, the principal lower ideal $X_{\le x}$
(resp. strict principal lower ideal $X_{< x}$) of $x$ is
the subposet of elements below $x$, including $x$ (resp. excluding $x$).

The following lemma is proved as Corollary 4.5 and Proposition 5.3
in \cite{Santos-refine}. 

\begin{lemma}
\label{lemma.baues}
Let $\Pi$ be a polyhedral subdivision of $\A$. The following
conditions are equivalent:
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}

\item $\Pi$ has only two proper refinements.
\item All the proper refinements of $\Pi$ are triangulations.
\item $\Pi$ has only two proper refinements and they are triangulations
which differ by a geometric bistellar flip.
\end{enumerate}
Moreover, any pair of triangulations which differ by a geometric
bistellar flip is in these conditions. 
\qed
\end{lemma}

From now on we call 
geometric bistellar flip (or flip, for short) 
a subdivision in the conditions of Lemma \ref{lemma.baues}.
For any $X\subset \Omega(\A)$ we denote $G(X)$ the Baues poset
restricted to the triangulations and flips
in $X$. If $X$ is a lower ideal 
then $G(X)$ is a lower ideal as well, and is naturally a 
subgraph of the graph of triangulations of $\A$.
The following is a
version of Lemma 3.1 in \cite{Reiner-survey} or 
Proposition 4.8 in \cite{Santos-refine}. 


\begin{corollary}
\label{coro.baues}
Let $X$ be any lower ideal in $\Omega(\A)$. 
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}

\item If $G(X)$ is connected then $X$ is connected.
\item If $X_{<\Pi}$ is connected for every $\Pi\in X\setminus G(X)$,
then $G(X)$ is connected.
\item If the graph of triangulations $G(\Omega(\A))$ is disconnected then
there is a $\Pi\in \Omega(\A)\setminus G(\Omega(\A))$ 
whose strict lower ideal is disconnected. If, moreover, $\A$
is in general position, then there is a subconfiguration of $\A$ whose
strict Baues poset is disconnected.
\end{enumerate}
\end{corollary}


\begin{proof}
Part (i) is trivial because any subdivision can be refined to a
triangulation. Part (ii) is easy and implies the first half of (iii).
The ``moreover'' holds since in general position $\Omega(\A)_{<\Pi}$
is the product of the Baues posets of the cells of $\Pi$.
\end{proof}


\subsection{The coherent poset of subdivisions}
\label{sub.coherent}


A {\em height function} on $\A$ is any map $h:\A\to \reals$. A height
function is {\em affine} if it is the restriction of an affine map
$\reals^k \to \reals$. The
{\em coherent} \cite{GKZbook,Reiner-survey,Ziegler} or {\em regular}
\cite{BiFiSt,Lee}
subdivision of $\A$ induced by a height function
$h$ is 
$$
\{(h-f)^{-1}(0): f
 \hbox{ is an affine height function with } h\ge f\}.
$$ 
In other words, it is the subdivision of $\A$
obtained by orthogonal projection of the lower facets of the
configuration $\{(a,h(a))\in \reals^{k+1} : a\in \A\}$. 

Let $\Pi$ be a subdivision of $\A$ and let $\Pi'$ be a refinement of it.
We want to modify the Baues poset by considering $\Pi
< \Pi'$ only if $\Pi$ refines $\Pi'$ in a coherent way:

\begin{defi}[Alexeev]
\label{defi.orders}
\label{defi.coherent}
A {\em system of height functions} on $\Pi$ is a family $\{h_B :B\in
\Pi\}$, where $h_B$ is a height function on the cell $B$ 
and $h_B-h_{B'}$ is an affine height
function on $B\cap B'$ for every $B,B'\in\Pi$.

We say that $\Pi'$ is a {\em coherent refinement} of
$\Pi$ if there is a system of height functions on $\Pi$ such that
$\Pi'$ restricted to each $B\in\Pi$ is the coherent subdivision of
$B$ given by $h_B$.
\end{defi}
Coherent refinements are called {\em regular subdecompositions} in
\cite[Section 2.12]{Alexeev}. In \cite{Santos-refine}, the more
restrictive condition that
a global height function on $\A$ is valid to refine all the cells of
$\Pi$ is considered. Here we call this {\em strongly coherent refinement}.
All the results in this section are true (and easier to prove, since the
relation is transitive) for strongly coherent refinement.

\begin{example}
\label{exm.6points}
Let $\A=\{(4,0,0),(0,4,0),(0,0,4),(2,1+\epsilon,1-\epsilon),
(1-\epsilon,2,1+\epsilon),(1+\epsilon,1-\epsilon,2)\}$, where
$\epsilon$ is a sufficiently small real number, possibly zero.
%($|\epsilon| < \sqrt{5} -2$ is enough). 
This is the smallest example of a configuration with non-coherent
subdivisions \cite{BiFiSt,GKZbook,Reiner-survey,Ziegler}.  If
$\epsilon=0$, then $\A$ consists of the vertices of two homothetic
triangles one inside another. If $\epsilon\ne 0$, then the interior
triangle is slightly rotated, but the Baues poset is independent of
this rotation since the oriented matroid is preserved.

Let the points in $\A$ be labelled $1,\dots,6$ in the order we have
written them. The subdivision $\Pi=\{456,1245,2356,1346\}$ is coherent
(with height function $(1,1,1,0,0,0)$) if and only if $\epsilon=0$.
Regardless of the value of $\epsilon$
all the refinements of $\Pi$ are coherent refinements
and they are in poset
isomorphism with the faces of a 3-cube. If $\epsilon\ne 0$ then they are
all also strongly coherent
refinements. If $\epsilon=0$ then only the coherent
subdivisions refining $\Pi$ are strongly coherent refinements of
$\Pi$, and they are in poset isomorphism with the faces of a hexagon.
\end{example}

\begin{lemma}
Let $\Pi$ be a polyhedral subdivision of $\A$. 
\label{lemma.secondary}
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item
There is a polytope
$\Sigma_c(\Pi, \A)$ whose poset of non-empty faces is
isomorphic to the (refinement) poset of all coherent refinements of $\Pi$.

\item Vertices $\Sigma_c(\Pi, \A)$ correspond bijectively to triangulations.

\item The edges of $\Sigma_c(\Pi, \A)$ are geometric bistellar flips.
\end{enumerate}
\end{lemma}

\begin{proof}
(i) This is Lemma 2.12.11 in \cite{Alexeev}, where $\Sigma_c(\Pi, \A)$
is constructed in a way similar to the
construction of fiber polytopes in \cite{BilStu}.
For our purposes here it would be sufficient to prove that the poset
of coherent refinements of $\Pi$ is anti-isomorphic to
the face lattice of a certain complete polyhedral fan, as follows: 
The systems of
height functions on $\Pi$ form a real vector space, which is 
divided into convex polyhedral
cones by the property of defining the same coherent
refinement. These cones are easily seen to form
a polyhedral fan.

(ii) A coherent refinement is a triangulation if and only if it can be
obtained with a sufficiently generic system of height functions.

(iii) 
Let $v_0$ be a system of height functions on $\Pi$ which produces $\Pi'$.
Any system of height functions sufficiently close to $v_0$ produces a
coherent refinement of $\Pi$ which refines $\Pi'$. We will prove that
if $\Pi'$ is not a flip then more than two refinements can be produced
in this way.

If a certain cell $B$ of $\Pi'$ has more than $d+2$ vertices, then
every coherent subdivision of $B$ appears in some coherent refinement
of $\Pi$, and there are more than two of them. Hence, we can assume
that each non-simplicial cell of $\Pi'$ contains the support of 
a unique (up to sign reversal) circuit. If the same circuit is
contained in all of them, then $\Pi'$ is a flip on that circuit. If
there are two different supports of circuits
$Z_1$ and $Z_2$ in cells of $\Pi'$,
then let $a\in Z_1\setminus Z_2$ and let $b\in
Z_2\setminus Z_1$. Modifying $v_0$ by the addition
of two global sufficiently small constants to the heights of $a$ and $b$ we can
produce at least four coherent refinements of $\Pi$ which refine
$\Pi'$, in which the two circuits are triangulated
independently.
\end{proof}

Following Alexeev, we call the polytopes $\Sigma_c(\Pi,\A)$ {\em
generalized secondary polytopes}. A similar
polytope $\Sigma_{sc}(\Pi,\A)$ is constructed in
\cite{Santos-refine} for the strong-coherent case. 
The main difference is that
$\Sigma_{sc}(\Pi',\A)$ equals the face of $\Sigma_{sc}(\Pi,\A)$
corresponding to $\Pi'$, while $\Sigma_{c}(\Pi',\A)$
only {\em projects} onto the face
of $\Sigma_{c}(\Pi,\A)$ corresponding to $\Pi'$,
whenever $\Pi'$ is a strongly coherent (resp. coherent)
refinement of $\Pi$. Similarly, if $\Pi'$ refines $\Pi$
(coherently or not) then $\dim(\Sigma_{sc}(\Pi',\A))\le
\dim(\Sigma_{sc}(\Pi,\A))$,
while the same does not hold for $\Sigma_c$.
The generalized secondary polytope may have dimension higher
than the dimension $|A|-d-1$ of the
whole secondary polytope $\Sigma(\A):=\Sigma_c(\{\A\},\A)$.
Examples exist with 10 points in dimension two.

We will denote $\Omega_{sc}(\A)$ and $\Omega_{c}(\A)$ the
posets of all the subdivisions of $\A$ partially ordered by
strongly coherent and (the transitive closure of) coherent refinement,
respectively.
We use  $<_{sc}$, $<_{c}$ to denote the partial orders
and $<$ for the usual refinement.

The existence and properties of generalized secondary polytopes for
$\Omega_{c}(\A)$ and $\Omega_{sc}(\A)$
provides the following interpretation of the order complexes of
these posets: they are homeomorphic to 
the union of all the generalized secondary polytopes of the 
different subdivisions, each polytope glued into faces of the
generalized secondary
polytopes of the subdivisions of which it is a 
coherent (resp. strongly coherent) refinement. In the strong-coherent
case the glueing is face to face in the polytopes, and easy to
understand. In the coherent case, the projection of
$\Sigma_c(\Pi',\A)$ onto a face $F$ of $\Sigma_c(\Pi,\A)$ when $\Pi'$
coherently refines $\Pi$ induces a simplicial embedding of the
barycentric subdivision of $F$ into the barycentric subdivision of
$\Sigma_c(\Pi',\A)$. Each face of $F$ is identified with the maximal
face of $\Sigma_c(\Pi',\A)$ of which it is a projection. 

\medskip
\noindent{\em Example \ref{exm.6points} (continued)}
$\Sigma_c(\Pi,\A)$ is a combinatorial 3-cube no matter what $\epsilon$ is.
$\Sigma_{sc}(\Pi,\A)$ is the same cube if $\epsilon\ne 0$, but it is a
hexagon otherwise. If $\epsilon\ne 0$ then the cube
$\Sigma_c(\Pi,\A)=\Sigma_{sc}(\Pi, \A)$ has three facets in common with
the secondary polytope
$\Sigma(\A)$. If $\epsilon=0$, then
$\Sigma_{sc}(\Pi,\A)$ is a hexagonal facet of
$\Sigma(\A)$ while $\Sigma_c(\Pi,\A)$ has this facet glued through its
interior.

If $\epsilon\ne 0$ then $\Omega_{c}(\A)=\Omega_{sc}(\A)$ and, moreover,
forgetting the trivial subdivision they coincide with $\Omega(\A)$. If
$\epsilon=0$ the latter is still true for $\Omega_c(\A)$ but not for
$\Omega_{sc}(\A)$. In this case the order complex of
$\Omega_{sc}(\A)$ without the top element has a relatively complicated
homotopy type: it is a 2-sphere (the boundary of the secondary polytope) glued
along the equator to another 2-sphere (the boundary of the 3-cube of
refinements of $\Pi$).
In contrast, the order complex of $\Omega_{c}(\A)$ without
$\{\A\}$ remains a homotopy 2-sphere, as the Baues complex is.
Finally, although the order complex of 
$\Omega_c(\A)$ is a 3-dimensional ball only if $\epsilon\ne 0$, 
its homotopy type does not change with $\epsilon$.
All this indicates that $\Omega_c(\A)$ is a more interesting
poset than $\Omega_{sc}(\A)$, both for its intrinsic properties and for
its relation to the Baues poset.

\begin{lemma} Let $\Pi$ be a subdivision of $\A$.
\label{lemma.relations}
\label{lemma.connected}
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item If $\Pi'$ is a coherent refinement of $\Pi$ then there
is a triangulation which coherently refines both $\Pi$ and $\Pi'$.

\item If $X=\Omega_c(\A)_{\le \Pi}$, then $G(X)$ is connected. That is to say,
any two triangulations below $\Pi$ in the coherent-refinement poset
are connected by geometric bistellar flips all below $\Pi$.

\item Part (ii) remains true if $X$ is any connected lower ideal in
$\Omega_c(\A)$. 

\item Conversely, if $G(X)$ is connected for a lower ideal $X$ then
$X$ is connected.
\end{enumerate}
\end{lemma}


\begin{proof}
For part (i), it suffices to slightly perturb the system of heights on
$\Pi$ which gives $\Pi'$ in a sufficiently generic way.
Part (iv) is trivial, since any subdivision can be refined to a
triangulation and $G(X)$ is a subposet of $X$.

Part (ii) is trivially true when $\Pi$ is a triangulation or a flip, 
so we can take as
inductive hypothesis that it is true for any subdivision $\Pi'$ with
$\Pi'<_c\Pi$. Also, part (iii) of Lemma \ref{lemma.secondary} implies
that every two triangulations which coherently refine $\Pi$ are
connected by flips in $X$. Thus,  it suffices to show that any
triangulation in $X$ which does not coherently refine $\Pi$ is
connected by flips in $X$ to one which does. 

Let $\T$ be such a triangulation. There has to be a
coherent refinement $\Pi'$ of $\Pi$ with $T <_c \Pi'$. By (i)
there is a triangulation $\T'$ which coherently refines both $\Pi$ and
$\Pi'$. Inductive hypothesis implies that $\T$ and $\T'$ are connected
by flips in the principal lower ideal of $\Pi'$.

In part (iii), let $\T$ and $\T'$ be two triangulations in $X$ and 
let $\{\T= \Pi_0 ,\Pi_1 ,\dots,$ $ \Pi_{k-2} ,\Pi_{k-1} , \Pi_k=\T'\}$ be
a sequence of subdivisions such that for every $i\in\{1,\dots,k\}$
either $\Pi_{i-1}$ is a coherent refinement of $\Pi_i$ or
viceversa. The case $k=2$ is solved in
(ii), so we proceed by induction on $k$. 
By (i), there is a
triangulation $\T''$ which coherently refines both $\Pi_{k-2}$ and
$\Pi_{k-1}$.
This breaks our sequence in two shorter ones:
$\{\T , \Pi_1 , \dots, \Pi_{k-2} , \T''\}$ and $\{\T'' , \Pi_{k-1} , 
\T'\}$.
\end{proof}

%Parts (iii) and (iv) above can be made a bit more explicit: for any
%lower ideal $X$ in $\Omega_c(\A)$, 
%the inclusion of $G(X)$ in $X$ preserves connected components.
%For $\Omega(\A)$, 
%still it might be true that part (iii) holds when $X$ is the
%strict Baues poset. In this case our triangulation without flips
%would disprove the GBC for the simplex case. 

\begin{corollary} 
\label{coro.connected}
$\Omega_c(\A)$ is connected if and only if its graph of triangulations
is connected.\qed
\end{corollary}


\subsection{Toric GIT-quotients of the projective space
and moduli spaces of stable semiabelic toric pairs}
\label{sub.alexeev}

Here we show the relation of the coherent poset of subdivisions
$\Omega_c(\Pi,\A)$ and two algebraic schemes considered respectively
in \cite[Section 4]{KaStZe} and \cite[Section 2]{Alexeev}. We assume
that $\A$ is an integer point configuration.

First we sketch an alternative definition of the secondary polytope
$\Sigma(\A)$ as a particular case of a fiber polytope \cite{BilStu}. 
Let $\Delta$ 
be the unit simplex of dimension $|A|-1$, let $Q=\conv(\A)$ and let 
$\pi:\Delta\to Q$ be the affine projection sending the vertices of $\Delta$ to
$\A$. For each $b\in Q$ let $\Sigma_b=\pi^{-1}(b)$.
The {\em chamber complex} of $\A$ is the coarsest common refinement of
all its triangulations, and it is a polyhedral complex with the
property that for any $b$ and $b'$ in the same {\em chamber} the
fibers $\pi^{-1}(b)$ and $\pi^{-1}(b')$ 
have the same normal fan.
The secondary polytope equals the
Minkowski integral of $\Sigma_b$ over $Q$. At the combinatorial level,
it coincides with the Minkowski sum of a finite number of $\Sigma_b$,
with one $b$ chosen in each chamber.

The normal toric variety associated to a polytope depends only on its
normal fan, so there is no ambiguity in calling $F_\sigma$ the one
of $\Sigma_b$ for any $b\in \sigma$.
If $b\in\sigma$ and  $b'\in\tau$ for two
chambers with $\tau\subset \overline{\sigma}$ then the normal fan of
$\Sigma_{b}$ refines the normal fan of $\Sigma_{b'}$, 
which implies that there is a
natural equivariant morphism $f_{\sigma\tau}: F_{\sigma}\to F_{\tau}$. 
Let us denote $\Lambda_\A:=\invlim F_\sigma$ 
the inverse limit of all the $F_\sigma$ and
morphisms $f_{\sigma\tau}$. It has the following two interpretations:

\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item Let $X_\Delta$ be the projective space of dimension $|\A|-1$, 
which is the toric variety associated with the simplex $\Delta$ (what
follows is valid for any polytope $\Delta$).
In \cite{KaStZe}, the toric varieties $F_{\sigma}$ are shown to be
the different toric GIT-quotients of 
$X_\Delta$ modulo the algebraic sub-torus whose
characters are given by $\A$
\cite[Proposition 3.5]{KaStZe}. $\Lambda_\A$ is the inverse limit of all of
them, which contains the Chow quotient as an irreducible component
\cite[Corollary 4.3]{KaStZe}. 

\item In \cite[Section 2.11]{Alexeev} a scheme $M_{simp}$ is defined
exactly in the same way as our $\Lambda_\A$. Although $\A$ is assumed
there to be the set of all lattice points in $Q$, the connection of
$M_{simp}$ with $\Sigma_c(\A)$
carried out there (our Theorem \ref{thm.alexeev}) is independent of
this fact. 

The main interest in that paper is in 
the moduli space $M$ of {\em stable semiabelic toric pairs
of type $\le Q$} (see Sections 1.1.A, 1.2.B and 1.2.F in
\cite{Alexeev} for the definitions). The author shows that there is a
finite morphism $M\to M_{simp}$ (Corollary 2.11.11) and uses
$M_{simp}$ as a simplified model for studying $M$.
\end{enumerate}


\begin{theorem}[Alexeev]
\label{thm.alexeev}
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item For each subdivision $\Pi$ of $\A$ there is a morphism
$F_{\Sigma(\Pi,\A)}\to M_{simp}$, where $F_{\Sigma(\Pi,\A)}$ is the toric
variety associated with the generalized secondary polytope
$\Sigma(\Pi,\A)$ (See \cite[2.12.13]{Alexeev}). This induces a natural
stratification on $M_{simp}$ (and on $M$) whose strata are (perhaps
non-normal) toric varieties in
1-to-1 correspondence with subdivisions of $\A$ (Corollary 2.11.10).
\item The glueing of the moment maps in the different strata induces a
surjective continuous
map $\Mom: M_{simp}\to\invlim \Sigma_c(\Pi,\A)$ (Lemma
2.13.2) whose image $\invlim \Sigma_c(\Pi,\A)$ is glued from
the generalized secondary polytopes $\Sigma_c(\Pi,\A)$ via the coherent
refinement relation. The same holds for $M$.
\end{enumerate}
\end{theorem}

Most probably, the glueing referred to in the second part makes
$\invlim \Sigma_c(\Pi,\A)$
homeomorphic to the order complex of the poset
$\Omega_c(\A)$. In other words, most probably 
barycentric subdivisions of the generalized secondary polytopes
$\Sigma_c(\Pi,\A)$ can be chosen in a way compatible with the glueings
induced by the moment maps. Even if this is not the case, it is
straightforward that $\invlim \Sigma_c(\Pi,\A)$ 
is connected if and only if (the
order complex of) $\Omega_c(\A)$ is connected. Hence:

\begin{corollary}
\label{coro.alexeev}
The following properties are equivalent for an integer point configuration
$\A$.
\begin{enumerate}
\renewcommand{\labelenumi}{{\rm(\roman{enumi})}}
\item The graph of triangulations of $\A$ is connected.
\item The coherent refinement poset $\Omega_c(\A)$ is connected.
\item The inverse limit of all the toric GIT-quotients of the
projective space of dimension $|\A|-1$ modulo the subtorus defined
taking the elements of $\A$ as characters is connected, and
\item (If $\A$ contains all the integer points in its convex
hull $Q$) the moduli space of all stable semiabelic toric pairs of
type $\le Q$ is connected.
\qed
\end{enumerate}
\end{corollary}



\medskip\noindent
{\bf Acknowledgements: } The author  wishes to thank C. Athanasiadis, M.
Azaola, D. Maclagan, R. Thomas and, specially, J. de Loera for their 
comments
on a first version of this paper. Thanks go also to J\"org Rambau, who
double-checked the correctness of our main result with his program {\tt
TOPCOM} \cite{topcom}.


\addcontentsline{toc}{section}{References}

\begin{thebibliography}{99}

%\small

\bibitem{AbMaRa}{\sc D. Abramovich, K. Matsuki and S. Rashid},{\em A
note on the factorization theorem of toric birational maps after
Morelli and its toroidal extension}, preprint 1998. Available at Los
Alamos e-print archive, {\tt
http://xxx.lanl.gov/e-print/ math.AG/9803126}.

\bibitem{Alexeev}{\sc V. Alexeev}, {\em Complete moduli in the presence of
semiabelian group action}, preprint 1999. Available at Los Alamos e-print
archive {\tt http//xxx.lanl.gov/ e-print/math.AG/9905103}.

\bibitem{Anderson}{\sc L. Anderson},
{Matroid bundles and sphere bundles}, 
in: {\em New Perspectives in Algebraic Combinatorics},
MSRI publications {\bf 38} (1999), Cambridge University Press.

%\bibitem{AtRaSa}
%{\sc C.A.~Athanasiadis, J.~Rambau and F.~Santos}, 
%The generalized Baues problem for cyclic polytopes II,
%in ``Proceedings of Geometric Combinatorics'98 (Kotor)",
%{\em Publ. de l'Institut Mathematique}, Belgrade, to appear.

%\bibitem{Azaola} {\sc M. Azaola}, {\em On the Baues conjecture in corank 3},
%preprint 1999.

\bibitem{Baues} {\sc J. Baues}, Geometry of loop spaces and the cobar
construction, {\em Mem. Am. Math. Soc.} {\bf 25} (1980), 99--124.

\bibitem{BiFiSt}{\sc L. Billera, P. Filliman and B. Sturmfels}, Constructions
and complexity of secondary polytopes, {\em Adv. Math.}  {\bf 83} (1990), 
155--179.

\bibitem{BiKaSt} {\sc L. Billera, M.M. Kapranov and 
B. Sturmfels},
Cellular Strings on Polytopes, {\it Proc. Am. Math. Soc.} {\bf
122}(2) (1994), 549--555.

\bibitem{BilStu} {\sc L. Billera and B. Sturmfels}, Fiber polytopes, {\em
Ann. Math.} {\bf 135} (1992), 527--549.

\bibitem{Bjorner} {\sc A. Bj\"orner}, Topological methods, in: {\em Handbook
of Combinatorics},  Elsevier, Amsterdam, 1995.

\bibitem{BjoLut} {\sc A. Bj\"orner and F. H. Lutz}, Simplicial manifolds,
bistellar flips and a 16-vertex triangulation of the Poincar\'e homology
3-sphere, {\em Experiment. Math.},  to appear.

\bibitem{OMbook}{\sc A. Bj\"orner, M. Las Vergnas, B. Sturmfels, N. White
and G. M. Ziegler}, {\em Oriented Matroids}, Cambridge University Press,
Cambridge 1992. 

\bibitem{deLoera} {\sc J.A. de Loera}, {\em Triangulations of Polytopes and
Computational Algebra}, Ph.D. thesis, Cornell University, 1995.

\bibitem{LoHoSaSt} {\sc J.A. de Loera, S. Ho\c sten, F. Santos and
B. Sturmfels}, The polytope of all triangulations of a point
configuration, {\em Doc. Math.} {\bf 1} (1996), 103--119.

\bibitem{LoSaUr} {\sc J.A. de Loera, F. Santos and J. Urrutia}, The number
of geometric bistellar neighbors of a triangulation, {\em Discrete Comput.
Geom.}, {\bf 21} (1999) 1, 131--142.

%\bibitem{EdeRei} {\sc P. Edelman and V. Reiner}, Visibility complexes and the
%Baues problem for triangulations in the plane, {\em Discrete Comput. Geom.}
%{\bf 20} (1998), 35--59.

\bibitem{EdeSha} {\sc H. Edelsbrunner and N.R. Shah}, Incremental
topological flipping works for regular triangulations, {\em Algorithmica}
{\bf 15} (1996), 223--241.

\bibitem{EilSte} {\sc S. Eilenberg and N. E. Steenrod}, {\em Foundations of
algebraic topology}, Princeton University Press, 1952.

\bibitem{Ewald} {\sc G. Ewald}, \"Uber stellare \"Aquivalenz konvexer
Polytope,  {\em Resultate Math.} {\bf 1} (1978), 54--60.

\bibitem{GeKaZe} {\sc I.M. Gel'fand, M.M. Kapranov and
A.V. Zelevinsky}, { Discriminants of polynomials in several variables
and triangulations of Newton polyhedra}, {\em Leningrad Math. J.} {\bf
2} (1990), 449--505.  (English translation of {\em Algebra i Analiz}
{\bf 2} (1990), 1--62, in Russian).

\bibitem{GKZbook} {\sc I.M. Gel'fand, M.M. Kapranov and A.V. Zelevinsky},
{\em Discriminants, Resultants and Multidimensional Determinants},
Birkh\"auser, Boston, 1994.

\bibitem{HuRaSa}{\sc B. Huber, J. Rambau and F. Santos},
{\em The Cayley Trick, Lawrence polytopes, and the Bohne-Dress theorem on
zonotopal tilings}, preprint 1999. To appear in {\em J. Eur. Math. Soc.
(JEMS)}.

\bibitem{IteRoy}{\sc I. Itenberg and M.-F. Roy},
Interactions between real algebraic geometry and discrete and computational
geometry, in: {\em Advances in discrete and computational
geometry. Proceedings of the 1996
AMS-IMS-SIAM joint summer research conference on discrete and computational
geometry: ten years later} (Bernard Chazelle et al. eds.), pp. 217--236.
Contemp. Math. {\bf 223}, Am. Math. Soc., Providence, 1999.

\bibitem{KaStZe} {\sc M.M. Kapranov, B. Sturmfels and A.V. Zelevinsky}, 
Quotients of toric varieties, {\em Math. Ann.} {\bf 290} (1991), 643--655.

\bibitem{Lawson} {\sc C.L. Lawson},  Software for
$C^1$-interpolation, in {\em Mathematical Software III} (John Rice ed.),
Academic Press, New York, 1977.

\bibitem{Lee} {\sc C.W. Lee}, The associahedron and triangulations of the
$n$-gon, {\em European J. Combin.} {\bf 10} (1990), 551--560.

\bibitem{Lee-survey} {\sc C.W. Lee}, Subdivisions and triangulations of
polytopes, in {\em Handbook of Discrete and Computational Geometry} (J.E.
Goodman and J. O'Rourke eds.), pp. 271--290, CRC Press, New York, 1997.  

\bibitem{MacTho} {\sc D. Maclagan and R. Thomas}, 
{\em Combinatorics of the Toric Hilbert Scheme}, preprint 1999. Available at
Los Alamos e-print archive, {\tt
http:/{}/xxx.lanl.gov/ e-print/math.AG/9912014}.

\bibitem{MacPherson}{\sc R. MacPherson}, Combinatorial Differential
Manifolds, in {\it To\-po\-logical Methods in Modern Mathematics: a Symposium
in Honor of John Milnor's Sixtieth Birthday}, Publish or Perish, 1993.

\bibitem{Morelli}{\sc R. Morelli}, {The birational geometry of toric
varieties}, {\em J. Alg. Geom.} {\bf 5} (1996), 751--782.

\bibitem{Oda} {\sc T. Oda}, {\em Convex bodies and algebraic
geometry. An introduction to the theory of toric varieties},
Springer-Verlag, 1988.

\bibitem{Pachner2}{\sc U. Pachner}, PL-homeomorphic manifolds are
equivalent by elementary shellings, {\em European J. Combin.} {\bf 12} (1991),
129--145.

\bibitem{PeeSti}{\sc I. Peeva and N. Stillman}, Toric Hilbert schemes,
preprint 1999. Available at {\tt http://www.math.cornell.edu/\~{}irena/publications.html}.

\bibitem{topcom}
{\sc J.~Rambau},
{\tt TOPCOM:} Triangulations Of Point Configurations and Oriented Matroids,
software available at {\tt http:/{}/www.zib.de/rambau/TOPCOM.html}.

%\bibitem{RamSan}
%{\sc J.~Rambau and F.~Santos},
%The generalized Baues problem for cyclic polytopes,
%{\em European J.\ Combin.}, {\bf 21} (2000), 65--83.

\bibitem{RamZie}
{\sc J.~Rambau and G.M.~Ziegler},
Projections of polytopes and the generalized Baues conjecture,
{\it Discrete Comput.\ Geom.} (3) {\bf~16} (1996), 215--237.

\bibitem{Reiner-survey}{\sc V. Reiner},
{The generalized Baues problem}, 
in: {\em New Perspectives in Algebraic Combinatorics},
MSRI publications {\bf 38} (1999), Cambridge University Press.


\bibitem{Santos-fewflips}{\sc F. Santos}, Triangulations with very few
geometric bistellar neighbors, {\em Discrete Comput. Geom.}, {\bf 23}
(2000), 15--33. 

\bibitem{Santos-OMtri}{\sc F. Santos}, Triangulations of Oriented Matroids,
{\em Mem. Am. Math. Soc.}, to appear. Available at
{\tt http://matsun1.matesco.unican.es/\~{}santos/ Articulos/OMtri.ps.gz}

\bibitem{Santos-refine} {\sc F. Santos}, On the refinements of a polyhedral
subdivision, preprint, 1999, 26 pages. Available at
{\tt http://matsun1.matesco.unican.es/\~{}santos/ Articulos/refine.ps.gz}

\bibitem{SlTaTh} {\sc D. Sleator, R. Tarjan  and W. Thurston},
Rotation distance, triangulations, and hyperbolic 
geometry, {J. Am. Math. Soc.} {\bf 1} (1988), 647--681.

\bibitem{Stasheff} {\sc J.D. Stasheff}, Homotopy associativity of
H-spaces, {\em Trans. Am. Math. Soc.} {\bf 108} 
(1963), 275--292.

\bibitem{Sturmfels-book} {\sc B. Sturmfels}, {\em Gr\"obner bases and convex
polytopes},  University Series Lectures {\bf 8}, American Mathematical
Society, Providence, 1995.

\bibitem{Sturmfels-agraded} {\sc B. Sturmfels}, {\em The geometry of
$A$-graded algebras},  preprint 1994. Available at Los Alamos e-print {\tt
http://xxx.lanl.gov/e-print/math.AG/9410032}.

%\bibitem{StuZie} {\sc B. Sturmfels and G. M. Ziegler}, {Extension
%spaces of oriented matroids}, {\em Discrete Comput. Geom.} {\bf 10}
%(1993), 23--45.

\bibitem{Tamari} {\sc D. Tamari}, {\em The algebra of bracketings and their
enumeration},  {\em Nieuw Arch. Wisk.} {\bf 10} (1962), 131--146.

\bibitem{Ziegler}{\sc G. M. Ziegler}, {\em Lectures on Polytopes},
Springer-Verlag, New  York, 1994.

\bibitem{Ziegler-recent}{\sc G. M. Ziegler}, {\em Recent progress on
polytopes}, in ``Advances in Discrete and Computational Geometry" (B.
Chazelle, J.E. Goodman, R. Pollack, eds.), {\em Contemporary Mathematics}
{\bf 223} (1998), Am. Math. Soc., Providence, 395--406.


\end{thebibliography}

\end{document}