Diameters and eigenvalues

Abstract

We derive a new upper bound for the diameter of a<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"><mml:semantics><mml:mi>k</mml:mi><mml:annotation encoding="application/x-tex">k</mml:annotation></mml:semantics></mml:math></inline-formula>-regular graph<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"><mml:semantics><mml:mi>G</mml:mi><mml:annotation encoding="application/x-tex">G</mml:annotation></mml:semantics></mml:math></inline-formula>as a function of the eigenvalues of the adjacency matrix. Namely, suppose the adjacency matrix of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"><mml:semantics><mml:mi>G</mml:mi><mml:annotation encoding="application/x-tex">G</mml:annotation></mml:semantics></mml:math></inline-formula>has eigenvalues<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda 1 comma lamda 2 comma ellipsis comma lamda Subscript n Baseline"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mo>,</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow><mml:mo>,</mml:mo><mml:mo>…</mml:mo><mml:mo>,</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">{\lambda _1},{\lambda _2}, \ldots ,{\lambda _n}</mml:annotation></mml:semantics></mml:math></inline-formula>with<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue lamda 1 EndAbsoluteValue greater-than-or-equal-to StartAbsoluteValue lamda 2 EndAbsoluteValue greater-than-or-equal-to midline-horizontal-ellipsis greater-than-or-equal-to StartAbsoluteValue lamda Subscript n Baseline EndAbsoluteValue"><mml:semantics><mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow></mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mo>≥</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:mrow><mml:mo>|</mml:mo></mml:mrow><mml:mo>≥</mml:mo><mml:mo>⋯</mml:mo><mml:mo>≥</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mi>n</mml:mi></mml:msub></mml:mrow></mml:mrow><mml:mo>|</mml:mo></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">\left | {{\lambda _1}} \right | \geq \left | {{\lambda _2}} \right | \geq \cdots \geq \left | {{\lambda _n}} \right |</mml:annotation></mml:semantics></mml:math></inline-formula>where<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda 1 equals k"><mml:semantics><mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mn>1</mml:mn></mml:msub></mml:mrow><mml:mo>=</mml:mo><mml:mi>k</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">{\lambda _1} = k</mml:annotation></mml:semantics></mml:math></inline-formula>,<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda equals StartAbsoluteValue lamda 2 EndAbsoluteValue"><mml:semantics><mml:mrow><mml:mi>λ</mml:mi><mml:mo>=</mml:mo><mml:mrow><mml:mo>|</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mrow class="MJX-TeXAtom-ORD"><mml:msub><mml:mi>λ</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:mrow><mml:mo>|</mml:mo></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">\lambda = \left | {{\lambda _2}} \right |</mml:annotation></mml:semantics></mml:math></inline-formula>. Then the diameter<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D left-parenthesis upper G right-parenthesis"><mml:semantics><mml:mrow><mml:mi>D</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>G</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">D(G)</mml:annotation></mml:semantics></mml:math></inline-formula>must satisfy<disp-formula content-type="math/mathml">\[<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper D left-parenthesis upper G right-parenthesis less-than-or-equal-to left ceiling log left-parenthesis n minus 1 right-parenthesis slash log left-parenthesis k slash lamda right-parenthesis right ceiling"><mml:semantics><mml:mrow><mml:mi>D</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>G</mml:mi><mml:mo stretchy="false">)</mml:mo><mml:mo>≤</mml:mo><mml:mrow><mml:mo>⌈</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext>log</mml:mtext></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>k</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>λ</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mo>⌉</mml:mo></mml:mrow></mml:mrow><mml:annotation encoding="application/x-tex">D(G) \leq \left \lceil {\log (n - 1)/{\text {log}}(k/\lambda )} \right \rceil</mml:annotation></mml:semantics></mml:math>\]</disp-formula>. We will consider families of graphs whose eigenvalues can be explicitly determined. These graphs are determined by sums or differences of vertex labels. Namely, the pair<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet i comma j EndSet"><mml:semantics><mml:mrow><mml:mo>{</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>i</mml:mi><mml:mo>,</mml:mo><mml:mi>j</mml:mi></mml:mrow><mml:mo>}</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">\left \{ {i,j} \right \}</mml:annotation></mml:semantics></mml:math></inline-formula>being an edge depends only on the value<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="i plus j"><mml:semantics><mml:mrow><mml:mi>i</mml:mi><mml:mo>+</mml:mo><mml:mi>j</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">i + j</mml:annotation></mml:semantics></mml:math></inline-formula>(or<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="i minus j"><mml:semantics><mml:mrow><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mi>j</mml:mi></mml:mrow><mml:annotation encoding="application/x-tex">i - j</mml:annotation></mml:semantics></mml:math></inline-formula>for directed graphs). We will show that these graphs are expander graphs with small diameters by using an inequality on character sums, which was recently proved by N. M. Katz.