Stiffness matrices of graph blow-ups and the $d$-dimensional algebraic connectivity of complete bipartite graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908295889944576 |
|---|---|
| author | Jung, Yunseong Lew, Alan |
| author_facet | Jung, Yunseong Lew, Alan |
| contents | 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-λ)$, where $λ\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01181 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stiffness matrices of graph blow-ups and the $d$-dimensional algebraic connectivity of complete bipartite graphs Jung, Yunseong Lew, Alan Combinatorics 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-λ)$, where $λ\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. |
| title | Stiffness matrices of graph blow-ups and the $d$-dimensional algebraic connectivity of complete bipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2504.01181 |