Sandbox:DavidKohler/Relativized Alon Conjecture/Regular tree completion

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, Tree_d(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

${\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}}$

Where λ₁(Tree_d(ψ)) 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 {\text{det}}\left[I-Z_{G}(z)\right]=0$ In other words, we have $\displaystyle {\frac {1}{\lambda _{1}({\text{Tree}}_{d}(\psi ))}}=\inf \left\{z\mid {\text{det}}\left[I-Z_{G}(z)\right]=0\right\}$ Where ZG(z) is the adjacency matrix of G. Lemma For any connected graph ψ and the variable length graph G = Treed(ψ) we have $\displaystyle Z_{G}(z)=zA+{\frac {dI-D}{d-1}}S_{d}(z)$ where A = Aψ is the adjacency matrix of the graph ψ, D = Dψ is its degree matrix and $S_{d}(z)={\frac {1-{\sqrt {1-4(d-1)z^{2}}}}{2}}$ Proof (As in Friedman) Lemma The largest irreducible eigenvalue of the graph ψ, λIrred(ψ) is the inverse of the smallest root, y of the equation $\displaystyle \det[I-yA+y^{2}(D-I)]=0$ Proof This is a straight consequence of Bass' formula: $\displaystyle \det[H-\lambda I]=(\lambda ^{2}-1)^{\chi (\psi )}\cdot \det[(\lambda ^{2}+d-1)I-\lambda A]$ 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 y=y(z)={\frac {z}{1-S_{d}(z)}}\iff z=z(y)={\frac {y}{(d-1)y^{2}+1}}$ which is valid if $\displaystyle |z|<{\frac {1}{2{\sqrt {d-1}}}}\quad {\text{and}}\quad |y|<{\frac {1}{\sqrt {d-1}}}$ Notice that this change of variable is increasing as long as it converges. Then we have $\displaystyle I-Z_{G}(z)=(1-S_{d}(z))(I-yA+y^{2}(D-I))$ which holds for $\displaystyle |z|<{\frac {1}{2{\sqrt {d-1}}}}$ We can now finish the proof. First, take the case where λ1(Treed(ψ)) > 2√d-1 then there is a z0 such that $\displaystyle z_{0}<{\frac {1}{2{\sqrt {d-1}}}}$ which is a root of the equation $\displaystyle \det[I-Z_{G}(z)]=0$ Let $\displaystyle y_{0}=y(z_{0})={\frac {z_{0}}{1-S_{d}(z_{0})}}$ which is clearly a root of the equation $\displaystyle \det[I-yA+y^{2}(D-I)]=0$ and since $\displaystyle y_{0}<{\frac {1}{\sqrt {d-1}}}$ we can conclude that $\displaystyle \lambda _{\text{Irred}}(\psi )>{\sqrt {d-1}}$ 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 {\frac {1}{z_{0}}}\leq 2{\sqrt {d-1}}$ Assume by contradiction that $\displaystyle \lambda _{\text{Irred}}(\psi )>{\sqrt {d-1}}$ then there exists a y0 such that $\displaystyle y_{0}<{\frac {1}{\sqrt {d-1}}}$ and that is a root of the equation $\displaystyle \det[I-yA+y^{2}(D-I)]=0$ But then, our correspondence of eigenvalues gives an associated eigenvalue z0 such that $\displaystyle z_{0}<{\frac {1}{2{\sqrt {d-1}}}}$ which contradicts our hypothesis. Hence we can claim that $\displaystyle \lambda _{\text{Irred}}(\psi )\leq {\sqrt {d-1}}$ which concludes the proof of this property.

To do
	In the proof of the property, there is a lemma that is missing a proof.