En teoría de conjuntos extremales, el teorema de Ahlswede-Khachatrian generaliza el teorema de Erdös-Ko-Rado a familias -intersecantes. Dados los parámetros , y , describe el tamaño máximo de una familia -intersecante de subconjuntos de de tamaño , así como las familias que alcanzan dicho tamaño máximo.
Enunciado Sean parámetros enteros. Una familia -intersecante es una colección de subconjuntos de de tamaño tal que si entonces . Frankl construyó las familias -intersecantes
El teorema de Ahlswede–Khachatrian establece que si es -intersecante, entonces
Además, la igualdad es posible solo si es equivalente a una familia de Frankl, lo que significa que coincide con una de ellas tras permutar las coordenadas.
Más explícitamente, si
(donde se ignora el límite superior cuando ) entonces , dándose la igualdad si y solo si es equivalente a ; y si
entonces , dándose la igualdad si y solo si es equivalente a o a .
Historia
Erdős, Ko y Rado demostraron que si , entonces el tamaño máximo de una familia -intersecante es . Frankl probó que, cuando , se cumple la misma cota para todo , que es ajustada según el ejemplo . Wilson extendió este resultado a todo (utilizando técnicas completamente diferentes).
En cuanto a valores menores de , Erdős, Ko y Rado formularon la conjetura , que establece que cuando , el tamaño máximo de una familia -intersecante es
lo que coincide con el tamaño de la familia de Frankl . Esta conjetura es un caso particular del teorema de Ahlswede-Khachatrian.
Ahlswede y Khachatrian demostraron su teorema de dos formas distintas: utilizando conjuntos generadores y utilizando su dual. Mediante técnicas similares, demostraron posteriormente el teorema de Hilton-Milner correspondiente, que determina el tamaño máximo de una familia con intersección bajo la condición adicional de que ningún elemento esté contenido en todos los conjuntos de la familia.
Resultados relacionados
Versión ponderada El teorema de intersección de Katona determina el tamaño máximo de una familia con intersección de subconjuntos de . Cuando es impar, la única familia óptima consta de todos los conjuntos de tamaño al menos (correspondiente a la función mayorante), y cuando es impar, las únicas familias óptimas consisten en todos los conjuntos cuya intersección con un conjunto fijo de tamaño es al menos (mayorante en las coordenadas ).
Friedgut consideró una generalización del teorema de Katona basada en la teoría de la medida, en la que, en lugar de maximizar el tamaño de la familia con intersección, se maximiza su medida , donde viene dada por la fórmula
La medida corresponde al proceso que elige un subconjunto aleatorio de añadiendo cada elemento con probabilidad de forma independiente.
El teorema de intersección de Katona corresponde al caso . Friedgut consideró el caso . El análogo ponderado del teorema de Erdős–Ko–Rado establece que si es una familia intersecante, entonces para todo , dándose la igualdad si y solo si consiste en todos los conjuntos que contienen un punto fijo. Friedgut demostró el análogo del resultado de Wilson en este contexto: si es -intersecante, entonces para todo , dándose la igualdad si y solo si consiste en todos los conjuntos que contienen puntos fijos. Las técnicas de Friedgut son similares a las de Wilson.
Dinur y Safra, así como Ahlswede y Khachatrian observaron que el teorema de Ahlswede–Khachatrian implica su propia versión ponderada, para todo . Para enunciar la versión ponderada, primero se definen los análogos de las familias de Frankl:
El teorema ponderado de Ahlswede–Khachatrian establece que si es -intersecante, entonces para todo ,
dándose la igualdad solo si es equivalente a una familia de Frankl. Explícitamente, es óptima en el rango
El argumento de Dinur y Safra demuestra este resultado para todo , sin la caracterización de los casos óptimos. La idea principal es que si se toma un subconjunto aleatorio de de tamaño , entonces la distribución de su intersección con tiende a a medida que .
Filmus demostró el teorema de Ahlswede–Khachatrian ponderado para todo utilizando los argumentos originales de Ahlswede y Khachatrian para , y empleando un argumento diferente de Ahlswede y Khachatrian —utilizado originalmente para ofrecer una demostración alternativa del teorema de Katona— para . También demostró que las familias de Frankl son las únicas familias óptimas para todo .
Versión para cadenas Ahlswede y Khachatrian demostraron una versión del teorema de Ahlswede–Khachatrian para cadenas sobre un alfabeto finito. Dado un alfabeto finito , una colección de cadenas de longitud es -intersecante si cualesquiera dos cadenas de la colección coinciden en al menos posiciones. Los análogos de la familia de Frankl en este contexto son
donde es una palabra arbitraria y es el número de posiciones en las que y coinciden.
El teorema de Ahlswede–Khachatrian para cadenas establece que si es -intersecante, entonces
dándose la igualdad si y solo si es equivalente a una familia de Frankl. El teorema se demuestra mediante una reducción al teorema ponderado de Ahlswede–Khachatrian, con .
Referencias
Bibliografía
Categoría:Familias de conjuntos Categoría:Intersección Categoría:Teoremas de la matemática discreta Categoría:Temas factoriales y binomiales