Coincidencia perfecta en hipergrafos de alto grado

Área de investigación en matemáticas (teoría de grafos)

En teoría de grafos , el emparejamiento perfecto en hipergrafos de alto grado es una línea de investigación que intenta encontrar condiciones suficientes para la existencia de un emparejamiento perfecto en un hipergrafo , basándose únicamente en el grado de los vértices o subconjuntos de ellos.

Introducción

Grados y correspondencias en gráficos

En un gráfico simple G = ( V , E ) , el grado de un vértice v , a menudo denotado por deg( v ) o δ( v ) , es el número de aristas en E adyacentes a v . El grado mínimo de un gráfico, a menudo denotado por deg( G ) o δ( v ) , es el mínimo de deg( v ) sobre todos los vértices v en V .

Un emparejamiento en un grafo es un conjunto de aristas tal que cada vértice es adyacente a, como máximo, una arista; un emparejamiento perfecto es un emparejamiento en el que cada vértice es adyacente a exactamente una arista. Un emparejamiento perfecto no siempre existe, por lo que es interesante encontrar condiciones suficientes que garanticen su existencia.

Una de esas condiciones se desprende del teorema de Dirac sobre ciclos hamiltonianos . Dice que, si deg( G ) ≥ n ⁄ 2 , entonces el grafo admite un ciclo hamiltoniano ; esto implica que admite un emparejamiento perfecto. El factor n ⁄ 2 es estricto, ya que el grafo bipartito completo sobre ( n ⁄ 2 – 1, n ⁄ 2 + 1) vértices tiene grado n ⁄ 2 – 1 pero no admite un emparejamiento perfecto.

Los resultados que se describen a continuación tienen como objetivo ampliar estos resultados de gráficos a hipergráficos .

Grados en hipergrafos

En un hipergrafo H = ( V , E) , cada arista de E puede contener más de dos vértices de V . El grado de un vértice v en V es, como antes, el número de aristas en E que contienen a v . Pero en un hipergrafo también podemos considerar el grado de subconjuntos de vértices: dado un subconjunto U de V , deg( U ) es el número de aristas en E que contienen todos los vértices de U . Por lo tanto, el grado de un hipergrafo puede definirse de diferentes maneras dependiendo del tamaño de los subconjuntos cuyo grado se considera.

Formalmente, para cada entero d ≥ 1 , deg _d ( H ) es el mínimo de deg( U ) sobre todos los subconjuntos U de V que contienen exactamente d vértices. Por lo tanto, deg ₁ ( H ) corresponde a la definición de un grado de un grafo simple, es decir, el grado más pequeño de un solo vértice; deg ₂ ( H ) es el grado más pequeño de un par de vértices; etc.

Un hipergrafo H = ( V , E ) se llama r -uniforme si cada hiperarista en E contiene exactamente r vértices de V . En grafos r -uniformes, los valores relevantes de d son 1, 2, … , r – 1 . En un grafo simple, r = 2 .

Condiciones en grado de 1 vértice

Varios autores han demostrado condiciones suficientes para el caso d = 1 , es decir, condiciones sobre el menor grado de un solo vértice.

• Si H es un hipergrafo 3-uniforme en n vértices, n es un múltiplo de 3, y

  ${\displaystyle \deg _{1}(H)\geq {\bigg (}5/9+o(1){\bigg )}{n \choose 2},}$

  Entonces H contiene una coincidencia perfecta. ^[1]

• Si H es un hipergrafo 3-uniforme en n vértices, n es un múltiplo de 3, y

  ${\displaystyle \deg _{1}(H)\geq {n-1 \choose 2}-{2n/3 \choose 2}+1,}$

  Entonces H contiene una correspondencia perfecta, una correspondencia de tamaño k . Este resultado es el mejor posible. ^[2]

• Si H es un hipergrafo 4-uniforme con n vértices, n es un múltiplo de 4, y

  ${\displaystyle \deg _{1}(H)\geq {n-1 \choose 3}-{3n/4 \choose 3},}$

  Entonces H contiene una correspondencia perfecta, una correspondencia de tamaño k . Este resultado es el mejor posible. ^[3]

