\documentclass[12pt]{amsart}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{enumerate}
\usepackage{verbatim}
%\numberwithin{equation}{section}

%%%Document Configuration
\pagestyle{headings}
%\addtolength{\topmargin}{-.5in}
\textwidth = 6in 
\oddsidemargin = .25in
\evensidemargin = .25in
\voffset = -1in
\textheight = 9.5 in
%\textwidth = 6in
%\parindent = 0in
%\headsep = 0in
\relpenalty = 9999
\binoppenalty = 9999
%linespacing
\renewcommand{\baselinestretch}{1.25}
\reversemarginpar     
%%%

%%%Theorem Configuration
\theoremstyle{plain}
\newtheorem*{main}{Main~Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem*{thm*}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{exer}[thm]{Exercise}
\newtheorem{fact}[thm]{Fact}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{hw}[section]{}
%\newtheorem{hw}[section]{HW}
\newtheorem{dfn}{Definition}[section]
\newtheorem*{dfn*}{Definition}
%%%

%%%Bibliography Configuration
\bibliographystyle{plain}
%%%

%%%semantic definitions
\DeclareMathOperator*{\Aut}{Aut}
\DeclareMathOperator*{\Dom}{Dom}
\DeclareMathOperator*{\Mod}{Mod}
\DeclareMathOperator*{\Th}{Th}
\DeclareMathOperator*{\tp}{tp}
\renewcommand{\div}{\mid}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\Acl}[1]{\obar{#1}}
\newcommand{\assign}{\leftarrow}
\newcommand{\caseif}{\Rightarrow}
\newcommand{\caseonlyif}{\Leftarrow}
\newcommand{\cantprove}{\nvdash}
\newcommand{\ceil}[1]{\lceil{#1}\rceil}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\minus}{\setminus}
\newcommand{\power}[1]{{\mathcal{P}}({#1})}
\newcommand{\nonnegative}{\mathbb{N}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\intersect}{\cap}
\newcommand{\isomorphic}{\simeq}
\newcommand{\obar}[1]{\overline{#1}}
\newcommand{\proves}{\vdash}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\union}{\cup}
\newcommand{\units}[1]{{\left(#1\right)}^{\times}}
%%%

%%%local definitions
\newcommand{\bd}{\partial}
\newcommand{\eleq}{\equiv}
\newcommand{\elleq}{\preccurlyeq}
\newcommand{\lang}[1]{{\mathcal{#1}}}
\newcommand{\gspan}[1]{{\langle{#1}\rangle}}
\newcommand{\Los}{{\L o\'s}}
\newcommand{\LS}{{L\"{o}wenheim-Skolem }}
\newcommand{\mathscr}[1]{{\mathcal{#1}}}
\newcommand{\monster}{{\mathbb{M}}}
\newcommand{\st}[1]{{\mathcal{#1}}}
\newcommand{\structure}[1]{{\mathcal{#1}}}
\newcommand{\struct}[1]{\left\langle#1\right\rangle}
\newcommand{\subst}{\prec}
\newcommand{\symAnd}{\mathop{\bigwedge}}
\newcommand{\symand}{\wedge}
\newcommand{\symimply}{\rightarrow}
\newcommand{\symiff}{\leftrightarrow}
\newcommand{\symnot}{\neg}
\newcommand{\symor}{\vee}
\newcommand{\tuple}[1]{\obar{#1}}
\newcommand{\Tfcp}{T_E^{\text{fcp}}}
\newcommand{\WFF}{well-formed formula}
\newcommand{\0}{\textbf{0}}
\newcommand{\suc}{\textbf{S}}
\newcommand{\A}{\mathfrak{A}}
\newcommand{\B}{\mathfrak{B}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\NNN}{\mathfrak{N}}
\newcommand{\E}{\textbf{E}}
\newcommand{\Cn}{\textrm{Cn}}
\newcommand{\res}{\upharpoonright}
%%%

\begin{document}

\title{Arithmetic Combinatorics Homework 1}
\author{Dakota Blair}
\maketitle

\begin{hw}
Let $G$ be a $k$-regular graph.
Prove that the largest eigenvalue of $A(G)$,
the adjacency matrix of $G$ is $k$ and
has multiplicity equal to the number of connected components.
\end{hw}

\begin{thm*}[Gershgorin Circle Theorem]
Every eigenvalue $\lambda$ of a matrix $A$ satisfies
$\lambda \leq |a_{i,i} - \sum_{i \neq j}^{n-1}a_{i,j}|$
for some $i$.
\end{thm*}

\begin{thm*}[Perron-Frobenius Theorem]
If $A$ is a nonnegative irreducible matrix
then the largest eigenvalue has multiplicity $1$.
\end{thm*}

\begin{proof}
Without losing generality
the vertices of $G$ may be reordered appropriately so that
$A = A(G)$ is a block diagonal matrix,
with each block corresponding to a connected component of $G$.
Let $A = (a_{i,j})$ where $a_{i,j}$ is
the entry of $A$ in the $i$th row and $j$th column.
Further let $A = \sum_{i=0}^{n-1}c_i e_i$
where $e_i = (\delta_{i,j})_{j=0}^{n-1}$
and $\delta_{i,j} = 1$ when $i=j$ and $0$ otherwise.
Let $v = \sum_{i=0}^{n-1} e_i$.
Then $Av^T = kvT$ 
Therefore $k$ is an eigenvalue of $A$.
Let $A'$ be the adjacency matrix of a connected component of $G$.
Note that if $t > k$ then $A' - tI$ is diagonally dominated,
that is the sum of entries on any row is
less in absolute value than the diagonal entry.
Thus by the Gershgorin circle theorem $k$ must be maximal among eigenvalues.
Since $A'$ is the adjacency matrix of a connected graph it is irreducible.
Therefore the eigenvalue $k$ has multiplicity $1$ by the Perron-Frobenius theorem.
Further in $A - \lambda I$ the determinant will be
the product of the determinants of the blocks
corresponding to connected components of $G$.
Therefore the multiplicity of $k$ as an eigenvalue of $A$ is exactly
the number of connected components of $G$.
\end{proof}

\begin{hw}
Let $G_{n,k} = (V,E)$ be a bipartite graph on $2n$ vertices.
Let $V$ be partitioned into $(X,Y)$
where $X = \{x_i\}_{i=0}^{n-1}$ and $Y = \{y_i\}_{i=0}^{n-1}$.
Pick $S = \{\sigma_i\}_{i=0}^{k-1} \subset S_n$ randomly.
Let $(x_i, y_j) \in E \iff \sigma(i) = j$ for some $\sigma \in S$.
Note that this definition implies that $G_{n,k}$ is $k$-regular.
Then $G_{n,k}$ forms a family of expanders almost surely.
\end{hw}

\begin{proof}
For any graph $G_{n,k}$, $c(B)$ will be minimal for $|B| = n$.
In our graph we should select half the vertices in $X$ and half in $Y$.
If $n$ is odd, select the last vertex from $X$.
Without losing generality we may relabel $X$ such that our selection
corresponds to
$B_0 = \{x_i\}_{i=0}^{\ceil{n/2}} \union \{y_i\}_{i=0}^{\floor{n/2}}$.
The probability that $(u,v) \in E$ such that $u \in B_0$ and $v \not \in B_0$
is $1/2$ since $S$ was chosen at random,
and $B_0$ contains half the vertices of $V$.
Therefore the expected value of $|\bd B_0| = \frac{kn}{2}$.
Thus the expected value of $c(G_{n,k})$ is $\frac{kn/2}{n} = k/2$.

If $G_{n,k}$ is not connected then $c(G_{n,k}) = 0$.
If the action of $\gspan{S}$ on $\{0, 1 \cdots, n-1\}$ is transitive
then $G_{n,k}$ is connected.
In this case there is a Hamiltonian cycle in the graph
If the choice of $S$ is restricted to sets
of permutations with this property,
then the graphs will form a family of expanders. 
\end{proof}

\begin{hw}
Let $A = (a_{i,j})$ be an adjacency matrix of a graph
with vertices $\{v_i\}_{i=0}^{n-1}$ and that $A^{2m} = (b_{2m,i,j})$.
%Prove that $b_{i,i}$ is
%the number of closed walks of length $2m$ from $v_i$ to $v_i$.
Show that $b_{i,i}$ is greater than or equal to
the number of closed walks of length $2m$
on a $k$-regular tree from a vertex to itself.
\end{hw}

\begin{proof}
The number of walks of length $m$ on a $k$-regular tree from one vertex
is equal to $k(k-1)^{m-1}$.
Since a tree has no cycles, these walks are all distinct.
By symmetry a vertex at the end of a walk of length $m$ has the same number
of walks back to the original vertex.
Therefore the total number of walks of length $2m$
from a vertex to itself in a $k$-regular tree
is $(k(k-1)^{m-1})^2$.
This is the maximum number of distinct walks as introducing a cycle
would identify vertices in the tree,
thereby decreasing the number of disjoint walks.
\end{proof}
\end{document}
