From - Wed Sep  1 10:35:03 1999
Return-Path: <alek@mathcs2.haifa.ac.il>
Received: from isis.lip6.fr ([132.227.60.2] (may be forged))
          by mail.liafa.jussieu.fr (8.8.6/jtpda-5.2) with ESMTP id PAA18171
          for <Claude.Precetti@liafa.jussieu.fr>; Tue, 31 Aug 1999 15:52:01 +0200 (MET DST)
Received: from research.haifa.ac.il (root@research.haifa.ac.il [132.74.99.4])
          by isis.lip6.fr (8.8.8/jtpda-5.2.9.1+lip6) with ESMTP id PAA09201
          for <Claude.Precetti@liafa.jussieu.fr>; Tue, 31 Aug 1999 15:51:57 +0200 (MET DST)
Received: from mathcs11.haifa.ac.il (alek@mathcs11.haifa.ac.il [132.74.9.7])
	by research.haifa.ac.il (8.8.8/8.8.8) with ESMTP id QAA38020
	for <Claude.Precetti@liafa.jussieu.fr>; Tue, 31 Aug 1999 16:50:40 +0300
Date: Tue, 31 Aug 1999 16:51:23 +0300 (IDT)
From: Alexander Vainshtein <alek@mathcs2.haifa.ac.il>
X-Sender: alek@mathcs11.haifa.ac.il
To: Claude PRECETTI <Claude.Precetti@liafa.jussieu.fr>
Subject: AMSTEX file
In-Reply-To: <199908311348.PAA16640@mail.liafa.jussieu.fr>
Message-ID: <Pine.A32.4.05.9908311650480.23179-100000@mathcs11.haifa.ac.il>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-UIDL: 63c3689245e637d217dabe9501580457
X-Mozilla-Status: 0001
Content-Length: 11450

\input amstex
\documentstyle{amsppt}
\magnification 1200
\hsize=14truecm
\vsize=23truecm
\tolerance 1000

\def\ls{\leqslant}
\def\gs{\geqslant}
\def\Fl{\operatorname{Fl}}
\def\FF{\Bbb F}
\def\RR{\Bbb R}
\def\T{\tau}
\def\codim{\operatorname{codim}}
\def\Arf{\operatorname{Arf}}
\def\GG{\frak G}
\def\Gg{\frak G}
\def\D{\frak D}
\def\G{\Gamma}
\def\g{{\gamma}}
\def\P{\Cal P}
\def\L{\Lambda}
\def\A{\Cal A}

