En teoría de grafos , una rama de las matemáticas, un grafo t -libre de biclicues es un grafo que no tiene K t , t ( grafo bipartito completo con 2t vértices) como subgrafo . Una familia de grafos es libre de biclicues si existe un número t tal que los grafos de la familia son todos t -libres de biclicues. Las familias de grafos libres de biclicues forman uno de los tipos más generales de familia de grafos dispersos . Surgen en problemas de incidencia en geometría discreta y también se han utilizado en complejidad parametrizada .
Según el teorema de Kővári–Sós–Turán , cada grafo t -biclique-libre de n -vértices tiene O ( n 2 − 1/ t ) aristas, significativamente menos que las que tendría un grafo denso . [1] Por el contrario, si una familia de grafos está definida por subgrafos prohibidos o cerrada bajo la operación de tomar subgrafos, y no incluye grafos densos de tamaño arbitrariamente grande, debe ser t -biclique-libre para algún t , ya que de lo contrario incluiría grafos bipartitos completos densos grandes.
Como límite inferior , Erdős, Hajnal y Moon (1964) conjeturaron que cada grafo bipartito libre de t -bicliques máximo (uno al que no se pueden agregar más aristas sin crear un t -biclique) tiene al menos ( t − 1)( n + m − t + 1) aristas, donde n y m son los números de vértices en cada lado de su bipartición. [2]
Un grafo con degeneración d es necesariamente ( d + 1) -libre de grafos biclique. Además, cualquier familia de grafos que no sea densa en ninguna parte es libre de grafos biclique. De manera más general, si existe un grafo de n -vértices que no sea un menor 1-superficial de ningún grafo en la familia, entonces la familia debe ser libre de grafos biclique , porque todos los grafos de n -vértices son menores 1-superficiales de K n , n . De esta manera, las familias de grafos libres de grafos biclique unifican dos de las clases más generales de grafos dispersos. [3]
En geometría discreta , muchos tipos de grafos de incidencia son necesariamente libres de biclicuos. Como ejemplo simple, el grafo de incidencias entre un conjunto finito de puntos y líneas en el plano euclidiano no tiene necesariamente ningún subgrafo K 2,2 . [4]
Los grafos libres de bicliques se han utilizado en la complejidad parametrizada para desarrollar algoritmos que sean eficientes para grafos dispersos con valores de parámetros de entrada adecuadamente pequeños. En particular, encontrar un conjunto dominante de tamaño k , en grafos t -libres de bicliques, es manejable con parámetros fijos cuando se parametriza por k + t , aunque hay evidencia sólida de que esto no es posible utilizando k solo como parámetro. Resultados similares son verdaderos para muchas variaciones del problema del conjunto dominante. [3] También es posible probar si un conjunto dominante de tamaño como máximo k se puede convertir en otro mediante una cadena de inserciones y eliminaciones de vértices, preservando la propiedad dominante, con la misma parametrización. [5]