The regular tree completion of a given graph allows us to see important properties of the starting graph. In particular, it shows us that some subgraphs, that we call tangles, have a high second eigenvalue.
Definition
Let G be a finite connected graph with maximal degree less or equal to some integer d larger than 2. We define the d-regular tree completion of G to be the unique (up to isomorphism) infinite graph, Treed(G) which consists of attaching additional free edges to all vertices so that the graph obtained is d-regular. Equivalently, this is the universal covering of the starting graph.
Properties
Let ψ be a connected graph with maximal degree at most d > 2. Then we have
![{\displaystyle {\begin{aligned}\lambda _{1}({\text{Tree}}_{d}(\psi ))&=2{\sqrt {d-1}}\iff \lambda _{\text{Irred}}(\psi )\leq {\sqrt {d-1}}\\\lambda _{1}({\text{Tree}}_{d}(\psi ))&>2{\sqrt {d-1}}\iff \lambda _{\text{Irred}}(\psi )>{\sqrt {d-1}}\end{aligned}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/66790e99f35bf5b3f401361bcd2d87644d983fdf)
Where λ1(Treed(ψ)) is the spectral radius of that infinite graph and where λIrred(ψ) is the largest irreducible eigenvalue of the graph ψ.
Proof
|
Consider G, the VLG based on the graph ψ that realizes Treed(ψ). Then λ1(Treed(ψ)), the spectral radius of the d-regular tree completion of the the graph ψ, is the inverse of the infimum of all the positive roots, z, of the equation
![{\displaystyle \displaystyle {\text{det}}\left[I-Z_{G}(z)\right]=0}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/40798a1d9b1779d50bb1074ab69a665554061ab0)
In other words, we have
![{\displaystyle \displaystyle {\frac {1}{\lambda _{1}({\text{Tree}}_{d}(\psi ))}}=\inf \left\{z\mid {\text{det}}\left[I-Z_{G}(z)\right]=0\right\}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/f5f803a0873fd44c9343adad08bb74fa420437fa)
Where ZG(z) is the adjacency matrix of G.
Lemma
For any connected graph ψ and the variable length graph G = Treed(ψ) we have
![{\displaystyle \displaystyle Z_{G}(z)=zA+{\frac {dI-D}{d-1}}S_{d}(z)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/bfd125b6f4bb128c11940ea1b2bf00a33c368499)
where A = Aψ is the adjacency matrix of the graph ψ, D = Dψ is its degree matrix and
![{\displaystyle S_{d}(z)={\frac {1-{\sqrt {1-4(d-1)z^{2}}}}{2}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/a4f59689aaec3b2f3f20749be0668f0fd82ae8e7)
Lemma
The largest irreducible eigenvalue of the graph ψ, λIrred(ψ) is the inverse of the smallest root, y of the equation
![{\displaystyle \displaystyle \det[I-yA+y^{2}(D-I)]=0}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/be2db9e37d80bde8f465c27f6df4db96e6a79c03)
Proof
|
This is a straight consequence of Bass' formula:
![{\displaystyle \displaystyle \det[H-\lambda I]=(\lambda ^{2}-1)^{\chi (\psi )}\cdot \det[(\lambda ^{2}+d-1)I-\lambda A]}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/deb374b0b97d4d04ef512f470f46ec37740640f7)
where λIrred(ψ) is the largest solution of the equation
- Failed to parse (syntax error): {\displaystyle \displaystyle \det[H - \lambda I ] = 0 }
by substituting y = 1/λ we get the equivalence of the solutions.
|
Now consider the change of variables
![{\displaystyle \displaystyle y=y(z)={\frac {z}{1-S_{d}(z)}}\iff z=z(y)={\frac {y}{(d-1)y^{2}+1}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/8eafc61f3a3b186906b7999aa218961adc209721)
which is valid if
![{\displaystyle \displaystyle |z|<{\frac {1}{2{\sqrt {d-1}}}}\quad {\text{and}}\quad |y|<{\frac {1}{\sqrt {d-1}}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/b1cc0f7e4fa486414d3e02fb740fc4a267c9eb47)
Notice that this change of variable is increasing as long as it converges. Then we have
![{\displaystyle \displaystyle I-Z_{G}(z)=(1-S_{d}(z))(I-yA+y^{2}(D-I))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/e5d2bcecd2067f52438a3353519ee701eae679a4)
which holds for
![{\displaystyle \displaystyle |z|<{\frac {1}{2{\sqrt {d-1}}}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/c1bbea680074fc672bc34fcdeb455803cbea1755)
We can now finish the proof. First, take the case where λ1(Treed(ψ)) > 2√d-1
then there is a z0 such that
![{\displaystyle \displaystyle z_{0}<{\frac {1}{2{\sqrt {d-1}}}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/2ee888e42ce1af21d7fbb36a2eb9cc06c64843d1)
which is a root of the equation
![{\displaystyle \displaystyle \det[I-Z_{G}(z)]=0}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/0315dbb686a19c842efb4682af13269c2a2a701d)
Let
![{\displaystyle \displaystyle y_{0}=y(z_{0})={\frac {z_{0}}{1-S_{d}(z_{0})}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/95bb22636812aa63e4869e5b8d21a1c7619fd1dd)
which is clearly a root of the equation
![{\displaystyle \displaystyle \det[I-yA+y^{2}(D-I)]=0}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/be2db9e37d80bde8f465c27f6df4db96e6a79c03)
and since
![{\displaystyle \displaystyle y_{0}<{\frac {1}{\sqrt {d-1}}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/233e8378ae05ef50ea049c05bbe706cf53b076ef)
we can conclude that
![{\displaystyle \displaystyle \lambda _{\text{Irred}}(\psi )>{\sqrt {d-1}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/ca554fd0c718cff54d291147d5fc94c9d57a7525)
Finally, for the case where λ1(Treed(ψ)) = 2√d-1 then this means that if z0 is a root of det[I-ZG(z)] = 0 then we have that
![{\displaystyle \displaystyle {\frac {1}{z_{0}}}\leq 2{\sqrt {d-1}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/c7a2e0d3f8c6f64ab035748ffd2e0e720ff3740a)
Assume by contradiction that
![{\displaystyle \displaystyle \lambda _{\text{Irred}}(\psi )>{\sqrt {d-1}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/ca554fd0c718cff54d291147d5fc94c9d57a7525)
then there exists a y0 such that
![{\displaystyle \displaystyle y_{0}<{\frac {1}{\sqrt {d-1}}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/233e8378ae05ef50ea049c05bbe706cf53b076ef)
and that is a root of the equation
![{\displaystyle \displaystyle \det[I-yA+y^{2}(D-I)]=0}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/be2db9e37d80bde8f465c27f6df4db96e6a79c03)
But then, our correspondence of eigenvalues gives an associated eigenvalue z0 such that
![{\displaystyle \displaystyle z_{0}<{\frac {1}{2{\sqrt {d-1}}}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/2ee888e42ce1af21d7fbb36a2eb9cc06c64843d1)
which contradicts our hypothesis. Hence we can claim that
![{\displaystyle \displaystyle \lambda _{\text{Irred}}(\psi )\leq {\sqrt {d-1}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/6dbc29b227689b7427344c1c008cfe2a74f59dfc)
which concludes the proof of this property.
|
To do
|
|
In the proof of the property, there is a lemma that is missing a proof.
|