Teorema nulo combinatorio

El teorema del cero combinatorio (teorema de Alon, combinatorial nullstellensatz ) es un teorema algebraico que relaciona el coeficiente de un polinomio en un determinado monomio con sus valores. El teorema da una estimación más baja de las dimensiones de un paralelepípedo combinatorio en el que el polinomio no es idénticamente igual a cero. Esta estimación depende del grado del monomio principal en cada variable.

Historia

El teorema fue probado y aplicado por primera vez en un artículo de 1989 por Noga Alon y Michel Tarcy [1] y desarrollado por Alon, Natanzon y Ruzsa en 1995–1996. Fue reformulado por Alon en 1999. [2]

Enunciado del teorema

Además, la entrada significa el coeficiente de un polinomio en un monomio en un polinomio . $[{{x_{1}}^{d_{1}}\puntos {x_{n}}^{d_{n}}}]f(x_{1},\puntos,x_{n})$ $F$ ${x_{1}}^{d_{1}}\puntos {x_{n}}^{d_{n}}$ $F$

Sea un polinomio sobre algún campo y sea su monomio principal en el sentido de que en cualquier otro monomio (con coeficiente distinto de cero) el grado de al menos una variable es menor que en la dada. ${\ estilo de visualización f (x_ {1}, \ puntos, x_ {n})}$ $k$ ${x_{1}}^{d_{1}}{x_{2}}^{d_{2}}\puntos {x_{n}}^{d_{n}}$

El teorema establece que si , entonces para cualquier conjunto con cardinalidades , existen tales que . $[{{x_{1}}^{d_{1}}\puntos {x_{n}}^{d_{n}}}]f\not =0$ $A_{1},\puntos,A_{n}$ $|A_{i}|\geq d_{i}+1$ $a_{i}\en A_{i}$ $f(a_{1},\dots,a_{n})\not =0$

Polinomio de interpolación

El teorema se deriva directamente de una generalización de la fórmula del polinomio de interpolación de Lagrange para un polinomio de grado . $f(x)=\sum \limits _{i=0}^{n}{y_{i}\prod \limits _{i\not =j}{\frac {x-x_{j)) {x_{i}-x_{j}}}}$ $F$ $norte$

