Reforzar la hipótesis de la inducción

Question

Supongamos que se trata de probar el resultado $X$ por inducción y no están llegando a ninguna parte rápidamente. Un buen truco es intentar demostrar un resultado más fuerte $X'$ (que realmente no te importa) por inducción. Esto tiene una posibilidad de éxito porque tienes más con qué trabajar en el paso de inducción. Mi ejemplo favorito de esto es la hermosa prueba de Thomassen de que todo grafo planar es 5-elegible. La prueba es bastante sencilla una vez que se sabe lo que hay que demostrar. Aquí está la forma reforzada (que es un buen ejercicio para demostrar por inducción),

Teorema. Dejemos que $G$ sea un grafo plano con al menos 3 vértices tal que cada cara de $G$ está delimitada por un triángulo (excepto posiblemente la cara exterior). Sea la cara exterior de $G$ estar delimitado por un ciclo $C=v_1 \dots v_kv_1$ . Supongamos que $v_1$ se ha coloreado 1 y que $v_2$ se ha coloreado 2. Supongamos además que para cualquier otro vértice de $C$ se ha especificado una lista de al menos 3 colores, y para cada vértice de $G - C$ se ha especificado una lista de al menos 5 colores. Entonces, la coloración de $v_1$ y $v_2$ puede extenderse a una coloración de $G$ con las listas especificadas.

Pregunta 1. ¿Cuáles son otros buenos ejemplos de este fenómeno?

Pregunta 2. ¿En qué condiciones es probable que funcione la estrategia de reforzar la hipótesis de inducción?

Answer 1

La prueba de la 5-elección también es mi favorita. Es realmente un ejemplo clásico.

Mi ejemplo consiste en acotar la combinación de dos invariantes globales acotando la combinación de dos invariantes locales.

Reed's $\omega$ , $\Delta$ , $\chi$ La conjetura propone que $\chi \leq \gamma := \lceil \frac 12 (\omega+\Delta+1)\rceil$ . Un truco favorito a la hora de acotar el número cromático es considerar un contraejemplo mínimo, eliminar uno o más conjuntos estables (que se convierten en clases de color), y demostrar (o rezar) que la invariante de acotación disminuye por el número de conjuntos estables que se eliminan.

Pero es difícil hacer que el grado máximo disminuya en 2, y/o hacer que el número de camarilla disminuya en 1 -- esto es lo que se necesita cuando se elimina un conjunto estable en este caso. En su lugar, deja que el invariante sea el máximo sobre todos los vértices de $\gamma$ para el gráfico inducido en la vecindad cerrada de $v$ (es decir, el grado de $v$ más el tamaño de la mayor camarilla que contiene $v$ más uno, redondeado). En otras palabras, $\max_v \gamma(G[\bar N(v)])$ . Ahora, cuando se elimina un conjunto estable, el invariante es más fácil de controlar, y se puede ignorar un vértice cuya vecindad cerrada está debidamente contenida en la vecindad cerrada de otro vértice.

En el entorno de los grafos sin garras con número de estabilidad $\leq 3$ esta era la única manera de probar la conjetura de Reed. Hay muchos casos básicos, sobre todo los gráficos con número de estabilidad $2$ .

Answer 2

Fórmula de Euler $V-E+F=2$ para los politopos convexos tiene una prueba inductiva trivial después de sustituir los politopos por grafos planos conectados (eliminar aristas hasta obtener un árbol), y aún más trivial si sustituimos 2 por $1+C$ , donde $C$ es un número de componentes conectados de un grafo plano arbitrario (eliminar aristas hasta obtener un grafo sin aristas). Obsérvese que tales operaciones sobre un conjunto de politopos no están bien definidas. Esta es probablemente la razón por la que Euler no demostró este hecho.

Answer 3

Creo que el papel del caso base de la inducción es crucial y debería separarse del análisis.

Es concebible que se pueda obtener alguna comprensión teórica de la prueba de la "inducción sin la base", es decir, el fenómeno de cómo el fortalecimiento de la propiedad $P_{\rm weak}$ a $P_{\rm strong}$ puede hacer que la implicación $P(n) \to P(n+1)$ más fácil de probar. Sin embargo, $P_{\rm strong}(1)$ y $P_{\rm weak}(1)$ son diferentes, y es difícil imaginar cómo podría establecerse una teoría del caso base. Tal vez al considerar las familias de $P$ se podría decir algo, pero por lo demás uno se encuentra con toda la extrañeza de lo finito y accidental.

Answer 4

Si $p$ es un polinomio en $n$ variables reales que es positiva en $[0,1]^n$ la integral $\int_{[0,1]^n} p(\mathbf{x})^s d\mathbf{x}$ converge para $s$ un número complejo con parte real positiva. Para continuar esta función de $s$ a una función compleja meromorfa en otro lugar, se puede emplear el Teorema de Bernstein-Sato : existe un polinomio $b(s)$ y un polinomio (no conmutativo) $D(x_i, \frac{\partial}{\partial x_i}, s)$ , de tal manera que $b(s)p(\mathbf{x})^s = D\cdot p(\mathbf{x})^{s+1}$ . Esto permite ampliar la integral en términos de $p(\mathbf{x})^{s+1}$ pero la nueva integral tiene términos adicionales. Para que una prueba inductiva de la continuación funcione, hay que demostrar que una clase más general de integrales puede ser continuada, a saber, los productos de términos de la forma $p(\mathbf{x})^s$ con polinomios.

Answer 5

Un buen ejercicio es demostrar que la recurrencia $T(x+y)\le T(x)+T(y)+\lg(\min\{x,y\})$ es tal que $T(n)=O(n)$ . (Tenga en cuenta que $\lg$ es log base 2).

La hipótesis de inducción reforzada es $T(n)\le n-\lg n-1$ . Una vez que hemos asumido esto, obtenemos \begin{eqnarray*} T(x+y) & \le & T(x)+T(y)+\lg(\min\{x,y\})\\ & \le & (x-\lg x-1)+(x-\lg y-1)+\lg(\min\{x,y\})\\ & = & (x+y)-\lg(x+y)-1+(\lg(x+y)+\lg(\min\{x,y\})-\lg x-\lg y-1)\\ & = & (x+y)-\lg(x+y)-1+\lg\frac{(x+y)\min\{x,y\}}{2xy}\\ & \le & (x+y)-\lg(x+y)-1. \end{eqnarray*}

La razón por la que me gusta el ejemplo es que parece que el $\text{“}-1\text{''}$ es necesario.