2 votos

¿Es cierto que para cada matroid conectado $M$ tenemos $\chi(M)=\chi(M^*)$ ?

Si para cualquier matroid conectado $M$ en $E$ dejamos que $\chi(M)$ sea el tamaño mínimo de cualquier partición de $E$ en conjuntos independientes de $M$ entonces es $\chi(M)=\chi(M^*)$ ? (donde nota $M^*$ es el dual de $M$ y $|E|>2$ )

3voto

relep Puntos 589

Esto no es cierto. Consideremos un gráfico de ciclo $C_n$ y el matroid correspondiente $M$ . Entonces $\chi(M) = 2$ . El dual es el matroide correspondiente al grafo con dos vértices y $n$ aristas paralelas entre estos vértices. De ello se deduce que $\chi(M^*) = n$ .

En términos más generales, si $M = U^r_n$ es un matroid uniforme de rango $r$ entonces $\chi(M) = \lceil n / r\rceil$ mientras que para $M^* = U_n^{n-r}$ tenemos $\chi(M^*) = \lceil n / (n-r) \rceil$ y estos no son iguales en general.

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