¿Es posible que tanto un grafo como su complemento tengan una conectividad pequeña?

Question

Sea $G=(V,E)$ sea un grafo simple con $n$ vértices. La constante isoperimétrica de $G$ se define como

$$ i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|} $$

donde $\partial A$ es el conjunto aristas $uv \in E$ con $v \in A$ y $u \in A^c$ .

¿Existe un gráfico $G$ tal que $$i(G) + i(G^c) < \frac 12$$ donde $G^c$ denota el complemento de $G$ ?

Answer 1

Es casi obvio. Sea $i(A)=\frac{|\partial_G A|}{|A|}$ y $j(B)$ sea la misma relación para un conjunto de vértices $B$ y el complemento de $G$ . Sea $x=|A\cap B|, y=|A\cap B^c|, z=|A^c\cap B|, t=|A^c\cap B^c|$ . Los bordes que van entre $A\cap B$ y $A^c\cap B^c$ son aristas límite para ambos $A$ y $B$ y también lo son los bordes entre $A^c\cap B$ y $A\cap B^c$ . Por lo tanto, tenemos $$ i(A)(x+y)+j(B)(x+z)\ge xt+yz $$ Si $i(A)+j(B)<1$ el lado izquierdo es estrictamente menor que $x+\max(y,z)$ que es como máximo $xt+yz$ si $t,y,z>0$ . Tenga en cuenta que si $t=0$ entonces $x=0$ debido a la condición $|A|,|B|\le \frac n2$ por lo que si $y,z>0$ en este caso, todavía tenemos una contradicción. Por último, si, por ejemplo, $y=0$ entonces $x>0$ (de lo contrario $A=\varnothing)$ y $t\ge \frac n2$ (porque $|B|\le\frac n2$ ), por lo que la RHS es al menos $\frac n2$ mientras que el LHS es inferior a $\max(|A|,|B|)\le \frac n2$ y volvemos a tener una contradicción.

Answer 2

Como para comentario es largo, escribo aquí la contribución:

Sea $A$ et $L$ sean la matriz de adyacencia y la matriz laplaciana del grafo $G$ respectivamente. Además, supongamos $\mu_2$ denota el segundo valor propio más pequeño de $L$ y $\lambda_2$ sea el segundo mayor valor propio de $A$ . Se demuestra que $i(G)\geq \frac{\mu_2}{2}$ (véase el teorema 4.1 de "Números isoperimétricos de grafos" por Bojan Mohar ). Por lo tanto, tenemos $$i(G)+i(G^c)\geq \frac{\mu_2(G)+\mu_2(G^c)}{2}$$ .

Por lo tanto, si tenemos un ejemplo para su pregunta, debemos encontrar gráfico $G$ tal que $\mu_2(G)+\mu_2(G^c)<1$ . Mediante un poco de teoría espectral de grafos, se puede ver que encontrar un grafo de este tipo es un problema difícil. Pero, encontrar el espectro de un grafo es mucho más fácil que encontrar su número isoperimétrico.

Además, se puede demostrar que este problema está relacionado con la clasificación de los grafos basada en su segundo mayor valor propio de la matriz de adyacencia. En realidad, si podemos encontrar un grafo adecuado tal que: $$\lambda_2(G)+\lambda_2(G^c)\leq \delta(G)-\Delta(G)+n-2$$ ,

A continuación encontramos un ejemplo $\delta(G)$ y $\Delta(G)$ muestra el grado mínimo y máximo del gráfico $G$ con $n$ vértices.

$\textbf{Added later:}$ Por la relación $\mu_2(G)+\mu_2(G^c)<1$ y algunas pruebas de grafos aleatorios, parece que esos grafos son muy raros. No hay ningún ejemplo de este tipo de gráfico hasta $6$ vértices. Además, parece que podemos demostrar $\mu_2(G)+\mu_2(G^c)\geq 1$ lo que significa que no existe tal ejemplo.