Thursday, 21 January 2016

graph theory - Comparing number of spanning subgraphs

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

No comments:

Post a Comment