Una clase hereditaria de estructuras (p. Ej., Gráficas) es aquella que se cierra bajo subestructuras inducidas, o de manera equivalente, se cierra bajo eliminación de vértices.
Las clases de gráficos que excluyen a un menor tienen buenas propiedades que no dependen del menor excluido específico. Martin Grohe demostró que para las clases de gráficos que excluyen un menor, existe un algoritmo polinomial para el isomorfismo, y la lógica de punto fijo con conteo captura el tiempo polinómico para estas clases de gráficos. (Grohe, Definibilidad de punto fijo y tiempo polinomial en gráficos con menores excluidos , LICS, 2010.) Estas pueden considerarse propiedades "globales".
¿Existen propiedades "globales" similares conocidas para las clases hereditarias (gráficos o estructuras más generales)?
Sería bueno ver que cada respuesta se centre en una sola propiedad específica.
fuente
Puede que esto no sea exactamente lo que tenía en mente, pero existen restricciones conocidas sobre cuántos gráficos en vértices puede haber en una clase hereditaria de gráficos. Por ejemplo, no existe una clase hereditaria de gráficos que tenga entre 2 Ω ( n ) y 2 o ( n log n ) gráficos en n vértices.norte 2Ω ( n ) 2o ( n logn ) norte
Referencia: E. Scheinerman, J. Zito, Sobre el tamaño de las clases hereditarias de gráficos, Journal of Combinatorial Theory Series B
fuente
Esto está relacionado con la respuesta de Travis. De hecho, podría considerarse una versión más fuerte.
Un artículo de Bollob \ 'as y Thomason (Combinatorica, 2000) muestra que en Erd \ H {o} sR \' enyi gráficos aleatorios (con p alguna constante fija), cada propiedad hereditaria puede aproximarse por lo que Llamar a una propiedad básica . Básico casi significa gráficos cuyos conjuntos de vértices son uniones de clases r ,Gn,p p r de las cuales abarcan camarillas y r - s de las cuales abarcan conjuntos independientes, pero no del todo. Esta aproximación se utiliza para caracterizar el tamaño de un conjunto P más grande, así como elnúmero cromático P de G n ,s r−s P P , donde P es alguna propiedad hereditaria fija. Si sepermite quepvaríe, el comportamiento no se entiende bien.Gn,p P p
Para obtener más antecedentes sobre este y el trabajo relacionado, hay una encuesta realizada por Bollob \ 'as (Proceedings of the ICM 1998) que también da una conjetura tentadora a lo largo de estas líneas, pero para hipergrafías.
Encuentro la profunda conexión entre las propiedades hereditarias y el Lema de regularidad de Szem \ 'eredi muy intrigante, ya que se usó tanto aquí como en el resultado de Alon y Shapira.
fuente
La respuesta de Suresh sobre la conjetura de AKR me hizo pensar en la misma conjetura para las propiedades hereditarias. Creo que (a menos que haya cometido un error) puedo mostrar que todas las propiedades hereditarias no triviales tienen una complejidad de árbol de decisión (aleatoria y determinista) , que resuelve la conjetura AKR para tales propiedades (hasta constantes).Θ(n2)
Traté de buscar en la literatura para ver si esto se ha mostrado en alguna parte, pero no pude encontrar una referencia. Entonces, o no pude encontrarlo, pero existe, o el teorema no es interesante o cometí un error.
Entonces, este es otro ejemplo de una propiedad global de todas las propiedades hereditarias de gráficos.
fuente
fuente
Esta es la dirección "inversa", pero la conocida conjetura de Aanderaa-Rosenberg-Karp se aplica a las propiedades del gráfico que son monótonas hacia arriba (es decir, si G satisface la propiedad, también lo hace cualquier gráfico en los mismos nodos cuyo conjunto de bordes contiene E (G )).
fuente