Tamaño mínimo de árbol de expansión o separador

Question

Dado un grafo $G$ $n$ vértices vértices y subconjuntos $A_1, A_2, ... A_k$, es siempre el caso de que no es un árbol de tamaño en la mayoría de las $\sqrt{n}$ que cruza todas las $A_i$, o un conjunto $S$ del tamaño en la mayoría de los $\sqrt{n}$ que se cruza cada árbol? (En otras palabras, no hay componente conectado de $G-S$ cruza todas las $A_i$).

Para el caso de $k = 2$, esto es implícita por Menger del teorema. De hecho, la creación de un gráfico de mayor tamaño con $k-1$ copias de $G$ y la identificación de los vértices en $A_i$ $i$ $i+1$th capa muestra que el obligado es en la mayoría de las $\sqrt{(k-1)n}$. Sin embargo, no he sido capaz de hacer nada mejor que eso.

¿Alguien sabe si esto es cierto, o si es desconocido, lo que los enfoques que puedo tomar? He tratado de buscar en internet, pero no he sido capaz de encontrar nada que le ayuda.

Answer 1

Desafortunadamente, resulta que la respuesta es no. Por ejemplo, una cuadrícula símplex$k-1$ con lados de longitud$x$ tiene${x+k-2}\choose{k-1}$ vértices con un árbol de expansión mínimo de tamaño$x$ y un conjunto separado mínimo de tamaño${x+k-3}\choose{k-2}$. El producto de estos es aproximadamente$(k-1)n$, lo que significa que el límite trivial también es ajustado. En particular, para$k=3$, es imposible hacer mejor que$\sqrt{2n} - \frac{1}{2}$.