Empaquetado en un hipergrafo

En matemáticas, un empaquetamiento en un hipergrafo es una partición del conjunto de las aristas del hipergrafo en un número de subconjuntos disjuntos tales que ningún par de aristas en cada subconjunto comparte ningún vértice. Hay dos algoritmos famosos para lograr un empaquetamiento asintóticamente óptimo en hipergrafos k -uniformes. Uno de ellos es un algoritmo aleatorio voraz que fue propuesto por Joel Spencer . Utilizó un proceso de ramificación para demostrar formalmente el límite óptimo alcanzable bajo algunas condiciones laterales. El otro algoritmo se llama nibble de Rödl y fue propuesto por Vojtěch Rödl et al. Demostraron que el empaquetamiento alcanzable por el nibble de Rödl es en cierto sentido cercano al del algoritmo aleatorio voraz.

El problema de encontrar el número de tales subconjuntos en un hipergrafo 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 aleatorio codicioso en 1989.

En las siguientes definiciones, el hipergrafo se denota por H = ( V , E ). H se llama hipergrafo k -uniforme si cada arista en E consta de exactamente k vértices.

${\estilo de visualización P}$es un empaquetamiento de hipergrafos si es un subconjunto de aristas en H tal que no hay ningún par de aristas distintas con un vértice común.

${\estilo de visualización H}$es un hipergrafo ( , )-bueno${\estilo de visualización D_{0}}$${\displaystyle \épsilon}$ si existe un tal que para todos y y se cumplen ambas condiciones siguientes. ${\estilo de visualización D_{0}}$${\displaystyle x,y\en V}$${\displaystyle D\geq D_{0}}$

${\displaystyle D(1-\epsilon )\leq {\text{grados}}(x)\leq D(1+\epsilon )}$

${\displaystyle {\text{código}}(x,y)\leq \epsilon D}$

donde el grado de un vértice es el número de aristas que contiene y el grado de código de dos vértices distintos y es el número de aristas que contienen ambos vértices. ${\displaystyle {\text{grados}}(x)}$${\estilo de visualización x}$${\estilo de visualización x}$ ${\displaystyle {\text{código}}(x,y)}$${\estilo de visualización x}$${\estilo de visualización y}$

Existe un empaquetamiento asintótico P de tamaño al menos para un hipergrafo -uniforme bajo las dos condiciones siguientes, ${\displaystyle {\frac {n}{K+1}}(1-o(1))}$${\estilo de visualización (K+1)}$

1. Todos los vértices tienen el grado de en el cual tiende a infinito.${\displaystyle D(1+o(1))}$${\estilo de visualización D}$
2. Porque cada par de vértices comparte sólo aristas comunes.${\displaystyle o(D)}$

donde es el número total de vértices. Este resultado fue demostrado por Pippenger y luego fue probado por Joel Spencer. Para abordar el problema de empaquetamiento asintótico de hipergrafos, Joel Spencer propuso un algoritmo aleatorio voraz. En este algoritmo, se utiliza un proceso de ramificación como base y se demostró que casi siempre logra un empaquetamiento asintóticamente óptimo bajo las condiciones laterales anteriores. ${\estilo de visualización n}$

Hay dos algoritmos famosos para el empaquetamiento asintótico de hipergrafos k-uniformes: el algoritmo aleatorio voraz mediante un proceso de ramificación y el nibble de Rödl.

Cada arista se asigna de forma independiente y uniforme a un "momento de nacimiento" real distinto . Las aristas se toman una por una en el orden de sus momentos de nacimiento. La arista se acepta y se incluye si no se superpone a ninguna arista previamente aceptada. Obviamente, el subconjunto es un empaquetamiento y se puede demostrar que su tamaño es casi con seguridad. Para demostrarlo, detengamos el proceso de agregar nuevas aristas en el momento . Para un , elija tal que para cualquier hipergrafo -bueno donde denota la probabilidad de supervivencia de un vértice (un vértice sobrevive si no está en ninguna arista en ) hasta el momento . Obviamente, en tal situación, el número esperado de sobrevivientes en el momento es menor que . Como resultado, la probabilidad de sobrevivir siendo menor que es mayor que . En otras palabras, debe incluir al menos vértices lo que significa que . ${\displaystyle E\en H}$${\displaystyle t_{E}\en [0,D]}$${\estilo de visualización E}$${\estilo de visualización P}$${\estilo de visualización P}$${\displaystyle |P|={\frac {n}{K+1}}}$${\estilo de visualización c}$${\displaystyle \gamma >0}$${\displaystyle c,D_{0},\epsilon }$${\displaystyle (D_{0},\epsilon )}$${\displaystyle f_{x,H}(c)<\gamma ^{2}}$${\displaystyle f_{x,H}(c)}$${\estilo de visualización x}$${\estilo de visualización P}$${\estilo de visualización c}$${\estilo de visualización x}$${\estilo de visualización c}$$Estilo de visualización: gamma ^{2}n$${\estilo de visualización x}$${\displaystyle \gamma n}$${\estilo de visualización 1-\gamma}$$Estilo de visualización P_{c}$${\displaystyle (1-\gamma )n}$${\displaystyle |P|\geq (1-\gamma ){\frac {n}{K+1}}}$

