Articulo de referencia

El lema de Gordon

El lema de Gordon es un lema de geometría convexa y geometría algebraica . Se puede enunciar de varias maneras. Dejar A {\displaystyle A} Sea una matriz de enteros. METRO {\disp...

El lema de Gordon es un lema de geometría convexa y geometría algebraica . Se puede enunciar de varias maneras.

El lema recibe su nombre del matemático Paul Gordon (1837-1912). Algunos autores lo han escrito erróneamente como "el lema de Gordon".

Pruebas

Existen demostraciones topológicas y algebraicas.

Demostración topológica

Dejarσ{\displaystyle \sigma }Sea el cono dual del cono poliédrico racional dado.1,,r{\displaystyle u_{1},\dots ,u_{r}}sean vectores enteros de modo queσ={incógnitai,incógnita0,1ir}.{\displaystyle \sigma =\{x\mid \langle u_{i},x\rangle \geq 0,1\leq i\leq r\}.}Entonces eli{\displaystyle u_{i}}generan el cono dobleσ{\displaystyle \sigma ^{\vee }}; de hecho, escribir C para el cono generado pori{\displaystyle u_{i}}'s, tenemos:σdo{\displaystyle \sigma \subset C^{\vee }}, que debe ser la igualdad. Ahora, si x está en el semigrupo

Sσ=σZd,{\displaystyle S_{\sigma }=\sigma ^{\vee }\cap \mathbb {Z} ^{d},}

entonces se puede escribir como

incógnita=inorteii+irii,{\displaystyle x=\sum _{i}n_{i}u_{i}+\sum _{i}r_{i}u_{i},}

dóndenortei{\displaystyle n_{i}}son enteros no negativos y0ri1{\displaystyle 0\leq r_{i}\leq 1}. Pero como x y la primera suma del lado derecho son enteros, la segunda suma es un punto de la red en una región acotada, y por lo tanto solo hay un número finito de posibilidades para la segunda suma (la razón topológica). Por lo tanto,Sσ{\displaystyle S_{\sigma }}es generado de forma finita.

Demostración algebraica

La demostración [ 3 ] se basa en el hecho de que un semigrupo S es finitamente generado si y solo si su álgebra de semigruposdo[S]{\displaystyle \mathbb {C} [S]}es un álgebra finitamente generada sobredo{\displaystyle \mathbb {C} }Para demostrar el lema de Gordan, por inducción (véase la demostración anterior), basta con probar la siguiente afirmación: para cualquier subsemigrupo unitario S deZd{\displaystyle \mathbb {Z} ^{d}},

Si S es finitamente generado, entoncesS+=S{incógnitaincógnita,v0}{\displaystyle S^{+}=S\cap \{x\mid \langle x,v\rangle \geq 0\}}, v un vector integral, es finitamente generado.

PonerA=do[S]{\displaystyle A=\mathbb {C} [S]}, que tiene una baseχa,aS{\displaystyle \chi ^{a},\,a\in S}TieneZ{\displaystyle \mathbb {Z} }-calificación otorgada por

Anorte=durar{χaaS,a,v=norte}{\displaystyle A_{n}=\operatorname {span} \{\chi ^{a}\mid a\in S,\langle a,v\rangle =n\}}.

Por hipótesis, A es finitamente generado y, por lo tanto, es noetheriano. Del lema algebraico que se presenta a continuación se deduce quedo[S+]=0Anorte{\displaystyle \mathbb {C} [S^{+}]=\oplus _{0}^{\infty }A_{n}}es un álgebra finitamente generada sobreA0{\displaystyle A_{0}}Ahora, el semigrupoS0=S{incógnitaincógnita,v=0}{\displaystyle S_{0}=S\cap \{x\mid \langle x,v\rangle =0\}}es la imagen de S bajo una proyección lineal, por lo tanto, finitamente generada y asíA0=do[S0]{\displaystyle A_{0}=\mathbb {C} [S_{0}]}es finitamente generado. Por lo tanto,S+{\displaystyle S^{+}}entonces se genera de forma finita.

Lema : Sea A unZ{\displaystyle \mathbb {Z} }- anillo graduado . Si A es un anillo noetheriano , entoncesA+=0Anorte{\displaystyle A^{+}=\oplus _{0}^{\infty }A_{n}}es un finito generadoA0{\displaystyle A_{0}}-álgebra.

Demostración: Sea I el ideal de A generado por todos los elementos homogéneos de A de grado positivo. Dado que A es noetheriano, I es generado en realidad por un número finito de elementos homogéneos de A.Fis{\displaystyle f_{i}'s}, homogéneo de grado positivo. Si f es homogéneo de grado positivo, entonces podemos escribirF=igramoiFi{\textstyle f=\sum _{i}g_{i}f_{i}}congramoi{\displaystyle g_{i}}homogéneo. Si f tiene un grado suficientemente grande, entonces cadagramoi{\displaystyle g_{i}}tiene grado positivo y estrictamente menor que el de f . Además, cada pieza de gradoAnorte{\displaystyle A_{n}}es un finito generadoA0{\displaystyle A_{0}}-módulo. (Prueba: Seanortei{\displaystyle N_{i}}ser una cadena creciente de submódulos generados finitamente deAnorte{\displaystyle A_{n}}con uniónAnorte{\displaystyle A_{n}}. Luego la cadena de los idealesnorteiA{\displaystyle N_{i}A}se estabiliza en pasos finitos; también lo hace la cadenanortei=norteiAAnorte.{\displaystyle N_{i}=N_{i}A\cap A_{n}.}) Así, por inducción sobre el grado, vemosA+{\displaystyle A^{+}}es un finito generadoA0{\displaystyle A_{0}}-álgebra.

Aplicaciones

Un hipergrafo múltiple sobre un conjunto determinadoV{\displaystyle V}es un multiconjunto de subconjuntos deV{\displaystyle V}(Se denomina "multihipergrafo" ya que cada hiperarista puede aparecer más de una vez). Un multihipergrafo se denomina regular si todos sus vértices tienen el mismo grado . Se denomina descomponible si posee un subconjunto propio no vacío que también es regular. Para cualquier entero n , seaD(norte){\displaystyle D(n)}Sea el grado máximo de un multihipergrafo indescomponible con n vértices. El lema de Gordon implica queD(norte){\displaystyle D(n)}es finito. [ 1 ] Demostración : para cada subconjunto S de vértices, definamos una variable x S (un entero no negativo). Definamos otra variable d (un entero no negativo). Consideremos el siguiente conjunto de n ecuaciones (una ecuación por vértice):SvincógnitaSd=0 a pesar de vV{\displaystyle \sum _{S\ni v}x_{S}-d=0{\text{ para todo }}v\in V}Cada solución ( x , d ) denota un multihipergrafo regular enV{\displaystyle V}donde x define las hiperaristas y d es el grado. Por el lema de Gordon, el conjunto de soluciones está generado por un conjunto finito de soluciones, es decir, hay un conjunto finitoMETRO{\displaystyle M}de multihipergrafos, de tal manera que cada multihipergrafo regular es una combinación lineal de algunos elementos deMETRO{\displaystyle M}. Todo multihipergrafo no descomponible debe estar enMETRO{\displaystyle M}(ya que, por definición, no puede ser generado por otro multihipergrafo). Por lo tanto, el conjunto de multihipergrafos no descomponibles es finito.

Véase también

  • El algoritmo de Birkhoff es un algoritmo que, dada una matriz biestocástica (una matriz que resuelve un conjunto particular de ecuaciones), encuentra su descomposición en matrices enteras. Está relacionado con el lema de Gordon, ya que demuestra que el conjunto de estas matrices se genera a partir de un conjunto finito de matrices enteras.

Referencias

  1. 1 2 Alon, N ; Berman, KA (1986-09-01). "Hipergrafos regulares, lema de Gordon, lema de Steinitz y teoría de invariantes" . Journal of Combinatorial Theory, Serie A . 43 (1): 91– 97. doi : 10.1016/0097-3165(86)90026-9 . ISSN 0097-3165 . 
  2. David A. Cox, Lecciones sobre variedades tóricas . Lección 1. Proposición 1.11.
  3. Bruns, Winfried; Gubeladze, Joseph (2009). Polytopes, rings, and K-theory . Springer Monographs in Mathematics. Springer. doi : 10.1007/b105283 . ISBN 978-0-387-76355-2., Lema 4.12.

Véase también