% !TeX spellcheck = en_US
\documentclass[12pt,letter]{amsart}
%\usepackage[french]{babel}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{textcomp}
\usepackage[margin=2cm]{geometry}
\usepackage{graphicx, graphics}
\usepackage{todonotes}
\usepackage{genyoungtabtikz}
\usepackage{pgf,tikz,pgfplots}
\pgfplotsset{compat=1.13}
\usepackage{mathrsfs}
\usetikzlibrary{arrows}
\usepackage{hyperref}
%for the due date to appear at the beggining of the page
\usepackage{etoolbox}
\makeatletter
\patchcmd{\@maketitle}
{\ifx\@empty\@dedicatory}
{\ifx\@empty\@date \else {\vskip3ex \centering\footnotesize\@date\par\vskip1ex}\fi
\ifx\@empty\@dedicatory}
{}{}
\patchcmd{\@adminfootnotes}
{\ifx\@empty\@date\else \@footnotetext{\@setdate}\fi}
{}{}{}
\makeatother
\DeclareMathOperator{\GLn}{GL_n}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\tr}{tr}
\linespread{1.2}
\setlength\parindent{0pt}
\sloppy
\title{Final exam (take-home)}
\author{Algebraic Combinatorics (Math 68)}
\date{\vspace{-.5em}Due November 27, 2019}
\begin{document}
\maketitle
As this is an exam, \textbf{you are not allowed to give or receive any help}, except from the instructor.
However, \textbf{you are allowed to use the lectures notes} and any assignment you have completed for this course. Other references are not allowed.
You must write the appropriate justification as part of the solutions.\\
Please, \textbf{turn in your solutions by email} (since we won't meet over the period of time for the exam).\\
\begin{enumerate}
\item (25 points)\quad Prove this interpretation of Erd\H{o}s-Szekeres theorem: Any permutation of length greater than $n^2$ must contain either an increasing sequence of length at least $n$ or a decreasing sequence of length at least $n$. Prove that this bound is sharp (i.e. that there is a permutation of length $n^2$ with no increasing nor decreasing sequence of length $n+1$).\\
\item (25 points)\quad Let $A_n$ denote the alternating subgroup of $S_n$ (i.e. the group of even permutations). Let $\sigma \in S_n$ have cycle type $(\lambda_1,\ldots, \lambda_l)$.
\begin{enumerate}
\item Show that $\sigma \in A_n$ if and only if $n-l$ is even.
\item Explain why $A_4$ has four irreducible representations.
\item Do all characters of $A_n$ have integer values? Why?
\item Give two important differences between the table of characters of $A_n$ and of $S_n$.\\
\end{enumerate}
\item (20 points)\quad True or False: If every chain and every antichain of a poset $P$ is finite, then $P$ is finite (as a set). You must justify your answer.\\
\item (10 points)\quad How many compositions of 17 use only parts of length $2$ and $3$?\\
\item (20 points)\quad How many distinct regular tetrahedra are there under rotation if the faces are colored from a set with $r$ colors. Also, give a numerical answer for $r = 1,2,3,4,5$.\\
\end{enumerate}
\begin{center}
\textbf{Good luck!}
\end{center}
\end{document}