Ancho de un hipergrafo

En teoría de grafos , existen dos propiedades relacionadas de un hipergrafo que se denominan su "anchura". Dado un hipergrafo H = ( V , E ), decimos que un conjunto K de aristas fija otro conjunto F de aristas si cada arista en F interseca alguna arista en K. ^{[ 1 ]} Entonces :

• El ancho de H , denotado w( H ), es el tamaño más pequeño de un subconjunto de E que fija a E. ^{[ 2 ]}
• El ancho de emparejamiento ^de H , denotado mw( H ), es el máximo, sobre todos los emparejamientos M en H , del tamaño mínimo de un subconjunto de E que fija M. [ ^{3 ]}

Dado que E contiene todos los emparejamientos en E , para todo H : w( H ) ≥ mw( H ).

El ancho de un hipergrafo se utiliza en teoremas de tipo Hall para hipergrafos .

Sea H el hipergrafo con conjunto de vértices V = {A,B; a,b} y conjunto de aristas:

E = { {A,a}, {B,b}, {A,b}, {B,a} }

Los anchos de H son:

• w( H ) = 2, ya que E está fijado por el conjunto { {A,a}, {B,b} }, y no puede ser fijado por ningún conjunto más pequeño.
• mw( H ) = 1, ya que cada emparejamiento puede ser fijado por una sola arista. Hay dos emparejamientos: {{A,a}, {B,b}} está fijado, por ejemplo, por { {A,b} }, y { {A,b}, {B,a} } está fijado, por ejemplo, por { {A, a} }.

El grafo de disyunción de H , denotado D( H ), es un grafo donde cada arista en H es un vértice en D( H ), y cada dos aristas disjuntas en H son adyacentes en D( H ). Los emparejamientos en H corresponden a las camarillas en D( H ). Meshulam ^{[ 2 ]} caracterizó las anchuras de un hipergrafo H en términos de las propiedades de D( H ). Para cualquier entero positivo r :

• w( H ) > r si y solo si D( H ) satisface una propiedad llamada P( r ,∞), lo que significa que cada conjunto de r vértices en D( H ) tiene un vecino común. Esto se debe a que w( H ) > r si y solo si H no tiene un conjunto de anclaje de tamaño r , si y solo si para cada subconjunto de r aristas de H hay una arista que no está anclada por él, si y solo si cada subconjunto de r aristas de H tiene un vecino común en D( H ).
• mw( H ) > r si y solo si D( H ) satisface una propiedad llamada P( r ,0), lo que significa que cada conjunto de r vértices en D( H ) tiene un vecino común, y además, hay una camarilla C en D( H ) que contiene un vecino común de cada uno de esos conjuntos.

El grafo de líneas de H , denotado L( H ), es un grafo donde cada arista en H es un vértice en L( H ), y cada dos aristas que se intersecan en H son adyacentes en L( H ). Los emparejamientos en H corresponden a los conjuntos independientes en L( H ). Dado que L( H ) es el complemento de D( H ), la caracterización anterior se puede traducir a L( H ):

• w( H ) > r si y solo si para cada conjunto de r vértices en L( H ) hay un vértice que no es adyacente a ninguno de ellos.
• mw( H ) > r si y solo si para cada conjunto de r vértices en L( H ) hay un vértice que no es adyacente a ninguno de ellos, y además, hay un conjunto independiente I en L( H ) que contiene un vértice que no es adyacente a ningún conjunto de este tipo.

El número de dominación de un grafo G , denotado por γ ( G ), es el tamaño mínimo de un conjunto de vértices que domina a todos los vértices de G. El ancho de un hipergrafo es igual al número de dominación de su grafo lineal: w( H ) = γ (L( H )). Esto se debe a que las aristas de E son los vértices de L( H ): cada subconjunto de E que fija a E en H corresponde a un conjunto de vértices en L( H ) que domina a todos los L( H ).

El número de dominación de independencia de un grafo G , denotado iγ ( G ), es el máximo, sobre todos los conjuntos independientes A de G , del conjunto más pequeño que domina a A. ^{[ 4 ]} El ancho de emparejamiento de un hipergrafo es igual al número de dominación de independencia de su grafo lineal: mw( H ) = iγ (L( H )). Esto se debe a que cada emparejamiento M en H corresponde a un conjunto independiente I _M en L( H ), y cada subconjunto de E que fija M en H corresponde a un conjunto que domina a I _M en L( H ).

• Para otros conceptos denominados "anchura" en la teoría de grafos, consulte Anchura (desambiguación)#Teoría de grafos .