Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Maybe you could include a link to the MO question to make it easier for us to see what, if any, response you got there? Alternatively, maybe you should just make some trivial edit to the MO question, so as to bounce it back up to the front page. Maybe then someone will see it who missed it (or wasn't around MO) in 2010. – Gerry Myerson Oct 6 '11 at 1:19
Hi Gerry,thank you for the suggestions. I will add here the mathoverflow link. – Leandro Oct 6 '11 at 1:40
I'm voting to close this question as off-topic because it has also been posted (and has received an answer) on Mathoverflow. – Mike Pierce Sep 20 '15 at 19:03
@MikePierce: The 'answer' there says "Unfortunately, I only have suggestions for attempts, not an answer." – user21820 Sep 21 '15 at 2:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.