3
$\begingroup$

I posted this question on mathoverflow in 2010 and until now this question remains unanswered there. In my opinion the problem is also suitable to be discussed here and I hope there is no problem with this duplication. (If I am wrong I do not mind to delete this question.)

Question. 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=\{\ \{z,w\}: z,w\in V_n\ \text{and}\ \ \sum_{i=1}^2 |z_i-w_i| =1 \ \}.$ For each fixed $n$ the graph $G_n$ is the usual square lattice of side $n$.

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\ , \text{whenever}\ p < m ?$

Here $[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 available 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 quantities of horizontal and vertical are switched ?

Link for the Mathoverflow thread.

  • 0
    @MikePierce: The 'answer' there says "Unfortunately, I only have suggestions for attempts, not an answer."2015-09-21

0 Answers 0