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{array}{rl}{\lambda }_1({\text{Tree}}_d(\psi ))& =2\sqrt{d-1}⟺{\lambda }_{\text{Irred}}(\psi )\le \sqrt{d-1}\\ {\lambda }_1({\text{Tree}}_d(\psi ))& >2\sqrt{d-1}⟺{\lambda }_{\text{Irred}}(\psi )>\sqrt{d-1}\end{array}$

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 $\text{det}[I-Z_G(z)]=0$ In other words, we have $\frac{1}{{\lambda }_1({\text{Tree}}_d(\psi ))}=\inf \{z\mid \text{det}[I-Z_G(z)]=0\}$ Where ZG(z) is the adjacency matrix of G. Lemma For any connected graph ψ and the variable length graph G = Treed(ψ) we have $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 $\det [I-yA+y^2(D-I)]=0$ Proof This is a straight consequence of Bass' formula: $\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 $y=y(z)=\frac{z}{1-S_d(z)}⟺z=z(y)=\frac{y}{(d-1)y^2+1}$ which is valid if $|z|<\frac{1}{2\sqrt{d-1}}\text{and}|y|<\frac{1}{\sqrt{d-1}}$ Notice that this change of variable is increasing as long as it converges. Then we have $I-Z_G(z)=(1-S_d(z))(I-yA+y^2(D-I))$ which holds for $|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 $z_0<\frac{1}{2\sqrt{d-1}}$ which is a root of the equation $\det [I-Z_G(z)]=0$ Let $y_0=y(z_0)=\frac{z_0}{1-S_d(z_0)}$ which is clearly a root of the equation $\det [I-yA+y^2(D-I)]=0$ and since $y_0<\frac{1}{\sqrt{d-1}}$ we can conclude that ${\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 $\frac{1}{z_0}\le 2\sqrt{d-1}$ Assume by contradiction that ${\lambda }_{\text{Irred}}(\psi )>\sqrt{d-1}$ then there exists a y0 such that $y_0<\frac{1}{\sqrt{d-1}}$ and that is a root of the equation $\det [I-yA+y^2(D-I)]=0$ But then, our correspondence of eigenvalues gives an associated eigenvalue z0 such that $z_0<\frac{1}{2\sqrt{d-1}}$ which contradicts our hypothesis. Hence we can claim that ${\lambda }_{\text{Irred}}(\psi )\le \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.