latex file for MATH3632 Group Problem #1

GroupPresentation1.tex

\documentclass{amsart}
\usepackage{amssymb,amsmath,latexsym,times,tikz, enumitem}

\pagestyle{empty}

\begin{document}

\hrule

\vspace{1pt}

\hrule

\vspace{4pt}

\begin{center}
Solution of Presentation Problem Set 1, \# 5\\
Solved by: Phil Lopreiato and Brannon McGraw
\end{center}

\hrule

\vspace{1pt}

\hrule

\vspace{20pt}

\noindent
\textbf{Problem 5:} \emph{Prove that for any simple graph G = (V, E), there is a partition ${U, W}$ of V for which \textit{e}(U, W) \textgreater $\frac{|E|}{2}$ where \textit{e}(U, W) is the number of edges that have one endpoint in U and the other in W. Also, prove that every simple graph with average degree \textit{d} has a bipartite subgraph with average degree greater than $\frac{d}{2}$}

\vspace{.5cm}

\begin{enumerate}[label=\alph*]

\item Let's show that there is a partition ${U, W}$ of V for which \textit{e}(U, W) \textgreater $\frac{|E|}{2}$
\begin{description}
    \item[First] Investigate the average value of \textit{e}(U, W) over all possible partition $(U, W)$. This value is equal to $\sum_{partition U,W}^{} \frac{\sum_{edge \in E}{} |e(U, W|}{\# of partitions}$. We also know that $e(U, W)$ is a bijective function (because every edge can contribute at most once per possible partition), so the average value is also equal to: $\sum_{e \in E}^{} \frac{\# partitions where e \in e(U, W)}{\# of partitions}$
    \item[Second] If we take a graph with n vertices, and fix two of those vertices in different partitions (so, $v_1 \in U$ and $v_2 \in W$), then there are $2^{n-2}$ ways to assign partitions to the remaining vertices. Further, by a similar reasoning, there are $2^{n-1} - 1$ total possible partitions ($2^{n-1}$ total possible partitions, less the case where all vertices are assigned to the same partition). This makes the average value of $\sum_{e \in E}^{} \frac{2^{n-2}}{2^{n-1} - 1}$. Since the inner part of the summation is a constant, we can rearrange the terms to get the average value for $e(U, W)$
        \begin{equation} \label{eq:avg}
        \frac{|E| * 2^{n-2}}{2^{n-1} - 1}
        \end{equation}
    \item[Third] Now, assume that there exists a graph where, for every partition $(U, W)$, $E(U, W) \leq \frac{|E|}{2}$. If we still want to maximize the average value of $e(U, W)$, then every partision will have $e(U, W) = \frac{|E|}{2}$, which would also be the average value. $\frac{|E|}{2} < \frac{|E| * 2^{n-2}}{2^{n-1} - 1}$ for $n > 1$ (And when $n = 1$, the graph has no edges (because it's simple), so the case is trivial). Thereofre, there must be at least one partition where $e(U, W) > \frac{|E|}{2}$. $\square$
\end{description}

\item Now, let's show that every simple graph with average degree \textit{d} has a bipartite subgraph with average degree greater than $\frac{d}{2}$
\begin{description}
    \item[First] If the average degree of the graph is $d$, then $d = \frac{2|E|}{|V|}$ (using the Handshake Lemma).
    \item[Second] Use the result of the first part and choose a partition $(U, W)$ of the graph where $e(U, W) > \frac{|E|}{2}$. Remove all of the edges that go in between vertices in the same partition. Now, the average degree of the bipartite subgraph (since the only remaining edges are from $e(U, W)$, which goes between the two partitions, by definition) is $\frac{2* e(U, W)}{|V|}$. We know $e(U, W) > \frac{|E|}{2}$, therefore $2 * e(U, W) > |E| \rightarrow \frac{2 * e(U, W)}{|V|} > \frac{|E|}{|V|} = \frac{d}{2}$ $\square$
\end{description}

\end{enumerate}

\end{document}