• Si H es r -uniforme, n es un múltiplo de r , y

  ${\displaystyle \deg _{1}(H)>{\frac {r-1}{r}}\left({{\binom {n-1}{r-1}}-{\binom {n-kr-1}{r-1}}}\right),}$

  entonces H contiene una correspondencia de tamaño al menos k + 1. En particular, al establecer k = n ⁄ r – 1 se obtiene que, si

  ${\displaystyle \deg _{1}(H)>{\frac {r-1}{r}}\left({{\binom {n-1}{r-1}}-1}\right),}$

  Entonces H contiene una correspondencia perfecta. ^[4]

• Si H es r -uniforme y r -partito, cada lado contiene exactamente n vértices, y

  ${\displaystyle \deg _{1}(H)>{\frac {r-1}{r}}\left({n^{r-1}-(n-k)^{r-1}}\right),}$

  entonces H contiene una correspondencia de tamaño al menos k + 1. En particular, al establecer k = n – 1 se obtiene que si

  ${\displaystyle \deg _{1}(H)>{\frac {r-1}{r}}\left({n^{r-1}-1}\right),}$

  Entonces H contiene una coincidencia perfecta. ^[4]

A modo de comparación, el teorema de Dirac sobre los ciclos hamiltonianos dice que, si H es 2-uniforme (es decir, un gráfico simple) y

${\displaystyle \deg _{1}(H)\geq {n-1 \choose 1}-{n/2 \choose 1}+1=n/2,}$

Entonces H admite una correspondencia perfecta.

Condiciones de grado (r-1)-tupla

Varios autores han demostrado condiciones suficientes para el caso d = r – 1 , es decir, condiciones sobre el menor grado de conjuntos de r – 1 vértices, en hipergrafos r -uniformes con n vértices.

Ena-partidoa-hipergrafos uniformes

Los siguientes resultados se relacionan con hipergrafos r -partitos que tienen exactamente n vértices en cada lado ( rn vértices en total):

• Si ${\displaystyle \deg _{r-1}(H)\geq n/2+{\sqrt {2n\log _{2}n}}}$

  y n ≥ 1000 , entonces H tiene una correspondencia perfecta. Esta expresión es la más pequeña posible hasta el término de orden inferior; en particular, n ⁄ 2 no es suficiente. ^[5]

• Si ${\displaystyle \deg _{r-1}(H)\geq n/r}$

  entonces H admite una correspondencia que cubre todos los vértices excepto como máximo r – 2 en cada clase de vértice de H. El factor n ⁄ r es esencialmente el mejor posible. ^[5]

• Sean V ₁ , … , V _r los lados r de H . Si el grado de cada ( r – 1) -tupla en V ⁄ V ₁ es estrictamente mayor que n ⁄ 2 , y el grado de cada ( r – 1) -tupla en V ⁄ V _r es al menos n ⁄ 2 , entonces H admite un emparejamiento perfecto. ^[6]

En generala-hipergrafos uniformes

• Para cada γ > 0 , cuando n es suficientemente grande, si

  ${\displaystyle \deg _{r-1}(H)\geq (1/2+\gamma )n}$

  Entonces H es hamiltoniano y, por lo tanto, contiene una correspondencia perfecta. ^[7]

• Si ${\displaystyle \deg _{r-1}(H)\geq n/2+3r^{2}{\sqrt {n\log _{2}n}}}$

  y n es suficientemente grande, entonces H admite un emparejamiento perfecto. ^[5]

• Si ${\displaystyle \deg _{r-1}(H)\geq n/r+3r^{2}{\sqrt {n\log _{2}n}},}$

  Entonces H admite una correspondencia que cubre todos los vértices excepto como máximo 2 r ² . ^[5]

• Cuando n es divisible por r y suficientemente grande, el umbral es

  ${\displaystyle \deg _{r-1}(H)\geq n/2-r+c_{k,n}}$

  donde c _{k , n} es una constante que depende de la paridad de n y k (todas las expresiones siguientes son las mejores posibles): ^[8]

  • 3 cuando r ⁄ 2 es par y n ⁄ r es impar;
  • 5 ⁄ 2 cuando r es impar y ( n -1) ⁄ 2 es impar;
  • 3 ⁄ 2 cuando r es impar y ( n -1) ⁄ 2 es par;
  • 2 de lo contrario.
• Cuando n no es divisible por r , el grado suficiente es cercano a n ⁄ r : si deg _{r -1} ( H ) ≥ n ⁄ r + O (log( n )) , entonces H admite un emparejamiento perfecto. La expresión es casi la más pequeña posible: el más pequeño posible es ⌊ n ⁄ r ⌋ . ^[8]

