\documentclass[12pt]{amsart}
\pagestyle{empty}
\usepackage[hmargin=1in,vmargin=1in]{geometry}
\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{fancyhdr} 
\usepackage[T1]{fontenc}


\usepackage{url,  mathrsfs}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{graphicx,  epstopdf}
\usepackage{subfig}
\usepackage{color}
\usepackage{bbm}
\usepackage{subfloat}
\usepackage[draft]{fixme}
\usepackage{bm} 
\usepackage{bbm} 
\usepackage{epigraph}
\usepackage{endnotes}
\usepackage{ifpdf}
\usepackage{array}

\usepackage{multicol}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{tikz}

\newcommand{\A}{\mathbb{A}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\ol}{\overline}
\newcommand{\J}{\mathcal{J}}
\newcommand{\X}{\mathcal{X}}
\theoremstyle{definition}
\newtheorem{prob}{Problem}
\newtheorem{extraProb}{Extra Problem}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\ext}{ext}




\begin{document}
 \thispagestyle{empty}
\begin{center} {\large \textbf{Math 409 -- Homework  6}} \smallskip \\ 
Due on Thursday, May 16\ \\ \ \\
 \end{center}

You are welcome to talk with other students in the class about problems but should write up solutions on your own. 
Solutions can be handwritten or typed but need to be legible and submitted via Gradescope by the end of the day 
on Thursday. You should justify all your answers in order to receive full credit.  


\bigskip 


\begin{prob}
Let $G = (V_1\cup V_2,E)$ be a bipartite graph. We saw in class the maximum size matching of $G$ 
can be solved by the linear program 
\[
{\rm (P)} \ \ \ \max 
\sum_{e\in E} x_e  \ \ \ {\rm s.t.} \ \ \  0\leq x_e \ \ \forall e \in E \ \ \  \text{ and }  \ \ \  \sum_{e\ni v} x_e \leq 1   \ \ \forall v\in V
\]
\begin{enumerate}
\item[(a)] How should you define $A$, $b$, $c$ so that (P) has the form $\max\{ c^Tx : Ax\leq b, x\geq 0\}$? \smallskip 
\item[(b)] Write the dual linear program (D) as in Problem 3 of Homework 5 explicitly in variables $y_v$ for $v\in V$. \smallskip 
\item[(c)] Prove that all of the vertices of the feasible region for (D) are integer. \smallskip 
\item[(d)] 
What familiar discrete optimization problem does this dual LP solve? Explain. 
\end{enumerate}
\end{prob}
\bigskip 

\begin{prob}
Show that the node-edge incidence matrix of any  (undirected) cycle of odd length has determinant equal to $\pm 2$. 
After a permutation of labels, you can take the cycle to have edges $e_1, \hdots, e_{2n+1}$ where $e_1 = \{v_1, v_2\}, \hdots, e_{2n} = \{v_{2n}, v_{2n+1}\} $ and $e_{2n+1} = \{v_{2n+1}, v_1\}$. \smallskip

\noindent\emph{Remark:} A graph is bipartite if and only if is has no odd cycles. This shows that the node-edge incidence matrix of a undirected non-bipartite graph is not totally unimodular.
\end{prob}


\bigskip 

\begin{prob} \ 
\begin{itemize}
\item[(a)] Which of the following matrices are totally unimodular? Explain why or why not. 
$$A_1 = \left( \begin{array}{ccccc} 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \end{array} \right), 
\,\,\,\,\, A_2 = \left( \begin{array}{rrrrrrr} -1& 0 & 1 & 0 & -1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ -1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & -1 & 0 \end{array} \right).$$
\item[(b)] Give an example of a polytope $P = \{x\in \R^n: Ax\leq b\}$ with $b\in \Z^m$, where $A\in \{0,\pm 1\}^{m\times n}$ is \emph{not} 
totally unimodular but all of the vertices of $P$ are integer. \smallskip \\
\end{itemize}
\end{prob}



\end{document}