Geometric Realization of a Poset and Projection Map is Continuous

Geometric Realization

Wait-Free Computability for General Tasks

Maurice Herlihy , ... Sergio Rajsbaum , in Distributed Computing Through Combinatorial Topology, 2014

11.4.3 Colors and covers

Fact 11.4.9

A set of vertices $\left\{v_0\text{,}\dots \text{,}{v}_q\right\}$ of a complex $\mathcal{K}$ forms a simplex if and only if the intersection of their open stars is non-empty:

${\displaystyle \bigcap _{i=0}^q}{\mathrm{St}}^{\circ }(v_i\text{,}\mathcal{K})\ne \varnothing \text{.}$

To construct a color-preserving simplicial map from ${\mathrm{Ch}}^N\mathcal{I}$ to $\mathrm{Div}\mathcal{I}$ , we will need the vertex colors to "align" nicely. More specifically, the open stars of the vertices in a $\mathrm{Div}\mathcal{I}$ form an open cover for $\mathcal{I}$ . This open-star cover has a natural coloring inherited from the coloring of $\mathcal{I}:\mathrm{name}({\mathrm{St}}^{\circ }(v\text{,}\mathcal{I}))=\mathrm{name}(v)$ . The open-star cover of $\mathrm{Div}\mathcal{I}$ is chromatic on ${\mathrm{Ch}}^N\mathcal{I}$ if every simplex of ${\mathrm{Ch}}^N\mathcal{I}$ is covered by open stars of vertices of a simplex in $\mathrm{Div}\mathcal{I}$ of matching color:

$\mathrm{for}\mathrm{all}\sigma \in {\mathrm{Ch}}^N\mathcal{I}\text{,}\sigma \subseteq {\displaystyle \bigcup _{t\in \tau }}{\mathrm{St}}^{\circ }(t\text{,}\mathrm{Div}\mathcal{I})\text{,}$

for some $\tau \in \mathrm{Div}\mathcal{I}$ where $\mathrm{names}(\sigma )\subseteq \mathrm{names}(\tau )$ .

We will show that without loss of generality, the geometric realization of $\mathrm{Div}\mathcal{I}$ can be chosen so that its open-star cover is chromatic on any iterated standard chromatic subdivision of $\mathcal{I}$ .

Lemma 11.4.10

The geometric realization of $\mathrm{Div}\mathcal{I}$ can be chosen so that its open-star cover is chromatic on each of the subdivisions

$\mathcal{I}\text{,}\mathrm{Ch}\mathcal{I}\text{,}{\mathrm{Ch}}^2\mathcal{I}\text{,}{\mathrm{Ch}}^3\mathcal{I}\text{,}\dots \text{.}$

Figure 11.12 shows how an open-star covering can fail to be chromatic. Simplices of $\mathrm{Div}\mathcal{I}$ are shown with dotted lines and square vertices, whereas simplices of ${\mathrm{Ch}}^n\mathcal{I}$ are shown with solid lines and round vertices. The gray vertex marked $v$ lies on the boundary between two gray open stars, so it is not covered by an open star of the same color.

Figure 11.12. How an open-star covering can fail to be chromatic. Simplices of $\text{Div}\mathcal{I}$ are shown with dotted lines and square vertices; simplices of ${\text{Ch}}^n\mathcal{I}$ are shown with solid lines and round vertices. The gray vertex marked $v$ lies on the boundary between two gray open stars, so this open-star covering fails to be chromatic.

Note, however, that if we perturb some of the square vertices by an arbitrarily small amount, then $v$ moves off the boundary and into the open star of a vertex of matching color. This observation suggests a strategy: We will pick an arbitrary geometric realization of $\mathrm{Div}\mathcal{I}$ , and if its open-star cover fails to be chromatic, then we will "perturb" vertex positions by very small amounts until the open-star cover becomes chromatic.

Readers willing to accept Lemma 11.4.10 can skip directly to Section 11.4.4.

We can recast some familiar concepts in terms of convex combinations. Every point $x$ in the polyhedron of a complex $\mathcal{I}$ can be expressed uniquely as the convex combination of the vertices of a simplex $\sigma$ of $\mathcal{I}$ . The open star ${\mathrm{St}}^{\circ }(v\text{,}\mathcal{I})$ is just the set of points that can be expressed as the convex combination of the vertices of a simplex that includes $v$ .

In this definition and in the subsequent lemmas, $\mathrm{Div}\mathcal{I}$ and ${\mathrm{Ch}}^n\mathcal{I}$ may be replaced by arbitrary chromatic subdivisions. Two simplices conflict if they share no colors.

Definition 11.4.11

A conflict point for $\mathrm{Div}\mathcal{I}$ and ${\mathrm{Ch}}^N\mathcal{I}$ is a point that can be expressed as the convex combination of vertices of two conflicting simplices, $\sigma =\left\{s_0\text{,}\dots \text{,}{s}_p\right\}\in \mathrm{Div}\mathcal{I}$ and $\tau =\left\{t_0\text{,}\dots \text{,}{t}_q\right\}\in {\mathrm{Ch}}^N\mathcal{I}$ , were $\mathrm{names}(\sigma )\cap \mathrm{names}(\tau )=\varnothing$ :

$x={\displaystyle \sum _{i=0}^p}{a}_i·t_i={\displaystyle \sum _{j=0}^q}{b}_j·t_j$

for $0<a_i\text{,}{b}_j$ and $1={\sum }_i{a}_i={\sum }_j{b}_j$ .

Lemma 11.4.12

The open-star cover of $\mathrm{Div}\mathcal{I}$ is chromatic for ${\mathrm{Ch}}^N\mathcal{I}$ if and only if there are no conflict points.

Proof

As noted, every point $x$ in $\mathcal{I}$ has a unique expression as the convex combination of the vertices of a $\sigma \in \mathrm{Div}\mathcal{I}$ , and similarly for a $\tau \in {\mathrm{Ch}}^N\mathcal{I}$ .

