24 votos

Conjuntos estables disjuntos en torneos

Sea $(V,A)$ ser un torneo . Un subconjunto de vértices $V'\subseteq V$ es estable si no existe $v\in V\setminus V'$ tal que $V'\cup$ { $v$ } contiene un subtorno transitivo de inclusión máxima con origen $v$ .

(En otras palabras, $V'$ es estable si para cada subtorno transitivo $T\subseteq V'\cup$ { $v$ } con $v\in T$ y $(v,x)\in A$ para todos $x\in T\setminus$ { $v$ }, existe un $w\in V'$ tal que $(w, x)\in A$ para todos $x\in T$ .)

¿Es cierto que ningún torneo contiene dos conjuntos estables disjuntos?

La afirmación implicaría que cada torneo contiene un único conjunto mínimo estable, lo que tendría varias consecuencias atractivas en las ciencias sociales. La afirmación es una versión débil de una conjetura de Schwartz (véase este documento y sus referencias). Los análisis informáticos han demostrado que no existe ningún contraejemplo con menos de 13 vértices.

8voto

enzotib Puntos 38044

La afirmación es falsa. La existencia de un contraejemplo utilizando 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