stringtranslate.com

Número de turán

En matemáticas, el número de Turán T( n , k , r ) para hipergrafos r -uniformes de orden n es el número más pequeño de r -aristas tales que cada subgrafo inducido en k vértices contiene una arista. Este número fue determinado para r  = 2 por Turán (1941), y el problema para r general fue introducido en Turán (1961). El artículo (Sidorenko 1995) ofrece un estudio de los números de Turán.

Definiciones

Fijemos un conjunto X de n vértices. Para un valor dado de r , una arista o bloque de r es un conjunto de r vértices. Un conjunto de bloques se denomina sistema de Turán ( n , k , r ) ( nkr ) si cada subconjunto de elementos k de X contiene un bloque. El número de Turán T( n , k , r ) es el tamaño mínimo de un sistema de este tipo.

Ejemplo

Los complementos de las rectas del plano de Fano forman un sistema de Turán (7,5,4). T(7,5,4) = 7. [1]

Relaciones con otros diseños combinatorios

Se puede demostrar que

La igualdad se cumple si y sólo si existe un sistema de Steiner S( n - k , n - r , n ). [2]

Un diseño de ( n , r , k , r )-lotto es un sistema ( n , k , r )-Turán. Por lo tanto, T( n , k , r ) = L( n , r , k , r ). [3]

Véase también

Referencias

  1. ^ Colbourn y Dinitz 2007, pág. 649, Ejemplo 61.3
  2. ^ Colbourn y Dinitz 2007, pág. 649, Observación 61.4
  3. ^ Colbourn y Dinitz 2007, pág. 513, Proposición 32.12

Bibliografía