Temas interesantes y accesibles de la teoría de grafos

Question

Este verano, impartiré un curso de introducción a la teoría de grafos a estudiantes de último año de secundaria con talento. La intención del curso no es establecer la competencia en la teoría de grafos, per se. Más bien, espero utilizar la teoría de grafos como vehículo para transmitir una sensación de desarrollo de las matemáticas "avanzadas" (recordemos que estos estudiantes habrán visto el cálculo de primer año, en el mejor de los casos).

¿Cuáles son tus fragmentos favoritos de la teoría de grafos, interesantes y accesibles?

"Interesante" puede significar que el tema tiene una aplicación especialmente útil en el mundo real o que es un resultado teórico sorprendente o elegante. Una ventaja añadida sería si el tema puede revelar lagunas en nuestro conocimiento colectivo (por ejemplo, aún no se conocen con exactitud los pequeños números de Ramsey). "Accesible" significa que un estudiante brillante y motivado sin conocimientos de combinatoria puede seguir el desarrollo del tema desde el principio, aunque le lleve varias clases.

Answer 1

He comprobado que el Problema de la galería de arte atrae a los estudiantes de secundaria y preparatoria, y conduce rápidamente a lo desconocido, lo que en sí mismo puede ser revelador para los estudiantes. (Sobre este último punto, los estudiantes tienden a pensar en las matemáticas como algo establecido, por lo que es agradable para ellos llegar a problemas no resueltos que puedan comprender, que abundan en la interfaz entre la geometría y la teoría de grafos). Demostrar el tradicional teorema de la galería de arte (que $\lfloor n/3 \rfloor$ Los guardias son suficientes y a veces son necesarios para cubrir un $n$ -galería de paredes) introduce las triangulaciones y el número cromático de un grafo. Hay muchas fuentes, incluido el reciente libro (si se me permite la autopromoción) Geometría discreta y computacional .

               

Adenda. Me permito recomendar también " Cómo vigilar una galería de arte y otras aventuras matemáticas discretas ", de T.S. Michael, a quien tuve el placer de enseñar dos décadas antes de que se publicara su libro publicado.

Answer 2

Teoría de la correspondencia. Esto incluye el teorema del matrimonio de Hall, el teorema de Tutte y el teorema del emparejamiento estable de Gale-Sharpley.

Una de las razones para enseñar esta asignatura a los estudiantes de grado es que cambia la forma de pensar de los matemáticos sobre los algoritmos. Los algoritmos estándar que se aprenden en la escuela secundaria y en los estudios de grado (algoritmo de Dijkstra, quicksort y similares, etc. ) son generalmente despreciados por los matemáticos, ya que (1) parecen ser sólo métodos particularmente eficientes para calcular algunos objetos que ya están claros que existen, (2) suelen ser de baja complejidad (mucho menor que la de las pruebas en las matemáticas de pregrado), (3) no añaden ningún valor teórico (de hecho lo hacen, pero el contenido algorítmico en las pruebas matemáticas es a menudo hábilmente ocultado por quien escribe la prueba, por lo que parece que no lo hacen). Por el contrario, el algoritmo de emparejamiento perfecto (mediante el uso de caminos de aumento) y el algoritmo de Gale-Sharpley son bastante no triviales y, de hecho, son componentes importantes en las pruebas de la existencia de emparejamientos perfectos rsp. emparejamientos estables.

Answer 3

Dualidad de grafos planos. Por ejemplo, los hechos de que

• Un conjunto de aristas forma un subgrafo conexo de un grafo plano G si y sólo si el conjunto complementario de aristas forma un subgrafo acíclico del dual, y viceversa.
• Dado que los árboles de extensión son sólo subgrafos acíclicos conectados, se deduce que un subgrafo es un árbol si y sólo si su complemento es dual a un árbol. La fórmula de Euler se deduce inmediatamente.
• Las aristas que no están en el árbol de expansión mínima de un grafo plano G son los duales de las aristas que están en el árbol de expansión máxima de su dual.
• Un gráfico plano es bipartito si y sólo si su dual es euleriano.
• Un grafo plano es de 3 conexiones (poliédrico) si y sólo si su dual lo es.
• El matroide gráfico de un grafo plano es el dual del matroide gráfico del grafo dual. Los grafos planos son los únicos grafos para los que el dual del matroide gráfico es también gráfico.
• Un grafo plano dirigido es acíclico si y sólo si su grafo dual (con las aristas duales orientadas 90 grados en el sentido de las agujas del reloj respecto a las primarias) está fuertemente conectado.

Answer 4

Un problema que me pareció bastante interesante es el Problema de Hadwiger-Nelson para colorear el plano. Las pruebas de que la respuesta es como máximo $7$ y al menos $4$ son fáciles y elegantes (pero también bastante diferentes), y tiene la ventaja añadida de que es un problema abierto.

Edición: Ahora se sabe que el número cromático es al menos 5 .

Answer 5

El " $-1$ colores". Esto permite hablar de coloración, de polinomios cromáticos, y (por ejemplo) de arreglos de hiperplanos, sus cámaras y demás (el libro de Orlik+Terao sobre arreglos de hiperplanos tiene los detalles)

Hacer todo en detalle es un poco de trabajo, pero probablemente no lo necesites.

Todos los que aprecian las bellas matemáticas deberían caer en esto.