\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{times}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{graphicx}
\newcommand{\myparskip}{6pt}
\parskip \myparskip
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{assumption}[lemma]{Assumption}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{prop}[lemma]{Proposition}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{prob}{Problem}
\newenvironment{myprob}{\begin{prob} \em}{\end{prob}}
\newcommand{\opt}{\mbox{\sc opt}}
\newcommand{\eps}{\epsilon}
\newcommand{\mE}{\mathcal{E}}
\newcommand{\mI}{\mathcal{I}}
\newcommand{\mM}{\mathcal{M}}
\newcommand{\elconn}{\kappa'}
\begin{document}
\setlength{\fboxrule}{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength{\boxlength}\setlength{\boxlength}{\textwidth}
\addtolength{\boxlength}{-4mm}
%\begin{center}\framebox{\parbox{\boxlength}{%\bf
\begin{center}
{\bf Spring 2022, CS 586/IE 519: Combinatorial Optimization\\
Homework 4}\\
Due: Thursday, April 14, 2022
\end{center}
%}}\end{center}
\vspace{5mm}
\noindent {\bf Instructions and Policy:}
Each person should write up their own solutions independently. You
need to indicate the names of the people you discussed a problem
with. Solutions to most of these problems can be found from one source
or the other. Try to solve on your own first, and cite your sources if
you do use them.
\noindent
Please write clearly and concisely. Refer to known facts. You should
try to convince us that you know the solution, as quickly as possible.
Submit solutions to at least four problems.
\noindent
\begin{myprob}
Given a graph $G=(V,E)$ let $\mI = \{ S \subseteq V \mid \mbox{there
is a matching $M$ in $G$ that covers $S$}\}$. Prove that $(V,\mI)$
is a matroid.
\end{myprob}
\iffalse
\begin{myprob}
Let $G=(V,\mE)$ be a hypergraph, that is each $e \in \mE$ is a
hyperedge, in other words $e \subseteq V$. We say that $X \subseteq \mE$ a
{\em forest-representable} if one can choose for each $e \in X$ two nodes
in $e$ such that the chosen pairs when viewed as edges form a forest
on $V$. Prove that $(\mE,\mI)$ is a matroid where
$\mI = \{ X \subseteq \mE \mid \mbox{$X$ is forest-representable}\}$.
This is called the hypergraphic matroid.
\end{myprob}
\fi
\begin{myprob}
Let $G=(V,E)$ be a graph and let $\mI=\{J\subseteq E: |J \cap E(U)| \le 2|U| - 3, U \subseteq V, |U| > 1\}$.
Show that $(E,\mI)$ is a matroid.
\end{myprob}
\begin{myprob}
Let $A$ be a full-rank $n \times n$ matrix over the reals. Let $R$
and $C$ be the index sets of the rows and columns. Given $I \subset
R$ show that there exists $J \subset C$ such that $|I| = |J|$ and
both $A(I,J)$ and $A(R\setminus I, C\setminus J)$ are of full
rank. Use matroid intersection.
\end{myprob}
\begin{myprob}
We saw that matroid union can be algorithmically reduced to matroid
intersection. One can derive the matroid intersection theorem from
matroid union theorem. Givem two matroids $\mM_1=(S, \mI_1)$ and
$\mM_2=(S,\mI_2)$ let $\mM = \mM_1 \vee \mM_2^*$ be the union of
$\mM_1$ and the dual of $\mM_2$. Let $B$ be a base of $\mM$; it
follows that $B$ can be partitioned into $J_1$ and $J_2$ where $J_1$
is independent in $\mM_1$ and $J_2$ is independent in $\mM_2^*$.
Extend $J_2$ (in an arbitrary way) to a base $B_2$ in
$\mM_2^*$. Show that $B\setminus B_2$ is maximum cardinality common
independent set of $\mM_1$ and $\mM_2$.
\end{myprob}
\begin{myprob}
Consider the following graph orientation problem: given an undirected
graph $G=(V,E)$ and a positive integer $k$, determine if there exists
an orientation of the edges of $G$ such that each vertex has in-degree
at most $k$.
\begin{itemize}
\item Formulate this problem as a matroid intersection problem.
\item Use the min-max relation for the max cardinality of a common independent set of two matroids to show that such an orientation exists if and only if $|E[S]|\le k|S|$ for every subset $S\subseteq V$.
\end{itemize}
\end{myprob}
\iffalse
\begin{myprob}
\end{myprob}
\begin{myprob}
\end{myprob}
\fi
\end{document}