Comparación del número de subgrafos que se extienden

Question

Hola a todos,

Que sea $G_n=(V_n,E_n)$ un gráfico finito, donde $V_n= \{0,1,\ldots, n\} \times\{0,1,\ldots,n\}$

y $E_n\subset V_n^{(2)}$ es el conjunto de aristas de los vecinos más cercanos en el $\ell^1$ norma, es decir, $\ E_n=\{\ \{z,w\}\subset V_n; \ \sum_{i=1}^2 |z_i-w_i| =1 \ \}.$

Fijar un vértice $x=(x_1,x_2)\in G_n$ tal que $x_2>x_1$ (diagonal superior). Me gustaría saber si es cierta la siguiente desigualdad:

$\sharp[m,p]_{x}\leq \sharp[p,m]_x$ , siempre que $p < m$

donde $[m,p]_{x}$ es el conjunto de todos los subgrafos de extensión de $G_n$ que satisface las siguientes propiedades:

1- el subgrafo de extensión tiene $m$ bordes horizontales y $p$ bordes verticales;

2- los vértices $(0,0)$ y $x=(x_1,x_2)$ están en el mismo componente conectado,

y $\sharp A$ es la cardinalidad de $A$ .

En otras palabras, si tengo disponibles más aristas verticales que horizontales, ¿es cierto que puedo encontrar más configuraciones que conecten $0$ y $x$ si $x$ es diagonal ascendente que en el caso de que las cantidades de horizontal y vertical estén invertidas?

Gracias de antemano por cualquier idea o referencia.

Answer 1

Mi idea de un abarcan subgrafo es generalmente un árbol de expansión, lo cual implica tanto subgrafo y gráfico están conectados. Que no parece ser el caso aquí, así que voy a suponer que el conjunto de vértices de la expansión subgrafo es la misma que la de la gráfica original (el que se parece a un cuadrado de la cuadrícula para mí). Por desgracia, sólo tengo sugerencias para los intentos, no una respuesta.

Tenga en cuenta que la reflexión a través de la línea x=y mapas conectado subdiagramas a sí mismos, por lo que su desigualdad sería la igualdad si la condición de que la expansión subgrafo estaba conectado, se añadió. No veo ninguna otra simetrías que ayudar con este problema.

Consideremos ahora el problema de la enumeración; suponiendo que m y p son ambas suficientemente grande como para que hay gráficos de ambos tipos ([m.p] frente a [p,m]), que tiene x y (0,0) en la misma componente conectado, mira el recuento simple de todos los caminos de longitud l que presentan la conexión. Esto no te da la respuesta, sino que te prepara para el siguiente paso, que es contar todos los gráficos con l bordes que están conectados, y que contienen x y (0,0). Cuando usted tiene que la enumeración de cada una de las dos clases, que debe llegar cerca de la respuesta, para tener algo de libertad en la asignación de los bordes restantes.

Existe también la comprobación de fácil casos, por ejemplo, cuando m = n^2-n y p = x_2. Se sugiere su desigualdad debe tener y ser estrictos a la cercana factible valores de m y p.

Gerhard "Me Preguntan Sobre El Diseño Del Sistema" Paseman, 2010.02.14