Demostración de los resultados de paridad mediante el lema Handshaking

Question

Me gusta especialmente la siguiente estrategia para demostrar que el número de algunos objetos combinatorios es par: construir un grafo en el que correspondan a vértices de grado impar (=valencia).

Permítanme mencionar tres resultados de esta naturaleza:

1. Si el gráfico $G$ tiene un número par de vértices y todos ellos tienen un grado par, entonces tiene un número par de árboles de expansión. Se puede demostrar utilizando el teorema del árbol matriz, aunque no inmediatamente. Me refiero al siguiente argumento elemental: consideremos el nuevo grafo, en el que los árboles de expansión de $G$ sirven de vértices, y dos árboles $T$ , $T'$ están unidas si difieren en una arista (es decir, todas las aristas de $T$ excepto una arista son también aristas de $T'$ ). A continuación, todos los grados en el nuevo gráfico son impar y hemos terminado.

2. (Este argumento se debe a Andrew Thomason). Dados los vértices $x$ , $y$ en un grafo finito $G$ en el que todos los vértices excepto $x$ , $y$ tienen grado impar (paridad de grados de $x$ y $y$ no importa). Entonces, el número de caminos hamiltonianos de $x$ a $y$ es par. Para demostrarlo, consideremos todas las trayectorias hamiltonianas que comienzan en $y$ en el gráfico $G-x$ . Son los vértices de un nuevo grafo. Une dos caminos de este tipo si difieren en una arista (es decir, todas las aristas del primer camino excepto una son también aristas del segundo). Entonces, el grado de un camino $yz\dots v$ en el nuevo gráfico es uno menos que el grado de $v$ en $G-x$ . Por lo tanto, es impar si $v$ se une a $x$ y los vértices impar de nuestro nuevo grafo corresponden a caminos hamiltonianos desde $x$ a $y$ en $G$ .

3. (Esto se debe a László Lovász). Sea $G=(V,E)$ sea un grafo finito. Llamamos subconjunto $A\subset V$ dominante si cualquier vértice $v\in V\setminus A$ tiene al menos un vecino en $A$ . Entonces cualquier grafo tiene un número impar de conjuntos dominantes. Demostramos que el número de subconjuntos no dominantes no vacíos de $V$ es par. Son vértices de un nuevo grafo, y dos de ellos $B_1,B_2$ están unidas si no hay aristas entre $B_1$ y $B_2$ en $G$ . Todos los grados son impar (grado de $B$ es igual a $2^k-1$ donde $k$ es el número de vértices en $V\subset B$ no unido a $B$ ), y ya hemos terminado de nuevo.

Tengo una pregunta general: ¿cuáles son otros ejemplos de tal sabor? Por supuesto, la demostración de la paridad por partición en pares formalmente es un caso particular (correspondiente a la gráfica con grados 1), y por partición en subconjuntos pares también, pero yo más bien preguntar acerca de los gráficos más involucrados utilizados en la prueba:)

Y una pregunta concreta: ¿puede demostrarse con estas técnicas el resultado de Redei de que cualquier torneo tiene un número impar de trayectorias hamiltonianas?

Answer 1

Otro ejemplo muy famoso es Lema de Sperner . Otros ejemplos son el teorema de Chevalley para $p=2$ , Lema de Tucker , el hecho de que el número de descomposiciones en ciclos hamiltonianos sea par, etc. (Véase el documento que figura a continuación). Los análogos continuos de algunos de ellos también se derivan de las mismas pruebas, por lo que se podría contar el teorema del punto fijo de Brower (a partir del lema de Sperner) y Teorema de Borsuk-Ulam y el Teorema del sándwich de jamón (del lema de Tucker), como se deduce del lema del apretón de manos.

Por otro lado, puede que le interesen las clases de complejidad CCE y PPAD que ofrecen una posible formalización de su pregunta. Hay muchos artículos (en teoría de la complejidad) que estudian estos ejemplos, pero no puedo hacer más comentarios porque no estoy muy familiarizado con la bibliografía. Un punto de partida es el artículo de Christos Papadimitriou (1994), "Sobre la complejidad del argumento de paridad y otras pruebas ineficientes de existencia" . Revista de Informática y Ciencias de Sistemas 48 (3): 498-532. Pensé que esto era relevante ya que mencionas que quieres problemas que puedan ser resueltos por un argumento de paridad pero el grafo involucrado es lo suficientemente complejo como para que no sea fácil exhibir una involución.

Answer 2

Hay un buen artículo de Kathie Cameron y Jack Edmonds, Algunos usos gráficos de un número par de nodos impar con varios ejemplos del uso del lema del apretón de manos para demostrar varios hechos de la teoría de grafos.

Gjergi Zaimi ya mencionó la relevancia de las clases de complejidad PPA y PPAD. Además del artículo de Papadimitriou, este documento de Beame et al. es una referencia útil.

Creo recordar que el Teorema de Chevalley se puede demostrar por este método, pero no puedo reconstruir el argumento, así que tal vez estoy confundido.

Answer 3

El siguiente enigma puede resolverse con la misma técnica. A cordillera es una función lineal a trozos $f$ definida en un intervalo cerrado $[a,b]$ que satisface $f(a)=f(b)=0$ y $f(c) > 0$ para todos $c \in (a,b)$ . Hay excursionistas $A$ en el punto $(a,0)$ y un excursionista $B$ en el punto $(b,0)$ . Los dos excursionistas comienzan a moverse a lo largo de la cordillera, con la única restricción de que deben estar siempre a la misma altura. Demuestra que $A$ y $B$ siempre pueden encontrarse en algún punto de la cordillera.

Hablando un poco más en serio, recuerdo vagamente que la existencia de equilibrios de Nash puede demostrarse mediante un argumento de paridad (a través del lema de Sperner).