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$
4
  • 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, 2015 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, 2015 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$ Mar 29, 2015 at 0:23
  • $\begingroup$ So, what is the motivation/context for this conjecture? $\endgroup$ Apr 5, 2015 at 1:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.