\topmatter
\title
Intersections of Schubert cells and groups generated by symplectic
transvections
\endtitle
\author
B.~Shapiro$^{\ddag}$, M.~Shapiro$^*$, and A.~Vainshtein$^\dag$ \endauthor
\affil
$^\ddag$ Department of Mathematics, University of Stockholm\\
S-10691, Sweden, {\tt shapiro\@matematik.su.se}\\ 
$^*$ Department of Mathematics, Royal Institute of Technology\\
S-10044, Sweden, {\tt mshapiro\@math.kth.se} \\ 
$^\dag$ Dept. of Mathematics and  Dept. of Comp. Science, University of Haifa
\\ Mount Carmel, 31905 Haifa, Israel, {\tt alek\@mathcs11.haifa.ac.il} 
\endaffil
\leftheadtext{B.~Shapiro, M.~Shapiro, and A.~Vainshtein}
\abstract
We prove that the number of connected
components in the intersection of two open Schubert cells in relative position
$w$ in the space of complete real $n$-dimensional flags equals
$3\cdot 2^{n-1}$ for a generic permutation $w\in S_n$. Our construction
combines the machinery of pseudo-line arrangements with the theory of
groups generated by symplectic transvections.
%\medskip
%\noindent
%{\smc R\'esum\'e}. 
\endabstract
\rightheadtext{Intersections of Schubert cells}

\thanks{The third author was supported in part by the Swedish Science
Foundation during his visit to the Royal Institute of Technology in the
Spring 1998 and Fall 1998.}
\endthanks
\keywords{symplectic transvection, reduced decomposition, real flags,
Schubert cell decomposition}\endkeywords
\endtopmatter

\document

The point of departure for this talk is the following result
obtained in \cite{SSV2, SSV3}.
Let $N_n^0$ denote the semi-algebraic set of all unipotent
upper-triangular $n \times n$ matrices $x$ with real entries such that
for every $k =1,\ldots, n-1$, the minor of $x$ with rows $1,\ldots,k$ and 
columns $n-k+1,\ldots,n$ is non-zero. Then the number $\#_n$ of connected 
components of $N_n^0$ is as follows: $\#_2 = 2$, $\#_3 = 6$, $\#_4 = 20$, 
$\#_5 = 52$, and $\#_n = 3\cdot2^{n-1}$ for $n \gs 6$.

Let $\Fl_n$ be the space of complete flags in $\RR^n$. Given any $f\in Fl_n$,
the Schubert cell decomposition assigns to each $w\in S_n$ a Schubert cell
$C_w^f$ whose dimension equals the number of inversions in $w$. For any
$g\in\Fl_n$ we put $C_{w_1,w_2}^{f,g}=C_{w_1}^f\cap C_{w_2}^g$. Recall that
$C_{w_1,w_2}^{f,g}$ depends only on the relative position of $f$ and $g$,
that is, $C_{w_1,w_2}^{f,g_1}$ and $C_{w_1,w_2}^{f,g_2}$ are isomorphic,
provided $g_1$, $g_2$ belong  to the same $C_w^f$. For this reason, we 
write $C_{w_1,w_2}^w$ instead of $C_{w_1,w_2}^{f,g}$, $g\in C_w^f$. The
geometry and combinatorics of pairwise intersections  $C_{w_1,w_2}^w$
for arbitrary $w_1,w_2,w$ was studied in \cite{SSV1}.

Let $C^w=C_{w_0,w_0}^w$, where $w_0=n\, n-1 \dots 1$ is the longest 
permutation in $S_n$. Intersections $C^w$ appeared in the literature in
various contexts, and were studied (in various degrees of generality)
in \cite{BFZ,BZ,R1,R2}. It is easy to see that
$N_n^0=C^{w_0}$, so the result cited above gives the number of
connected components in $C^{w_0}$. The main result of the present talk is the 
following generalization of the above result. 

\proclaim{Theorem~1} For a generic $w\in S_n$ the number of connected 
components in $C^w$ equals $3\cdot 2^{n-1}$.
\endproclaim

Our basic construction relies on the machinery of pseudoline arrangements
associated with reduced expressions in the symmetric group developed
in \cite{BFZ}. Let $w\in S_n$ be an arbitrary permutation, and let
$\omega=s_{i_1}s_{i_2}\dots s_{i_m}$ be an arbitrary reduced expression
for $w$. We denote by $\sigma=\sigma^\omega$ the sequence 
$1\, 2\dots n-1\, i_1\dots i_m$, 
and by $\sigma_i$ the $i$th element of $\sigma$.
A pair $(\sigma_i,\sigma_j)$, $i<j$, is called a chamber (of level $k$) if 
$\sigma_i=\sigma_j=k$ and $\sigma_p\ne k$ for $i<p<j$. A chamber 
$(\sigma_i,\sigma_j)$ is called bounded if $i>n-1$ and unbounded otherwise.

We assign to $\sigma^\omega$ an undirected graph $G^\omega$ in the following 
way. The vertices of $G^\omega$ are all the chambers of $\sigma^\omega$;
we denote the vertex set of $G^\omega$ by $\Gamma^\omega$. 
Let $\g_1=(\sigma_{i_1},\sigma_{j_1})$
be a chamber of level $k_1$,  $\g_2=(\sigma_{i_2},\sigma_{j_2})$
be a chamber of level $k_2$; assume without loss of generality 
that $i_1<i_2$. The vertices
$\g_1$ and $\g_2$ are joined  by an edge in $G^\omega$ if and only if one of 
the following two conditions holds:

(i) $k_1=k_2$ and $\sigma_i\ne k_1$ for $j_1<i<i_2$;

(ii) $|k_1-k_2|=1$ and $i_2<j_1<j_2$.

Denote by $V^\omega=\FF_2^{\G^\omega}$
the vector space over $\FF_2$ with the basis $e_\gamma$, 
$\gamma\in\Gamma^\omega$. The graph $G^\omega$ induces an alternating 
bilinear form $\Omega^\omega$ on $V^\omega$, namely, 
$$
\Omega^\omega=\sum_{(\alpha,\beta)\in G^\omega}e^*_\alpha\wedge e^*_\beta.
$$
For any $\g\in\G^\omega$ we define a linear transformation 
$\T_\g\: V^\omega\to V^\omega$ by the following rule:
$$
\T_\g v=v-\Omega^\omega(v,e_\g)e_\g\qquad\text{for any $v\in V^\omega$};
$$
$\T_\g$ is called the symplectic transvection at $\g$ with respect to 
$\Omega^\omega$.
Let $\G_0^\omega\subset\G^\omega$ be the set of bounded chambers of 
$\sigma^\omega$. We denote by $\GG^\omega$ the group
of linear transformations $V^\omega\to V^\omega$ generated by 
$\{\T_\g, \g\in\G_0^\omega\}$. 
  
The following result is a generalization of the main theorem of \cite{SSV2}.

\proclaim{Theorem~2} For any $w\in S_n$ and any reduced expression 
$\omega$ for $w$, the number 
of connected components of $C^w$ equals the number of orbits of 
$\GG^\omega$ in $V^\omega$.
\endproclaim

Our construction of $\GG^\omega$ is a special case of a more general 
construction, which uses an arbitrary finite set $\G$, an arbitrary undirected
graph $G$ without loops and multiple edges on the vertex set $\G$, and 
an arbitrary subset $\G_0\subseteq\G$. The orbits of $\GG$ in $V=\FF_2^\G$ 
in case
$\G_0=\G$ were studied in \cite{Ja} under certain assumptions of
general position; the number of orbits in this case is equal to~$3$. Here we
prove that under similar assumptions the number of $\GG$-orbits in $V$ 
equals $3\cdot 2^r$, where $r=|\G|-|\G_0|$.

Let us define the linear operator $L\: V\to V^*$ by 
$\Omega(x,y)=(x,Ly)$, where $(\cdot,\cdot)$ is the standard
pairing between $V$ and $V^*$; evidently,  $L^*=L$. Let $V_0=\FF_2^{\G_0}$ 
be the space spanned by $e_\g$, $\g\in\G_0$; 
by $\iota$ we denote the injection $V_0\hookrightarrow V$, 
and by $\iota^*$ its dual $V^*\to V_0^*$. Combining $L$ with $\iota$ and 
$\iota^*$ we get the maps $\L=L\circ \iota\:V_0\to V^*$ and 
$L_{0}=\iota^*\circ \L\: V_0\to V_0^*$; evidently, $L_{0}^*=
i^*\circ L^*\circ i=i^*\circ L\circ i=L_{0}$.

The following observation turns out to be crucial for our construction.
Let $\Omega_0$ denote the restriction of the form $\Omega$ to $V_0$.

\proclaim{Theorem~3}  Let $\G$, $\G_0$ and $G$ satisfy condition
$$
\text{$\Lambda^*\: V\to V_0^*$ is a surjection}, \tag *
+$$
then the $\GG$-action on $V_0$ by symplectic transvections with respect
to $\Omega_0$ is dual to the $\GG$-action on $V_0^*$ induced by $\L^*$.
\endproclaim

We say that a subset $\Delta\subseteq \G_0$ is a transversal
if $|\G_0|-|\Delta|=\dim\ker L_0$ and the restriction of $\Omega$ to
$\FF_2^\Delta$ is nondegenerate. A transversal is called nonspecial
if the subgraph of $G$ induced by $\Delta$ is connected and contains
six vertices that span a subgraph isomorphic to the Dynkin diagram 
$E_6$.

\proclaim{Theorem~4} Let $\G$, $\G_0$ and $G$ satisfy $(*)$
and let there exist two nonspecial transversals
$\Delta_1,\Delta_2\subseteq \G_0$ such that 
$$\gather
\Delta_1\cup\Delta_2=\G_0,\tag **\\
\text{$(\gamma_1,\gamma_2)\in G$ for some pair 
$\gamma_1,\gamma_2\in \Delta_1\cap\Delta_2$}.\tag ***
\endgather
$$ 
Then the number of orbits of 
$\GG$ on $V$ equals $3\cdot 2^r$, where $r=|\G|-|\G_0|$.
\endproclaim

To apply Theorem~4 we have to verify its
assumptions for the triple $(\G^\omega, \G_0^\omega, G^\omega)$. 
First of all, we have the following proposition. 

\proclaim{Proposition~5}
For any $w\in S_n$ and any reduced expression $\omega$ for $w$,
the linear operator $(\Lambda^\omega)^*$ satisfies $(*)$.
\endproclaim

Let $\omega$ be a reduced expression for some $w\in S_n$. If the subgraph 
$G_0^\omega$ of $G^\omega$ induced by $\Gamma_0^\omega$ is not connected, then
$w$ can be decomposed into the product of two permutations on the index 
sets $[1,\dots,i]$ and $[i,\dots,n]$ with $1<i<n$; moreover, $G_0^{\omega'}$
remains not connected for any other reduced expression $\omega'$ of $w$.
Therefore, the fraction of permutations for which $G_0^\omega$ is connected
tends to 1 with $n\to\infty$, and hence this property is generic. On the
other hand, the existence of a reduced expression $\omega$ such that 
$\sigma^\omega$ contains three consequent indices $i-1$, $i$, $i+1$ at least
$k$ times is also generic for any fixed $k$.

\proclaim{Proposition~6} Let $w\in S_n$ possess a reduced expression
$\omega$ such that $G_0^\omega$ is connected and $\sigma^\omega$ contains 
each of the indices $i-1$, $i$, $i+1$ at least $5$ times for some $i$, 
$1<i<n-2$. Then there exist two nonspecial transversals 
$\Delta_1,\Delta_2\subseteq\G_0^\omega$ satisfying $(**)$ and $(***)$.
\endproclaim

To get Theorem~1 from Theorem~4 it remains to observe that  
$r^\omega=|\G^\omega|-|\G_0^\omega|$ 
is just the number of unbounded chambers, $r^\omega=n-1$.

\Refs
\widestnumber\key{SSV3}

\ref\key{BFZ} 
\by A.~Berenstein, S.~Fomin, and A.~Zelevinsky
\paper Parametrizations of canonical bases and totally positive matrices
\jour Adv. Math.\vol 122 \yr 1996 \pages 49--149
\endref

\ref\key{BZ} 
0\by A.~Berenstein and A.~Zelevinsky
\paper  Total positivity in Schubert varieties
\jour Comm. Math. Helv. \vol 72\yr 1997\pages 128--166
\endref

\ref\key{Ja}
\by W.~A.~M.~Janssen
\paper Skew-symmetric vanishing lattices and their monodromy groups
\jour Math. Ann. \yr 1983 \vol 266 \pages 115--133
\endref

\ref\key{R1}
\by K.~Rietsch
\paper The intersection of opposed big cells in real flag varieties
\jour Proc. Royal Soc. Lond. A \vol 453 \yr 1997\pages 785--791
\endref

\ref\key{R2}
\by K.~Rietsch
\paper Intersections of Bruhat cells in real flag varieties
\jour Intern. Math. Res. Notices
\yr 1997
\issue 13
\pages 623--640
\endref

\ref\key{SSV1}
\by B.~Shapiro, M.~Shapiro, and A.~Vainshtein
\paper On combinatorics and topology of pairwise intersections
of Schubert cells in $SL_n/B$
\inbook Arnold--Gelfand Mathematical Seminars
\publ Birkh\"auser
\yr 1997
\pages 397--437
\endref

\ref\key{SSV2}
\by B.~Shapiro, M.~Shapiro, and A.~Vainshtein
\paper Connected components in the
intersection of two open opposite Schubert cells in $SL_n(\RR)/B$
\jour Intern. Math. Res. Notices
\yr 1997
\issue 10
\pages 469--493
\endref

\ref\key{SSV3}
\by B.~Shapiro, M.~Shapiro, and A.~Vainshtein
\paper Skew-symmetric vanishing lattices and intersection of Schubert cells
\jour Intern. Math. Res. Notices
\yr 1998
\issue 11
\pages 563--588
\endref

\endRefs
\enddocument