Complejo de tablero de ajedrez

Objeto matemático en la teoría de grafos topológicos.

Un complejo de tablero de ajedrez es un tipo particular de complejo simplicial abstracto , que tiene varias aplicaciones en teoría de grafos topológicos y topología algebraica . ^{[1] [2]} Informalmente, el complejo ( m , n )-tablero de ajedrez contiene todos los conjuntos de posiciones en un tablero de ajedrez m -by- n , donde las torres se pueden colocar sin atacarse entre sí. De manera equivalente, es el complejo coincidente del gráfico bipartito completo ( m , n ) , o el complejo de independencia del gráfico de torre m - por n .

Definiciones

Para dos enteros positivos cualesquiera m y n , el complejo ( m, n )-tablero de ajedrez es el complejo simplicial abstracto con un conjunto de vértices que contiene todos los subconjuntos S tales que, si y son dos elementos distintos de S , entonces ambos y . El conjunto de vértices puede verse como una cuadrícula bidimensional (un "tablero de ajedrez") y el complejo contiene todos los subconjuntos S que no contienen dos celdas en la misma fila o en la misma columna. En otras palabras, todos los subconjuntos S tales que se puedan colocar torres sobre ellos sin tomarse entre sí. ${\displaystyle \Delta _{m,n}}$ ${\displaystyle [m]\times [n]}$ ${\displaystyle (i_{1},j_{1})}$ ${\displaystyle (i_{2},j_{2})}$ ${\displaystyle i_{1}\neq i_{2}}$ ${\displaystyle j_{1}\neq j_{2}}$

El complejo del tablero de ajedrez también se puede definir de manera sucinta usando unión eliminada . Sea D _m un conjunto de m puntos discretos. Entonces _, el complejo del tablero de ajedrez es la unión eliminada n veces en dos sentidos de Dm , denotada por . ^{[3] : 176} ${\displaystyle (D_{m})_{\Delta (2)}^{*n}}$

Otra definición es el conjunto de todas las coincidencias en el gráfico bipartito completo . ^[1] ${\displaystyle K_{m,n}}$

Ejemplos

En cualquier complejo de tablero de ajedrez ( m , n ), la vecindad de cada vértice tiene la estructura de un complejo de tablero de ajedrez ( m − 1, n − 1). En términos de torres de ajedrez, colocar una torre en el tablero elimina las casillas restantes en la misma fila y columna, dejando un conjunto más pequeño de filas y columnas donde se pueden colocar torres adicionales. Esto permite estudiar jerárquicamente la estructura topológica de un tablero de ajedrez, en función de sus estructuras de dimensiones inferiores. Un ejemplo de esto ocurre con el complejo de tablero de ajedrez (4,5) y los complejos de tablero de ajedrez (3,4) y (2,3) dentro de él: ^[4]

• El complejo (2,3)-tablero de ajedrez es un hexágono , que consta de seis vértices (los seis cuadrados del tablero de ajedrez) conectados por seis aristas (pares de cuadrados no atacantes).
• El complejo del tablero de ajedrez (3,4) es una triangulación de un toroide , con 24 triángulos (triplas de cuadrados no atacantes), 36 aristas y 12 vértices. Seis triángulos se encuentran en cada vértice, en el mismo patrón hexagonal que el complejo del tablero de ajedrez (2,3).
• El complejo del tablero de ajedrez (4,5) forma una pseudovariedad tridimensional : en la vecindad de cada vértice, se encuentran 24 tetraedros, en el patrón de un toro, en lugar del patrón esférico que se requeriría de una variedad . Si se eliminan los vértices de este espacio, al resultado se le puede dar una estructura geométrica como una variedad triple hiperbólica en cúspide , topológicamente equivalente al complemento de enlace de un enlace de 20 componentes .

Propiedades

Cada faceta de contiene elementos. Por tanto, la dimensión de es . ${\displaystyle \Delta _{m,n}}$ ${\displaystyle \min(m,n)}$ ${\displaystyle \Delta _{m,n}}$ ${\displaystyle \min(m,n)-1}$

La conectividad homotópica del complejo del tablero de ajedrez es al menos (tan ). ^{[1] : Sección 1} ${\displaystyle \min \left(m,n,{\frac {m+n+1}{3}}\right)-2}$ ${\displaystyle \eta \geq \min \left(m,n,{\frac {m+n+1}{3}}\right)}$

