la combinatoria de los complejos cúbicos de tipo …math.sfsu.edu/federico/talks/bucaramanga.pdfla...

definiciones ejemplos caracterizaciones aplicaciones

La combinatoria de loscomplejos cúbicos de tipo CAT(0)

Federico Ardila M.

San Francisco State University, San Francisco, California.Universidad de Los Andes, Bogotá, Colombia.

Congreso Colombiano de MatemáticasBucaramanga, 15 de julio de 2011


Complejos cúbicos CAT(0).

Trabajo conjunto con:Megan Owen (UC Berkeley), Seth Sullivant (NCSU)Tia Baker (SFSU) Diego Cifuentes (Los Andes) Rika Yatchak (SFSU)

8 R. GHRIST & V. PETERSON

FIGURE 4. A positive articulated robot arm example [left] with fixedendpoint. One generator [center] flips corners and has as its tracethe central four edges. The other generator [right] rotates the end ofthe arm, and has trace equal to the two activated edges.

FIGURE 5. The state complex of a 5-link positive arm has one cell ofdimension three, along with several cells of lower dimension.

systems is a discrete type of configuration space for these systems. Such spaceswere considered independently by Abrams [1] and also by Swiatkowski [38].

For example, if the graph is K5 (the complete graph on five vertices), N = 2, andA = {0, 1, 2}, it is straightforward to show that each vertex has a neighborhoodwith six edges incident and six 2-cells patched cyclically about the vertex. There-fore, S is a closed surface. One can (as in [2]) count that there are 20 vertices, 60edges, and 30 faces in the state complex. The Euler characteristic of this surface istherefore !10. This surface can be given an orientation; thus, the state complex hasgenus six.

Example 3.4 (digital microfluidics). An even better physical instantiation of the pre-vious system arises in digital microfluidics [17, 18]. In this setting, small (e.g., 1mmdiameter) droplets of fluid can be quickly and accurately manipulated on a platecovering a network of current-controlled wires by an electrowetting process thatexploits surface tension effects to propel a droplet. Applying a current drives thedroplet a discrete distance along the wire. In this setting, one desires a “laboratoryon a chip” in which droplets of various chemicals can be positioned, mixed, andthen directed to the appropriate outputs.

Representing system states as marked vertices on a graph is appropriate given thediscrete nature of the motion by electrophoresis on a graph of wires. This adds a

1. Hay muchos complejos cúbicos CAT(0) “en el mundo".

2. Los complejos cúbicos CAT(0) tienen estructura elegante y útil.


Motivación: mover robots.

Una culebra robótica puede mover:1. la cabeza o la cola o 2. una articulación

sin autointersectarse.

Culebra: Movimientos:

1:

2:



¿Cómo moverla (óptimamente) de una posición a otra?

Posición 1 → Posición 2



Una pregunta más fácil:

¿Cómo llegó Tristram Bogart (óptimamente) del hotel a la UIS?

Posición 1 → Posición 2



¿Cómo llegó Tristram Bogart (óptimamente) del hotel a la UIS?

¡Con un mapa!

7/15

/11

2:43

AM

My

Save

d Pl

aces

- G

oogl

e M

aps

Page

1 o

f 2ht

tp:/

/map

s.go

ogle

.com

/map

s/m

s?m

sa=

0&m

sid=

2026

3480

8560

6897

51…

2&sp

n=0.

0463

31,0

.069

523&

z=14

&ei

=EO

8fTr

2YB6

XozA

T-u6

z_Aw

&pw

=2

My

Save

d Pl

aces

Pub

lic ·

0 v

iew

sC

reat

ed o

n J

ul 1

5 ·

By

Fede

rico

· U

pdat

ed <

1 m

inut

e a

go

Uni

vers

idad

Indu

stria

l de

San

tand

erU

nive

rsid

ad In

dust

rial d

e S

anta

nder

¿Hagamos lo mismo!Construyamos un mapa de las posibles posiciones del robot.