If $x$ is a conflict point, then it lies in the interior of $\tau$ but not in ${\mathrm{St}}^{\circ }(v\text{,}\mathrm{Div}\mathcal{I})$ for any vertex $v$ where $\mathrm{name}(v)\in \mathrm{names}(\tau )$ . The open stars of $\mathrm{Div}\mathcal{I}$ with colors from $\mathrm{names}(\tau )$ therefore fail to cover $\tau$ .

If the open-star cover is chromatic, then every $x$ lies in the open star of some vertex $v$ of $\mathrm{Div}\mathcal{I}$ and $u$ of ${\mathrm{Ch}}^N\mathcal{I}$ such that $\mathrm{name}(v)=\mathrm{name}(u)$ , implying that $x$ is not a conflict point. $\square$

Corollary 11.4.13 follows because the definition of conflict point is symmetric in terms of the two subdivisions.

Corollary 11.4.13

If the open-star cover of $\mathrm{Div}\mathcal{I}$ is chromatic on ${\mathrm{Ch}}^N\mathcal{I}$ , then the open-star cover of ${\mathrm{Ch}}^N\mathcal{I}$ is chromatic on $\mathrm{Div}\mathcal{I}$ .

We say that $\mathrm{Div}\mathcal{I}$ has an $∊$ -perturbation at vertex $v$ for some $∊>0$ if there is a point $v\prime \text{,}\mid v-v\prime \mid <∊$ , such that replacing $v$ with $v\prime$ in each simplex of $\mathrm{Div}\mathcal{I}$ yields a subdivision $\mathrm{Div}\prime \mathcal{I}$ isomorphic to $\mathrm{Div}\mathcal{I}$ . (This isomorphism means that both complexes are geometric realizations of the same abstract complex.) See Figure 11.13. For brevity, we write such a perturbation as:

Figure 11.13. An $∊$ -perturbation.

$(v\text{,}\mathrm{Div}\mathcal{I}){\mapsto }_{∊}(v\prime \text{,}\mathrm{Div}\prime \mathcal{I})\text{.}$

If $\mathrm{Div}\prime \mathcal{I}$ is the result of applying $∊$ -perturbations at multiple vertices, we write:

$\mathrm{Div}\mathcal{I}{\mapsto }_{∊}\mathrm{Div}\prime \mathcal{I}\text{.}$

We will see that there is always an $∊>0$ such that any vertex of a $\mathrm{Div}\mathcal{I}$ can be perturbed to any position within $∊$ within its carrier.

Lemma 11.4.14

If $v$ is a vertex in $\mathrm{Div}\mathcal{I}$ whose carrier is an $n$ -simplex $\sigma$ , then there is an $∊$ -perturbation

$(v\text{,}\mathrm{Div}\mathcal{I}){\mapsto }_{∊}(v\prime \text{,}\mathrm{Div}\prime \mathcal{I})$

for any $v\prime \in B(v\text{,}∊)$ .

Proof

We must check that any choice of $v\prime \in B(v\text{,}∊)$ yields a subdivision. We can pick $∊$ small enough that $v\prime$ lies in the open star of $v$ . We must check that $v\prime$ can be made affinely independent of each simplex $\upsilon =\left\{u_0\text{,}\dots \text{,}{u}_p\right\}$ in $\mathrm{Lk}(v\text{,}\mathrm{Div}\sigma )$ . Each such $\upsilon$ defines a hyperplane $\mathbb{H}(\upsilon )$ of dimension $p<n$ . Because each $\left\{v\right\}\cup \upsilon$ is a simplex of $\mathrm{Div}\sigma$ , $v\text{,}{u}_0\text{,}\dots \text{,}{u}_p$ are affinely independent, and hence $v$ is not in any $\mathbb{H}(\upsilon )$ . By Fact 11.4.4, there is an $∊>0$ so that for any $v\prime \in B(v\text{,}∊)$ , $v\prime \neg \in \mathbb{H}(\upsilon )$ , and thus is affinely independent of the vertices of $\upsilon$ . $\square$

Lemma 11.4.15

If $v$ is a vertex of $\mathrm{Div}\mathcal{I}$ whose carrier is an $n$ -simplex $\sigma$ , then there is a perturbation $(v\text{,}\mathrm{Div}\mathcal{I}){\mapsto }_{∊}(v\prime \text{,}\mathrm{Div}\prime \mathcal{I})$ such that $\mathrm{St}(v\prime \text{,}\mathrm{Div}\prime \mathcal{I})$ contains no conflict points with ${\mathrm{Ch}}^N\mathcal{I}$ .

Proof

Let $\mathbb{H}$ be the set of hyperplanes defined by all pairs of conflicting simplices, one from $\mathrm{Lk}(v\text{,}\mathrm{Div}\sigma )$ and one from ${\mathrm{Ch}}^N\sigma$ . By Fact 11.4.3, there is an $∊>0$ so that some point $v\prime$ within $∊$ of $v$ does not intersect any of these hyperplanes. By Lemma 11.4.14, this choice of $v\prime$ defines a perturbation $(v\text{,}\mathrm{Div}\mathcal{I}){\mapsto }_{∊}(v\prime \text{,}\mathrm{Div}\prime \mathcal{I})$ .

We claim that ${\mathrm{St}}^{\circ }(v\prime \text{,}\mathrm{Div}\prime \mathcal{I})$ and ${\mathrm{Ch}}^N\mathcal{I}$ have no conflict points. Otherwise, if $x$ is a conflict point, then there are conflicting simplices $\rho =\left\{r_0\text{,}\dots \text{,}{r}_p\right\}$ in $\mathrm{Lk}(v\text{,}\mathrm{Div}\sigma )$ and $\tau =\left\{t_0\text{,}\dots \text{,}{t}_q\right\}$ in ${\mathrm{Ch}}^N\sigma$ such that

$x=({\displaystyle \sum _{i=0}^p}{a}_i·r_i)+a_{p+1}·v={\displaystyle \sum _{j=0}^q}{b}_j{t}_j$

