\documentclass[finalversion]{FPSAC2020}
\articlenumber{10}
\addbibresource{fpsac.bib}
\received{\today}


\usepackage{amsmath,amstext,amssymb,amscd, color}
\usepackage{graphicx}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\newtheorem{statement}[theorem]{}
\newtheorem{prop}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\crefname{example}{Example}{Examples}



\makeatletter \@addtoreset{equation}{section} \makeatother



\renewcommand{\theequation}{\thesection.\arabic{equation}}

%                         numbered textual expression
\newenvironment{numitem1}{\refstepcounter{equation}\begin{enumerate}%
\item[(\thesection.\arabic{equation})]}{\end{enumerate}}
 
\def\Rset{{\mathbb R}}
\def\Zset{{\mathbb Z}}

\def\Ascr{{\cal A}}
\def\Bscr{{\cal B}}
\def\Cscr{{\cal C}}
\def\Dscr{{\cal D}}
\def\Escr{{\cal E}}
\def\Fscr{{\cal F}}
\def\Gscr{{\cal G}}
\def\Hscr{{\cal H}}
\def\Iscr{{\cal I}}
\def\Jscr{{\cal J}}
\def\Lscr{{\cal L}}
\def\Mscr{{\cal M}}
\def\Nscr{{\cal N}}
\def\Oscr{{\cal O}}
\def\Pscr{{\cal P}}
\def\Qscr{{\cal Q}}
\def\Rscr{{\cal R}}
\def\Sscr{{\cal S}}
\def\Tscr{{\cal T}}
\def\Uscr{{\cal U}}
\def\Vscr{{\cal V}}
\def\Wscr{{\cal W}}
\def\Xscr{{\cal X}}
\def\Yscr{{\cal Y}}
\def\Zscr{{\cal Z}}

\def\Cbold{{\bf C}}
\def\Qbold{{\bf Q}}
\def\Sbold{{\bf S}}
\def\Wbold{{\bf W}}

\def\frakS{\mathfrak{S}}

\def\suppo{{\rm supp}}
\def\Inver{{\rm Inv}}
\def\ident{{\rm id}}
\def\hor{{\rm hor}}
\def\vert{{\rm vert}}
\def\bottom{{\rm bt}}
\def\Spec{{\rm Sp}}
\def\conv{{\rm conv}}
\def\Vert{{\rm Vert}}

\def\tilde{\widetilde}
\def\hat{\widehat}
\def\bar{\overline}
\def\eps{\epsilon}
\def\vareps{\varepsilon}

\def\below{\lessdot}
\def\beloweq{\preceq^\square}
\def\lessdoteq{\,{\underline{\lessdot}}\,}

\def\bfC{{\bf C}}
\def\bfQ{{\bf Q}}
\def\bfS{{\bf S}}
\def\bfT{{\bf T}}
\def\bfW{{\bf W}}

\def\Qst{Q^{\rm st}}
\def\Qant{Q^{\rm ant}}
%\def\bd{{\rm bd}}
\def\bd{\partial}
%\def\lbd{{\rm lbd}}
%\def\rbd{{\rm rbd}}
%\def\Pack{{\rm Pac}}

\def\Zfr{Z^{\,\rm fr}}
\def\Zrear{Z^{\,\rm rear}}
\def\Zrim{Z^{\,\rm rim}}
\def\Cfr{C^{\,\rm fr}}
\def\Crear{C^{\,\rm rear}}
\def\Crim{C^{\,\rm rim}}
\def\Sfr{S^{\,\rm fr}}
\def\Srear{S^{\,\rm rear}}
\def\zetafr{\zeta^{\,\rm fr}}
\def\zetarear{\zeta^{\,\rm rear}}
\def\taufr{\tau^{\,\rm fr}}
\def\taurear{\tau^{\,\rm rear}}
\def\Mfr{M^{\,\rm fr}}
\def\Pifr{\Pi^{\,\rm fr}}
\def\Pirear{\Pi^{\,\rm rear}}
\def\Vfr{V^{\,\rm fr}}
\def\Vrear{V^{\,\rm rear}}
\def\Ffr{F^{\,\rm fr}}
\def\Frear{F^{\,\rm rear}}
\def\Frim{F^{\,\rm rim}}

