Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.