Los números de Betti de los complejos de tablero de ajedrez son cero si y sólo si . ^{[5] : 200} Los valores propios de los laplacianos combinatorios del complejo del tablero de ajedrez son números enteros. ^{[5] : 193} ${\displaystyle b_{r-1}}$ ${\displaystyle (m-r)(n-r)>r}$

El complejo del tablero de ajedrez está conectado, donde . ^{[6] : 527} El grupo de homología es un grupo de 3 exponentes como máximo 9, y se sabe que es exactamente el grupo cíclico de 3 elementos cuando . ^{[6] : 543–555} ${\displaystyle (\nu _{m,n}-1)}$ ${\displaystyle \nu _{m,n}:=\min\{m,n,\lfloor {\frac {m+n+1}{3}}\rfloor \}}$ ${\displaystyle H_{\nu _{m,n}}(M_{m,n})}$ ${\displaystyle m+n\equiv 1{\pmod {3}}}$

El complejo -esqueleto del tablero de ajedrez es descomponible en vértices en el sentido de Provan y Billera (y por tanto desgranable), y todo el complejo es descomponible en vértices si . ^{[7] : 3} Como corolario, cualquier posición de k torres en un tablero de ajedrez de m por n , donde , puede transformarse en cualquier otra posición utilizando como máximo movimientos de una sola torre (donde cada posición intermedia tampoco es una toma de torres). ). ^{[7] : 3} ${\displaystyle (\lfloor {\frac {n+m+1}{3}}\rfloor -1)}$ ${\displaystyle n\geq 2m-1}$ ${\displaystyle k\leq \lfloor {\frac {m+n+1}{3}}\rfloor }$ ${\displaystyle mn-k}$

Generalizaciones

El complejo es un "complejo de tablero de ajedrez" definido para un tablero de ajedrez de k dimensiones. De manera equivalente, es el conjunto de coincidencias en un hipergrafo k -partito completo . Este complejo está al menos -conexo, para ^{[1] : 33} ${\displaystyle \Delta _{n_{1},\ldots ,n_{k}}}$ ${\displaystyle (\nu -2)}$ ${\displaystyle \nu :=\min\{n_{1},\lfloor {\frac {n_{1}+n_{2}+1}{3}}\rfloor ,\dots ,\lfloor {\frac {n_{1}+n_{2}+\dots +n_{k}+1}{2k+1}}\rfloor \}}$

Referencias

1. , A.; Lovász, L.; Vrećica, ST; Živaljević, RT (1 de febrero de 1994). "Complejos de tablero de ajedrez y complejos de combinación". Revista de la Sociedad Matemática de Londres . 49 (1): 25–39. doi :10.1112/jlms/49.1.25.
2. Vrećica, Siniša T.; Živaljević, Rade T. (1 de octubre de 2011). "Complejos de tablero de ajedrez indomables". Revista de teoría combinatoria . Serie A. 118 (7): 2157–2166. arXiv : 0911.3512 . doi : 10.1016/j.jcta.2011.04.007 . ISSN  0097-3165.
3. Matoušek, Jiří (2007). Uso del teorema de Borsuk-Ulam : conferencias sobre métodos topológicos en combinatoria y geometría (2ª ed.). Berlín-Heidelberg: Springer-Verlag. ISBN 978-3-540-00362-5. Escrito en colaboración con Anders Björner y Günter M. Ziegler
4. Goerner, Matthias Rolf Dietrich (2011). "1.2.2 Relación con el Complejo Tablero de Ajedrez 4×5". Visualización de teselaciones regulares: principales vínculos de congruencia y morfismos equivalentes desde superficies hasta 3 variedades (PDF) (Tesis doctoral). Universidad de California, Berkeley.
5. Friedman, Joel; Hanlon, Phil (1 de septiembre de 1998). "Sobre los números de Betti de los complejos de tablero de ajedrez". Revista de combinatoria algebraica . 8 (2): 193–203. doi :10.1023/A:1008693929682. hdl : 2027.42/46302 . ISSN  1572-9192.
6. Shareshian, John; Wachs, Michelle L. (10 de julio de 2007). "Torsión en el complejo de emparejamiento y complejo de tablero de ajedrez". Avances en Matemáticas . 212 (2): 525–570. arXiv : matemáticas/0409054 . doi : 10.1016/j.aim.2006.10.014 . ISSN  0001-8708.
7. Ziegler, Günter M. (23 de septiembre de 1992). "Descascarabilidad de complejos de tablero de ajedrez".