where $1={\sum }_i{a}_i={\sum }_j{b}_j$ , and $0<a_i\text{,}{b}_j$ . And yet, this equation implies that $x$ lies on the hyperplane defined by the vertices of $\rho \cup \tau$ , which contradicts the choice of $v\prime$ . $\square$

Lemma 11.4.16

If $v$ is a vertex of $\mathrm{Div}\sigma$ whose carrier is an $n$ -simplex $\sigma$ , then there is a perturbation $(v\text{,}\mathrm{Div}\mathcal{I}){\mapsto }_{∊}(v^{\ast }\text{,}{\mathrm{Div}}^{\ast }\mathcal{I})$ such that ${\mathrm{St}}^{\circ }(v^{\ast }\text{,}{\mathrm{Div}}^{\ast }\mathcal{I})$ has no conflict points with any of the subdivisions

$\sigma \text{,}\mathrm{Ch}\sigma \text{,}{\mathrm{Ch}}^2\sigma \text{,}{\mathrm{Ch}}^3\sigma \text{,}\dots \text{.}$

Proof

By Lemma 11.4.14, there is a $∊>0$ such that $(v\text{,}\mathrm{Div}\mathcal{I}){\mapsto }_{∊}(v\prime \text{,}\mathrm{Div}\prime \mathcal{I})$ is a perturbation for any $v\prime \in B(v\text{,}∊)$ .

We inductively construct a sequence of subdivisions

$(v^{(i-1)}\text{,}{\mathrm{Div}}^{(i-1)}\sigma ){\mapsto }_{{∊}_i}(v^{(i)}\text{,}{\mathrm{Div}}^{(i)}\sigma )$

such that ${\mathrm{St}}^{\circ }(v^{(i)}\text{,}{\mathrm{Div}}^{(i)}\sigma )$ has no conflict points with ${\mathrm{Ch}}^i\sigma$ .

For the base case, the open-star cover of ${\mathrm{Ch}}^0\sigma =\sigma$ is already a chromatic cover for $\mathrm{Div}\sigma$ , so let $v^{(0)}=v$ and ${\mathrm{Div}}^{(0)}\sigma =\sigma$ .

For the induction step, Lemma 11.4.15 states that there is a perturbation

$(v^{(i-1)}\text{,}{\mathrm{Div}}^{(i-1)}\sigma ){\mapsto }_{{∊}_i}(v^{(i)}\text{,}{\mathrm{Div}}^{(i)}\sigma )$

such that ${\mathrm{St}}^{\circ }(v^{(i)}\text{,}{\mathrm{Div}}^{(i)}\sigma )$ has no conflict points with ${\mathrm{Ch}}^i\sigma$ .

If we pick each

${∊}_i\le \frac{∊}{2^i}\text{,}$

then $v^{(0)}\text{,}{v}^{(1)}\text{,}\dots$ is a Cauchy sequence that converges to $v^{\ast }$ , where

$\begin{array}{cc}\hfill \mid v-v^{\ast }\mid \le & \mid v^{(0)}-v^{(1)}\mid +\mid v^{(1)}-v^{(2)}\mid +\cdots \hfill \\ \hfill \le & \frac{∊}{2}+\frac{∊}{4}+\cdots \hfill \\ \hfill \le & ∊\text{.}\hfill \end{array}$

As a result, we have constructed a perturbation

$(v\text{,}\mathrm{Div}\sigma ){\mapsto }_{∊}(v^{\ast }\text{,}{\mathrm{Div}}^{\ast }\sigma )$

where ${\mathrm{St}}^{\circ }(v^{\ast }\text{,}{\mathrm{Div}}^{\ast }\sigma )$ and ${\mathrm{Ch}}^i\sigma$ have no conflict points for all $i\ge 0$ . $\square$

Lemma 11.4.17

Every chromatic subdivision $\mathrm{Div}\mathcal{I}$ has a perturbation

$\mathrm{Div}\mathcal{I}{\mapsto }_{∊}{\mathrm{Div}}^{\ast }\mathcal{I}$

such that ${\mathrm{Div}}^{\ast }\mathcal{I}$ has no conflict points with any of the subdivisions

$\mathcal{I}\text{,}\mathrm{Ch}\mathcal{I}\text{,}{\mathrm{Ch}}^2\mathcal{I}\text{,}{\mathrm{Ch}}^3\mathcal{I}\text{,}\dots \text{.}$

Proof

By induction on $n$ . In the base case, when $n=0$ , the claim is trivial because both complexes are discrete sets of vertices.

Inductively assume that the open-star cover of $\mathrm{Div}{\mathrm{skel}}^{n-1}\mathcal{I}$ is chromatic for each of

${\mathrm{skel}}^{n-1}\mathcal{I}\text{,}\mathrm{Ch}{\mathrm{skel}}^{n-1}\mathcal{I}\text{,}{\mathrm{Ch}}^2{\mathrm{skel}}^{n-1}\mathcal{I}\text{,}{\mathrm{Ch}}^3{\mathrm{skel}}^{n-1}\mathcal{I}\text{,}\dots \text{.}$

For each vertex $v$ in $\mathrm{Div}\mathcal{I}$ whose carrier has dimension $n$ , Lemma 11.4.16 states that we can construct a perturbation that eliminates all conflict points from its open star. Successively applying this construction to each such vertex yields a perturbation

$\mathrm{Div}\mathcal{I}{\mapsto }_{∊}{\mathrm{Div}}^{\ast }\mathcal{I}$

that has no conflict points with any iterated standard chromatic subdivision ${\mathrm{Ch}}^i\mathcal{I}$ . $\square$

Because $\mathrm{Div}\mathcal{I}$ and its perturbation ${\mathrm{Div}}^{\ast }\mathcal{I}$ are just different geometric realizations of the same abstract complex, we have completed the proof of Lemma 11.4.10.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124045781000115

Finite-Dimensional Algebras and Quivers

A. Savage , in Encyclopedia of Mathematical Physics, 2006

Nakajima's Quiver Varieties

We introduce here a description of the quiver varieties first presented by Nakajima. They yield a geometric realization of the irreducible highest-weight representations of simply-laced Kac–Moody algebras. The construction was motivated by the work of Kronheimer and Nakajima on solutions to the anti-self-dual Yang–Mills equations on ALE gravitational instantons ( see Instantons: Topological Aspects).

Definition 3

For $\mathit{\upsilon },\mathit{w}\in {\mathbb{Z}}_{\ge 0}^I$ , choose I-graded vector spaces V and W of graded dimensions v and w , respectively. Then define

$\text{Λ}\equiv \text{Λ}(\mathit{\upsilon },\mathit{w})={\text{Λ}}_V\times {\displaystyle \underset{i\in I}{\oplus }}\text{Hom}({\mathit{V}}_i,{\mathit{W}}_i)$

Definition 4

Let ${\text{Λ}}^{\text{<mi mathvariant="italic" is="true">st</mi>}}=\text{Λ}{\left(\mathit{\upsilon },\mathit{w}\right)}^{\text{<mi mathvariant="italic" is="true">st</mi>}}$ be the set of all (x, t) ∈ Λ( υ , w ) satisfying the following condition: if S = ( S _i ) with S _i ⊂ V _i is x-stable and t _i ( S _i = 0 for i ∈ I, then S _i = 0 for i ∈ I.

The group G _V acts on Λ( υ , w ) via

$(g,(x,t))\mapsto ((g_{h(\rho )}{x}_{\rho }{g}_{t(\rho )}^{-1}),(t_i{g}_i^{-1}))$

and the stabilizer of any point of Λ( υ , w )^st in G _V is trivial. We then make the following definition.

Definition 5

Let $\mathcal{L}\equiv \mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)=\text{Λ}{\left(\mathit{\upsilon },\mathit{w}\right)}^{\text{<mi mathvariant="italic" is="true">st</mi>}}/G_{\mathit{V}}$ .

We should note that while the above definition and other constructions in this article are algebraic, there are also more geometric ways of looking at quiver varieties. In particular, the space

$\mathit{M}(\mathit{\upsilon },\mathit{w})=(\underset{\rho \in Q_1}{\oplus }\text{Hom}({\mathit{V}}_{t(\rho )},{\mathit{V}}_{h(\rho )}))\oplus \left(\underset{i\in I}{\oplus }\text{Hom}({\mathit{W}}_i,{\mathit{V}}_i)\oplus \text{Hom}({\mathit{V}}_i,{\mathit{W}}_i)\right)$

has a natural hyper-Kähler metric and one can consider a hyper-Kähler quotient by the group ∏ U( V _i ). The variety $\mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)$ is a Lagrangian subvariety of (and is homotopic to) this hyper-Kähler quotient. In the case $\mathfrak{g}={\mathfrak{sl}}_n$ , the varieties involved are closely related to flag varieties.

Let $\mathit{w},\mathit{\upsilon },\mathit{\upsilon }\prime ,\mathit{\upsilon }″\in {\mathbb{Z}}_{\ge 0}^I$ be such that $\mathit{\upsilon }=\mathit{\upsilon }\prime +\mathit{\upsilon }″$ . Consider the maps

[2] $\text{Λ}(\mathit{\upsilon }″,0)\times \text{Λ}(\mathit{\upsilon }\prime ,\mathit{w})\stackrel{p_1}{\leftarrow }\tilde{\mathit{F}}(\mathit{\upsilon },\mathit{w};\mathit{\upsilon }″)\stackrel{p_2}{\to }\mathit{F}(\mathit{\upsilon },\mathit{w};\mathit{\upsilon }″)\stackrel{p_3}{\to }\text{Λ}(\mathit{\upsilon },\mathit{w})$

where the notation is as follows. A point of F ( υ , w ; υ ″) is a point (x, t) ∈ Λ( υ , w ) together with an I-graded, x-stable subspace S of V such that dim S = υ ′ = υ − υ ″. A point of $\tilde{\mathit{F}}(\mathit{\upsilon },\mathit{w};\mathit{\upsilon }″)$ is a point (x, t, S ) of F ( υ , w ; υ ″) together with a collection of isomorphisms $R_i^{\prime }:{\mathit{V}}_i^{\prime }\cong {\mathit{S}}_i$ and $R_i^{″}:{\mathit{V}}_i^{″}\cong {\mathit{V}}_i/{\mathit{S}}_i$ for each i ∈ I. Then we define $p_2(x,t,\mathit{S},R\prime ,R″)=(x,t,\mathit{S}),p_3(x,t,\mathit{S})=(x,t)$ and $p_1(x,t,\mathit{S},R\prime ,R″)=(x″,x\prime ,t\prime )$ where x″, x′, t′ are determined by

$\begin{array}{l}{R}_{h(\rho )}^{\prime }{x}_{\rho }^{\prime }=x_{\rho }{R}_{t(\rho )}^{\prime }:{\mathit{V}}_{t(\rho )}^{\prime }\to {\mathit{S}}_{h(\rho )}\hfill \\ t_i^{\prime }=t_i{R}_i^{\prime }:{\mathit{V}}_i^{\prime }\to {\mathit{W}}_i\hfill \\ R_{h(\rho )}^{″}{x}_{\rho }^{″}=x_{\rho }{R}_{t(\rho )}^{″}:{\mathit{V}}_{t(\rho )}^{″}\to {\mathit{V}}_{h(\rho )}/{\mathit{S}}_{h(\rho )}\hfill \end{array}$

It follows that x′ and x″ are nilpotent.

Lemma 1

One has

