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
    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.2011-10-06
  • 0
    Hi Gerry,thank you for the suggestions. I will add here the mathoverflow link.2011-10-06
  • 1
    I'm voting to close this question as off-topic because it has also been posted (and has received an answer) on Mathoverflow.2015-09-20
  • 0
    @MikePierce: The 'answer' there says "Unfortunately, I only have suggestions for attempts, not an answer."2015-09-21

0 Answers 0