Para completar la prueba, debe demostrarse que . Para ello, el comportamiento asintótico de la supervivencia se modela mediante un proceso de ramificación continua. Fijemos y comencemos con Eva con la fecha de nacimiento de . Supongamos que el tiempo va hacia atrás, de modo que Eva da a luz en el intervalo de con una distribución de Poisson de densidad unitaria . La probabilidad de que Eva tenga un nacimiento es . Al condicionar que las horas de nacimiento se distribuyen de forma independiente y uniforme en . Cada nacimiento dado por Eva consta de descendientes todos con la misma hora de nacimiento, digamos . El proceso se itera para cada descendencia. Se puede demostrar que para todos existe un de modo que con una probabilidad mayor que , Eva tiene como máximo descendientes. ${\displaystyle \lim_{c\rightarrow \infty}\lim_{x,H}f_{x,H}(c)=0}$${\estilo de visualización x}$${\displaystyle c>0}$${\estilo de visualización c}$${\displaystyle [0,c)}$${\estilo de visualización k}$${\displaystyle {\frac {e^{-c}c^{k}}{k!}}}$${\estilo de visualización k}$${\displaystyle x_{1},...,x_{k}}$${\displaystyle [0,c)}$${\estilo de visualización Q}$${\estilo de visualización a}$${\displaystyle \epsilon >0}$${\estilo de visualización K}$${\displaystyle (1-\epsilon )}$${\estilo de visualización K}$

Un árbol enraizado con las nociones de padre, hijo, raíz, orden de nacimiento y compañera de útero se llamará árbol de cría. Dado un árbol de cría finito, decimos para cada vértice que sobrevive o muere. Un vértice sin hijos sobrevive. Un vértice muere si y solo si tiene al menos una cría, todas las cuales sobreviven. Sea 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 mostrar que . Estas dos relaciones completan nuestro argumento. ${\estilo de visualización T}$${\estilo de visualización f(c)}$${\estilo de visualización T}$${\displaystyle \lim _{c\rightarrow \infty }f(c)=0}$${\estilo de visualización c}$${\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}$

Para demostrar , sea . Para valores pequeños, como, aproximadamente, una Eva que comienza en el tiempo podría tener un nacimiento en el intervalo de tiempo en el que todos sus hijos sobreviven, mientras que Eva no tiene nacimientos en en el que todos sus hijos sobreviven. Si se deja , se obtiene la ecuación diferencial . El valor inicial da una solución única . Nótese que, de hecho , . ${\displaystyle f(c)=0}$${\displaystyle c\geq 0,\Delta c>0}$${\displaystyle \Delta c}$${\displaystyle f(c+\Delta c)-f(c)\approx -(\Delta c)f(c)^{Q+1}}$${\displaystyle c+\Delta c}$${\displaystyle [c,c+\Delta c)}$${\displaystyle [0,c)}$${\displaystyle \Delta c\rightarrow 0}$${\displaystyle f'(c)=-f(c)^{Q+1}}$${\displaystyle f(0)=1}$${\displaystyle f(c)=(1+Qc)^{-1/Q}}$${\displaystyle \lim _{c\rightarrow \infty }f(c)=0}$

Para demostrar , considere un procedimiento que llamamos Historia que aborta o produce un árbol de cría. Historia contiene un conjunto de vértices, inicialmente . tendrá una estructura de árbol de cría con la raíz. Los son procesados ​​o no procesados, inicialmente no se procesa. A cada uno se le asigna una hora de nacimiento , inicializamos . Historia es tomar un no procesado y procesarlo de la siguiente manera. Para el valor de todos con pero con ninguno que ya se ha procesado, si alguno tiene y con o algunos tienen con y , entonces Historia se aborta. De lo contrario para cada con agregar todos a como compañeros de útero con padre y fecha de nacimiento común . Ahora se considera procesado. Historia se detiene, si no se aborta, cuando todos se procesan. Si Historia no aborta, entonces raíz sobrevive árbol de cría si y solo si sobrevive en el momento . Para un árbol de cría fijo, sea la probabilidad de que el proceso de ramificación produzca árbol de cría . Entonces la probabilidad de que Historia no aborte es . Debido a la finitud del proceso de ramificación, , la suma de todos los árboles de cría y la historia no se anula. La distribución de su árbol de cría se aproxima a la distribución del proceso de ramificación. Por lo tanto . ${\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}$${\estilo de visualización T}$${\displaystyle T=\{x\}}$${\displaystyle T}$${\displaystyle x}$${\displaystyle y\in T}$${\displaystyle x}$${\displaystyle y\in T}$${\displaystyle t_{y}}$${\displaystyle t_{x}=c}$${\displaystyle y\in T}$${\displaystyle t_{E}}$${\displaystyle y\in E}$${\displaystyle x\in E}$${\displaystyle E}$${\displaystyle t_{E}<t_{y}}$${\displaystyle y,z\in E}$${\displaystyle z\in T}$${\displaystyle E,E'}$${\displaystyle t_{E},t_{E'}<t_{y}}$${\displaystyle y\in E,E'}$${\displaystyle |E\cup E'|>1}$${\displaystyle E}$${\displaystyle t_{E}<t_{y}}$${\displaystyle z\in E-\{y\}}$${\displaystyle T}$${\displaystyle y}$${\displaystyle t_{E}}$${\displaystyle y}$${\displaystyle y\in T}$${\displaystyle x}$${\displaystyle T}$${\displaystyle x}$${\displaystyle c}$${\displaystyle f(T,c)}$${\displaystyle T}$${\displaystyle f(T,c)}$${\displaystyle \sum f(T,c)=1}$${\displaystyle T}$${\displaystyle lim^{*}}$${\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}$