${(p_3\circ p_2)}^{-1}(\text{Λ}{(\mathit{\upsilon },\mathit{w})}^{\text{<mi mathvariant="italic" is="true">st</mi>}})\subset p_1^{-1}(\text{Λ}(\mathit{\upsilon }″,0)\times \text{Λ}{(\mathit{\upsilon }\prime ,\mathit{w})}^{\text{<mi mathvariant="italic" is="true">st</mi>}})$

Thus, we can restrict [2] to Λ^st, forget the Λ( υ ″, 0 )-factor and consider the quotient by G _V and G _V ′. This yields the diagram

[3] $\mathcal{L}(\mathit{\upsilon }\prime ,\mathit{w})\stackrel{{\pi }_1}{\leftarrow }\mathcal{F}(\mathit{\upsilon },\mathit{w};\mathit{\upsilon }-\mathit{\upsilon }\prime )\stackrel{{\pi }_2}{\to }\mathcal{L}(\mathit{\upsilon },\mathit{w})$

where

$\mathcal{F}(\mathit{\upsilon },\mathit{w},\mathit{\upsilon }-\mathit{\upsilon }\prime )\underset{=}{\text{def}}\left\{(x,t,\mathit{S})\in \mathit{F}(\mathit{\upsilon },\mathit{w};\mathit{\upsilon }-\mathit{\upsilon }\prime )|(x,t)\in \text{Λ}{(\mathit{\upsilon },\mathit{w})}^{\text{st}}\right\}/G_V$

Let $M\left(\mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)\right)$ be the vector space of all constructible functions on $\mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)$ . Then define maps

$\begin{array}{l}{h}_i:M(\mathcal{L}(\mathit{\upsilon },\mathit{w}))\to M(\mathcal{L}(\mathit{\upsilon },\mathit{w}))\hfill \\ e_i:M(\mathcal{L}(\mathit{\upsilon },\mathit{w}))\to M(\mathcal{L}(\mathit{\upsilon }-{\mathit{e}}^i,\mathit{w}))\hfill \\ f_i:M(\mathcal{L}(\mathit{\upsilon }-{\mathit{e}}^i,\mathit{w}))\to M(\mathcal{L}(\mathit{\upsilon },\mathit{w}))\hfill \end{array}$

by

$\begin{array}{l}{h}_{i}f=u_{i}f\hfill \\ e_{i}f={({\pi }_1)}_{!}({\pi }_2^{*}f)\hfill \\ f_{i}g={({\pi }_2)}_{!}({\pi }_1^{*}g)\hfill \end{array}$

Here

$\mathit{u}={}^t(u_0,\dots ,u_n)=\mathit{w}-C\mathit{\upsilon }$

where C is the Cartan matrix of $\mathfrak{g}$ and we are using diagram 3 with υ ′ = υ − e ⁱ where e ⁱ is the vector whose components are given by ${\mathit{e}}_j^i={\delta }_{\text{<mi mathvariant="italic" is="true">ij</mi>}}$ .

Now let ϕ be the constant function on $\mathcal{L}\left(\mathbf{0},\mathit{w}\right)$ with value 1. Let L( w ) be the vector space of functions generated by acting on ϕ with all possible combinations of the operators f _i . Then let $L\left(\mathit{\upsilon },\mathit{w}\right)=M\left(\mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)\right)\cap L\left(\mathit{w}\right)$ .

Proposition 3

The operators e _i , f _i , h _i on L( w ) provide it with the structure of the irreducible highest-weight integrable representation of $\mathfrak{g}$ with highest weight ${\sum }_{i\in Q_0}{\mathit{w}}_i{\omega }_i$ . Each summand of the decomposition $L(\mathit{w})={\oplus }_{\mathit{\upsilon }}L(\mathit{\upsilon },\mathit{w})$ is a weight space with weight ${\sum }_{i\in Q_0}{\mathit{w}}_i{\omega }_i-{\mathit{\upsilon }}_i{\alpha }_i$ . Here the ω _i and α _i are the fundamental weights and simple roots of $\mathfrak{g}$ , respectively.

Let $Z\in \text{Irr}\mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)$ and define a linear map $T_Z:L\left(\mathit{\upsilon },\mathit{w}\right)\to \mathbb{C}$ that associates to a constructible function f ∈ L( υ , w ) the (constant) value of f on a suitable open dense subset of Z. The fact that L( υ , w ) is finite dimensional allows us to take such an open set on which any f ∈ L( υ , w ) is constant. So we have a linear map

$\Phi :L(\mathit{\upsilon },\mathit{w})\to {ℂ}^{\text{Irr}\mathcal{L}(\mathit{\upsilon },\mathit{w})}$

Then we have the following proposition.

Proposition 4

The map Φ is an isomorphism; for any $Z\in \text{Irr}\mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)$ , there is a unique function g _Z ∈ L( υ , w ) such that for some open dense subset O of Z we have g _Z | _O = 1 and for some closed G _V -invariant subset $K\subset \mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)$ of dimension $<\text{dim}\mathcal{L}\left(\mathit{\upsilon },\mathit{w}\right)$ we have g _Z = 0 outside Z ∪ K. The functions g _Z for Z ∈ Irr Λ( υ , w ) form a basis of L( υ , w ).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B0125126662004181

Topology

Reinhard Klette , Azriel Rosenfeld , in Digital Geometry, 2004

6.2.4 The number of digital topologies

There is only one digital topology for n = 1: the alternating topology on $Z$ .

Theorem 6.4

Let S be a subset of $Z^2$ that contains a translate of the set G ₀ shown in Figure 6.9. Then there is no topology on S in which connectivity is the same as 8-connectivity.

FIGURE 6.9. The set G ₀ used in Theorem 6.4.

Let $\left[Z^2,G\right]$ be a digital topology, and let U(p) be the intersection of all of the open sets of G that contain p. Then, for all p ∈ $Z^2$ , we must have U (p) ⊆ N ₈(p). If not, the 8-disconnected set $Z^2$ /A₈ (p) would be connected in $\left[Z^2,G\right]$ , because any open set containing p would also contain a point in $Z^2$ /N ₈(p).

This result limits the possible topologic neighborhoods U(p) that can be used to define a basis for a digital topology:

Theorem 6.5

Up to homeomorphism (see Definition 6.8), there are only two digital topologies on $Z^2$ .

It follows that the 2D grid point and grid cell topologies are the only two possible 2D digital topologies.

Theorem 6.6

Up to homeomorphism, there are only five digital topologies on $Z^3$ .

In addition to the 3D grid point and grid cell topologies, we also have the product of two one-dimensional grid cell topologies and one one-dimensional grid point topology; a topology $\left[Z^2,G\right]$ in which alternate grid planes have the grid point and grid cell topologies; and a topology with open sets that are the closed sets of $\left[Z^2,G\right]$ .

Theorem 6.7

Up to homeomorphism, there are only 24 digital topologies on $Z^4$ .

The grid point and grid cell topologies exist on $Z^n$ for all n; they are the "most regular" digital topologies.

Geometric realizations such as those shown in Figures 2.13 and 2.14 are models for the 2D and 3D grid cell topologies; these models can be generalized to n dimensions. ³ The grid point topology can also be geometrically represented by a tessellation of the Euclidean plane or space into convex polygons or polyhedra. For example, in Figure 6.10, the squares represent odd grid points (2-cells), and the trapezoids represent even grid points (1-cells); there are no 0-cells in this digital topology.

FIGURE 6.10. Left: geometric representation of the smallest neighborhoods of even grid points. Right: the closed set of Figure 6.4, which is now shown as a union of convex polygons.

The algorithms described in Section 5.4.1 can be used to assign 1-cells to their adjacent 2-cells that have the largest pixel values.

The values of topologic properties of a set M of pixels or voxels depend in general on which digital topology is being used. These values remain the same if the topologic spaces are homeomorphic (see Definition 6.8) and M is interpreted in the same way (e.g., as an open set).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9781558608610500080

Elements of Combinatorial Topology

Maurice Herlihy , ... Sergio Rajsbaum , in Distributed Computing Through Combinatorial Topology, 2014

3.2.3 The topological view

Finally, we proceed to the topological framework. Given a geometric simplicial complex $\mathcal{K}$ in ${\mathbb{R}}^d$ , we let $\mid \mathcal{K}\mid$ denote the union of its simplices, called its polyhedron. This space has the usual topology as the subspace of ${\mathbb{R}}^d$ . Somewhat confusingly, the space $\mid \mathcal{K}\mid$ is called the geometric realization of $\mathcal{K}$ . If $\mathcal{A}$ is an abstract simplicial complex, we can first construct $\mathcal{K}$ , such that $\mathcal{C}(\mathcal{K})=\mathcal{A}$ , and then let $\mid \mathcal{A}\mid =\mid \mathcal{K}\mid$ . This construction does not depend on the choice of $\mathcal{K}$ , only the choice of $\mathcal{A}$ . One can also construct $\mid \mathcal{A}\mid$ by starting with a set of disjoint simplices, then gluing them together along their boundaries using the combinatorial data as the gluing schema.

Let us now look at the maps between the objects we just described. Let $\mathcal{A}$ and $\mathcal{B}$ be abstract simplicial complexes. Recall that a vertex map $\mu :V(\mathcal{A})\to V(\mathcal{B})$ maps each vertex of $\mathcal{A}$ to a vertex of $\mathcal{B}$ and that $\mu$ is a simplicial map if it also carries simplices to simplices. A vertex map $\mu :V(\mathcal{A})\to V(\mathcal{B})$ need not induce a continuous map between the geometric realizations $\mid \mathcal{A}\mid$ and $\mid \mathcal{B}\mid$ . For example, if both $\mathcal{A}$ and $\mathcal{B}$ have the vertex set $\left\{0\text{,}1\right\}$ , and the edge $\left\{0\text{,}1\right\}$ is a simplex of $\mathcal{A}$ but not of $\mathcal{B}$ , then the identity map $\mathrm{id}:\left\{1\text{,}2\right\}\to \left\{1\text{,}2\right\}$ is a vertex map, but there is no continuous map from an edge to its endpoints that is the identity on the endpoints. However, any simplicial map $\mu$ induces a continuous map $\mid \mu \mid$ between geometric realizations. For each $n$ -simplex $\sigma =\left\{s_0\text{,}\dots \text{,}{s}_n\right\}$ in $\mathcal{A}\text{,}\mid \mu \mid$ is defined on points of $\mid \sigma \mid$ by extending barycentric coordinates:

(3.2.2) $\mid \mu \mid \left({\displaystyle \sum _{i=0}^n}{t}_i{s}_i\right)={\displaystyle \sum _{i=0}^n}{t}_i\mu (s_i)\text{.}$

Before proceeding with constructions, we would like to mention that in standard use in algebraic topology the word simplex is overloaded. It is used to denote the abstract simplicial complex consisting of all subsets of a certain finite set, but it is also used to refer to individual elements of the family of sets constituting and abstract simplicial complex. There is a relation here: With a simplex in the second sense one can associate a subcomplex of the considered abstract simplicial complex, which is a simplex in the first sense. We will use simplex in both of these meanings. In some texts, simplex is also used to denote the geometric realization of that abstract simplicial complex; here we say geometric simplex instead.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124045781000036

Inferring Interactions in Molecular Networks via Primary Decompositions of Monomial Ideals

Matthew Macauley , Brandilyn Stigler , in Algebraic and Combinatorial Computational Biology, 2019

6.2.2 Square-Free Monomial Ideals

A special type of monomial ideal that arises in a number of applications are those that are square-free. These are defined exactly as their name suggests: the monomial x ^α is square-free if each α _i ∈{0, 1}, and a monomial ideal I is square-free if can be generated by square-free monomials. These are also called Stanley-Reisner ideals. Clearly, the exponent vector α = (α ₁, …, α _n ) canonically determines a subset of [n] = {1, …, n}; namely, the coordinates i whose entry α _i is nonzero. Though it is a slight abuse of notation, we will often speak of α as a subset of [n] rather than a vector for convenience.

