Parece que muchos, si no casi todos, de las propiedades estudiadas en la teoría de grafos son monótonas. (Propiedad de los medios es invariante bajo permutación de vértices, y monotono significa que la propiedad está bien conservado bajo la adición o eliminación de bordes, la fijación de los vértices set). Por ejemplo: conectado, plana, triángulo libre, bipartito, etc. Muchos cuantitativo gráfico invariantes también puede ser considerado monotono propiedades de gráfico, por ejemplo, cromática número $\ge k$ o de la circunferencia $\ge g$.
Mi pregunta es si hay no-monótona gráfico las propiedades que se han estudiado bien, o que surgen de forma natural.
Una obvia de la clase de los ejemplos es la intersección de una monótona creciente y monótona decreciente de la propiedad: por ejemplo gráficos con la cromática número $\ge k$ y la circunferencia $\ge g$. (Esto no es del todo evidente si se cruzan dos propiedades que tendrán una intersección no vacía, en este caso es un conocido teorema de la teoría de grafos.
Otro ejemplo es la presencia de la inducida por subdiagramas isomorfo a $H$ para cualquier gráfico de $H$. La adición de bordes sólo aumenta el número de subdiagramas, pero puede destruir la propiedad de ser inducida.
Estoy especialmente interesado en saber si algún no-monótona propiedades han sido estudiadas para grafos aleatorios. Un famoso teorema de Friedgut y Kalai es que cada monotono gráfico de la propiedad tiene un fuerte umbral, y me gustaría saber acerca de cualquiera de los ejemplos de sharp umbrales para los no-monótona y propiedades.
