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^{(2)}$ is the edge set of the nearest 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.
Best Answer
My idea of a spanning subgraph is usually a spanning tree, which implies both subgraph and graph are connected. That does not seem to be the case here, so I will assume that the vertex set of the spanning subgraph is the same as that of the original graph (which looks like a square grid to me). Unfortunately, I only have suggestions for attempts, not an answer.
Note that reflection across the line x=y maps connected subgraphs to themselves, so that your inequality would be equality if the condition that the spanning subgraph was connected was added. I don't see any other symmetries that help with this problem.
Consider now the problem of enumeration; assuming m and p are both large enough that there are graphs of both types ([m.p] versus [p,m]) which have x and (0,0) in the same connected component; look at counting all simple paths of length l that exhibit the connection. This does not give you the answer, but it prepares you for the next step, which is counting all graphs with l edges that are connected, and contain x and (0,0). When you have that enumeration for each of the two classes, that should get you close to the answer, for you will have some freedom in assigning the remaining edges.
There is also checking easy cases, e.g. when m = n^2-n and p = x_2. It does suggest your inequality should hold and be strict for nearby feasible values of m and p.
Gerhard "Ask Me About System Design" Paseman, 2010.02.14