existe un $c>0$ de manera que cada $3$ -El gráfico bipartito regular es un $(2n,3,c)$ -expansor

Question

Definición : Un gráfico $G = (V, E)$ se llama $(n, d, c)$ -expansor si tiene $n$ vértices, el grado máximo de un vértice es $d$ y, para cada conjunto de vértices $W \subset V$ de cardinalidad $|W| \le n2$ la desigualdad $|N(W)| \ge c|W|$ se mantiene, donde $N(W)$ denota el conjunto de todos los vértices de $V \backslash W$ adyacente a algún vértice de $W$

Considerando un grafo bipartito trirregular aleatorio en $2n$ vértices obtenidos eligiendo tres permutaciones aleatorias entre las dos clases de color, demostrar que existe un $c > 0$ tal que para cada n existe un $(2n, 3, c)$ -expansor.

Esta es la pregunta 9.6.1 de El método probabilístico y estoy tentado de argumentar que para cualquier $c\le 1$ el gráfico es trivialmente un expansor.

En la pregunta se nos pide que consideremos el grafo bipartito 3-regular que se obtiene tomando la unión de aristas de tres permutaciones sobre $[n]$ . Una permutación es básicamente un emparejamiento perfecto, por lo tanto esta construcción contiene un emparejamiento perfecto y por el teorema de Hall, cada subconjunto $W\subset[n]$ satistiface $|N(W)|\ge|W|\ge c|W|$ en particular para los conjuntos $|W|\le 1/2$ .

(en realidad es incluso más sencillo que eso, no hace falta el teorema de Hall: por la regularidad 3 $|N(W)|<|W|$ implicaría $3|N(W)|<3|W|$ que en inglés significa $\#\{\text{outedges of } |N(W)|\} < \#\{\text{outedges of } |W|\}$ lo cual es obviamente falso).

Pero entonces estos consejos de este sitio web apuntan a un enfoque completamente diferente. Me interesaría recibir más pistas sobre cómo calcular la probabilidad de que $N(W)<(1+\epsilon)|W|$ para un determinado $W\subset[n]$ como se dice en las insinuaciones.

Y por supuesto me gustaría saber si tomar $c\le 1$ está bien...

Answer 1

Es posible que se haya confundido con la definición de $N(W)$ . Por lo general, esto sólo significa "el conjunto de vértices adyacentes a $W$ ". En la definición que has citado de Alon y Spencer, no incluimos los vértices que son en $W$ , que es lo habitual para medir la expansión de los vértices.

Como resultado, muchos grafos bipartitos cúbicos no son expansores para $c =1$ . Para un ejemplo extremo, tomemos dos copias de cualquier gráfico bipartito cúbico, y dejemos que $W$ sea el conjunto de todos los vértices de un ejemplar. Entonces $|W| = \frac n2$ y $|N(W)| = 0$ por lo que la expansión de vértices de dicho gráfico es $0$ .

Para una familia de ejemplos conectados con mala expansión, considere los grafos prismáticos, como el de abajo :

Estos son $3$ -regular con $n=2k$ vértices, y cuando $k$ es par, son bipartitos. Sin embargo, podemos cortar el prisma por la mitad verticalmente (si está dibujado como en la imagen anterior) y tomar $W$ para ser los vértices de una mitad. Entonces $|W| = \frac n2$ y $|N(W)|=4$ por lo que, en el mejor de los casos, este gráfico tiene una expansión de vértices $\frac 8n$ que va a $0$ como $n \to \infty$ .

Así que no: no todos los grafos cúbicos bipartitos son expansores.

---

La razón por la que estás viendo pistas para probar que $|N(W)| \ge (1+\epsilon)|W|$ no es porque $c$ no puede ser inferior a $1$ . Es porque en general, si $W = W_1 \cup W_2$ donde $W_1$ está en un lado de la bipartición y $W_2$ por el otro, $$ N(W) = (N(W_1) \setminus W_2) \cup (N(W_2) \setminus W_1) $$ lo que nos lleva a $$|N(W)| \ge (|N(W_1)| - |W_2|) + (|N(W_2)| - |W_1|) = |N(W_1)| + |N(W_2)| - |W|.$$ si podemos demostrar que $|N(W_1)| \ge (1+\epsilon)|W_1|$ y $|N(W_2)| \ge (1+\epsilon)|W_2|$ entonces concluimos que $|N(W)| \ge \epsilon|W|$ . Si esto se cumple siempre, entonces tenemos un $\epsilon$ -expansor.

Tenemos que tener cuidado porque $|W| \le \frac12|V|$ no implica que $|W_1| \le \frac12n$ y $|W_2| \le \frac12n$ . Pero también tenemos $|N(W)| \ge |N(W_1)| - |W_2| \ge |W_1| - |W_2|$ , y de forma similar $|N(W)| \ge |W_2| - |W_1|$ por lo que si los dos lados de $W$ están demasiado desequilibrados, obtenemos inmediatamente la expansión de los vértices. Eso nos dice que $|W_1|, |W_2| \le (\frac12 + \frac12\epsilon)n$ en todos los casos difíciles.