\def\Zpfr{Z'^{\,\rm fr}}
\def\Zprear{Z'^{\,\rm rear}}
\def\Zprim{Z'^{\,\rm rim}}

\def\Gammapfr{\Gamma'^{\,\rm fr}}
\def\Gammaprear{\Gamma'^{\,\rm rear}}

\def\epsfr{{\eps,\rm fr}}
\def\epsrear{{\eps,\rm rear}}

\def\Mscrw{{\Mscr^{\rm w}}}
\def\Mscre{{\Mscr^{\rm e}}}

\def\Deltafr{\Delta^{\,\rm fr}}
\def\Deltarear{\Delta^{\,\rm rear}}

\def\Hup{H^{\,\rm up}}
\def\Hlow{H^{\,\rm low}}
\def\Vup{V^{\,\rm up}}
\def\Vlow{V^{\,\rm low}}

\def\Sdeltafr{S^{\,\delta,\rm fr}}
\def\Sdeltarear{S^{\,\delta,\rm rear}}
\def\Hdeltafr{H^{\,\delta,\rm fr}}
\def\Hdeltarear{H^{\,\delta,\rm rear}}
\def\Hpdeltafr{H'^{\,\delta,\rm fr}}
\def\Hpdeltarear{H'^{\,\delta,\rm rear}}
\def\Vdeltafr{V^{\,\delta,\rm fr}}
\def\Vdeltarear{V^{\,\delta,\rm rear}}
\def\Vpdeltafr{V'^{\,\delta,\rm fr}}
\def\Vpdeltarear{V'^{\,\delta,\rm rear}}
\def\Pscrdeltafr{\Pscr^{\,\delta,\rm fr}}
\def\Pscrdeltarear{\Pscr^{\,\delta,\rm rear}}
\def\Pscrpdeltafr{\Pscr'^{\,\delta,\rm fr}}
\def\Pscrpdeltarear{\Pscr'^{\,\delta,\rm rear}}

\def\Qcon{Q^{\,\rm con}}

\def\Qfrag{Q^\equiv}
\def\Cfrag{C^\equiv}
\def\Qpfrag{Q'^{\,\equiv}}
\def\Pifrag{\Pi^\equiv}
\def\Qfragpl{Q^{\bullet+}}

\def\Yturn{\Lambda}

\def\XT{X\,|\,T}
\def\XU{X\,|\,U}

\def\wsep{\hbox{\unitlength=1mm\begin{picture}(8,4)%
\put(3.5,1){\oval(6,3)}\put(1.2,0){{\rm ws}}\end{picture}}}

\def\strong{\hbox{\unitlength=1mm\begin{picture}(8,4)%
\put(3.5,1){\oval(6,3)}\put(1.2,0){{\small str}}\end{picture}}}

\def\weak{\hbox{\unitlength=1mm\begin{picture}(10.5,4)%
\put(5,1){\oval(9,3)}\put(1.2,0){{\small weak}}\end{picture}}}

%--------------

\begin{document}

\title[Cubillages in odd dimensions]{Cubillages in odd dimensions}

\author[V.~Danilov, A.~Karzanov, and G.~Koshevoy]{Vladimir~I.~Danilov\thanks{\href{mailto: danilov@cemi.rssi.ru}{danilov@cemi.rssi.ru}.}\addressmark{1}, Alexander~V.~Karzanov\thanks{\href{mailto: akarzanov7@gmail.com}{akarzanov7@gmail.com}.}\addressmark{1},
\and Gleb~A.~Koshevoy\thanks{\href{mailto: koshevoyga@gmail.com}{koshevoyga@gmail.com}. Supported in part by grant RSF 16-11-10075.}\addressmark{2}
}

\address{\addressmark{1}Central Institute of Economics and Mathematics of the
RAS, Moscow, Russia \\
\addressmark{2}Institute for Information Transmission Problems of
the RAS, Moscow, Russia}

\received{\today}

\abstract{
In this abstract we discuss novel results on fine zonotopal tilings (called ``cubillages'' for short) in odd-dimensional cyclic zonotopes and their relations to generalized weakly separated set-systems, triangulations of cyclic polytopes, and others.}

\keywords{cyclic zonotope, cubillage, strong and weak separation, cyclic polytope, triangulation, combined tiling}
 
 \maketitle

%----------------------- Sec. 1

\section{Introduction}  \label{sec:intr}

For positive integers $n\ge d$, by a \emph{cyclic configuration} of size $n$ in
$\Rset^d$ we mean an ordered set $\Xi$ of $n$ vectors
$\xi_i=(\xi_i(1),\ldots,\xi_i(d))\in\Rset^d$, $i=1,\ldots,n$, satisfying:
  %
  \begin{numitem1} \label{eq:cyc_conf}
(a) $\xi_i(1)=1$ for each $i$; (b) any flag minor of the $d\times n$ matrix formed by $\xi_1,\ldots,\xi_n$
as columns (in this order) is positive; and (c)  all 0,1-combinations of these vectors are different.
  \end{numitem1}

(A typical sample of such configurations $\Xi$ is generated
by Veronese curve: take reals $t_1<t_2<\cdots<t_n$ and assign
$\xi_i:=\xi(t_i)$, where $\xi(t)=(1,t,t^2,\ldots,t^{d-1})$.)

We deal with fine zonotopal tilings related to $\Xi$. Recall that the (cyclic)
\emph{zonotope} $Z=Z(\Xi)$ generated by $\Xi$ is the Minkowski sum of line
segments $[0,\xi_i]$, $i=1,\ldots,n$. Then a \emph{fine zonotopal tiling} is (the
polyhedral complex determined by) a subdivision $Q$ of $Z$ into $d$-dimensional
parallelotopes such that: any two intersecting ones share a common face, and
each face of the boundary of $Z$ is entirely contained in some of these
parallelotopes. For brevity, we refer to these parallelotopes as \emph{cubes},
and to $Q$ as a \emph{cubillage}. Note that the choice of one or another cyclic configuration $\Xi$ (subject to~\eqref{eq:cyc_conf}) is not important to us in essence, and we will write $Z(n,d)$ rather than $Z(\Xi)$,
referring to it as the \emph{cyclic zonotope} with parameters $(n,d)$.

Let $[n]$ denote the set $\{1,2,\ldots, n\}$. Any point
$v$ in $Z(n,d)$ occurring as a vertex of a cubillage $Q$ is viewed as $\sum_{i\in X} \xi_i$ for some subset $X\subseteq[n]$ and
we identify such $v$ and $X$. So the set $V(Q)$ of vertices of $Q$ is
identified with the corresponding collection (set-system) in $2^{[n]}$, that we
call the \emph{spectrum} of $Q$. It is known that
 \begin{numitem1} \label{eq:VQ}
~the size (cardinality) of $V(Q)$  is equal to $\binom{n}{\le d}$ 
~~$\left(=\binom{n}{d}+\binom{n}{d-1}+\cdots
  +\binom{n}{0}\right)$.
  \end{numitem1}

The above correspondence
possesses a number of nice properties. One of them
involves so-called \emph{strongly separated} sets and set-systems. We
need some definitions.

For $X,Y\subseteq[n]$, we write $X<Y$ if the maximal element $\max(X)$ of $X$ is
smaller than the minimal element $\min(Y)$ of $Y$, letting $\max(\emptyset):=0$
and $\min(\emptyset):=n+1$. An \emph{interval} of $[n]$ is a subset of
the form $\{a,a+1,\ldots,b\}$, denoted as $[a,b]$. % (so $[n]=[1,n]$).
   

\begin{definition} 
For $r\in\Zset_{\ge 0}$, sets $A,B\subseteq [n]$
are called \emph{strongly $r$-separated} if there is no sequence
$i_1<i_2<\cdots<i_{r+2}$ of elements of $[n]$ such that those with odd
indices (namely, $i_1,i_3,\ldots$) belong to one of $A-B$ or $B-A$, while those with even indices
($i_2,i_4,\ldots$) belong to the other (where $A'-B'$ denotes the set difference $\{i\colon i \in A',\ i\notin B'\}$).
Accordingly, a set-system $\Sscr\subseteq 2^{[n]}$ is called $r$-separated if any 
two members of $\Sscr$ are such.
\end{definition}

In particular, $A,B$ are strongly 1-separated if  $\max(A-B)<\min(B-A)$ or\linebreak $\max(B-A)<\min(A-B)$. This notion 
was introduced and studied, under the name of ``strong separation'', by Leclerc and Zelevinsky~\cite{LZ}.
The case $r=2$ was studied by Galashin~\cite{gal}. 
Extending results in~\cite{LZ,gal} concerning the strong 1- and 2-separation to a general $r$, Galashin and Postnikov \cite{GP} showed that 
  %
\begin{numitem1} \label{eq:cub-separ}
The maximal size $s_{n,r}$ of a strongly $r$-separated collection in $2^{[n]}$
is equal to $\binom{n}{\le r+1}$; moreover (see \eqref{eq:VQ}), for any cubillage
$Q$ on $Z(n,d)$, its spectrum $V(Q)$ constitutes a maximal by size strongly
$(d-1)$-separated collection in $2^{[n]}$, and conversely, for any size-maximal strongly$(d-1)$-separated collection $\Sscr\subseteq 2^{[n]}$, there exists a cubillage
$Q$ on $Z(n,d)$ with $V(Q)=\Sscr$.
\end{numitem1}
 
(As a more general version of strong $r$-separation,~\cite{GP} considers the notion of M-separation in oriented matroids, but this is not needed to us in this paper.) 

Another sort of set separation introduced by Leclerc and Zelevinsky is known
under the name of \emph{weak separation} (which appeared in~\cite{LZ} in
connection with the problem of characterizing quasi-commuting flag minors of a
quantum matrix). We generalize that notion to ``higher odd dimensions'' in the following way. 
When $A,B\subseteq [n]$ are such that $\min(A-B)<\min(B-A)$ and
$\max(A-B)>\max(B-A)$, we say that $A$ \emph{surrounds} $B$. When $A,B$ are strongly
$r$-separated but not strongly $(r-1)$-separated, they are called
$(r+1)$-\emph{intertwined}. In other words, there are intervals
$I_1<I_2<\cdots <I_{r'}$ in $[n]$ with $r'= r+1$, but not $r'=r$, such that
one of $I_1\cup I_3\cup \ldots$\; and $I_2\cup
I_4\cup\ldots$\; includes $A-B$, and the other $B-A$; we say that $(I_1,\ldots,I_{r'})$ is an \emph{interval cortege} for $A,B$.
For example, $A=\{1,2,5,6,7,10,11\}$ and
$B=\{1,3,4,6,9,11\}$ are 5-intertwined  
(with an interval cortege $(\{2\},[3,4],[5,7],\{9\},\{10\})$) 
and $A$ surrounds $B$.
  

\begin{definition}
Let $r$ be \emph{odd}. Sets
$A,B\subseteq[n]$ are called \emph{weakly $r$-separated} if they are either strongly $r$-separated, or
they are $r+2$-intertwined, and in the latter case, if 
~$A$ surrounds $B$ then $|A|\le |B|$, while if $B$ surrounds $A$ then $|B|\le|A|$.
Accordingly, a set-system $\Wscr\subseteq 2^{[n]}$ is called weakly
$r$-separated if any two members of $\Wscr$ are such.
\end{definition}

In case $r=1$, this turns into the weak separation of~\cite{LZ}. 
   
Using a machinery of cubillages in cyclic zonotopes of odd dimensions, 
we generalize, to an arbitrary odd $r\ge 1$, two well-known results on
weakly separated collections obtained in~\cite{LZ} and develop a method of
constructing a representable class of size-maximal weakly $r$-separated set-systems. 
One of those results \cite{LZ} says that
  %
  \begin{numitem1}\label{eq:max_size} 
the maximal sizes of strongly and weakly
separated collections in $2^{[n]}$ are the same (and equal to $\frac12 n(n+1)+1=
\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$).
 \end{numitem1}

Let $w_{n,r}$ denote the maximal possible size
of a weakly $r$-separated collection in $2^{[n]}$. We generalize~\eqref{eq:max_size} as follows.

  %
  \begin{theorem} \label{tm:w=s}
Let $r$ be odd. Then $w_{n,r}=s_{n,r}$.
 \end{theorem}

(Note that for even $r>0$, at present we see no way of defining
the notion of weak $r$-separation ensuring that the maximal size of such
collections in $2^{[r+1]}$ does not exceed $s_{n,r}$. So the odd and even cases
behave differently. Note also that for an odd $r\ge 3$, a maximal by inclusion weakly $r$-separated collection need not
be maximal by size.)

Another impressive result in~\cite{LZ} says that a weakly separated collection
can be transformed into another one by making a \emph{flip} (a sort of
mutation) ``in the presence of four witnesses''. This relies on the following
property (\cite[Theorem~7.1]{LZ}):
  %
  \begin{numitem1} \label{eq:four_witn}
Let $\Wscr\subset 2^{[n]}$ be weakly separated, and suppose that there are
elements $i<j<k$ of $[n]$ and a set $X\subseteq[n]-\{i,j,k\}$ such that $\Wscr$
contains four sets (``witnesses'') $Xi$, $Xk$, $Xij$, $Xjk$ and a set
$U\in\{Xj,Xik\}$; then the collection obtained from $\Wscr$ by replacing $U$ by
the other member of $\{Xj,Xik\}$ is again weakly separated.
  \end{numitem1}
  %
Hereinafter for disjoint sets $A$ and $\{a,\ldots,b\}$, we write $Aa\ldots b$ for $A\cup\{a,\ldots,b\}$.
Also for $a\in A$, we abbreviate $A-\{a\}$ as $A-a$.
We generalize~\eqref{eq:four_witn} as follows.
  %
  \begin{theorem} \label{tm:gen_witn}
For an odd $r$, let $r':=(r+1)/2$. Let $P=\{p_1,\ldots,p_{r'}\}$ and
$Q=\{q_0,\ldots,q_{r'}\}$ consist of elements of $[n]$ such that
$q_0<p_1<q_1<p_2< \ldots<p_{r'}<q_{r'}$, and let $X\subseteq[n]-(P\cup Q)$.
Define the sets of  ``upper'' and ``lower'' \emph{neighbors} (or ``witnesses'') of $P,Q$ to be
   %
  \begin{eqnarray}
  \Nscr^\uparrow(P,Q) &:=& \{Pq\colon q\in Q\}\cup \{(P-p)q\colon
  p\in P,\, q\in Q\}; \quad\mbox{and} \label{eq:NupP}\\
   \Nscr^\downarrow(P,Q) &:=& \{Q-q\colon q\in Q\}\cup \{(Q-q)p\colon
  p\in P,\, q\in Q\}. \label{eq:NdownQ}
  \end{eqnarray}
 %
Suppose that a weakly $r$-separated collection $\Wscr\subset 2^{[n]}$ contains
the set $X\cup P$ (resp. $X\cup Q$) and the sets $X\cup S$ for all $S\in\
\Nscr^\downarrow(P,Q)$ (resp. $S\in\ \Nscr^\uparrow(P,Q)$). Then the collection
obtained from $\Wscr$ by replacing $X\cup P$ by $X\cup Q$ (resp.
$X\cup Q$ by $X\cup P$) is weakly $r$-separated as well.
  \end{theorem}

The above theorems give rise to an important construction. More precisely, for a
cubillage $Q$ in $Z(n,d)$, we introduce a natural \emph{fragmentation} $\Qfrag$
of $Q$, by cutting each ``cube'' $C$ of $Q$ by the ``horizontal'' hyperplanes
through the vertices of $C$, and define a class of $(d-1)$-dimensional
subcomplexes $M$ of $\Qfrag$, called \emph{weak membranes}. These membranes form a distributive lattice. Based on \cref{tm:gen_witn},
we show that if $r:=d-2$ is odd, then the vertex set of $M$ has size
exactly $w_{n,r}$ and constitutes a weakly $r$-separated collection in
$2^{[n]}$. This gives a plenty of size-maximal weakly $r$-separated collections
associated with $Q$, and any two collections among these are linked by a
sequence of (lowering or raising) ``elementary'' \emph{flips}.

In this abstract, \cref{prelim} contains additional definitions and reviews some
basic facts.
\cref{sec:proof1} outlines a proof of \cref{tm:w=s}. The construction of 
max-size weakly r-separated collections via weak membranes in cubillages is described in \cref{sec:weaksep-cubil}.
The concluding \cref{sec:triangl} discusses issues related to the problem of extending a triangulation
in a cyclic polytope to a cubillage and raises some conjectures.

The abstract is based on abridged versions of parts of~\cite{DKK4}
and~\cite{DKK2}, and some results are also reflected in the survey~\cite{DKK3}.
 

%----------------------- Sec. 2

\section{Preliminaries}  \label{prelim}

This section contains additional definitions, notation and conventions. 
Also we review some known properties of cubillages. For details, see~\cite{DKK4,DKK3}.
 

\noindent $\bullet$ ~Let $\pi$ denote the projection $\Rset^d\to\Rset^{d-1}$
given by $(x(1),\ldots,x(d))\mapsto (x(1),\ldots,x(d-1))$. Due
to~\eqref{eq:cyc_conf}(b), the vectors $\pi(\xi_1),\ldots,\pi(\xi_n)$ form a cyclic
configuration as well, and we may say that $\pi$ projects $Z(n,d)$ to the
zonotope $Z(n,d-1)$.
 

\noindent $\bullet$ ~The 0-, 1-, and $(d-1)$-dimensional faces of a cubillage $Q$
in $Z(n,d)$ are called \emph{vertices}, \emph{edges}, and \emph{facets}, respectively. While each vertex is identified with a subset of $[n]$, each
edge $e$ is a parallel translation of some segment $[0,\xi_i]$; we say that $e$
has \emph{color} $i$. 
 

\noindent $\bullet$ ~When a cell (face) $C$ of $Q$ has the lowest point
$X\subseteq[n]$ and when $T\subseteq[n]$ is the set of colors of edges in $C$,
we say that $C$ has the \emph{root} $X$ and \emph{type} $T$, and may write
$C=(X\,|\,T)$. One easily shows that $X\cap T=\emptyset$. 
 

\noindent $\bullet$ ~For a closed subset $U$ of points in $Z=Z(n,d)$, let
$U^{\rm fr}$ ($U^{\rm rear}$) be the subset of $U$ ``seen'' in the direction of
the last, $d$-th, coordinate vector $e_d$ (resp. $-e_d$), i.e., formed
by the points $x\in\pi^{-1}(x')\cap U$ with $x(d)$ minimum (resp. maximum) for
all $x'\in\pi(U)$. It is called the \emph{front} (resp. \emph{rear})
\emph{side} of $U$.

In particular, $\Zfr$ and $\Zrear$ denote the front and rear sides,
respectively, of the zonotope $Z$. We call $\Zrim:=\Zfr\cap\Zrear$
the \emph{rim} of $Z$.
 

\noindent $\bullet$ ~When a set $X\subseteq[n]$ is the union of $k$ intervals
and $k$ is as small as possible, we say that $X$ is a $k$-\emph{interval}. 
Then its complementary set $[n]-X$ is a $k'$-interval with
$k'\in\{k-1,k,k+1\}$. We will use the following known
characterization of the sets of vertices in the front and rear sides of a
zonotope of an odd dimension.
  %
  \begin{numitem1} \label{eq:Zfr-Zrear}
Let $d$ be odd. Then for $Z=Z(n,d)$,

(i) ~$V(\Zfr)$ is formed by all $k$-intervals of $[n]$ with $k\le (d-1)/2$; and
  
(ii) ~$V(\Zrear)$ is formed by the subsets of $[n]$ complementary to those in $V(\Zfr)$;
so it consists of all $k$-intervals with $k<(d-1)/2$, all
$(d-1)/2$-intervals containing at least one of the elements 1 and $n$ and all
$(d+1)/2$-intervals with both 1 and $n$.
    \end{numitem1}
 %
This implies that the set of
\emph{inner} vertices in $\Zfr$, i.e., $V(\Zfr)-V(\Zrim)$, consists of the
$(d-1)/2$-intervals containing none of 1 and $n$, whereas $V(\Zrear)-V(\Zrim)$
consists of the $(d+1)/2$-intervals containing both 1 and $n$.

The rest of this section describes an important class of subcomplexes
in a cubillage $Q$  and associate with $Q$ a certain path structure (used in the next section).

\begin{definition}
Let $Q$ be a cubillage in $Z(n,d)$. A \emph{strong membrane}, 
or, briefly, an
\emph{s-membrane}, in $Q$ is a subcomplex $M$ of $Q$ such that $M$ (regarded as
a subset of $\Rset^d$) is \emph{bijectively} projected by $\pi$ onto $Z(n,d-1)$.
\end{definition}

Then each facet of $Q$ occurring in $M$ is projected to a cube of dimension $d-1$ in $Z(n,d-1)$
and these cubes constitute a cubillage in $Z(n,d-1)$, denoted as $\pi(M)$. In
view of~\eqref{eq:cub-separ} and~\eqref{eq:VQ} (applied to $\pi(Q)$),
  %
  \begin{numitem1} \label{eq:size_membr}
all s-membranes $M$ in a cubillage $Q$ in $Z(n,d)$ have $s_{n,d-2}$ vertices, 
and the vertex set of $M$ (regarded as
a collection in $2^{[n]}$) is strongly $(d-2)$-separated.
  \end{numitem1}

Two s-membranes are of a particular interest. These are the front side $\Zfr$
and the rear side $\Zrear$ of $Z=Z(n,d)$. Following terminology in~\cite{DKK2,DKK3},
their projections $\pi(\Zfr)$ and $\pi(\Zrear)$ are called the \emph{standard}
and \emph{anti-standard} cubillages in $Z(n,d-1)$, respectively.

Next we distinguish certain vertices in cubes. When $n=d$, the zonotope turns
into the cube $C=(\emptyset|[d])$, and there holds:
  %
 \begin{numitem1} \label{eq:unique_inner}
the front side $\Cfr$ (rear side $\Crear$) of $C=(\emptyset|[d])$ has a unique
inner vertex, namely, $t_C:=\{i\in[n]\colon d-i$ odd$\}$ (resp.
$h_C:=\{i\in[n]\colon d-i$ even$\}$.
  \end{numitem1}

When $n$ is arbitrary and $Q$ is a cubillage in $Z=Z(n,d)$, we distinguish
vertices $t_C$ and $h_C$ of a cube $C(X\,|\,T)$ with $T=(p_1<\ldots <p_d)$ in $Q$ in a similar way; namely,
   %
 \begin{numitem1} \label{eq:gencube_inner}
~~~$t_C=X\cup\{p_i\colon d-i$
odd$\}$ and $h_C=X\cup\{p_i\colon d-i$ even$\}$.
  \end{numitem1}

Note that for each vertex $v$ of $Q$, unless $v$ is in $\Zrear$, there is a unique
cube $C\in Q$ such that $t_C=v$, and symmetrically, unless $v$ is in $\Zfr$,
there is a unique cube $C\in Q$ such that $h_C=v$ (to see this, consider the
line going through $v$ and parallel to $e_d$).

Therefore, by drawing for each cube $C\in Q$, the edge-arrow from $t_C$ to
$h_C$, we obtain a directed graph whose connected components are directed
paths going from $\Zfr-\Zrim$ to $\Zrear-\Zrim$. We call these
paths \emph{bead-threads} in $Q$. It is convenient to add to this graph the
elements of $V(\Zrim)$ as isolated vertices, forming \emph{degenerate}
bead-threads, each going from a vertex to itself. Let $B_Q$ be the resulting
directed graph. Then
  %
  \begin{numitem1} \label{eq:BQ}
~$B_Q$ contains  all vertices of $Q$, and each component of $B_Q$ is a
bead-thread going from $\Zfr$ to $\Zrear$.
  \end{numitem1}

Note that the heights $|X|$ of vertices $X$ along a bead-thread are monotone
increasing when $d$ is odd (whereas they are constant when $d$ is even).

%----------------------- Sec. 3

\section{Proof of \cref{tm:w=s}}  \label{sec:proof1}

Let $r$ be odd and $n>r$. We have to show that
  %
  \begin{numitem1} \label{eq:sizeW}
~if $\Wscr$ is a weakly $r$-separated collection in $2^{[n]}$, then $|\Wscr|\le
\binom{n}{\le r+1}$.
  \end{numitem1}

This is valid when $r=1$ (see \eqref{eq:max_size}) and is trivial when $n=r+1$. So
one may assume that $3\le r\le n-2$. We prove~\eqref{eq:sizeW} by induction,
assuming that the corresponding inequality holds for $\Wscr',n',r'$ when $n'\le
n$, $r'\le r$, and $(n',r')\ne (n,r)$.
Define the following subcollections in $\Wscr$:
  %
  \begin{eqnarray}
  \Wscr^-&:=& \{A\subseteq [n-1]\,\colon\,
  \{A,An\}\cap\Wscr\ne\emptyset\},\quad \mbox{and} \nonumber \\
  \Tscr&:=& \{A\subseteq [n-1]\,\colon\, \{A,An\}\subseteq \Wscr\}, \nonumber
  \end{eqnarray}

One easily shows that $\Wscr^-$ is weakly $r$-separated. Then by induction, $|\Wscr^-|\le\binom{n-1}{\le r+1}$. Also 
$|\Wscr|=|\Wscr^-|+|\Tscr|$. Therefore, in view of the identity
$\binom{n}{j}=\binom{n-1}{j} +\binom{n-1}{j-1}$ for any $j\le n-1$,  it suffices to show that
  %
  \begin{equation} \label{eq:Tscr}
  |\Tscr|\le\small{\tbinom{n-1}{\le r}}.
  \end{equation}

For $i=0,1,\ldots n-1$, define $\Tscr^i:=\{A\in\Tscr\,\colon\, |A|=i\}$. We
rely on two claims.
 \medskip

\noindent\textbf{Claim 1} ~\emph{For each $i$, the collection $\Tscr^i$ is
strongly $(r-1)$-separated; moreover, $\Tscr^i$ is weakly $(r-2)$-separated}.
 

\begin{proof}
Let $A,B\in\Tscr^i$. Take an interval cortege
$(I_1,\ldots,I_{r'})$ for $A,B$, %and let for definiteness $I_{r'}$ concerns $A$, 
and we may assume that $I_{r'}\cap (A-B)\ne \emptyset$. 
Then $(I_1,\ldots,I_{r'},I_{r'+1}:=\{n\})$ is an interval cortege for
$A$ and $B':=Bn$. Since $|A|<|B'|$ and $\max (A-B')<\max(B'-A)=n$,
and since $A,B'$ are weakly $r$-separated, $r'+1<r+2$. Then $r'\le r$, implying
that $A,B$ are $(r-1)$-separated. Since
$|A|=|B|$ and $r$ is odd, we also can conclude that $A,B$ are weakly
$(r-2)$-separated.
\end{proof}

Now consider the zonotope $Z=Z(n-1,r)$. For $j=0,1,\ldots,n-1$, define
$\Sscr^j$ ($\Ascr^j$) to be the set of vertices $X$ of $\Zfr$ (resp. $\Zrear$)
with $|X|=j$. We extend each collection $\Tscr^i$ to
  %
  \begin{equation} \label{eq:Dscr_i}
\Dscr^i:=\Tscr^i\cup (\Sscr^{i+1}\cup\ldots \cup \Sscr^{n-1}) \cup
      (\Ascr^0\cup\Ascr^1\cup\ldots \cup\Ascr^{i-1}).
  \end{equation}

\noindent\textbf{Claim 2} ~\emph{$\Dscr^i$ is weakly $(r-2)$-separated.}

\begin{proof} The vertex sets of $\Zfr$ and $\pi(\Zfr)$ are
essentially the same (regarding a vertex as a subset of $[n-1]$), and similarly
for $\Zrear$ and $\pi(\Zrear)$. Since $\pi(\Zfr)$ and $\pi(\Zrear)$ are
cubillages on $Z(n-1,r-1)$ (the so-called ``standard'' and ``anti-standard''
ones), ~\eqref{eq:cub-separ} implies that both collections
$V(\Zfr)=\Sscr^0\cup\ldots\cup \Sscr^{n-1}$ and
$V(\Zrear)=\Ascr^0\cup\ldots\cup \Ascr^{n-1}$ are $(r-2)$-separated, and
therefore, they are weakly $(r-2)$-separated as well.

Next, by~\eqref{eq:Zfr-Zrear}(i), each vertex $X$ of $\Zfr$ is a $k$-interval with
$k\le(r-1)/2$. Such an $X$ and any subset $Y\subseteq[n-1]$ are $k'$-intertwined
with $k'\le 2k+1$. Then $k'\le r$ and this holds with equality when $X$ and $Y$
are $r$-intertwined and $Y$ surrounds $X$. It follows that $X$ is weakly
$(r-2)$-separated from any $Y\subseteq[n-1]$ with $|Y|\le|X|$ (in particular,
if $X\in\Sscr^j$ and $j\ge i$, then $X$ is weakly $(r-2)$-separated from each
member of $\Tscr^i\cup\Ascr^0\cup\ldots\cup \Ascr^{i-1}$).

Symmetrically, by~\eqref{eq:Zfr-Zrear}(ii), each vertex $X$ of $\Zrear$ is the
complement to $[n-1]$ of a $k$-interval with $k\le(r-1)/2$. We can conclude
that such an $X$ is weakly $(r-2)$-separated from any $Y\subseteq[n-1]$ with
$|Y|\ge|X|$.

Now the result is provided by the inequalities $|X|>|A|>|X'|$ for any $A\in\Tscr^i$, $X\in\Sscr^{i+1}\cup\ldots\cup\Sscr^{n-1}$, and
$X'\in\Ascr^0\cup\ldots\cup \Ascr^{i-1}$.
\end{proof}

By induction, $|\Dscr^i|\le\binom{n-1}{\le r-1}$. Then, using~\eqref{eq:size_membr} (for $n-1$ and $r-2$), we have
  %
  \begin{equation} \label{eq:Di_VZfr}
|\Dscr^i|\le{\tbinom{n-1}{\le r-1}}=s_{n-1,r-2}=|V(\Zfr)|.
  \end{equation}

Let $\Sscr':=\Sscr^0\cup\Sscr^1\cup\ldots\cup \Sscr^i$ and
$\Ascr':=\Ascr^0\cup\Ascr^1\cup\ldots\cup\Ascr^{i-1}$. Since $\Sscr^{i+1}\cup
\ldots\cup \Sscr^{n-1}=V(\Zfr)-\Sscr'$, we obtain from~\eqref{eq:Dscr_i}
and~\eqref{eq:Di_VZfr} that
  %
  \begin{equation} \label{eq:T-D-S-A}
  |\Tscr^i|=|\Dscr^i|-(|V(\Zfr)-\Sscr'|)-|\Ascr'|\le |\Sscr'|-|\Ascr'|.
  \end{equation}

We now finish the proof by using a bead-thread technique (see
\cref{prelim}). Fix an arbitrary cubillage $Q$ in $Z=Z(n-1,r)$. Let
$\Rscr^i$ be the set of vertices $X$ of $Q$ with $|X|=i$, and let $\Bscr$ be
the set of paths in the graph $B_Q$ beginning at $\Zfr$ and
ending at $\Zrear$. Since $r$ is odd, each edge $(X,Y)$ of $B_Q$ is
``ascending'' (satisfies $|Y|>|X|$). This implies that each path $P\in\Pscr$
beginning at $\Sscr'$ must meet either $\Rscr^i$ or $\Ascr'$, and conversely,
each path meeting $\Rscr^i\cup\Ascr'$ begins at $\Sscr'$. This
and~\eqref{eq:T-D-S-A} imply
$|\Tscr^i|\le|\Rscr^i|$. 
Summing up these inequalities for $i=0,1,\ldots,n-1$, we have
  $$
 |\Tscr|=\sum\nolimits_i |\Tscr^i|\le\sum\nolimits_i|\Rscr^i| =|V_Q|= s_{n-1,r-1}
  =\tbinom{n-1}{\le r},
  $$
yielding~\eqref{eq:Tscr} and completing the proof of \cref{tm:w=s}.



%----------------------- Sec. 4

\section{Weakly $r$-separated collections generated by cubillages}  \label{sec:weaksep-cubil}

We have seen an interrelation between
strongly $\ast$-separated collections on the one hand, and cubillages and
s-membranes on the other hand (see~\eqref{eq:cub-separ} and \eqref{eq:size_membr}). This
section is devoted to geometric aspects of the weak $r$-separation when $r$ is odd. Being motivated by geometric constructions for maximal weakly
1-separated collections elaborated in~\cite{DKK1,DKK2}, we explain how to
construct maximal by size weakly $r$-separated collections by use of 
\emph{weak membranes}, which are analogs of s-membranes in 
\emph{fragmentations} of cubillages.

\subsection{Fragmentation and weak membranes.}
~Let $Q$ be a cubillage in $Z(n,d)$. The
\emph{fragmentation} of $Q$ is  the complex $\Qfrag$ obtained by
cutting $Q$ by the ``horizontal'' hyperplanes  $H_\ell:=\{x\in \Rset^d\,\colon\, x(1)=\ell\}$, 
~$\ell=1,\ldots,n-1$.

Such hyperplanes subdivide each cube $C=(X\,|\,T)$ of $Q$ into pieces
$\Cfrag_1,\ldots,\Cfrag_d$, where $\Cfrag_h$ is the portion of $C$
between $H_{|X|+h-1}$ and $H_{|X|+h}$, called a
\emph{fragment} of $C$ (and of $\Qfrag$). Let $S_h(C)$ denote $h$-th horizontal
section $C\cap H_{|X|+h}$ of $C$; this
is the convex hull of the set of vertices
 $(X\,|\,\tbinom{T}{h}):=\{X\cup A\,\colon\, A\subset T,\; |A|=h\}$ (forming a \emph{hyper-simplex}
and turning into a simplex when $h=1$ or $d-1$).  We call
$S_{h-1}(C)$ and $S_h(C)$ the \emph{lower} and \emph{upper} (horizontal) facets of the
fragment $\Cfrag_h$, respectively. (Here $S_0(C)$ and $S_d(C)$ degenerate
to the single points $X$ and $X\cup T$, respectively.)  The other facets of  $\Cfrag_h$ are conditionally called 
\emph{vertical} ones.

Note that the horizontal facets are ``not fully seen'' under the projection $\pi$. To
make all facets of fragments of $\Qfrag$ visible, we look at them
as though ``from the front and slightly from below'', i.e., by using the
projection $\pi^\eps: \Rset^d\to\Rset^{d-1}$ defined by
   %
   \begin{equation} \label{eq:pi_eps}
 x=(x(1),\ldots,x(d))\mapsto (x(1)-\eps x(d),x(2),\ldots,x(d-1))=: \pi^\eps(x)
   \end{equation}
 %
for a sufficiently small $\eps>0$. (Compare $\pi^\eps$ with $\pi$.)

This projection makes slanting front and rear sides of
objects in $\Qfrag$. More precisely, for a closed set $U$ of points in
$Z=Z(n,d)$, let $U^\epsfr$ ($U^\epsrear$) be the subset of $U$ formed by the points $x\in(\pi^\eps)^{-1}(x')\cap U$
with $x(d)$ minimum (resp. maximum) for all $x'\in\pi^\eps(U)$. We call it the
$\eps$-\emph{front} (resp. $\eps$-\emph{rear}) \emph{side} of $U$.

Obviously, $Z^\epsfr=\Zfr$ and $Z^\epsrear=\Zrear$, and similarly for any cube $C=(X|T)$ in $Z$. As to fragments of $C$, their
$\eps$-front and $\eps$-rear sides are viewed as follows:
   %
\begin{numitem1} \label{eq:sides_fragm}
for $h=1,\ldots,d$, ~$C^\epsfr_h=\Cfr_h\cup S_{h-1}(C)$ and 
$C^\epsrear_h=\Crear_h\cup S_{h}(C)$.
  \end{numitem1}

So $C^\epsfr_h\cup C^\epsrear_h$ is just the boundary of $\Cfrag_h$.
 

Next we explain the notion of weak membranes. They represent certain $(d-1)$-dimensional subcomplexes of
the fragmentation $\Qfrag$ of $Q$ and use the projection $\pi^\eps$ 
(in contrast to strong membranes which deal with $Q$ and $\pi$). 

To introduce them, we slightly modify cyclic zonotopes
in $\Rset^{d-1}$. Specifically, given a
cyclic configuration $\Xi=(\xi_1,\ldots,\xi_n)$ as in~\eqref{eq:cyc_conf}, define
$\psi^\eps_i:=\pi^\eps(\xi_i)$, $ i=1,\ldots, n$.
When $\eps$ is small enough, $\Psi^\eps=(\psi^\eps_1,\ldots,
\psi^\eps_n)$ obeys the condition~\eqref{eq:cyc_conf}(b), though slightly
violates~\eqref{eq:cyc_conf}(a). Yet we keep the term ``cyclic configuration'' for
$\Psi^\eps$ as well, and consider the zonotope in $\Rset^{d-1}$ generated by
$\Psi^\eps$, denoted as $Z^\eps(n,d-1)$.
 

\begin{definition} A \emph{weak membrane}, or, briefly, a \emph{w-membrane}, of a cubillage $Q$ in
$Z(n,d)$ is a subcomplex $M$ of the fragmentation $\Qfrag$ such that $M$
(regarded as a subset of $\Rset^d$) is bijectively projected by $\pi^\eps$ to
$Z^\eps(n,d-1)$.
  \end{definition}

A w-membrane $M$ uses facets of fragments in $\Qfrag$ which are  of two sorts, namely, ``horizontal'' and ``vertical'' ones  as mentioned above.
The set $\Mscrw(Q)$ of w-membranes of $Q$ is rich and forms a distributive lattice.
To see this, for fragments $\Delta=\Cfrag_i$ and $\Delta'=(C')^\equiv_j$ of $\Qfrag$, let us say that
$\Delta$ \emph{immediately precedes} $\Delta'$ if the $\eps$-rear side of
$\Delta$ and the $\eps$-front side of $\Delta'$ share a facet. In other words,
either $C\ne C'$ and $\Delta^{\rm rear}\cap(\Delta')^{\rm fr}$ is a vertical facet, or
$C=C'$ and $j=i+1$. A nice property of this relation is that
the directed graph whose vertices are the fragments in
$\Qfrag$ and whose edges are the pairs $(\Delta,\Delta')$ of fragments such
that $\Delta$ immediately precedes $\Delta'$ is acyclic  (see~\cite{DKK4,DKK3}).

It follows that the transitive closure of
this relation forms a partial order on the fragments of $\Qfrag$ ; denote
it as $(\Qfrag,\prec)$. To see that it is a lattice, associate with each w-membrane $M$
the set $\Qfrag(M)$ of fragments
in $\Qfrag$ lying in the region of $Z(n,d)$ between $\Zfr$ and $M$. One easily shows that for
fragments $\Delta,\Delta'$ of $\Qfrag$, if $\Delta$ immediately precedes
$\Delta'$ and if $\Delta'\in \Qfrag(M)$, then $\Delta\in\Qfrag(M)$ as well.
This implies a similar property for fragments $\Delta,\Delta'$ with
$\Delta\prec\Delta'$. So $\Qfrag(M)$ is an ideal of $(\Qfrag,\prec)$. A converse property is true as well. Thus,
  %
   \begin{numitem1} \label{eq:w-lattice}
$\Mscrw(Q)$ is a
distributive lattice in which for $M,M'\in\Mscrw(Q)$, the w-membranes $M\wedge
M'$ and $M\vee M'$ satisfy $\Qfrag(M\wedge M')=\Qfrag(M)\cap \Qfrag(M')$ and
$\Qfrag(M\vee M')=\Qfrag(M)\cup \Qfrag(M')$; the minimal and maximal elements
of this lattice are the s-membranes $\Zfr$ and $\Zrear$, respectively.
  \end{numitem1}

Next, if $M\in\Mscrw(Q)$ is different from $\Zfr$, then
$\Qfrag(M)\ne\emptyset$. Take a maximal (w.r.t. $\prec$) fragment $\Delta$ in $\Qfrag(M)$. 
Then $\Delta^\epsrear$ is entirely
contained in $M$ and the set $\Qfrag(M)-\{\Delta\}$ is again an ideal of
$(\Qfrag,\prec)$; so it is expressed as $\Qfrag(M')$ for a
w-membrane $M'$. Moreover, $M'$ is obtained from $M$ by replacing the disk
$\Delta^\epsrear$ by $\Delta^\epsfr$. We call the transformation $M\mapsto M'$
the \emph{lowering flip} in $M$ \emph{using} $\Delta$, and call the reverse
transformation $M'\mapsto M$ the \emph{raising flip} in $M'$ \emph{using}
$\Delta$. As a result, we obtain that
 %
  \begin{numitem1} \label{eq:flip} 
for any $M\in\Mscrw(Q)$, there exists a sequence of
w-membranes $M_0,M_1,\ldots,M_k\in \Mscrw(Q)$ such that $M_0=\Zfr$, $M_k=M$,
and for $i=1,\ldots,k$, $M_i$ is obtained from $M_{i-1}$ by the raising flip
using some fragment in $\Qfrag$.
  \end{numitem1}
 
\subsection{Weakly $r$-separated collections via w-membranes.} 
Based on \cref{tm:gen_witn} (see~\cite[Section~5]{DKK4} for the proof), we establish the following

 \begin{theorem} \label{tm:membr-wsepar}
Let $r$ be odd and $d=r+2$. For each w-membrane $M$ of a cubillage $Q$ in $Z=Z(n,d)$, its spectrum $V(M)$ 
has size $w_{n,r}$ and constitutes a maximal by size
weakly $r$-separated collection in $2^{[n]}$. 
  \end{theorem}
  %
  \begin{proof}
For $M\in\Mscrw(Q)$, consider a sequence $\Zfr=M_0,M_1,\ldots,M_k=M$ as in~\eqref{eq:flip}. Let $M_i$ ($i>0$) be obtained from $M_{i-1}$ by the raising flip
using a fragment $\Delta_i$ of $\Qfrag$. Since $V(\Zfr)$ is strongly r-separated and 
$V(\Zfr)=s_{n,r}=w_{n,r}$ (see \eqref{eq:size_membr}), it suffices to show that if
$V(M_{i-1})$ has size $w_{n,r}$ and is weakly $r$-separated, then so is $V(M_i)$.

To show this, let
$\Delta:=\Delta_i=\Cfrag_h$ for a cube $C=(X\,|\,T=(p(1)<\ldots<p(d)))$ and $h\in[d]$. Then
$V(\Cfr)=V(\Crim)\cup\{t_C\}$ and
$V(\Crear)=V(\Crim)\cup\{h_C\}$, where $t_C=Xp(2)p(4)\ldots p({d-1})$ and
$h_C=Xp(1)p(3)\ldots p(d)$ (see \eqref{eq:unique_inner}). Let $R$ be the
set of vertices in $\Crim\cap \Delta$, and let $r':=(d-1)/2$. Then $r'$ is an integer, $t_C$ lies in the section $S_{r'}(C)$,
and $h_C$ lies in $S_{r'+1}(C)$. Three cases are possible.

\noindent\emph{Case 1}: ~$h\le r'$. Since the vertices of $\Delta$ are formed
by the sections $S_{h-1}(C)$ and $S_h(C)$,
   $$
  V(\Delta)=(X\,|\,\tbinom{T}{h-1})\cup(X\,|\,\tbinom{T}{h}) \quad\mbox{and}
  \quad R\subseteq V(\Deltafr)\cup V(\Deltarear).
  $$
Also $V(\Deltafr)\subseteq V(\Delta^\epsfr)$ and
$V(\Deltarear)\subseteq V(\Delta^\epsrear)$. When $h<r'$, all vertices of
$\Delta$ belong to $\Crim$, implying
$V(\Delta^\epsfr)=R=V(\Delta^\epsrear)$. And when $h=r'$, the only vertex of
$\Delta$ not in $R$ is $t_C$. Since $t_C\in V(\Cfr)$, $t_C$ belongs to
$\Delta^\epsfr$. But $t_C$ also lies in the upper facet $S_{r'}(C)$, and this facet is included in $\Delta^\epsrear$.
Hence $t_C\in \Delta^\epsfr\cap \Delta^\epsrear$, implying
$V(\Delta^\epsfr)=V(\Delta^\epsrear)$.
  

\noindent\emph{Case 2}: ~$h\ge r'+2$. This is ``symmetric'' to the previous
case.
  

Thus, in both cases the raising flip $M\mapsto M'$ using $\Delta$ gives $V(M)=V(M')$.
 

\noindent\emph{Case 3}: ~$h=r'+1$. This case is most important. Here the lower
facet $S_{h-1=r'}(C)$ of $\Delta$ contains $t_C$, and the upper facet
$S_{h=r'+1}(C)$ contains $h_C$. Hence $t_C\in V(\Delta^\epsfr)$ and $h_C\in
V(\Delta^\epsrear)$. On the other hand, neither $t_C$ belongs to
$\Delta^\epsrear$ ($=\Deltarear\cup S_{r'+1}(C)$), nor $h_C$ belongs to
$\Delta^\epsfr$ ($=\Deltafr\cup S_{r'}(C)$).

It follows that $V(\Delta^\epsrear)=(V(\Delta^\epsfr)-\{t_C\})\cup\{h_C\}$. Hence
the raising flip $M\mapsto M'$ using $\Delta$ replaces $t_C$ by
$h_C$, while preserving the other vertices of the w-membrane. Also
the vertices of $\Delta$ different from $t_C,h_C$ form just the collection of
sets $XS$ such that $S$ runs over $\Nscr^\downarrow(\tilde P,\tilde Q)$, the set of
lower neighbors of $\tilde P:=p(2)p(4)\ldots p(d-1)$ and $\tilde Q:=p(1)p(3)\ldots
p(d)$. 
Now applying \cref{tm:gen_witn} to $\Wscr:=V(M),\,X,\tilde P,\tilde Q$, 
we conclude that $V(M')$ is weakly $r$-separated, as
required.
 \end{proof}

Note that the case $r=1$  of \cref{tm:membr-wsepar} is obtained in~\cite[Corollary~6.5]{DKK2}.

A natural question is whether any two size-maximal weakly separated collections in $2^{[n]}$ 
can be connected by a sequence of flips. This is strengthened in the following conjecture (which was proved for $r=1$ in~\cite[Theorem~7.1]{DKK2}):
 %
\begin{conjecture}\label{C1}
~for $r$ odd, any size-maximal weakly $r$-separated collection in $2^{[n]}$ is
representable as the spectrum of a weak membrane of some cubillage $Q$ in $Z(n,r+2)$.
\end{conjecture}

%----------------------- Sec. 5

\section{Triangulations, hyper-combies, and cubillages}  \label{sec:triangl}

Consider the polytope $P=P(n,d-1)$ that is the section of the zonotope $Z(n,d)$ by the hyperplane 
$H_1=\{x\in \Rset^d\,\colon\, x(1)=1\}$, called the \emph{cyclic polytope} with $n$ vertices of dimension $d-1$. Let $\Tscr(P)$ be the set of \emph{triangulations} of $P$ that are subdivisions of $P$ into $(d-1)$-dimensional simplexes whose vertices are vertices of $P$ (i.e., occur in $\Xi$ as in~\eqref{eq:cyc_conf}). It has been known (see~\cite{OS} for details) that
  %
\begin{numitem1} \label{eq:RS}
for any $\tau\in\Tscr(P(n,d-1))$, there exists a cubillage $Q$ in $Z(n,d)$ whose section
by $H_1$ (formed by the simplexes $C\cap H_1$ for cubes $C$ with the root $\emptyset$ in $Q$) is $\tau$.
  \end{numitem1}
 
To define more general objects, consider the projection $\pi^\eps$ and
the modified zonotope $Z^\eps(n,d-1)$ as in \cref{sec:weaksep-cubil}. Let $\Fscr(n,d)$ be the set of facets in fragments $\Cfrag_h$ of all (abstract) cubes $C=(X\,|\,T)$ in
$Z(n,d)$ (running $X,T\subset[n]$ with $|T|=d$ and $X\cap T=\emptyset$).

\begin{definition} A \emph{hyper-combi} $K$ is a subdivision of $Z^\eps(n,d-1)$ into $(d-1)$-dimensional
polytopes of the form $\pi^\eps(F)$, where $F\in\Fscr(n,d)$.
\end{definition}

%(In case $d=3$, this matches the notion of a \emph{(quasi-)combi} studied in~\cite{DKK1,DKK2}.) 
In particular, 
any w-membrane $M$ of a cubillage in $Z(n,d)$ generates the hyper-combi $\pi^\eps(M)$. An important special case arises
when $M$ is a \emph{principal} w-membrane in level $\ell\in[1,n-1]$. This means that $M$ is the section by 
$H_\ell=\{x\in\Rset^d\,\colon\, x(1)=\ell\}$ of some cubillage  in $Z=Z(n,d)$ to which the boundary parts 
\[
 \Zfr_{\ell\uparrow}:=\Zfr\cap\{x\in\Rset^d\,\colon\, x(1)\ge \ell\} \quad \mbox{and}\quad
\Zrear_{\ell\downarrow}:=\Zrear\cap\{x\in\Rset^d\,\colon\, x(1)\le \ell\}
\]
are added, where $\Zfr$ and $\Zrear$ are the (properly fragmented) front and rear sides of $Z$.  Then the essential (``horizontal'')
part of a principal w-membrane in level 1 is just a triangulation in $\Tscr(P(n,d-1))$ (while for an arbitrary $\ell$ it is known as ``hypersimplicial subdivision'' of the corresponding section of the zonotope, see~\cite{OS}). 
%
\begin{conjecture}\label{C2}
For any hyper-combi $K$ in $Z^\eps(n,d-1)$ with $d$ odd, there exists a cubillage $Q$ in $Z(n,d)$ and a w-membrane
$M$ in (the fragmentation) of $Q$ such that $\pi^\eps(M)=K$.
  \end{conjecture}

The validity of \cref{C2} for $d=3$ is proved in~\cite[Section~7]{DKK2} (where the desired $Q$ and $M$ are explicitly constructed for an arbitrary (properly triangulated) combi $K$ in $Z^\eps(n,2)$); also we are able to prove this for $d=5$.

Next, Oppermann and Thomas~\cite{OT2} revealed a nice property of triangulations of a cyclic polytope $P=P(n,2r)$ having an even dimension $2r=d-1$. More precisely, identify each $r$-dimensional face in a triangulation of $\tau$
(regarded as a complex) with the corresponding increasing $(r+1)$-tuple in $[n]$. Let $e(\tau)$ denote the set of sparse $r$-faces in $\tau$, where  a face (tuple) is called \emph{sparse} if it has no pair $i,i+1$. For
increasing tuples $A=(a_0,\ldots,a_r)$ and $B=(b_0,\ldots,b_r)$, one says that $A$ \emph{intertwines} $B$ if 
$a_0<b_0<a_1<b_1<\cdots<a_r<b_r$, and a collection $\Ascr$ of $(r+1)$-tuples is called \emph{non-intertwining} if no two
tuples in $\Ascr$ intertwine. In other words, $\Ascr$ is weakly $(2r-1=d-2)$-separated (since all elements of $\Ascr$
have the same size). By \cite[Theorems 2.4 and 2.5]{OT2},
%
 \begin{numitem1} \label{eq:Pn2r}
(a) For $P=P(n,2r)$ and $\tau\in\Tscr(P)$, the collection $e(\tau)$ has cardinality $\binom{n-r-1}{r}$ and is non-intertwining.
(b) Conversely, any non-intertwining collection $\Ascr$ of $\binom{n-r-1}{r}$ sparse $(r+1)$-tuples in $[n]$ represents $e(\tau)$ for
a unique $\tau\in\Tscr(P)$.
 \end{numitem1} 

We can use this as follows. Consider $\Ascr$ and $\tau$ as in~\eqref{eq:Pn2r}(b). By~\eqref{eq:RS}, there exists a cubillage $Q$ in $Z=Z(n,d)$ such that
$\tau$ is the section of $Q$ by $H_1$. Then each element $A\in\Ascr=e(\tau)$ labels a vertex  of $Q$ contained in level $r$. This vertex is not in $\Zfr$,
which follows from~\eqref{eq:Zfr-Zrear} and the fact that $A$ is sparse. Let $M$ be the principal w-membrane for $Q$ in level $r$.
Then $|V(\Zfr_{r\uparrow})|+|\Ascr|+|V(\Zrear_{(r-1)\downarrow})|\le |V(M)|=w_{n,d-2}$ (in view of \cref{tm:membr-wsepar}).
Moreover,  the inequality here holds with equality (which is seen by directly counting  the first and third summands and using 
$|\Ascr|=\binom{n-r-1}{r}$). 

As a consequence, \eqref{eq:RS} implies a weakened version of \cref{C1}:
for $d$ odd, any size-maximal collection of weakly $(d-2)$-separated  subsets $A\subset[n]$ with $|A|=(d-1)/2$ is contained in the spectrum
of a w-membrane of some cubillage in $Z(n,d)$.

%\acknowledgements{We thank the anonymous referees for useful remarks and suggestions.}

    %--------------------
\printbibliography

\end{document}
