Mi favorito probablemente sería la dualidad de línea de puntos ya mencionada por David Joyce, así que aquí va mi segundo lugar cercano.
Esta es una dualidad fundamental que se manifiesta en muchos lugares diferentes. Es posible que lo haya visto en algunas de las siguientes formas:
- La dualidad entre el programa lineal primario y el dual (Programación lineal: dualidad)
- La dualidad entre el flujo máximo y el corte mínimo en una red de flujo (Teorema de corte mínimo y flujo máximo)
- en gráficos bipartitos, la equivalencia entre coincidencias máximas y cubiertas de vértices mínimas (teorema de König)
- en una matriz 0-1, el número más pequeño de filas y columnas que cubre todos los 1 es el número más grande de 1, de modo que no hay dos que compartan una fila o columna (teorema de König para matrices)
- cualquier matriz doblemente estocástica puede escribirse como una combinación convexa de matrices de permutación (matriz doblemente estocástica)
- conectividad de bordes de un gráfico que se relaciona con el número máximo de caminos de separación de bordes entre dos vértices (teorema de Menger)
- El tamaño del antichain máximo en un poset es igual al tamaño de su partición más pequeña en cadenas (teorema de Dilworth)
- incluso el teorema del matrimonio de Hall es un caso especial de esta dualidad
La parte sorprendente (al menos para mí) fue que originalmente encontré la mayoría de estos resultados por separado, y me llevó un tiempo darme cuenta de que todos son básicamente la misma cosa.
- Cómo resolver problemas matemáticos muy rápido en mi cabeza
- A menudo se dice que las matemáticas son un juego de hombres (y mujeres) y, de hecho, parece que los grandes matemáticos suelen hacer sus primeros descubrimientos importantes a una edad temprana. ¿Es esto realmente cierto, y si es así, a qué edad es el caso de que, si uno aún no ha hecho un gran trabajo, debería aceptar que no están hechos para ser uno de los grandes?
- Matemáticas: ¿se pueden relacionar de alguna manera una topología y un espacio vectorial?
- Cómo demostrar que [matemáticas] \ sqrt {aa '} + \ sqrt {bb'} + \ sqrt {cc '} = \ sqrt {(a + b + c) (a' + b '+ c')} [ /matemáticas]
- ¿Cuáles son algunas de las ecuaciones más importantes que se han formulado?
A veces, la conexión entre estos resultados es bastante obvia; por ejemplo, el teorema de Menger se deduce claramente del teorema de Ford-Fulkerson sobre el flujo máximo. Una de las conexiones menos obvias pero fascinantes es la que existe entre los emparejamientos bipartitos y el teorema de Dilworth. Aquí está con una historia.
Imagina que eres el despachador de una compañía de taxis. Ya conoce todas las solicitudes para esta noche: dónde y cuándo recoger a cada cliente y dónde dejarlos. Ahora viene la pregunta: ¿cuál es el menor número de autos que necesita para satisfacer todas las demandas?
Esta pregunta es una pregunta sobre las cubiertas de ruta en un poset. Las solicitudes individuales son elementos del poset, y el orden parcial “A <B" es la relación "un automóvil puede atender la solicitud A y aún así llegar a tiempo para atender la solicitud B".
Ahora, ambos podemos encontrar el menor número de autos y construir un horario válido usando un algoritmo de tiempo polinómico: al reducir este problema a encontrar una coincidencia máxima en un gráfico bipartito adecuado.
Los vértices en cada partición del gráfico bipartito son las solicitudes. Un borde de izquierda a derecha representa que es posible hacer la solicitud izquierda antes que la derecha usando el mismo automóvil. Claramente, cada programación válida de automóviles produce una coincidencia en este gráfico, y viceversa: cada coincidencia le brinda un horario válido. La coincidencia vacía es el cronograma donde cada solicitud es atendida por un automóvil nuevo. Y cada vez que agrega una ventaja a la coincidencia, reduce la cantidad de automóviles en uno. Por lo tanto, los emparejamientos máximos corresponden precisamente a los horarios con la menor cantidad de autos. (Ejercicio: ¿qué representa una cobertura mínima de vértice en nuestro gráfico?)