Otras condiciones

Existen algunas condiciones suficientes para otros valores de d :

• Para todo d ≥ r ⁄ 2 , el umbral para deg _d ( H ) está cerca de: ^[9]

  ${\displaystyle \left({\frac {1}{2}}+o(1)\right){\binom {n}{r-d}}.}$

• Para todo d < r ⁄ 2 , el umbral para deg _d ( H ) es como máximo: ^[1]

  ${\displaystyle \left({\frac {r-d}{r}}+o(1)\right){\binom {n-d}{r-d}}}$

• Si H es r -partito y cada lado contiene exactamente n vértices, y

  ${\displaystyle \deg _{d}(H)\geq {\frac {r-d}{r}}n^{r-d}+rn^{r-d-1},}$

  entonces H contiene una correspondencia que cubre todos los vértices excepto ( d – 1) r . ^[1]

• Si n es suficientemente grande y divisible por r , y

  ${\displaystyle \deg _{d}(H)\geq {\frac {r-d}{r}}{\binom {n}{r-d}}+r^{r+1}(\ln {n})^{1/2}n^{r-d-1/2},}$

  entonces H contiene una correspondencia que cubre todos los vértices excepto ( d – 1) r . ^[1]

Véase también

• Teoremas de tipo Hall para hipergrafos : enumera otras condiciones suficientes para la existencia de emparejamientos perfectos en hipergrafos, análogos al teorema del matrimonio de Hall.

Referencias

1. Hàn, Hip; Person, Yury; Schacht, Mathias (1 de enero de 2009). "Sobre emparejamientos perfectos en hipergrafos uniformes con un grado de vértice mínimo grande". Revista SIAM de Matemáticas Discretas . 23 (2): 732–748. doi :10.1137/080729657. ISSN  0895-4801.
2. Khan, Imdadullah (1 de enero de 2013). "Emparejamientos perfectos en hipergrafos 3-uniformes con gran grado de vértice". Revista SIAM de Matemáticas Discretas . 27 (2): 1021–1039. doi :10.1137/10080796X. ISSN  0895-4801. S2CID  18434210.
3. Khan, Imdadullah (1 de enero de 2016). "Emparejamientos perfectos en hipergrafos 4-uniformes". Revista de teoría combinatoria, serie B. 116 : 333–366. arXiv : 1101.5675 . doi : 10.1016 /j.jctb.2015.09.005 . ISSN  0095-8956.
4. Daykin, David E.; Häggkvist, Roland (1981-02-01). "Grados que dan aristas independientes en un hipergrafo". Boletín de la Sociedad Matemática Australiana . 23 (1): 103–109. doi : 10.1017/S0004972700006924 . ISSN  1755-1633.
5. Kühn, Daniela; Osthus, Deryk (2006). "Matchings in hypergraphs of large minimum degree". Revista de teoría de grafos . 51 (4): 269–280. doi :10.1002/jgt.20139. ISSN  1097-0118. S2CID  6769560.
6. Aharoni, Ron; Georgakopoulos, Agelos; Sprüssel, Philipp (1 de enero de 2009). "Emparejamientos perfectos en grafos r-partitos". Revista Europea de Combinatoria . 30 (1): 39–42. arXiv : 0911.4008 . doi :10.1016/j.ejc.2008.02.011. ISSN  0195-6698. S2CID  1092170.
7. Rödl, Vojtěch; Szemerédi, Endre; Ruciński, Andrzej (1 de marzo de 2008). "Un teorema aproximado de tipo Dirac para k-hipergrafos uniformes". Combinatoria . 28 (2): 229–260. doi :10.1007/s00493-008-2295-z. ISSN  1439-6912. S2CID  5799411.
8. Rödl, Vojtech; Ruciński, Andrzej; Szemerédi, Endre (1 de abril de 2009). "Emparejamientos perfectos en hipergrafos uniformes grandes con un grado colectivo mínimo grande". Journal of Combinatorial Theory, Serie A . 116 (3): 613–636. doi : 10.1016/j.jcta.2008.10.002 . ISSN  0097-3165.
9. Pikhurko, Oleg (1 de septiembre de 2008). "Emparejamientos perfectos y teselados K ​​4 3 en hipergrafos de gran grado de código". Graphs and Combinatorics . 24 (4): 391–404. doi :10.1007/s00373-008-0787-7. ISSN  0911-0119. S2CID  29248979.