Gráficos con pocas camarillas.

En teoría de grafos , se dice que una clase de grafos tiene pocas camarillas si cada miembro de la clase tiene un número polinómico de camarillas máximas. ^[1] Ciertos problemas computacionales generalmente NP-difíciles se pueden resolver en tiempo polinómico en tales clases de gráficos, ^[1]^[2] creando gráficos con pocas camarillas de interés en la teoría de grafos computacional , análisis de redes y otras ramas de las matemáticas aplicadas . ^[3] De manera informal, una familia de gráficos tiene pocas camarillas si los gráficos no tienen una gran cantidad de grupos grandes.

Definición

Una camarilla de un gráfico es un subgrafo completo , mientras que una camarilla máxima es una camarilla que no está contenida adecuadamente en otra camarilla. Se puede considerar una camarilla como un grupo de vértices, ya que, por definición, todos están conectados entre sí por una arista. El concepto de clusters es omnipresente en el análisis de datos , como en el análisis de redes sociales . Por esa razón, limitar el número de camarillas máximas posibles tiene ramificaciones computacionales para algoritmos en gráficos o redes.

Formalmente, sea una clase de gráficos. Si para cada gráfico de vértice en , existe un polinomio tal que tiene camarillas máximas, entonces se dice que es una clase de gráficos con pocas camarillas. ^[1] $X$ $n$ $G$ $X$ $f(n)$ $G$ $O(f(n))$ $X$

Ejemplos

El gráfico de Turán tiene un número exponencial de camarillas máximas. En particular, esta gráfica tiene camarillas exactamente máximas cuando , que es asintóticamente mayor que cualquier función polinómica. ^[4]^{: 441} Este gráfico a veces se llama gráfico de Moon-Moser , después de que Moon y Moser demostraron en 1965 que este gráfico tiene el mayor número de camarillas máximas entre todos los gráficos sobre vértices. ^[5] Así que la clase de grafos de Turán no tiene pocos camarillas. $T(n,\lceil n/3\rceil)$ $3^{n/3}$ $n\equiv 0\mod 3$ $n$
Un árbol en los vértices tiene tantas camarillas máximas como aristas, ya que por definición no contiene triángulos. Cualquier árbol tiene exactamente bordes, ^[6]^{: 578} y por lo tanto ese número de camarillas máximas. Entonces la clase de árboles tiene pocas camarillas. $T$ $n$ $n-1$
Un gráfico cordal en los vértices tiene como máximo camarillas máximas, ^[7]^{: 49} por lo que los gráficos cordales tienen pocas camarillas. $n$ $n$
Cualquier gráfico plano en vértices tiene como máximo camarillas máximas, ^[8] por lo que la clase de gráficos planos tiene pocas camarillas. $n$ $8n-16$
Cualquier gráfico de vértice con boxicidad tiene camarillas máximas, ^[9]^{: 46} por lo que la clase de gráficos con boxicidad acotada tiene pocas camarillas. $n$ $b$ $O(n^{b})$
Cualquier gráfico de vértice con degeneración tiene como máximo camarillas máximas siempre que y , ^[10] por lo que la clase de gráficos con degeneración acotada tiene pocas camarillas. $n$ $d$ ${\textstyle (nd)3^{d/3}}$ $d\equiv 0\mod 3$ $n\geq d+3$
Sea un gráfico de intersección de politopos convexos en un espacio euclidiano de dimensiones cuyas facetas son paralelas a hiperplanos . Entonces, el número de camarillas máximas de es , ^[11]^{: 274} , que es polinomio para fijo y . Por lo tanto, la clase de gráficos de intersección de politopos convexos en un espacio euclidiano de dimensión fija con un número acotado de facetas tiene pocas camarillas. $G$ $n$ $d$ $k$ $G$ ${\textstyle O\left(n^{dk^{d+1}}\right)}$ $n$ $d$ $k$

Referencias

^ abc Prisner, E. (1995). Gráficos con pocas camarillas. En Y. Alavi & A. Schwenk (Eds.), Teoría de grafos, combinatoria y algoritmos: actas de la Séptima Conferencia Internacional Cuadrienal sobre Teoría y Aplicaciones de Gráficos (págs. 945–956). Nueva York, N. Y: Wiley.
^ Rosgen, B. y Stewart, L. (2007). La complejidad resulta en gráficos con pocas camarillas. Matemáticas discretas e informática teórica , vol. 9 núm. 1 (Gráficos y algoritmos), 387. https://doi.org/10.46298/dmtcs.387
^ Fox, J., Roughgarden, T., Seshadhri, C., Wei, F. y Wein, N. (2020). Encontrar camarillas en las redes sociales: un nuevo modelo sin distribución. Revista SIAM de Computación , 49 (2), 448–464. https://doi.org/10.1137/18M1210459
^ Graham, RL, Knuth, DE y Patashnik, O. (1994). Matemáticas concretas: una base para la informática (2ª ed.). Lectura, Misa: Addison-Wesley.
^ Luna, JW y Moser, L. (1965). Sobre camarillas en gráficos. Revista Israel de Matemáticas , 3 (1), 23–28. https://doi.org/10.1007/BF02760024
^ Pahl, PJ y Damrath, R. (2001). Fundamentos matemáticos de la ingeniería computacional: un manual . Berlín; Nueva York: Springer.
^ Gavril, F. (1974). Las gráficas de intersección de subárboles en árboles son exactamente las gráficas cordales. Revista de teoría combinatoria, Serie B , 16 (1), 47–56. https://doi.org/10.1016/0095-8956(74)90094-X
^ Madera, DR (2007). Sobre el número máximo de camarillas en un gráfico. Gráficos y combinatoria , 23 (3), 337–352. https://doi.org/10.1007/s00373-007-0738-8
^ Spinrad, JP (2003). Representaciones de intersección y contención. En Representaciones gráficas eficientes (págs. 31 a 53). Providence, RI: Sociedad Estadounidense de Matemáticas.
^ Eppstein, D., Löffler, M. y Strash, D. (2010). Listado de todas las camarillas máximas en gráficos dispersos en un tiempo casi óptimo. En O. Cheong, K.-Y. Chwa y K. Park (Eds.), Algoritmos y computación (Vol. 6506, págs. 403–414). Berlín, Heidelberg: Springer Berlín Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36
^ Brimkov, VE, Junosza-Szaniawski, K., Kafer, S., Kratochvíl, J., Pergel, M., Rzążewski, P., et al. (2018). Polígonos homotéticos y más: camarillas máximas en gráficos de intersección. Matemáticas aplicadas discretas , 247 , 263–277. https://doi.org/10.1016/j.dam.2018.03.046