Mostrar que los complementos de emparejamientos máximos (extendidos hacia abajo) forman un matroid

Question

Deje $G$ un Gráfico. Deje $\mathcal{F}\subset\mathcal{P}(V(G))$ ser una familia de conjuntos de nodos. Para cada conjunto $X\in\mathcal{F}$ es cierto, que hay un máximo de coincidencia de $M$ que no contiene ningún nodo $x\in X$.

Quiero mostrar, que $(V(G),\mathcal{F})$ es un Matroid.

Definición de un Matroid:

Deje $E$ ser un conjunto y $\mathcal{F}\subset\mathcal{P}(E)$. $(E,\mathcal{F})$ es un matroid si:

1. $\emptyset\in\mathcal{F}$
2. $X\subset Y\in\mathcal{F}\Rightarrow X\in\mathcal{F}$
3. $X,Y\in\mathcal{F}$ y $|X|>|Y|$ $\Rightarrow$ $\exists x\in X\setminus Y$ con $Y\cup\{x\}\in\mathcal{F}$

---

Edit: Después de lidiar un poco con Matroids me ocurrió con esta prueba.

1. Cada Gráfico de $G$ tiene un máximo de coincidencia. El conjunto vacío $\emptyset$ no contiene nodos, que podría ser cubierto por un máximo de coincidencia. De modo que el conjunto vacío $\emptyset$ debe ser en $\mathcal{F}$, por definición, de $\mathcal{F}$ en el ejercicio.

2. Deje $B\in\mathcal{F}$. Por definición, debe ser de un máximo de coincidencia, de tal manera que ningún nodo $x\in B$ está cubierto. Esto es cierto para cada subconjunto de $B$, demasiado. Por lo tanto es cierto para $A\subset B$.

3. Deje $A,B\in\mathcal{F}$$|A|<|B|$. Hay dos casos:

   1. $A\setminus B=\emptyset$: A continuación, $A\subset B$ y en este caso se resolvió con 2. (arriba)
   2. $A\setminus B\neq\emptyset$: Por supuesto, es cierto que $A,B\in\mathcal{F}$. Por definición es una máxima coincidente $\mathcal{M}_A$ correspondiente al conjunto $A$ y un máximo coincidente $\mathcal{M}_B$ correspondiente al conjunto $B$. Deje $x\in B\setminus A$:
      1. Deje $x\not\in V(\mathcal{M}_A)$. A continuación, $A\cup{x}\in\mathcal{F}$ es obviamente cierto.
      2. Deje $x\in V(\mathcal{M}_A)$. Uno tiene que demostrar, que hay un máximo de coincidencia $\mathcal{M}_{A\cup {x}}$. $x\in B \Rightarrow x\not\in\mathcal{M}_B$. Hay un $y\in V(G)$ tal que $y\not\in\mathcal{M}_A$ $y\in\mathcal{M}_B$ porque cada Base en $\mathcal{F}$ tiene la misma cardinalidad. Debido a $y\not\in\mathcal{M}_A$ es cierto que $y$ está en la Base de $\mathcal{B}_A$ ($A\subset \mathcal{B}_A$). Por construcción $y$ $x$ no $\mathcal{B}_A \cap \mathcal{B}_B$, y con el intercambio lema de Steinitz la prueba está terminado.

¿Qué piensas acerca de este enfoque? Mi lengua materna es el alemán, así que traté de traducir mi prueba de lo mejor que he podido. Matemática y lenguaje correcciones son bienvenidos! :-)

Answer 1

Dos observaciones.

En primer lugar, no se ha definido el matroid correctamente. Contiene todos los conjuntos de vértices de la satisfacción de su propiedad de ser disjunta de máxima coincidente. De lo contrario, no es un matroid - no tiene por qué contener el conjunto vacío.

En segundo lugar, la prueba de la Reivindicación 3 no puede ser cierto ya que no utiliza la condición de que $|X| > |Y|$. De hecho, en matroids todos el máximo de sets ("bases") tienen igual cardinalidad. Tomar dos diferentes conjuntos de la máxima $X,Y$. Es entonces imposible añadir ningún elemento $x \in X \setminus Y$$Y$, ya que el $Y$ es máxima.

En particular, su comentario en el Caso 2, "a mí me parece, que la Reivindicación 3 es verdadera para cada nodo $x \in X$" es totalmente injustificado. Su tratamiento del Caso 3 es aún más inestable - "La forma en que yo lo veo".

Lo que falta aquí es una prueba de que el único que no trivial parte de la afirmación de que tenemos un matroid aquí - a saber, la extensión de la propiedad (su "Reivindicación 3") en el caso de que $Y$ no es un subconjunto de a $X$ (de lo contrario no es muy interesante, ya que mostrar).

Esta prueba debe usar de alguna forma la definición particular de su sistema de conjunto. Por ejemplo, la prueba nunca se refiere a elecciones, y mucho menos a la máxima elecciones.

Answer 2

Definición:
Sea G ser un agraph y $M_{A},M_{B}$ elecciones. Definir $G^* = G(V,M_{A} \Delta M_{B})$

1. una ruta alterna en $G^*$ es una ruta en la que los bordes pertenecen como alternativa a la concordancia de $M_{A}$ y a la coincidencia de $M_{B}$.
   
2. un aumento de la ruta en $G^*$ es alternar un camino que se inicia desde y termina en los vértices coincidentes por el mismo.

• Deje $A,B\in\mathcal{F}$$|A|+1=|B|$. Si hay un $e \in B\setminus A$, de modo que $A+e \in \mathcal{F}$ hemos terminado. Suponga que no hay tal e.
• A continuación, ver el $M_{A} \Delta M_{B}$ donde $M_{X}$ es de un máximo de coincidencia de que no contiene ningún elment de X. Desde $M_{A}$ $M_{B}$ máximo de matchings $M_{A} \Delta M_{B}$ no contiene ningún aumento de la ruta(Si es que contendría dicha ruta de acceso de cualquiera de las $M_{A}$ o $M_{A}$ no es una máxima coincidente). Pues no $e \in B\setminus A$, $A+e$ es en $ \mathcal{F}$ la diferencia simétrica $M_{A} \Delta M_{B}$ contiene la alternancia de ruta de acceso (Todos los $e \in B\setminus A$ están cubiertos por $M_{A}$, pero no por $M_{B}$). Al menos una ruta termina en un nodo x que NO está en A. Esto es debido a que de lo contrario, para todos camino a partir de $e \in B\setminus A$ existe un $x \in A\setminus B$ en el que el camino se termina. Entonces lo que sigue es $|A|=|A\cap B| + |B\setminus A|= |B| > |A|$. Eso es una contradicción, por lo que hay, al menos, en la alternancia de la ruta P con un punto de partida $e \in B\setminus A$ y un punto final x $\notin A$.
• Ahora, retire todos los bordes a lo largo de P en $M_{A}$ y añadir todos los adges de $M_{B}$ a lo largo de P $M_{A}$ y llamar a esta creado Coincidente $M_{A + e}$.
• $M_{A + e}$ es de un máximo de coincidencia ya que nos quita la misma cantidad de aristas que hemos añadido
• Por construcción $M_{A + e}$ no cubre cualquier elemento de Una y no de la cubierta e, que es el elemento de $ B\setminus A$
• de ello se desprende que $A+e$ $\mathcal{F}$