Si $G$ tiene un juego con $k$ bordes, luego tiene un subgráfico bipartita con bordes de #% de #% % o más

Question

Supongamos $G$ es un (simple) del gráfico. Un conjunto de aristas $M\!\subseteq\!E(G)$ es una coincidencia si $\forall e,e'\!\in\!M:$ $e$ y $e'$ no tienen ningún vértice común. Un gráfico de $H$ es bipartito si $\exists A,B\!\subseteq\!V(H)$ tal que $A\cap B=\emptyset$, $V(H)=A\cup B$, y cada borde en $H$ tiene un vértice en $A$ y una en $B$. Un conjunto de vértices $A\subseteq V(G)$ es un anticlique (es decir, "vacío subgrafo") si no hay bordes en $G$ entre los vértices de $A$. Denotar $n:=|V(G)|$$m:=|E(G)|$.

Cómo puedo probar la siguiente declaración:

PROBLEMA: si $G$ tiene una correspondencia con la $k$ bordes, entonces tiene un bipartito subgrafo $H$, con al menos $(|E(G)+k|)/2$ bordes.

Intento de la prueba 1: he intentado esto con la inducción en $k$.

$k=m:$ esto significa que el $G$ es bipartito, por lo $H:=G$ es suficiente. $\checkmark$

$m,\ldots,k\rightarrow k\!-\!1:$ Hipótesis de inducción: supongamos que tenemos una coincidencia con $k-1$ bordes en $G$ y supongamos que la afirmación es verdadera para todos los matchings con al menos $k$ bordes. No sé cómo encontrar un borde adicional para agregar a la $(k-1)$de coincidencia...

Intento de prueba 2: tengo un fuerte presentimiento de que esto estaba destinado a ser resuelto mediante el método de probabilidades (que fue publicado en el Método de probabilidades pack de problemas). Sería suficiente para demostrar que si podemos elegir al azar dos anticliques $A,B\subseteq V(G)$, que el número esperado de bordes entre las $A$$B$$\mathbb{E}(|E[A,B]|)=(|E(G)+k|)/2$. Entonces se sigue que no existe una selección de $A,B$ que tiene más de $(|E(G)+k|)/2$ bordes. Pero creo que al azar la elección de cualquiera de los dos anticliques no será suficiente para obtener un alto valor esperado. Por otra parte, no sé cómo utilizar la hipótesis acerca de la existencia de una $k$de coincidencia...

todas las sugerencias son muy bienvenidas

Answer 1

Primero de todo, lo que usted define como "camarilla" es generalmente conocido como un "conjunto independiente". La camarilla es generalmente definido como el gráfico que contiene todos los posibles bordes.

Segundo, la noción de subgrafo que usted está utilizando aquí es un "no-subgrafo inducido", lo que significa que sólo debes elegir un subconjunto de los bordes. A menudo subgrafo es "inducida" por un conjunto de vértices - elige un subconjunto de los vértices, y se obtiene exactamente el correspondiente bordes, que pertenecía a la gráfica original.

Finalmente, he aquí cómo resolverlo mediante el método de probabilidades. Tome su coincidencia y asignar los vértices de forma aleatoria en dos bipartitions, bajo la condición de que dos vértices formando un borde asignados a dos diferentes bipartitions. Divida el resto de los vértices completamente al azar en los dos bipartitions. Cada uno de no-coincidencia de borde probabilidad de que haya exactamente $1/2$ a tienen sus extremos en los lados opuestos, por lo que el número esperado de "legal" de los bordes es $$k + \frac{|E|-k}{2} = \frac{|E|+k}{2}.$$

---

La construcción puede ser derandomized. En primer lugar, imaginemos $k=0$. Nos asignar los vértices a bipartitions en algún orden arbitrario $v_1,v_2,\ldots$. Cuando la asignación de $v_t$, nos aseguramos de que al menos la mitad de los bordes anteriores de los vértices $v_s,\; s<t$ son "legales" (esto siempre es posible, ejercicio). El argumento de $k > 0$ es similar.

Esta idea se puede convertir en una prueba por inducción sobre $k$. Demostrar que el caso base $k = 0$ favoritos en tu camino. Para pasar de la $k$$k+1$, tomar uno de los bordes de la correspondencia y del contrato. El uso de la inducción de la hipótesis de obtener un subgrafo con muchas aristas, y ahora dividir el vértice de nuevo. Usted tiene dos opciones para la posición de los dos extremos, escoger el que conduce a más bordes. Algunos de contabilidad conduce ahora a una prueba.

El caso base también puede ser demostrado por inducción con solo presentar la prueba en el primer párrafo (para el caso de $k=0$) como una prueba por inducción.

Answer 2

Tengo una idea de cómo probar sin el método de probabilidades, aunque. Me gustaría tratar de empezar con la coincidencia como un bipartito gráfico y, sucesivamente, agregar los otros vértices y algunas de las aristas que están conectados a la existente bipartito subgrafo. Si los vértices se incluye en la coincidencia no estaban vinculadas a otras de la coincidencia de que sería él y fácil. Pero usted realmente tiene que empezar antes "giro" de las elecciones de la manera correcta y agregar sucesivamente primera.

Me doy cuenta de que esto suena un poco críptico. Puedo intentar escribir una solución completa, si usted lo desea, pero usted pidió un toque a primera.