En matemáticas, un embalaje en un hypergraph es una partición del conjunto de la hypergraph 's bordes en un número de subconjuntos disjuntos de tal manera que ningún par de bordes en cada acción subconjunto cualquier vértice. Hay dos algoritmos famosos para lograr un empaquetamiento óptimo asintóticamente en hipergráficos uniformes k . Uno de ellos es un algoritmo codicioso aleatorio propuesto por Joel Spencer . Utilizó un proceso de ramificación para probar formalmente el límite óptimo alcanzable en algunas condiciones secundarias. El otro algoritmo se llama Rödl nibble y fue propuesto por Vojtěch Rödlet al. Demostraron que el empaquetamiento alcanzable por el nibble de Rödl es en cierto sentido cercano al del algoritmo codicioso aleatorio.
Historia
El problema de encontrar el número de tales subconjuntos en un hipergrama k -uniforme fue motivado originalmente a través de una conjetura de Paul Erdős y Haim Hanani en 1963. Vojtěch Rödl demostró su conjetura asintóticamente bajo ciertas condiciones en 1985. Pippenger y Joel Spencer generalizaron los resultados de Rödl usando un algoritmo codicioso aleatorio en 1989.
Definición y terminología
En las siguientes definiciones, el hipergráfico se denota por H = ( V , E ). H se llama un hipergrama k -uniforme si cada borde en E consta exactamente de k vértices.
es un empaquetamiento hipergráfico si es un subconjunto de aristas en H de manera que no hay un par de aristas distintas con un vértice común.
es un (,) -buen hipergrafo si existe un tal que para todos y y se cumplen las dos condiciones siguientes.
donde el grado de un vértice es el número de aristas que contienen y el codegree de dos vértices distintos y es el número de aristas que contienen ambos vértices.
Teorema
Existe un empaquetamiento asintótico P de tamaño al menos para -Hipergrama uniforme en las dos condiciones siguientes,
- Todos los vértices tienen el grado de en el cual tiende al infinito.
- Por cada par de vértices solo se comparte bordes comunes.
dónde es el número total de vértices. Este resultado fue mostrado por Pippenger y posteriormente probado por Joel Spencer. Para abordar el problema del empaquetamiento hipergráfico asintótico, Joel Spencer propuso un algoritmo codicioso aleatorio. En este algoritmo, se utiliza un proceso de ramificación como base y se demostró que casi siempre logra un empaquetamiento asintóticamente óptimo en las condiciones laterales anteriores.
Algoritmos de empaquetamiento asintótico
Hay dos algoritmos famosos para el empaquetamiento asintótico de hipergrafías k-uniformes: el algoritmo codicioso aleatorio a través del proceso de ramificación y el mordisco de Rödl.
Algoritmo codicioso aleatorio a través del proceso de ramificación
Cada borde se le asigna de manera independiente y uniforme una "hora de nacimiento" real distinta . Los bordes se toman uno por uno en el orden de sus horas de nacimiento. El borde es aceptado e incluido en si no se superpone a ningún borde aceptado previamente. Obviamente, el subconjunto es un embalaje y se puede demostrar que su tamaño es casi seguro. Para demostrarlo, detengamos el proceso de agregar nuevos bordes a la vez.. Por un arbitrario, elegir tal que para cualquier -buen hipergrafo dónde denota la probabilidad de vértice supervivencia (un vértice sobrevive si no está en ningún borde en ) hasta el momento . Obviamente, en tal situación, el número esperado de sobreviviendo en el tiempo es menos que . Como resultado, la probabilidad de sobrevivir siendo menos que es más alto que . En otras palabras, debe incluir al menos vértices lo que significa que .
Para completar la prueba, se debe demostrar que . Por eso, el comportamiento asintótico dela supervivencia se modela mediante un proceso de ramificación continuo. Reparar y empezar con Eva con la fecha de nacimiento de . Suponga que el tiempo retrocede, por lo que Eva da a luz en el intervalo decon una distribución de Poisson de densidad unitaria . La probabilidad de que Eva tenga el nacimiento es . Condicionando en las horas de nacimiento se distribuyen de forma independiente y uniforme en . Cada nacimiento dado por Eva consiste en todos los descendientes con la misma hora de nacimiento dicen . El proceso se repite para cada descendencia. Se puede demostrar que para todos existe un de modo que con una probabilidad superior a , Eve tiene como mucho descendientes.
Un árbol enraizado con las nociones de padre, hijo, raíz, progenitor y compañero de útero se llamará árbol de cría. Dado un árbol de cría finitodecimos por cada vértice que sobrevive o muere. Sobrevive un vértice sin hijos. Un vértice muere si y solo si tiene al menos una cría, todos los cuales sobreviven. Dejar denotar la probabilidad de que Eva sobreviva en el árbol de cría dado por el proceso anterior. El objetivo es mostrar y luego para cualquier fijo , se puede demostrar que . Estas dos relaciones completan nuestro argumento.
Mostrar , dejar . Para pequeña, como, aproximadamente, una Eva que comienza en el tiempo podría tener un nacimiento en el intervalo de tiempo todos cuyos hijos sobreviven mientras Eva no tiene nacimientos en todos cuyos hijos sobreviven. Dejando produce la ecuación diferencial . El valor inicial da una solución única . Tenga en cuenta que de hecho.
Probar , considere un procedimiento que llamamos Historia que aborta o produce un árbol de cría. La historia contiene un conjunto de vértices, inicialmente . tendrá una estructura de árbol de cría con la raíz. La están procesados o sin procesar, inicialmente no está procesado. A cada se le asigna una hora de nacimiento , inicializamos . La historia es tomar un sin procesary procesarlo de la siguiente manera. Por el valor de todos con pero sin que ya ha sido procesado, si alguna posee y con o algunos tengo con y , se cancela el historial. De lo contrario para cada con añadir todo a como compañeros de útero con los padres y fecha de nacimiento común . Ahorase considera procesado. La historia se detiene, si no se cancela, cuando todosson procesados. Si el historial no se cancela, rootear sobrevive al árbol de cría si y solo si sobrevive en el tiempo . Para un árbol de cría fijo, deje denotar la probabilidad de que el proceso de ramificación produzca un árbol de cría . Entonces, la probabilidad de que la Historia no aborte es. Por la finitud del proceso de ramificación,, la suma de todos los árboles de cría y la Historia no aborta. LaLa distribución de su árbol de cría se aproxima a la distribución del proceso de ramificación. Por lo tanto.
El mordisco de Rödl
En 1985, Rödl demostró la conjetura de Paul Erdős mediante un método llamado Rödl nibble. El resultado de Rödl se puede formular en forma de empaque o problema de recubrimiento. Para el número de cobertura denotado por muestra el tamaño mínimo de una familia de subconjuntos de k elementos de que tienen la propiedad de que cada conjunto de elementos l está contenido en al menos un . Paul Erdős y col. la conjetura fue
- .
dónde . Esta conjetura significa a grandes rasgos que una configuración táctica es alcanzable asintóticamente. Se puede definir de manera similar el número de empaque como el tamaño máximo de una familia de subconjuntos de k elementos de tener la propiedad de que cada conjunto de elementos l está contenido como máximo en uno .
Embalaje en condiciones más fuertes.
En 1997, Noga Alon , Jeong Han Kim y Joel Spencer también ofrecen un buen destino para bajo la condición de codegree más fuerte de que cada par distinto tiene como máximo una ventaja en común.
Para un hipergrama k -uniforme, D -regular en n vértices, si k > 3, existe un empaquetamiento P que cubre todos los vértices pero como máximo. Si k = 3 existe un empaque P que cubre todos los vértices pero como máximo.
Este límite es deseable en varias aplicaciones, como el sistema triple Steiner . Un sistema triple de Steiner es un hipergráfico simple de tres uniformes en el que cada par de vértices está contenido precisamente en un borde. Dado que un sistema triple de Steiner es claramente d = ( n -1) / 2-regular, el límite anterior proporciona la siguiente mejora asintótica.
Cualquier Steiner Triple System en n vértices contiene un empaque que cubre todos los vértices pero como máximo.
Ver también
Referencias
- Erdős, P .; Hanani, H. (1963), "Sobre un teorema del límite en el análisis combinatorio" (PDF) , Publ. Matemáticas. Debrecen , 10 : 10-13.
- Spencer, J. (1995), "Empaquetamiento asintótico mediante un proceso de ramificación", Estructuras y algoritmos aleatorios , 7 (2): 167-172, doi : 10.1002 / rsa.3240070206.
- Alon, N .; Spencer, J. (2008), The Probabilistic Method (3.a ed.), Wiley-Interscience, Nueva York, ISBN 978-0-470-17020-5.
- Rödl, V .; Thoma, L. (1996), "Empaquetamiento asintótico y algoritmo codicioso aleatorio", Estructuras y algoritmos aleatorios , 8 (3): 161-177, CiteSeerX 10.1.1.4.1394 , doi : 10.1002 / (SICI) 1098-2418 ( 199605) 8: 3 <161 :: AID-RSA1> 3.0.CO; 2-W.
- Spencer, J .; Pippenger, N. (1989), "Asymptotic Behavior of the Chromatic", Journal of Combinatorial Theory , Serie A, 51 (1): 24-42, doi : 10.1016 / 0097-3165 (89) 90074-5.
- Alon, N .; Kim, J .; Spencer, J. (1997), "Coincidencias casi perfectas en hipergráficos simples regulares", Israel Journal of Mathematics , 100 (1): 171–187, CiteSeerX 10.1.1.483.6704 , doi : 10.1007 / BF02773639.