\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math571}{Homework 5}{Due April 11, 2025}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\newcommand{\F}{\mathcal{F}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item{} Applications of Inclusion/Exclusion.
\begin{enumerate}
	\item A mathematics department has $n$ professors and $2n$ courses; each professor teaches two courses each semester.  How many ways are there to assign the courses in the fall semester?  How many ways are there to assign them in the spring so that no professor teaches the same two courses in the spring as in the fall?  (Your answer for the spring semester may be a summation.)
	\item At a circular table are $n$ students taking an exam.  The exam has four versions.  Given that no two neighboring students have the same version, how many ways are there to assign the exams?  Do not leave the answer as a sum.
\end{enumerate}

\item{} Let $f(n)$ be the least $k$ such that every set of $k$ elements in $[n]$ has two disjoint subsets with the same sum.  Prove that $1 + \floor{\lg n} < f(n) \le \ceil{1 + \lg n + \lg \lg n}$ for sufficiently large $n$.  (Here, $\lg n = \log_2 n$.)  (Hint: for the upper bound, show that if $2^k > nk + 1$, then $f(n) \le k$.)

\item A family $\F$ of permutations of $[n]$ is \emph{intersecting} if $\pi$ and $\pi'$ take the same value on at least one $k\in[n]$ when $\pi,\pi'\in\F$.  Determine the maximum size of an intersecting family of permutations of $[n]$.  (Note: correct solutions have two parts.  First, an upper bound on the size of intersecting families is needed.  Next, an existence proof (usually a construction) is needed to show that some intersecting family meets the upper bound.)

\item A \emph{conical rational combination} of real numbers $r_1,\ldots, r_t$ is a number of the form $\sum_{k=1}^t \alpha_kr_k$, where each $\alpha_k$ is a non-negative rational.  When $\alpha_k=0$ for each $k$, the combination is \emph{trivial}; otherwise, it is \emph{non-trivial}.  A set $T$ of real numbers is \emph{good} if every non-trivial conical rational combination of $T$ is irrational.  
\begin{enumerate}
	\item Prove that if $S$ is a set of $2n+1$ irrational numbers, then $S$ contains a good subset of size $n+1$.  [Hint: show that if $T$ is a maximal good subset, then the complement $S-T$ is also good.]
	\item Give an example of a set of $2n+1$ irrational numbers with no good subset of size $n+2$.
\end{enumerate}

\item Prove that a poset of size greater than $mn$ has a chain of size greater than $m$ or an antichain of size greater than $n$.  Use this to prove the Erdős--Szekeres Theorem: every list of $mn+1$ distinct integers has an increasing sublist with more than $m$ elements or a decreasing sublist with more than $n$ elements.

\item A family of sets is \emph{union-free} if it has no two distinct members whose union is a third member.  Moser asked for $f(n)$, the maximum size of a union-free subfamily that can be guaranteed to exist in any family of $n$ sets.
\begin{enumerate}
	\item Use Dilworth's Theorem to prove $f(n)\ge\sqrt{n}$.
	\item Prove $f(n) > \sqrt{2n} - 1$.
	\item Let $A_{i,j}$ consist of the integers from $-i$ to $+j$, and let $F=\{A_{i,j}\st (i,j)\in[t]^2\_$.  Prove that the maximum size of a union-free family in $F$ is $2t-1$.  Thus $f(n)\le 2\sqrt{n}-1$ when $n$ is a perfect square.
\end{enumerate}
Comment: Fox--Lee--Sudakov [2012] proved $f(n)=\floor{\sqrt{4n+1}} -1$ for all $n$.

\end{enumerate}
\end{document}
