


\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{soul}
\usepackage{fullpage}
\usepackage{enumitem}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{hyperref}
\usepackage{multicol}

\vfuzz2pt 
\hfuzz2pt 
\setul{.25ex}{}

\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{fact*}{Fact}
\numberwithin{equation}{section}

\newtheoremstyle{probstyle}  
{3ex}                        
{0pt}                        
{\normalfont}                
{-3ex}                       
{\normalfont\bfseries}       
{.}                          
{.5em}                       
{}                           
\theoremstyle{probstyle}
\newtheorem{problem}{Problem}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\R}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\setlength\parindent{0pt}

\begin{document}
\title{Math 154 Homework \#1\vspace{-3ex}}
\date{Spring 2023}
\maketitle
\begin{center}
	Due date: \textbf{11:59pm} Pacific Time on \textbf{Wed, Apr 12} (via \href{https://www.gradescope.com/}{Gradescope})
\end{center} 
\vskip 3ex

Welcome to your first homework assignment of Math 154! If you would like additional practice on background material, there are some links to review resources provided on the next page. You are also welcome to ask questions about background material in discussion section and office hours, and to come discuss any of the homework problems in office hours! 

\section*{Submission Instructions}

\begin{enumerate}

	\item To submit your completed work, log in to Gradescope with your \texttt{@ucsd.edu} email (either	directly or through Canvas).
	\item Here is a guide to submitting an assignment in Gradescope: \href{http://bit.ly/3LRFSil}{http://bit.ly/3LRFSil}. (Note: this assignment is ``variable length" and ``not timed")
	\item Please solve each problem on a separate page. If submitting as a single PDF, \textbf{be sure to ``assign pages"} in your submission to the corresponding problems in Gradescope (otherwise the grader may have trouble finding a problem, and you could lose credit for it).
	\item Don’t forget to double-check that your work was successfully submitted -- \textbf{it will take some time to upload your work, so start early!} If you submit work early, you can always update your submission before the deadline.\\
\end{enumerate}

\noindent\emph{At the \ul{top of your first page} of work, please write a list of everyone with whom you collaborated on this assignment, as well as any outside sources you consulted, apart from the textbook, your notes, and the course staff. If you did not collaborate with anyone, please explicitly write, ``No collaborators."}\\
	
\textit{\textcolor{red}{\textbf{For Homework 1 only, you will receive a bonus point if you collaborate with at least 2 other students in our class!}}}



\newpage

\section*{Review resources}

Here are review resources on a variety of topics, some of which appear on this homework, and some of which will be used later in the course. You are also encouraged to come and discuss these topics in office hours if you have questions!\\

I may add resources on other topics later, but these are the ones that many students felt less comfortable with, and/or those that will come up regularly in Math 154 (some others, such as multinomial coefficients and the inclusion-exclusion principle, will probably come up less often). 

\subsection*{Counting (permutations, combinations, etc.)}
\begin{itemize}
	\item \href{https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1\%3A_Counting}{The counting chapter of Discrete Mathematics (Levin)}, from LibreTexts, especially Section 1.3 on combinations and permutations.
	\item \href{https://www.khanacademy.org/math/statistics-probability/counting-permutations-and-combinations}{Counting, permutations, and combinations} from Khan Academy
	\item Apppendices A.2 and A.3 in our \href{https://mathweb.ucsd.edu/~gmckinley/154_sp22/154-notes-2021.pdf}{textbook}\\
\end{itemize}

\subsection*{Proof techniques}

\textbf{Induction and strong induction}
\begin{itemize}
	\item \href{https://www.sfu.ca/~mdevos/notes/graph/induction.pdf}{These notes} by Matt DeVos (includes helpful graph theory examples!)
	\item Apppendix A.6 in our \href{https://mathweb.ucsd.edu/~gmckinley/154_sp22/154-notes-2021.pdf}{textbook}
\end{itemize}

\textbf{Pigeonhole principle}
\begin{itemize}
	\item\href{https://www.youtube.com/watch?v=2-mxYrCNX60}{This video} (gives an overview of the principle, and several nice examples)
	\item \href{https://www.sfu.ca/~vjungic/RamseyNotes/sec_Pigeon.html}{These notes} by Veselin Jungic
	\item Apppendix A.7 in our \href{https://mathweb.ucsd.edu/~gmckinley/154_sp22/154-notes-2021.pdf}{textbook}\\
\end{itemize}

\subsection*{Bonus resource}

While searching for review resources, I came across \href{https://www.sfu.ca/~mdevos/notes/graph/advice.pdf}{this page} of nice advice on solving problems in graph theory, written by Matt DeVos at Simon Fraser University. It summarizes a number of great strategies! (Though it may be more useful after you've done a couple of homework assignments and have a feel for the kind of problems we'll be seeing.)


\newpage 

\section*{Problems}
\mbox{}\vspace{-3ex}
\begin{problem}
	Answer parts (a), (b), (c), (d), and (e) of \textbf{Question 1.1} at the end of chapter 1 of the textbook. For part (e), only determine whether $K_{1,7}$ is a subgraph of $G$. You do not need to determine whether $K_4$ or $K_{2,3}$ are subgraphs of $G$. \textit{For parts (a)--(d), you do not need to show any work or justify your answers.}\\
	\\
\end{problem}

\begin{problem}   
	Answer \textbf{Question 1.9} at the end of Chapter 1 of the textbook.\\ 
	
	\textit{(Note: you should not need to look up anything about Kneser graphs in order to answer this question; all the information you need is contained in the problem statement.)}\\
	\\
\end{problem}

\begin{problem}   
	Answer \textbf{Question 1.10(a)} at the end of Chapter 1 of the textbook.\\
	
	\textit{(Hint: I recommend thinking about it on your own for a while, and trying out some small examples, but if you get stuck, there are hints for one possible solution method on the last page of this document.)}\\
	\\
\end{problem}

\begin{problem}   
	A \textbf{\textit{tournament}} is an orientation of a complete graph. Prove that every tournament contains a directed path containing all of its vertices. That is, prove that a tournament with $n$ vertices has an ordering $v_1,v_2\dots, v_n$ of its vertices so that $(v_i,v_{i+1})$ is an arc for each $i\in\{1,2,\dots n-1\}$.\\
	
	\textit{(Hints: there are a couple of possible solutions for this problem; I recommend thinking about it on your own for a while, and trying out some small examples, but if you get stuck, there are hints for one possible solution method on the last page of this document.)}\\
	\\
	
	
	\textit{Some additional background}: an orientation of a complete graph on $n$ vertices is called a ``tournament" because it corresponds to a round-robin tournament (e.g., in chess or boxing or rock-paper-scissors), in which each member of a group of $n$ contestants plays one match against each of the other $n-1$ contestants, and each game results in a win for one player and a loss for the other. For example, an arc $(1,2)$ could represent a match in which player 1 defeats player 2, while $(2,1)$ would represent player 2 defeating player 1. The somewhat surprising fact proved in this problem is that, even in games with no element of skill whatsoever, there is always a way to arrange the players in a line so that each player has beaten the next player in the line.\\
\end{problem}



\newpage

\section*{Hint for Problem 3}

Try using the Pigeonhole Principle.\vspace{4cm}


\section*{Hints for Problem 4}

One possible solution approach for this problem uses induction on the number of vertices, which we will denote by $n$. Here are some of the steps:\\

\textbf{Base step:} choose an appropriate value of $n$, and prove that the result holds for a tournament with this number of vertices.\\

\textbf{Inductive step:} assume that the result holds for every tournament with $n$ vertices (fill in appropriate conditions for $n$). Consider a tournament $T$ with $n+1$ vertices, and remove any vertex $v$. Apply the induction hypothesis to obtain a directed path $v_1,v_2,\dots, v_n$ containing every vertex in $T-v$. To show that there is a directed path containing all the vertices in $T$, try breaking your analysis into the following cases:\\

\textbf{Case 1:} $(v,v_1)$ is an arc in $T$.\\

\textbf{Case 2:} $(v_n,v)$ is an arc in $T$.\\

\textbf{Case 3:} neither of the previous conditions hold.







\end{document} 