Construyamos un mapa de las posibles posiciones del robot.

Un pedazo pequeño: (modelo discreto)



Construyamos un mapa de las posibles posiciones del robot.

Un pedazo pequeño: (modelo continuo)



Construyamos un mapa. Un ejemplo completo:

¡Un complejo cúbico CAT(0)!¿Cómo entenderlos, navegarlos?



RegularCAT(0) CubeComplexes

Rick Scott

Intro to cubecomplexesCube complexes

CAT(0)

Vertex-regular

Key ExamplesRACG’s

RAMRG’s

Growth seriesDefinition

Properties of CAT(0)cube complexes

Recurrence relations

Growth formula

Examples

Remarks

Proof sketch

RACG vs. RAMRG

RACG:

RAMRG:¡Un complejo cúbico CAT(0)! ¿Cómo entenderlos, navegarlos?

Obstáculos:• Alta dimensión.• Ramificación complicada.

Esto es lo que necesitamos superar.


El plan

0. (Una) motivación: mover robots.1. Definiciones: Espacios CAT(0) y complejos cúbicos.2. Hay muchos complejos cúbicos CAT(0)

“en la naturaleza".• Mover robots (y otros sistemas de reconfiguración)• Filogenética• Teoría geométrica de grupos y grupos de Coxeter

3. Corte de comerciales4. Los complejos cúbicos CAT(0) tienen una

estructura muy elegante.• El criterio de Gromov• Nuestra descripción combinatoria

5. Tres aplicaciones.• La conjetura de embebimiento.• Todo complejo cúbico CAT(0) es robótico.• Un algoritmo para calcular geodésicas.


Definiciones: complejos cúbicos

Un complejo cúbico es un espacio que se obtiene pegandocubos (tal vez de diferentes dimensiones) cara a cara.








(Es como un complejo simplicial, pero los bloques son cubos.)


Definiciones: espacios CAT(0)