A partir de la fórmula de Lagrange, puede aislar el coeficiente principal del polinomio . En particular, el lado derecho se anula en cualquier polinomio de grado n − 1. $[x^{n}]f=\sum \limits _{i=0}^{n}{{y_{i}}\prod \limits _{i\not =j}{\frac {1 {x_{i}-x_{j}}}}$

Por lo tanto, bajo una condición dada sobre el grado de un monomio , esta fórmula se generaliza: el lado derecho ${x_{1}}^{d_{1}}\puntos {x_{n}}^{d_{n}}$

$[{{x_{1}}^{d_{1}}\dots {x_{n}}^{d_{n}}}]f=\sum \limits _{a_{1}\in A_ {1}}\puntos \sum \limits _{a_{n}\in A_{n}}{\frac {f(a_{1},\puntos,a_{n})}{\prod \limits_{ a_{1}\not =b_{1}\in A_{1}}\dots \prod \limits _{a_{n}\not =b_{n}\in A_{n}}{(a_{1} -b_{1})\puntos (a_{n}-b_{n})}}}$

sólo puede depender de , de donde se sigue la igualdad y, obviamente, el teorema del cero. ${\estilo de texto [{{x_{1}}^{d_{1}}\puntos {x_{n}}^{d_{n}}}]f}$

Aplicaciones

El teorema del cero combinatorio se puede usar para probar teoremas de existencia , cuando la existencia de un valor distinto de cero de un polinomio en algún punto significa que algún objeto satisface la propiedad deseada, y el conjunto de todos los objetos (entre los cuales se debe probar la existencia) es uno a uno comparado con el conjunto de posibles conjuntos de valores de las variables.

Teorema de Alon-Friedland-Kalai

Considere, por ejemplo, el siguiente teorema:

Sea un número primo y para la gráfica el grado máximo , y el grado medio . $pags$ $G=(V,E)$ ${\ estilo de visualización \ Delta (G) \ leq 2p-1}$ ${\frac{2|E|}{|V|}}>2p-2$

Entonces hay un subgrafo -regular en . [3] $GRAMO$ $pags$

Denote por el conjunto de aristas adyacentes al vértice . Para probar el teorema, considere un polinomio en el campo (módulo ) en variables correspondientes a los bordes del gráfico. ${\ estilo de visualización E (v)}$ $v$ ${\displaystyle {\mathbb {Z} }_{p))$ $pags$ $|E|$

$P(x_{1},\dots ,x_{|E|})=\prod \limits _{v\in V}{\left({1-\left({\sum \limits _{e \in E(v)}{x_{e}}}\right)^{p-1}}\right)}-\prod \limits _{e\in E}(1-x_{e})$

En este polinomio, el coeficiente del monomio más alto no es igual a cero. Al mismo tiempo, obviamente . Por lo tanto, hay un conjunto de aristas no vacío tal que si ponemos para ellos y para los demás , entonces el polinomio de dicho conjunto tomará un valor distinto de cero. $\prod \limits _{e\in E}{x_{e}}$ $P(0,\dots,0)=0$ ${\ estilo de visualización x_ {e} = 1}$ ${\ estilo de visualización x_ {e} = 0}$

Dado que la resta será cero en cualquier conjunto distinto de cero, entonces en el conjunto considerado para todo , es decir, en el subgrafo de estas aristas, todos los grados de vértices son múltiplos de . Y como todos son estrictamente menores que por condición , entonces, al eliminar los vértices con grado cero, obtenemos un subgrafo regular no vacío. $PAGS$ $\sum \limits _{e\in E(v)}{x_{e}}\equiv 0\ (mod\ p)$ $v$ $pags$ ${\ estilo de visualización 2p}$ $pags$

Un reforzamiento del teorema de Cauchy-Davenport

El siguiente es un número primo. $pags$

El teorema de Cauchy-Davenport, que establece que para , es relativamente fácil de probar por métodos elementales. $|A+B|=|\{{a+b:a\en A,b\en B}\}|\geq \min\{{p,|A|+|B|-1}\ }$ ${\displaystyle A\subconjunto {\mathbb {Z} }_{p},B\subconjunto {\mathbb {Z} }_{p))$

Sin embargo, aún no se ha encontrado ninguna prueba combinatoria para fortalecer la forma de . Pero se demuestra fácilmente a través del teorema del cero combinatorio. [cuatro] $|A\oplus B|=|\{{a+b:a\in A,b\in B,a\not =b}\}|\geq \min\{{p,|A|+ |B|-2}\}$ $A\subconjunto {\mathbb {Z} }_{p},B\subconjunto {\mathbb {Z} }_{p},A\not =B$

Probemos este fortalecimiento por contradicción. Asumiremos que , porque de lo contrario, algunos elementos pueden simplemente eliminarse de los conjuntos. $|A|+|B|-2\leq p$

Si , entonces el enunciado del teorema corresponde al enunciado del teorema original de Cauchy-Davenport. Si , entonces, ya que , podemos usar el hecho de que y llevar a cabo la inducción sobre el tamaño del conjunto más pequeño y . $|A|=|B|$ $A \cap B = \varnada$ $A\cap B\not =\varnada$ ${\ estilo de visualización A \ no = B}$ $(A\cap B)\oplus (A\cup B)\subset A\oplus B$ $A$ $B$

Por lo tanto, basta con considerar el caso . Sea y . Consideremos un polinomio . Este polinomio tiene explícitamente un coeficiente distinto de cero en el monomio , que se expresa en términos de la diferencia de los coeficientes binomiales. Sin embargo, para , este polinomio siempre se anula, lo que contradice el teorema del cero combinatorio. ${\ estilo de visualización | A | \ no = | B |}$ $(A\oplus B)\subconjunto C$ ${\ estilo de visualización | C | = | A | + | B | -3}$ ${\displaystyle (xy)\prod \limits_{c\in C}{(x+yc)))$ $pags$ ${\ estilo de visualización x^{|A|-1}y^{|B|-1}}$ $x \ en A$ ${\ estilo de visualización y \ en B}$

Véase también

Notas

↑ Alon, Noga ; Tarsis, Michael. Un punto cero en ninguna parte en mapeos lineales (neopr.) . - 1989. - T. 9 , N º 4 . - S. 393-395 . -doi : 10.1007/ BF02125351 .
↑ Alon, Noga . Combinatoria Nullstellensatz (neopr.) . - 1999. - V. 8 , N° 1-2 . - S. 7-29 . -doi : 10.1017/ S0963548398003411 .
↑ El teorema cero de Alon y sus aplicaciones, MIPT, primavera de 2014 . Consultado el 12 de febrero de 2016. Archivado desde el original el 17 de noviembre de 2016. (indefinido)
↑ Combinatoria aditiva, biblioteca abierta de conferencias en video, laboratorio matemático que lleva el nombre de P. L. Chebyshev