\documentclass[11pt]{article}
% Problem set: do not define TEMPLATE or SOL
% LaTeX template: define TEMPLATE but not SOL
% Solution: define both TEMPLATE and SOL
%
% \def\sol{1}
\def\template{1}
% STUDENTS:
% You can enter your solutions into this template by just
% typing them right after it says "SOLUTION".
% Ignore the \ifdefined\sol blocks; you can delete them if you want.
% (Note that it won't compile if you try to uncomment the
% solution flag :))
%
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usetikzlibrary{decorations.pathreplacing, shapes}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\newcommand{\expecting}[1]{\noindent{[\textbf{We are expecting:} \em #1\em]}}
\newcommand{\hint}[1]{\noindent{[\textbf{HINT:} \em #1 \em]}}
\newcommand{\pts}[1]{\textbf{(#1 pt.)}}
\newcommand{\sgn}{\mathrm{sgn}}
\definecolor{shadecolor}{gray}{0.95}
\newcommand{\bE}{\mathbb{E}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\eps}{\epsilon}
\newtheorem{theorem}{Theorem}
\newtheorem{assumption}{Assumption}
\newtheorem{definition}{Definition}

\begin{document}
\noindent
\textbf{Problem Set 5 \ifdefined\sol Solution \fi} \hfill CS265/CME309, Winter 2026
\ifdefined\sol\else
\newline
Due: Friday 2/20, 11:59pm on Gradescope
\ifdefined\template
\newline 
Group members: INSERT NAMES HERE
\fi

\vspace{.4cm}\noindent
Please follow the homework policies on the course website.
\fi

\noindent
\rule{\linewidth}{0.4pt}

\noindent


\begin{enumerate}
% ---------- Dominating set ----------

\item \pts{7} \textbf{[Dominating set.]}
Let $G=(V,E)$ be an undirected graph with $n$ vertices. A \emph{dominating set} is a subset $U$ of vertices such that every vertex $v\in V\setminus U$ is adjacent to at least one vertex in $U$. 

Suppose that $G$ has minimum degree $\delta$ (that is, every vertex is adjacent to at least $\delta$ distinct vertices). In this problem, we'll prove that $G$ has a dominating set of size at most~$n\cdot\frac{1+\ln(\delta+1)}{\delta+1}$.

\begin{enumerate}
\item \pts{1} Consider any set of vertices $S\subseteq V$. Let 
\[T=\{v\in V\setminus S\mid v\text{ is not adjacent to any vertex in }S\}.\]
explain why $S\cup T$ is a dominating set. 


\item \pts{6} Prove that $G$ has a dominating set of size at most $n\cdot \frac{1+\ln(\delta+1)}{\delta+1}$. You may use without proof the fact that $1-p\leq e^{-p}$ for any nonnegative $p$.

\hint{Use part (a)...} 

\end{enumerate}
\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/dominating.tex}
\fi
\end{shaded}
\fi

% ---------- Ranking altruism ----------

\item \pts{9} Suppose that we are trying to come up with a ranking on sports teams at the end of the season.  There are $n$ teams.  At the end of the season, each team has played every other team, and there were no ties.  We wish to aggregate these pairwise comparisons into a single ranking of all of the teams (for example ``Stanford $\geq$ UCLA $\geq$ USC $\geq$ Cal'').  Given a ranking of all of the teams, we say that a pair $\{A,B\}$ of teams is a \emph{violated pair} if $A \geq B$ in the ranking, but during the season, $B$ beat $A$.  For example, in the above ranking, if Cal beat USC this year, then $\{$USC, Cal$\}$ would be a violated pair.



\begin{enumerate}
\item \pts{2} Prove that, for any collection of pairwise game outcomes, there exists a ranking that violates at most half of the pairwise relationships.  

\item \pts{1} Prove that, for any collection of pairwise game outcomes, there exists a ranking that violates strictly less than half of the pairwise relationships.

\hint{What happens if you reverse the order of a ranking?  What happens if you reverse the order of an adjacent pair of teams in a ranking?}

\item \pts{6} Define a ``good'' ranking as one that violates at most 49\% of the pairwise relationships. Prove that for sufficiently large $n$, there exist possible pairwise game outcomes that admit \emph{no} good rankings. 

\hint{Use the probabilistic method. Suppose towards a contradiction that every collection of game outcomes admits a good ranking; for a fixed set of pairwise outcomes, what's the probability that a random ranking is good for it?  What does that say about the probability that a random ranking is good for a \emph{random} set of game outcomes?  Can you find a contradiction here?  (Perhaps by studying a fixed ranking and a random set of game outcomes?)}

\hint{It may be helpful that $n! = e^{\Theta(n \log n)}$ (by Stirling's approximation).}

\end{enumerate}

\ifdefined\template
\begin{shaded}
\textbf{SOLUTION:}
\ifdefined\sol
\input{solution/ranking.tex}
\fi
\end{shaded}
\fi



\item \pts{0}\textbf{[Who needs geometry?] [Optional: This question won't be graded, but it is an entertaining(ly obnoxious) use of the probabilistic method that you may find satisfying, especially as a brainteaser to stump your friends with after you've figured it out.]}

Suppose that your friend has -- perhaps adversarially -- drawn 10 points on the surface of a flat table, which you can think of as an infinite plane. Your friend gives you 10 quarters, which you can think of as discs, all of the same size.

Your challenge is to place the quarters on the table such that no quarters overlap, \textit{and} every one of your friend's chosen points is covered. Show that this is \textit{always} possible, regardless of the locations of the points.

One hint is below. Some more hints appear on the \textbf{next} page, so that you can avoid spoilers if you wish.\\\\
\hint{We'll save you some time: Trying to think about or classify the possible arrangements of points is not helpful, at least for the purpose of this problem in the context of this course. The solution we have in mind behaves the same way regardless of the locations of the points.}
\newpage

\hint{Imagine an arbitrarily large planar sheet of quarters, pressed together as tightly as possible. Such a sheet covers about 90.69\% of the plane. See \url{https://en.wikipedia.org/wiki/Circle_packing} for details.}

\hint{The fact that there are 10 points is important, although the significance may not be clear until you start down the right solution path...}

\ifdefined\template
\begin{shaded}
	\textbf{SOLUTION:}
	\ifdefined\sol
	\input{solution/quarters.tex}
	\fi
\end{shaded}
\fi


\end{enumerate}
\end{document}
