Hi all,
Let be $G_n=(V_n,E_n)$ a finite graph, where $V_n= \{0,1,\ldots, n\} \times\{0,1,\ldots,n\}$
and $E_n\subset V_n\times V_n$ V_n^{(2)}$ is the edge set joining of the nearest neighboors neighbors in the $\ell^1$ norm, that is, $\ E_n=\{\ \{z,w\}\subset V_n; \ \sum_{i=1}^2 |z_i-w_i| =1 \ \}.$
Fix a vertex $x=(x_1,x_2)\in G_n$ such that $x_2>x_1$ (up-diagonal). I would like to know if it is true the following inequality:
$\sharp[m,p]_{x}\leq \sharp[p,m]_x$, whenever $p < m$
where $[m,p]_{x}$ is the set of all spanning subgraphs of $G_n$ satisfying the following properties:
1- the spanning subgraph has $m$ horizontal edges and $p$ vertical edges;
2- the vertices $(0,0)$ and $x=(x_1,x_2)$ are in the same connected component,
and $\sharp A$ is the cardinality of $A$.
In other words, if I have avaliable more vertical edges than horizontal ones is it true that I can find more configurations connecting $0$ and $x$ if $x$ is up-diagonal than in case that the quanties of horizontal and vertical are inverted ?
Thanks in advance for any idea or reference.
Edition:
I would like to add a simple reduction for this problem. Since we have $(n+1)^2$ vertices
in any spanning subgraph the problem is solved if $m+p\geq (n+1)^2-1$, since any subgraph with this quantity of edges has a tree as subgraph on it. Therefore the reflection $R$ along the axis x=y sends $[m,p]_x$ to
$[p,m]_x$ bijectively and the inequality is this case becomes an equality.
The non-connected case still unanswered. Any help is very welcome.