En 1985, Rödl demostró la conjetura de Paul Erdős mediante un método llamado el nibble de Rödl. El resultado de Rödl puede formularse en forma de problema de empaquetamiento o de cubrimiento. Para el número de cubrimiento denotado por muestra el tamaño mínimo de una familia de subconjuntos de elementos de los cuales tienen la propiedad de que cada conjunto de elementos está contenido en al menos un . La conjetura de Paul Erdős et al. fue ${\displaystyle 2\leq l<k<n}$${\displaystyle M(n,k,l)}$${\displaystyle \kappa }$${\displaystyle k}$${\displaystyle \{1,...,n\}}$${\displaystyle l}$${\displaystyle A\in \kappa }$

${\displaystyle \lim _{n\rightarrow \infty }{\frac {M(n,k,l)}{{n \choose l}/{k \choose l}}}=1}$.

donde . Esta conjetura significa aproximadamente que una configuración táctica es alcanzable asintóticamente. De manera similar, se puede definir el número de empaquetamiento como el tamaño máximo de una familia de subconjuntos de elementos que tienen la propiedad de que cada conjunto de elementos está contenido en, como máximo, uno . ${\displaystyle 2\leq l<k}$${\displaystyle m(n,k,l)}$${\displaystyle \kappa }$${\displaystyle k}$${\displaystyle \{1,...,n\}}$${\displaystyle l}$${\displaystyle A\in \kappa }$

En 1997, Noga Alon , Jeong Han Kim y Joel Spencer también proporcionan un buen límite para la condición de grado de código más fuerte de que cada par distinto tiene como máximo un borde en común. ${\displaystyle \gamma }$${\displaystyle v,v'\in V}$

Para un hipergrafo 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 empaquetamiento P que cubre todos los vértices pero como máximo . ${\displaystyle O(nD^{-1/(k-1)})}$${\displaystyle O(nD^{-1/2}\ln ^{3/2}D)}$

Este límite es deseable en varias aplicaciones, como el sistema triple de Steiner . Un sistema triple de Steiner es un hipergrafo simple, 3-uniforme, en el que cada par de vértices está contenido precisamente en una arista. 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 sistema triple de Steiner en n vértices contiene un empaquetamiento que cubre todos los vértices pero como máximo . ${\displaystyle O(n^{1/2}\ln ^{3/2}n)}$

Esto ha mejorado posteriormente a ^[1] y ^[2].${\displaystyle n/3-O({\frac {\log n}{\log \log n}})}$${\displaystyle {\frac {n-4}{3}}}$

• Proceso de ramificación
• Conjunto independiente
• Coloración de gráficos
• Número de cubierta
• Conjunto de embalaje
• Teorema de Ramsey
• Problema con la cubierta del conjunto
• Empaquetado de esferas
• Sistema Steiner