6
$\begingroup$

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_n\subset 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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
1
$\begingroup$

My idea of a spanning subgraph is usually a spanning tree, which implies both subgraph and graph are connected. That does not seem to be the case here, so I will assume that the vertex set of the spanning subgraph is the same as that of the original graph (which looks like a square grid to me). Unfortunately, I only have suggestions for attempts, not an answer.

Note that reflection across the line x=y maps connected subgraphs to themselves, so that your inequality would be equality if the condition that the spanning subgraph was connected was added. I don't see any other symmetries that help with this problem.

Consider now the problem of enumeration; assuming m and p are both large enough that there are graphs of both types ([m.p] versus [p,m]) which have x and (0,0) in the same connected component; look at counting all simple paths of length l that exhibit the connection. This does not give you the answer, but it prepares you for the next step, which is counting all graphs with l edges that are connected, and contain x and (0,0). When you have that enumeration for each of the two classes, that should get you close to the answer, for you will have some freedom in assigning the remaining edges.

There is also checking easy cases, e.g. when m = n^2-n and p = x_2. It does suggest your inequality should hold and be strict for nearby feasible values of m and p.

Gerhard "Ask Me About System Design" Paseman, 2010.02.14

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Spanning means that it has the same vertex set, it can contain isolated vertices. But I agree that the word spanning is unnecessary. I do not think that reflection across the line x=y would be the identity for connected subgraphs. $\endgroup$
    – domotorp
    Commented Feb 14, 2010 at 8:46
  • $\begingroup$ The reflection map itself would not be the identity, but it would map spanning trees to spanning trees, using my notion of spanning. Under this notion, I see card(m,p,x) = card(p,m,x), because I am just counting some of the graphs which connect all the vertices, and reflection gives a bijection to two of the sets of interest. Of course, his notion of spanning gives a more challenging problem. $\endgroup$
    – Gerhard Paseman
    Commented Feb 14, 2010 at 8:58
  • $\begingroup$ hi Gerhard, thank you for think about the problem. I would like to remark that both $[m,p]_x$ and $[p,m]_x$ can not contain any connected spanning subgraphs, for instance as long as $ m+p < n-1 $. The problem with the reflection along the line $x=y$ is that it do not preserve in general the property 2, i.e., $0$ and $x$ are in the same connected component. For the other hand if $m$ and $p$ are large enough every spanning subgraph in $[m,p]_x$ could be connected and therefore the the reflection works because it maps connected in connected, in particular property 2 is in hold. $\endgroup$
    – Leandro
    Commented Feb 14, 2010 at 19:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .