24 votos

Conjuntos disjuntos estables en torneos

Dejar de dólares(V,A)$ ser un torneo. Un subconjunto de vértices $V'\subseteq V$ es estable si no existe $v\V\setminus V'$ tales que $V'\cup${$v$} contiene una inclusión del máximo transitiva subtournament con la fuente $v$.

(En otras palabras, $V$ es estable si para cada transitiva subtournament $T\subseteq V'\cup${$v$} $v\T$ y $(v,x)\in A$ para todo $x\T\setminus${$v$}, $w\V'$ tales que $(w, x)\in A$ para todo $x\in T$.)

Es cierto que el torneo no contiene dos disjuntas estable?

La declaración implica que cada torneo en el que contiene un único mínimo conjunto estable, que tiene varios atractivos consecuencias en las ciencias sociales. La declaración es una versión débil de una conjetura por Schwartz (consulte este documento y las referencias allí). Equipo de análisis ha demostrado que no existe ninguna contra-ejemplo con menos de 13 vértices.

8voto

enzotib Puntos 38044

La declaración es falsa. La existencia de un contraejemplo mediante un argumento probabilístico fue demostrada por Chudnovsky, Kim, Liu, Norin, Scott, Seymour y Thomasse.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X