\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,amsthm}
\PassOptionsToPackage{obeyspaces}{url}
\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref}
\usepackage{tikz}
\usepackage{enumitem}
\setlist{itemsep=0.5em}
%% header definitions
\def\course{MATH 314}
\def\courselink{https://mathematicaster.org/teaching/graphs2022}
\def\assign{HW \#10}
\def\assignlink{hw10.tex}
\def\due{Apr 12}
\def\doctype{This homework is from}
%% environments
% theorem style
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{defn}[theorem]{Definition}
% definition style
\theoremstyle{definition}
\newtheorem{problem}{Problem}
% custom
\newenvironment{solution}{\paragraph{Solution.}}{\qed}
%% custom commands
\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link
\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality
\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality
\newcommand*{\eps}{\varepsilon} % prettier epsilon
\newcommand*{\R}{\mathbb{R}} % real numbers
\newcommand*{\C}{\mathbb{C}} % complex numbers
\newcommand*{\Q}{\mathbb{Q}} % rational numbers
\newcommand*{\Z}{\mathbb{Z}} % integers
\newcommand*{\N}{\mathbb{N}} % natural numbers
\newcommand*{\F}{\mathbb{F}} % field
\newcommand*{\family}{\mathcal{F}} % family
\newcommand*{\GL}{\mathbf{GL}} % general linear group
\newcommand*{\what}[1]{\widehat{#1}} % wider hat
\newcommand*{\wbar}[1]{\overline{#1}} % wider bar
\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal
\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf
\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb
% operators
\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability
\DeclareMathOperator*{\E}{\mathbb{E}} % expectation
\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance
\DeclareMathOperator*{\Span}{span} % span
\DeclareMathOperator{\tr}{tr} % trace
\DeclareMathOperator{\rank}{rank} % rank
\DeclareMathOperator{\supp}{supp} % support
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator{\comp}{comp}
\DeclareMathOperator{\defect}{defect}
\begin{document}
\pagestyle{empty}
\noindent
\begin{minipage}{.33\textwidth}
\flushleft {\bf \course}
\end{minipage}
\begin{minipage}{.33\textwidth}
\centering {\bf \assign}
\end{minipage}
\begin{minipage}{.33\textwidth}
\flushright {\bf \due}
\end{minipage}
\vskip3pt
\hrule\hrule\hrule
\vskip5pt
\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}}
\vskip10pt
\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof.
You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem.
}
\vskip20pt
\begin{problem}[2pts]
Let $G$ be a graph on $n\geq 2$ vertices with $\delta(G)\geq n/2$.
Show that:
\begin{enumerate}
\item If $n$ is even, then $G$ has a perfect matching.
\item If $n$ is odd, then $G-v$ has a perfect matching for every $v\in V(G)$.
\end{enumerate}
\end{problem}
\begin{problem}[2pts]
Let $G$ be a $k$-regular bipartite graph.
Prove that we can partition the edges of $G$ into $k$ perfect matchings.
That is, show that we can can partition $E(G)=M_1\sqcup\dots\sqcup M_k$ where each $M_i$ is a perfect matching in $G$.
\end{problem}
\begin{problem}[2pts]\label{harmonic}
Let $G$ be a bipartite graph with parts $A,B$.
Prove that if
\[
\sum_{a\in A}{1\over\deg a}\leq 1,
\]
then $G$ contains a matching which saturates $A$.
Here, we employ the convention that ${1\over 0}=+\infty$.
Hint: Recall the following two ``tricks'' used in class for a somewhat similar problem:
\begin{itemize}
\item Silly sizes: If $X$ is a non-empty finite set, then $\abs X=\sum_{x\in X}1$ and $1=\sum_{x\in X}{1\over\abs X}$.
\item Switching the order of summation: Fix finite sets $X,Y$ and suppose that $\Omega\subseteq X\times Y$.
For any function $f\colon X\times Y\to\R$,
\[
\sum_{(x,y)\in\Omega}f(x,y)=\sum_{x\in X}\sum_{\substack{y\in Y:\\(x,y)\in\Omega}}f(x,y)=\sum_{y\in Y}\sum_{\substack{x\in X:\\(x,y)\in\Omega}}f(x,y).
\]
\end{itemize}
\end{problem}
\begin{problem}[2pts]
Fix any non-negative integers $n,k$ such that $k\leq(n-1)/2$.
Prove that there exists an injection
\[
f\colon{[n]\choose k}\to{[n]\choose k+1}
\]
with the property that $X\subseteq f(X)$ for all $X\in{[n]\choose k}$.
Note: you do not need to actually define the injection; it is enough to simply show that it exists.
\end{problem}
\begin{problem}[2pts]
Let $G$ be a bipartite graph with parts $A,B$ wherein no vertex of $A$ is isolated.
Show that if all vertices in $A$ have distinct degrees, then $G$ contains a matching which saturates $A$.
Hint: If $S\subseteq[n]$ is non-empty, how do $\abs S$ and $\max S$ (the largest element in $S$) compare?
\end{problem}
\begin{problem}[1 bonus point]
Fix positive integers $m,n$ and let $X$ be a set of size $mn$.
Also, fix any two partitions $X=A_1\sqcup\dots\sqcup A_n$ and $X=B_1\sqcup\dots\sqcup B_n$ where $\abs{A_i}=\abs{B_i}=m$ for all $i\in[n]$.
Prove that there exists a bijection $\pi\colon[n]\to[n]$ (i.e.\ a permutation on $[n]$) such that $A_i\cap B_{\pi(i)}\neq\varnothing$ for all $i\in[n]$.
This problem will be graded all-or-nothing.
(Also, I won't lie to you: notation gets really annoying here; as long as your notation is well explained, you'll be fine, even if your notation is somewhat ambiguous.)
\end{problem}
\begin{problem}[2 bonus points]
Sportsball is a game played between two teams that cannot end in a tie, so one of these two teams wins the game and the other loses, no matter what.
We have a sportsball league with $2n$ teams for some integer $n\geq 1$.
Over a season of $2n-1$ days, every team plays every other team at most once.
Furthermore, each team plays at most one game per day.
We have $2n-1$ trophies to hand out, one for each day of the season.
Reasonably, a trophy for a particular day must go to one of the winning teams on that day.
We seek to hand out as many trophies as possible so that each team gets at most one trophy.
We hand out the trophies at the end of the season, so we can take into account the full results of the season before making our decision.
Let $T$ be the set of all teams.
For each team $t\in T$, let $p(t)\subseteq T\setminus\{t\}$ denote the set of teams that team $t$ played over the course of the season.
Prove that we can hand out at least
\[
\min_{R\subsetneq T}\ \max_{t\in T\setminus R}\ \abs{R\cup p(t)}
\]
of the trophies.\footnote{There are instances in which strictly more of the trophies can be handed out. For example, if at most one game is played per day and each team plays exactly once, then we can hand out $n$ trophies, yet the stated expression evaluates to $1$. I'd be interested to know if you can derive a better lower bound without taking into account the actual results of any game. I'm more than happy to dish out even more bonus points for such a result, though send any such argument to me separately from your homework.}
\vskip5pt
This problem will be essentially graded all-or-nothing, except you can get \textbf{one of the two bonus points for proving the following special case}:
If each team plays every other team \emph{exactly} once over the course of the season (i.e.\ $p(t)=T\setminus\{t\}$ for all $t\in T$), then we can hand out all $2n-1$ trophies.
\end{problem}
\end{document}