7
$\begingroup$

Denote the adjacency matrix of a given undirected graph by $g$. It is an $n$-by-$n$ symmetric Boolean matrix with elements on the diagonal to be zero ($n\geq 3$). Let $g_{12}=g_{21}=g_{13}=g_{31}=1$ and $g_{23}=g_{32}=0$. We further define $$(x_1,x_2,...,x_n)^T=\left(\mathbf{I}-\lambda (g\ominus (1,2)\ominus(2,1))\right)^{-1}\mathbf{1};$$ $$(y_1,y_2,...,y_n)^T=\left(\mathbf{I}-\lambda g\right)^{-1}\mathbf{1};$$ $$(z_1,z_2,...,z_n)^T=\left(\mathbf{I}-\lambda (g\oplus (2,3)\oplus(3,2))\right)^{-1}\mathbf{1},$$ where $\lambda\in(0,1/(n-1))$, $\mathbf{I}$ is the identity matrix, $\mathbf{1}$ is an $n$-by-$1$ vector of ones, $g\ominus(1,2)\ominus(2,1)$ is the adjacency matrix of a graph that deletes the link between node $1$ and $2$ from the original graph $g$, and $g\oplus(2,3)\oplus(3,2)$ is the adjacency matrix of a graph that adds the link between node $2$ and $3$ to the original graph $g$.

If $y_1\geq y_2$ and $y_1\geq y_3$, we conjecture that $$x_1/y_1>y_3/z_3.$$

Let $\{y_{ij}\}_{n\times n}\equiv\left(\mathbf{I}-\lambda g\right)^{-1}.$ Clearly, $y_{i}=\sum_{j=1}^n y_{ij}$. It can be further shown that $$x_1=\frac{(1+\lambda y_{12})y_1-\lambda y_{11}y_2}{(1+\lambda y_{12})^2-\lambda^2 y_{11} y_{22}},$$ and $$z_3=\frac{\lambda y_{33}y_2+(1-\lambda y_{23})y_3}{(1-\lambda y_{23})^2-\lambda^2 y_{22} y_{33}}.$$ So our conjecture can rewritten as $$\frac{(1+\lambda y_{12})y_1-\lambda y_{11}y_2}{(1+\lambda y_{12})^2-\lambda^2 y_{11} y_{22}}\cdot \frac{\lambda y_{33}y_2+(1-\lambda y_{23})y_3}{(1-\lambda y_{23})^2-\lambda^2 y_{22} y_{33}}>y_1 y_3$$ if $y_1\geq y_2$ and $y_1\geq y_3$.

I initially wanted to look for a counter-example of this inequality, but after many trials, I couldn't find a counter-example. I wonder if this inequality always holds.

According to my simulation results, this inequality seems to always hold when $n\leq 8$ and both $y_1\geq y_2$ and $y_1\geq y_3$ are necessary for the inequality to hold.

Updates: it seems to me that even the condition that $g_{12}=g_{21}=g_{13}=g_{31}=1$ and $g_{23}=g_{32}=0$ is not necessary for this inequality to hold. In other words, given any symmetric Boolean matrix with elements on the diagonal to be zero, this inequality seems to hold as long as $y_1\geq y_2$ and $y_1\geq y_3$.

$\endgroup$
  • 2
    $\begingroup$ What is the meaning of $\lambda (g\ominus (1,2)\ominus(2,1))$, $\lambda (g\oplus (2,3)\oplus(3,2))$? $\endgroup$ – Russel Mar 26 '15 at 22:19
  • 1
    $\begingroup$ Reply to the first floor. I think $g\ominus(1,2)\ominus(2,1)$ should mean that replacing the elements in position (1,2) and (2,1) with 0 in matrix g. Similar: $g\oplus(1,2)\oplus(2,1)$ should mean that replacing the elements in position (1,2) and (2,1) with 1 in matrix g. $\endgroup$ – Galor Mar 28 '15 at 4:09
  • $\begingroup$ Thanks for the clarification above. $g\ominus(1,2)\ominus(2,1)$ is the adjacency matrix of a graph that deletes the link between node $1$ and $2$ from the original graph $g$. $g\oplus(2,3)\oplus(3,2)$ is the adjacency matrix of a graph that adds the link between node $2$ and $3$ to the original graph $g$. $\endgroup$ – liuchun deng Mar 29 '15 at 0:23
  • $\begingroup$ So, what is the motivation/context for this conjecture? $\endgroup$ – Felix Goldberg Apr 5 '15 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.