Remark 6.2

For many of our examples, we will work in the ring $\mathbb{F}[x,y,z]$ instead of $\mathbb{F}[x_1,x_2,x_3]$ ; the variables x, y, z are canonically identified with x ₁, x ₂, x ₃. In this setting, it is more convenient to write subsets as strings instead of vectors. For example, xz is short for {x, z}—we can express both the subset and the monomial with α = xz. This has the added advantage that we no longer need to distinguish between subsets, exponent vectors, and monomials.

For example, in $\mathbb{F}[x_1,x_2,x_3]$ , we would write a monomial as x ^α = x ^{(1, 0, 1)} = x ₁ x ₃, where $\alpha =\{1,3\}\subseteq [3]$ is a subset, or α = (1, 0, 1) is an exponent vector. In $\mathbb{F}[x,y,z]$ , we just write α = xz for both the subset and the monomial, which leaves the exponent vector unnecessary. Though this is a slight abuse of notation, it works well and greatly simplifies things. It should always be clear from the context what α represents.

To summarize, every square-free monomial ideal is minimally generated by a unique collection of monomials, each of which is described by a subset $\alpha \subseteq [n]$ . In other words, every square-free monomial ideal can be uniquely described by a canonical collection of subsets of [n]. Moreover, this collection of subsets is not arbitrary; it has the following key properties, which we will return to soon.

Proposition 6.2

Let I be a square-free monomial of $\mathbb{F}[x_1\dots ,x_n]$ , and $\alpha ,\beta \subseteq [n]$ . Then

$\begin{array}{ll}\hfill & x^{\alpha }\in I\text{and}{x}^{\beta }\in I⟹x^{\alpha \cup \beta }\in I,\hfill \\ \hfill & x^{\alpha }\notin I\text{and}{x}^{\beta }\notin I⟹x^{\alpha \cap \beta }\notin I.\hfill \end{array}$

Exercise 6.5

Prove Proposition 6.2.

As a direct consequence of Proposition 6.2, every square-free monomial ideal can be expressed uniquely using a very simple combinatorial diagram called a simplicial complex. One can think of a simplicial complex as a structure built with triangular "faces" in various dimensions, which we call its geometric realization . A k-dimensional face is called a k-face, but for small k, these have more familiar names:

•

A 0-dimensional face is a vertex, or node.

•

A 1-dimensional face is an edge.

•

A 2-dimensional face is a triangle.

•

A 3-dimensional face is a (solid) triangular pyramid.

If a simplicial complex has a two-face (a triangle), then it must have the three edges and three vertices contained in that triangle. Formally, a k-face is just any size-(k + 1) subset, and simplicies must be closed under taking subsets. This is the only restriction; the formal definition is following.

Definition 6.5

An abstract simplicial complex over a finite set X is a collection Δ of subsets of X that are closed under the operation of taking subsets. That is, if β ∈ Δ and $\alpha \subset \beta$ , then α ∈ Δ. The elements in Δ are called simplices or faces.

Most simplicial complexes in this chapter will be over [n] or over a set of letters (e.g., {a, b, c, d, e}). Recall that we usually prefer to write subsets as strings, for example,

$\begin{array}{ll}\hfill \{\varnothing ,a,b,c,d,ab,ac,bc,abc\}\text{instead of}& \left\{\varnothing ,\{a\},\{b\},\{c\},\{d\},\{a,b\},\{a,c\},\right.\hfill \\ \hfill & \left.\{b,c\},\{a,b,c\}\right\}.\hfill \end{array}$

Clearly, in this context, the order of the letters in a string does not matter, so abc = acb = ⋯ = cba.

We will now go over two examples: one on six variables that is large enough to see some intricacies, and a three-variable example that is small enough that we can visualize key features on the three-variable Boolean lattice.

Running Example 6.1

Consider the simplicial complex Δ on X = {a, b, c, d, e, f} shown below in two ways: as a collection of strings (subsets) at left, and its geometric realization at right.

The triangle cde is shaded to indicate that cde ∈ Δ, whereas the unshaded triangle def means that def∉Δ.

For reasons that will become clear soon, we will often be interested in the nonfaces of a simplicial complex. These are the subsets that are not in Δ. Clearly, if Δ is a simplicial complex over X, then the collection 2 ^X of all subsets of X is the disjoint union 2 ^X = Δ ⊔ Δ ^c , where Δ ^c := 2 ^X ∖ Δ is the set complement of Δ. Thus, every subset of X is either a face or a nonface. The following easy observation is crucial.

Remark 6.3

Let Δ be a simplicial complex.

(i)

Faces of Δ are closed under intersection: $\alpha ,\beta \in \Delta \Rightarrow \alpha \cap \beta \in \Delta$ .

(ii)

Nonfaces of Δ are closed under unions: $\alpha ,\beta \in {\Delta }^c\Rightarrow \alpha \cup \beta \in {\Delta }^c$ .

Due to Remark 6.3, we do not need to specify all of the faces (or nonfaces) of Δ to completely determine it. It should be clear that every simplicial complex is uniquely defined by its maximal faces, also called facets. Formally, we say that a face $\alpha \subseteq [n]$ of Δ is maximal if there is no $\beta ⫌\alpha$ in Δ. In terms of the geometric realization, the facets of a simplicial complex are what one would use if building them from physical materials.

Just as Δ is determined by its maximal faces, Δ ^c is determined by its minimal nonfaces. Formally, a nonface $\alpha \subseteq [n]$ of Δ ^c is minimal if there is no $\beta ⫋\alpha$ in Δ ^c . The following three-node example should help illustrate these concepts.

Running Example 6.2

Consider the following simplicial complex Δ over X = {x, y, z}, where the geometric realization is shown on the right.