Un espacio métrico X es CAT(0) si tiene curvatura no positivaglobalmente (“Tiene forma de silla de montar a caballo.")Más precisamente, X tiene triángulos angostos.

• Entre dos puntos de X hay un único camino geodésico.

• desigualdad CAT(0): Sea T un triángulo en X , T ′ un triángulode comparación en el plano, con las mismas longitudes.Consideremos dos puntos en el perímetro de T a distancia d .Si los dos puntos correspondientes en T ′ están a distancia d ′,

d ≤ d ′

RECONFIGURATION 13

a b

c

d

a b

c

d!

X R2

FIGURE 9. Comparison triangles measure curvature bounds.

4.2. The link condition. There is a well-known combinatorial approach to deter-mining when a cubical complex is nonpositively curved due to Gromov.

Definition 4.3. Let X denote a cell complex and let v denote a vertex of X . The linkof v, !k[v], is defined to be the abstract simplicial complex whose k-dimensionalsimplices are the (k + 1)-dimensional cells incident to v with the natural boundaryrelationships.

Certain global topological features of a metric cubical complex are completely de-termined by the local structure of the vertex links: a theorem of Gromov [26] assertsthat a finite dimensional Euclidean cubical complex is NPC if and only if the linkof every vertex is a flag complex without digons. Recall: a digon is a pair of ver-tices connected by two edges, and a flag complex is a simplicial complex whichis maximal among all simplicial complexes with the same 1-dimensional skeleton.Gromov’s theorem permits us an elementary proof of the following general result.

Theorem 4.4. The state complex of any locally finite reconfigurable system is NPC.

PROOF: Gromov’s theorem is stated for finite dimensional Euclidean cubical com-plexes with unit length cubes. It holds, however, for non-unit length cubes whenthere are a finite number of isometry classes of cubes (the finite shapes condition) [6].Locally finite reconfigurable systems possess locally finite and finite dimensionalstate complexes, which automatically satisfy the finite shapes condition (locally).

Let u denote a vertex of S. Consider the link !k[u]. The 0-cells of the !k[u] corre-spond to all edges in S(1) incident to u; that is, actions of generators based at u. Ak-cell of !k[u] is thus a commuting set of k + 1 of these generators based at u.

We argue first that there are no digons in !k[u] for any u " S. Assume that "1 and "2

are admissible generators for the state u, and that these two generators correspondto the vertices of a digon in !k[u]. Each edge of the digon in !k[u] corresponds toa distinct 2-cell in S having a corner at u and edges at u corresponding to "1 and"2. By Definition 2.7, each such 2-cell is the equivalence class [u; ("1, "2)]: the two2-cells are therefore equivalent and not distinct.

To complete the proof, we must show that the link is a flag complex. The interpre-tation of the flag condition for a state complex is as follows: if at u " S, one hasa set of k generators "!i , of which each pair of generators commutes, then the full

Nos interesan los complejos cúbicos que son CAT(0), porque:• Son abundantes en varios contextos.• Tienen una estructura combinatoria elegante y útil.


Ejemplo A. Tres cuadrados pegados en una esquina.



A

B

C

B'

A'

C'

|AB| = |BC| = |CA| = 1. → |A′B′| = |B′C′| = |C′A′| = 1.



A

B

C

B'

A'

C'

D' E'D

E

|AB| = |BC| = |CA| = 1. → |A′B′| = |B′C′| = |C′A′| = 1.

|DE | =

√2

2>

12

= |D′E ′|.

El triángulo no es angosto. → El espacio no es CAT(0).


Ejemplo B. Cinco cuadrados pegados en una esquina.



A

B

C

B'

A'

C'

|AB| = |AC| =√

5 → |A′B′| = |A′C′| =√

5|BC| = 2

√2 |B′C′| = 2

√2



A

B

C

B'

A'

C'

D' E'

D

E

|AB| = |AC| =√

5 → |A′B′| = |A′C′| =√

5|BC| = 2

√2 |B′C′| = 2

√2

|DE | = 1 <√

2 = |D′E ′|.

El triángulo sí es angosto. (Falta comparar muchas cuerdas.)El espacio sí es CAT(0). (Falta comparar muchos triángulos.)


Ejemplo 1. Robots y otros sistemas (Ghrist-Peterson 07)

Un robot se mueve usando ciertos movimientos locales.Grafo de transición:

vértices = posiciones, aristas = movimientos.

Teorema (GP) Este es, con frecuencia,el esqueleto de un complejo cúbico CAT(0).


Ejemplo 1. Robots y otros sistemas (Ghrist-Peterson 07)

Un robot se mueve usando ciertos movimientos locales.Complejo de estados:

vértices = posiciones, aristas = movimientos.cubos = movimientos “físicamente independientes".

Esto es muy general, y vale para muchos sistemas dereconfiguración, donde cambiamos un grafo usandomovimientos locales.


Ejemplo 2. Árboles filogenéticos (Billera,Holmes,Vogtmann)

Objetivo: Predecir el árbol evolutivode n especies / idiomas / ...

Estrategia:• Construir el espacio de todos los árboles posibles, Tn.• Estudiarlo, navegarlo.

14 BILLERA, HOLMES AND VOGTMANN

1 42 3

0

1 42 3

0

(1,0)

(0,1)

x+y=1

Figure 11: Constructing the link of the origin in T4

Figure 12 shows another portion of the link which forms a pentagonembedded in its ambient quadrants.

1 2 3 41

234

1 2 3 41 2 3 4

1 2 3 4

0 0

0

0

0

Figure 12: A pentagon in the link

The entire link of the origin is shown in Figure 13, without the ambientquadrants. The entire space T4 is an infinite cone on this graph, with conepoint the origin. It is interesting to note that the link of the origin in

SPACE OF PHYLOGENETIC TREES 15

this case is a well-known graph, called the Peterson graph. The Petersongraph has no planar embedding, and the space T4 cannot be embedded in3-dimensional space.

Figure 13: Link of the origin in T4

One can visualize T 4 as being obtained from the space pictured in Figure14 by gluing together edges with the same label. We note that the figuredoes not look metrically correct, since each triangle should be a right trian-gle with right angle at the origin; also, each triangle should extend foreverin the direction away from the origin.

a

b

cb

a

c

Figure 14: T4

3. COMBINATORICS OF THE SPACE OF TREES

In this section we consider certain combinatorial aspects of the space oftrees, and in particular relations to combinatorial structures which havebeen studied in other contexts. The combinatorial properties of the link of

Teorema. (BHV) Tn es un Cor. Tiene geodésicas únicas.complejo cúbico CAT(0). Cor. Puedo promediar árboles.


Example 3. Teoría Geométrica de Grupos.

Un grupo de Coxeter rectangular es un grupo de la forma

W (G) = 〈v ∈ V | v2 = 1 para v ∈ V , (uv)2 = 1 para uv ∈ E〉RegularCAT(0) CubeComplexes

Rick Scott


CAT(0)

Vertex-regular


RAMRG’s




Growth formula

Examples

Remarks

Proof sketch

Example

ExampleFor the graph

c

b

ad

the Davis complex is

abc

1 d

c

a

b

ab

cd

ac

bc

Ejemplo: a2 = b2 = c2 = d2 = 1(ab)2 = (ac)2 = (bc)2 = (cd)2 = 1

Thm. (Davis) Los grupos de Coxeter rectángulos son CAT(0):W (G) actúa “bien" sobre un complejo cúbico CAT(0), X (G).


Rick Scott


CAT(0)

Vertex-regular


RAMRG’s




Growth formula

Examples

Remarks

Proof sketch

Example

ExampleFor the graph

c

b

ad

the Davis complex is

abc

1 d

c

a

b

ab

cd

ac

bc

TGG usa la geometría de X (G) para estudiar el grupo W (G):• Si un grupo G es CAT(0), el “problema de la palabra" esresoluble en tiempo cuadrático. (En general es indecidible.)


Corte de comerciales.

Para más información sobre

• grupos de Coxeter,• politopos,• matroides, y• álgebra conmutativa combinatoria,

pueden ver los (150+) videos y las notas de mis cursos deSan Francisco State University y la Universidad de Los Andes.

http://math.sfsu.edu/federico/

San Francisco State University – Colombia Combinatorics Initiative


Caracterizaciones: ¿Cuáles complejos cúbicos son CAT(0)?

no CAT(0): CAT(0):

En general la condición CAT(0) es muy sutil.Para complejos cúbicos:

1. Caracterización de Gromov.

Theorem. (Gromov, 1987) Un complejocúbico es CAT(0) si y sólo si• es simplemente conexo, y• el link de cada vértice es bandera.

∆ bandera: (1-esqueleto de un símplex T en ∆) → T ∈ ∆.(“No hay cubos vacíos").


Rick Scott


CAT(0)

Vertex-regular


RAMRG’s




Growth formula

Examples

Remarks

Proof sketch

Vertex Links

In a cubical complex, the linksof vertices are simplicial complexes.

A simplicial complex L is aflag complex if whenever the1-skeleton of a simplex occursin L, so does the entire simplex.


Caracterizaciones: ¿Cuáles complejos cúbicos son CAT(0)?

2. Nuestra caracterización.

Idea: Los complejos cúbicos CAT(0) “parecen" retículosdistributivos.


Rick Scott


CAT(0)

Vertex-regular


RAMRG’s




Growth formula

Examples

Remarks

Proof sketch

RACG vs. RAMRG

RACG:

RAMRG:

Teorema. (AOS 08) Hay una biyección:(complejos cúbicos CAT(0) (puntuados))↔(posets con parejas inconsistentes = PPIs)

1

2

4

65

3

PPI: Poset P y conjunto de “parejas inconsistentes" {x , y} conx , y inconsistente, y < z → x , z inconsistente.


Teorema. (AOS 08) Hay una biyección:(complejos cúbicos CAT(0) (puntuados))↔(posets con parejas inconsistentes)

Idea de la demostración.Imitar biyección de Birkhoff: retículos distributivos↔ posets

“→ ”: X tiene hiperplanos que parten a los cubos en dos.(Sageev)


Biyección. “→ ”: Fijemos un vértice “inicial" v .

v

1

2 4

6

3

5 12345

12

123

124

234 1246

24

1234

2

2

12

1

2

4

65

3

Si i , j son hiperplanos, declaramos:

i < j si uno tiene que cruzar i antes de cruzar j .i , j inconsistentes si es imposible cruzarlos a los dos..


Anotación.

Sageev - Roller (95, 98) obtuvieron una descripcióncombinatoria diferente. Cuál es más útil depende del contexto.

La nuestra es especialmente útil cuando tenemos un vérticesespecial, o no hace daño elegir uno; e.g.:

• espacio de árboles: el origen• teoría geométrica de grupos: la identidad• robótica: una posición inicial.

Ahora discutimos varias aplicaciones del teorema principal.


Aplicación 1. Conjetura de embebimiento.

Conjetura. (Niblo, Sageev, Wise) Si un complejo cúbico CAT(0)tiene dimensión ≤ d , entonces se puede ver como parte de Zd .

v

1

2 4

6

3

5 12345

12

123

124

234 1246

24

1234

2

2

12

1

2

4

65

3

Dem. (AOS 08) Fijo v → poset con parejas inconsistentes P.vértice u ↔ Q ⊆ P consistente cerrado bajo ≤

intervalo [u, v ] ↔ retículo distributivo J(Q)

Dilworth ya mostró (¡en 1950!) cómo meter J(Q) en Zd :• Escribir a Q como unión disyunta de d cadenas. (246, 35, 1)• “Aplanar" el complejo cúbico a lo largo de cada cadena.(Brodzki, Campbell, Guentner, Niblo, Wright (08) también.)


Aplicación 2. Todo complejo cúbico CAT(0) es “robótico".

Teorema. (Ghrist-Peterson 07) Todo complejo cúbico CAT(0) esel complejo de estados de un sistema de reconfiguración (robot).

Su prueba es indirecta.

v

1

2 4

6

3

5 12345

12

123

124

234 1246

24

1234

2

2

12

1

2

4

65

3

Prueba alternativa proof. (AOS 10)Fijo v → poset con parejas inconsistentes P.

Un “robot enfermedad" infecta un poset P.Puede infectar un nuevo vértice q si y sólo si:

• ya infectó a todos los elementos p < q, y• no ha infectado a ningún elemento inconsistente con q.

Entonces X es el complejo de estados de este robot.


Aplicación 3. Hallar geodésicas en complejos cúbicos CAT(0).

Motivación:

Algoritmo. (Owen-Provan 09) Un algoritmo en tiempo polinomialque encuentra la geodésica entre dos árboles T1 y T2 en el espaciode árboles Tn.

(√

2-aproximación: Amenta 07)(exponencial.: GeoMeTree 08, GeodeMaps 09)Esto nos permite• encontrar la distancia entre dos árboles.• “promediar" árboles.


Aplicación 3. Hallar geodésicas en complejos cúbicos CAT(0).

Usamos la descripción combinatoria (“control remoto") de X y:

Algoritmo. (AOS, 10) Un algoritmo que encuentra la geodésicaentre dos puntos p and q en cualquier complejo cúbico CAT(0).

Esto nos permite• entender y navegar el “mapa"de muchos robots.• hallar la manera óptima de mover un robot de una posición aotra, bajo esta métrica.

(¿Tiempo polinomial?)


muchas gracias








El artículo y la presentación están en:

Advances in Applied Mathematicshttp://arxiv.org/abs/1101.2428http://math.sfsu.edu/federico

la combinatoria de los complejos cúbicos de tipo …math.sfsu.edu/federico/talks/bucaramanga.pdfla...

Documents