图扩张的刚度矩阵与完全二分图的$d$维代数连通性
Stiffness matrices of graph blow-ups and the $d$-dimensional algebraic connectivity of complete bipartite graphs
摘要 Abstract
图$G=(V,E)$的$d$维代数连通性$a_d(G)$是其$d$维刚性的定量度量,定义为与将图嵌入$\mathbb{R}^d$相关的刚度矩阵的特征值。对于函数$a:V\to \mathbb{N}$,我们记$G^{(a)}$为$G$的$a$-扩张图,即通过将每个顶点$v\in V$替换为大小为$a(v)$的独立集所得到的图。我们确定了$G^{(a)}$的刚度矩阵特征值与其原始图$G$的某些加权刚度矩阵特征值之间的关系。这解决了Lew、Nevo、Peled和Raz关于完全图平衡扩张的刚度特征值的一个猜想。作为应用,我们得到了完全二分图的$d$维代数连通性的下界。更具体地,我们证明如下:设$K_{n,m}$为具有大小分别为$n$和$m$两边的完全二分图。则对于每个$d\geq 1$,存在$c_d>0$,使得对于所有$n,m\geq d+1$且$n+m\geq \binom{d+2}{2}$,有$a_d(K_{n,m})\geq c_d\cdot \min\{n,m\}$。该界至多相差一个乘法常数。在特殊情况下$d=2$,$n=m=3$时,我们得到改进的界$a_2(K_{3,3})\geq 2(1-\lambda)$,其中$\lambda\approx 0.6903845$是多项式$176x^4-200x^3+47x^2+18x-9$的唯一正实根,我们推测此界为紧界。
The $d$-dimensional algebraic connectivity $a_d(G)$ of a graph $G=(V,E)$ is a quantitative measure of its $d$-dimensional rigidity, defined in terms of the eigenvalues of stiffness matrices associated with different embeddings of the graph into $\mathbb{R}^d$. For a function $a:V\to \mathbb{N}$, we denote by $G^{(a)}$ the $a$-blow-up of $G$, that is, the graph obtained from $G$ by replacing every vertex $v\in V$ with an independent set of size $a(v)$. We determine a relation between the stiffness matrix eigenvalues of $G^{(a)}$ and the eigenvalues of certain weighted stiffness matrices associated with the original graph $G$. This resolves, as a special case, a conjecture of Lew, Nevo, Peled and Raz on the stiffness eigenvalues of balanced blow-ups of the complete graph. As an application, we obtain a lower bound on the $d$-dimensional algebraic connectivity of complete bipartite graphs. More precisely, we prove the following: Let $K_{n,m}$ be the complete bipartite graph with sides of size $n$ and $m$ respectively. Then, for every $d\ge 1$ there exists $c_d>0$ such that, for all $n,m\ge d+1$ with $n+m\ge \binom{d+2}{2}$, $a_d(K_{n,m})\ge c_d\cdot \min\{n,m\}$. This bound is tight up to the multiplicative constant. In the special case $d=2$, $n=m=3$, we obtain the improved bound $a_2(K_{3,3})\ge 2(1-\lambda)$, where $\lambda\approx 0.6903845$ is the unique positive real root of the polynomial $176 x^4-200 x^3+47 x^2+18 x-9$, which we conjecture to be tight.