Since this example is small enough, it can be nicely visualized on the 3D Boolean lattice, as shown in Fig. 6.2. On the left is the full lattice with the faces in Δ circled, and the maximal faces shaded. In the middle diagram, the nonfaces are boxed with the minimal nonfaces shaded. The edges connecting the faces with nonfaces are dotted to emphasize the partition of the vertices into Δ ⊔ Δ ^c .

Fig. 6.2. The partition of the Boolean lattice on X = {x, y, z} into the simplicial complex Δ = {∅, x, y, z, xz} (a down-set) and its complement Δ ^c = {xy, yz, xyz} (an up-set). At right are the complements of the faces of Δ.

We added arrows in Fig. 6.2 to emphasize how the faces are precisely those vertices that lie on a downward path from the maximal faces, y and xz. Similarly, the nonfaces are precisely those that lie on an upward path from the minimal nonfaces, xy and yz, and this is shown in the middle diagram of Fig. 6.2. Formally, we say that the faces form a down-set of the Boolean lattice 2 ^X generated by {xz, y}, and the nonfaces form an up-set generated by {xy, yz}.

The diagram on the right of Fig. 6.2 shows the complements $\overline{\alpha }:=[n]\setminus \alpha$ of the faces α ∈ Δ. Soon, we will return to this diagram when we learn how to encode this information into an ideal of $\mathbb{F}[x,y,z]$ . Note that we are using different notations to help distinguish between the two different set-complements that arise in this chapter: we write the complement of a face α ∈ Δ as $\overline{\alpha }:=[n]\setminus \alpha$ , and the complement of a simplicial complex $\Delta \subseteq 2^X$ as Δ ^c := 2 ^X ∖ Δ.

We will now return to our first running example and find the maximal faces and minimal nonfaces. The same structure of the Boolean lattice 2 ^X being partitioned into an up-set and a down-set holds, but it is too large to easily draw, as it would contain 64 vertices.

Running Example 6.1 continued

Let Δ = {∅, a, b, c, d, e, f, bc, cd, ce, de, cde, df, ef}. There are 2⁶ = 64 subsets of a six-element set, and Δ has 14 faces. Hence, there are 50 nonfaces in Δ ^c . The maximal faces (facets) and minimal nonfaces are listed below.

•

Maximal faces: a, bc, cde, df, ef.

•

Minimal nonfaces: ab, ac, ad, ae, af, bd, be, bf, cf, def.

Note that by construction, every proper subset of a minimal nonface is in Δ, and every proper superset of a maximal face is in Δ ^c .

Now, let us turn back to square-free monomial ideals. Recall that every monomial ideal in $R=\mathbb{F}[x_1,\dots ,x_n]$ is uniquely determined by the (monic) monomials x ^α it contains, and so every square-free monomial ideal I is uniquely determined by a collection of subsets of [n].

Remark 6.4

Let I be a square-free monomial ideal, which is completely determined by the subsets α for which x ^α ∈ I.

•

If $\alpha \subseteq \beta$ and x ^α ∈ I, then x ^β ∈ I.

•

If $\alpha \subseteq \beta$ and x ^β ∉I, then x ^α ∉I.

In other words,

(i)

As subsets, exponents of square-free monomials in I are closed under unions.

(ii)

As subsets, exponents of square-free monomials not in I are closed under intersections.

By Remarks 6.3 and 6.4, we can describe a square-free monomial ideal I combinatorially as a collection of subsets that is closed under intersections. These subsets have two interpretations, one algebraic and one combinatorial.

•

algebraically: the monomials x ^α not in I; and

•

combinatorially: the faces α of a simplicial complex, that we will denote by ${\Delta }_{I^c}$ .

To summarize, every square-free monomial ideal I canonically defines a simplicial complex ${\Delta }_{I^c}$ , where the (monic) monomials in I correspond to the nonfaces of ${\Delta }_{I^c}$ , that is, the elements of ${\Delta }_{I^c}^c$ . Or equivalently, the faces of ${\Delta }_{I^c}$ correspond to the (monic) monomials not in I. This correspondence is bijective, as every simplicial complex Δ canonically defines a square-free monomial ideal. The formal definition is below.

Definition 6.6

Given an ideal I, define the simplicial complex ${\Delta }_{I^c}$ as

$\begin{array}{l}\hfill {\Delta }_{I^c}=\left\{\alpha \mid x^{\alpha }\notin I\right\}.\end{array}$

Given a simplicial complex Δ on [n], define a square-free monomial ideal $I_{{\Delta }^c}$ as

$\begin{array}{l}\hfill I_{{\Delta }^c}=〈x^{\alpha }\mid \alpha \notin \Delta 〉.\end{array}$

This is called the Stanley-Reisner ideal of Δ. The following theorem highlights the interplay between the combinatorial and algebraic structure of these objects. See [7, Section 1.1] for more details, including proofs.

Theorem 6.1

The correspondence $I\mapsto {\Delta }_{I^c}$ and $\Delta \mapsto I_{{\Delta }^c}$ is a bijection between:

(i)

simplicial complexes on [n] = {1, …, n}, and

(ii)

square-free monomial ideals in $\mathbb{F}[x_1,\dots ,x_n]$ .

Remark 6.5

Our notation in Definition 6.6 is nonstandard. Usually, the correspondence is denoted I↦Δ _I and Δ↦I _Δ . We choose to retain the small c to remind the reader that one must take the complement; this is sometimes called Alexander duality. The authors remember first-hand how confusing this can be initially! However, one can read right off of our notation that:

•

$I_{{\Delta }^c}$ is the ideal generated by the monomials not in Δ.

•

${\Delta }_{I^c}$ is the simplicial complex whose faces are the monomials not in I.

At this point, we will return to our first running example.

Running Example 6.1 continued

Consider the simplicial complex Δ on X = {a, b, c, d, e, f } shown below in two ways: as a collection of strings (subsets) at left, and its geometric realization at right.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128140666000064

wallsenisho.blogspot.com

Source: https://www.sciencedirect.com/topics/computer-science/geometric-realization

Share this post