\documentclass[]{beamer}
%\usepackage{wasysym}
\usepackage{amsmath,amssymb, enumerate}
\usepackage{multirow}
\usepackage{multicol}

\usepackage[all]{xy}

%\usepackage{ulem}%\sout
%\usepackage{pgfarrows,pgfnodes}
%\usepackage{url}
\usepackage{textcomp}
%\usepackage[normalem]{ulem}
%\usepackage{color}
\definecolor{dred}{rgb}{.8,0,.1}
\definecolor{dblue}{rgb}{.3,0,.8}
\definecolor{dgreen}{rgb}{0,.7,.2}
\definecolor{dorange}{rgb}{.9,.3,0}
\definecolor{dgrey}{rgb}{.4,.4,.4}
\definecolor{gray}{rgb}{.8,.8,.8}
\definecolor{purple}{rgb}{.5,0,.8}
  \definecolor{w}{rgb}{1,1,1}
  \definecolor{b}{rgb}{0,0,0}
  \definecolor{g}{rgb}{.7,.7,.7}
\colorlet{ke}{orange!95!yellow!90!black}
\colorlet{bo}{blue!90!black}
\colorlet{re}{blue!50!green!90!black}
\colorlet{co}{red!90!black}
\newcommand{\Alert}[2]{{\only<#1>{\color{blue}} #2 }}



\usenavigationsymbolstemplate{}

\usefonttheme[%
%  	stillsansserifsmall, 	% will cause 'small' text to be still typeset using sans serif. This refers to
  					% the text in the headline, footline, and sidebars. Using this options is often
  					% advisable since small  text is often easier to read in sans serif.
   	onlymath, % typset math in serif but nothing else
 ]{serif}

\usecolortheme[rgb={.5,0,.75}]{structure}
\setbeamercolor{alerted text}{fg=red!33!blue}
%\beamertemplatenavigationsymbolsempty 


%%%%% Alphabets %%%%% 
\def\cA{\mathcal{A}}\def\cB{\mathcal{B}}\def\cC{\mathcal{C}}\def\cD{\mathcal{D}}\def\cE{\mathcal{E}}\def\cF{\mathcal{F}}\def\cG{\mathcal{G}}\def\cH{\mathcal{H}}\def\cI{\mathcal{I}}\def\cJ{\mathcal{J}}\def\cK{\mathcal{K}}\def\cL{\mathcal{L}}\def\cM{\mathcal{M}}\def\cN{\mathcal{N}}\def\cO{\mathcal{O}}\def\cP{\mathcal{P}}\def\cQ{\mathcal{Q}}\def\cR{\mathcal{R}}\def\cS{\mathcal{S}}\def\cT{\mathcal{T}}\def\cU{\mathcal{U}}\def\cV{\mathcal{V}}\def\cW{\mathcal{W}}\def\cX{\mathcal{X}}\def\cY{\mathcal{Y}}\def\cZ{\mathcal{Z}}

\def\AA{\mathbb{A}} \def\BB{\mathbb{B}} \def\CC{\mathbb{C}} \def\DD{\mathbb{D}} \def\EE{\mathbb{E}} \def\FF{\mathbb{F}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \def\II{\mathbb{I}} \def\JJ{\mathbb{J}} \def\KK{\mathbb{K}} \def\LL{\mathbb{L}} \def\MM{\mathbb{M}} \def\NN{\mathbb{N}} \def\OO{\mathbb{O}} \def\PP{\mathbb{P}} \def\QQ{\mathbb{Q}} \def\RR{\mathbb{R}} \def\SS{\mathbb{S}} \def\TT{\mathbb{T}} \def\UU{\mathbb{U}} \def\VV{\mathbb{V}} \def\WW{\mathbb{W}} \def\XX{\mathbb{X}} \def\YY{\mathbb{Y}} \def\ZZ{\mathbb{Z}}  

\def\fa{\mathfrak{a}} \def\fb{\mathfrak{b}} \def\fc{\mathfrak{c}} \def\fd{\mathfrak{d}} \def\fe{\mathfrak{e}} \def\ff{\mathfrak{f}} \def\fg{\mathfrak{g}} \def\fh{\mathfrak{h}} \def\fj{\mathfrak{j}} \def\fk{\mathfrak{k}} \def\fl{\mathfrak{l}} \def\fm{\mathfrak{m}} \def\fn{\mathfrak{n}} \def\fo{\mathfrak{o}} \def\fp{\mathfrak{p}} \def\fq{\mathfrak{q}} \def\fr{\mathfrak{r}} \def\fs{\mathfrak{s}} \def\ft{\mathfrak{t}} \def\fu{\mathfrak{u}} \def\fv{\mathfrak{v}} \def\fw{\mathfrak{w}} \def\fx{\mathfrak{x}} \def\fy{\mathfrak{y}} \def\fz{\mathfrak{z}}
\def\fgl{\mathfrak{gl}}  \def\fsl{\mathfrak{sl}}  \def\fso{\mathfrak{so}}  \def\fsp{\mathfrak{sp}}  
\def\GL{\mathrm{GL}} \def\SL{\mathrm{SL}}  \def\SP{\mathrm{SL}}

\def\>{\rangle} \def\<{\langle}


\def\Aut{\mathrm{Aut}}\def\End{\mathrm{End}} \def\Hom{\mathrm{Hom}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{claim}{Claim}
\newtheorem*{cor}{Corollary}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{ex}{Example}
\newtheorem*{fex}{For example:}

\def\der{\frac{d}{dx}}
\def\img{\mathrm{img}}
\def\ker{\mathrm{ker}}
\def\Syl{\mathrm{Syl}}

\usepackage{mathabx}
\def\acts{\mathrel{\reflectbox{$\righttoleftarrow$}}}



\def\BLUE[#1,#2]{{\only<#1>{\color{dblue}}#2}}
%\def\RED[#1,#2]{{\only<#1>{\color{dred}}#2}}
\def\GREEN[#1,#2]{{\only<#1>{\color{dgreen}}#2}}
\def\SPACE{\phantom{\Big|}}
 \def\ANSWER[#1]{\uncover<2->{{\color{dblue} #1}}}


\usepackage[export]{adjustbox}

\newcommand{\isom}{\cong}
\newcommand{\bslash}{\symbol{'134}}%backslash
\newcommand{\bsl}{{\texttt{\bslash}}}
\newcommand{\lspace}[1]{\renewcommand{\baselinestretch}{#1}\small\normalsize}
\newcommand{\mb}[1]{\ensuremath{\mathbb{#1}}} %Math blackboard font
\newcommand{\nin}{\noindent} %no indent
\newcommand{\QS}[1]{\ensuremath{\mathbb{Q}S_{#1}}} %Shortcut for QS_n
\newcommand{\CS}[1]{\ensuremath{\mathbb{Q}S_{#1}}} %Shortcut for QS_n
\newcommand{\C}[1]{\ensuremath{\mathbb{Q}^{#1}}} %Shortcut for Q^n
\newcommand{\one}[1]{\ensuremath{\mathbf{1}_{#1}}} %1_n 
\newcommand{\mbf}[1]{\ensuremath{\mathbf{#1}}} %\mathbf{} 
\newcommand{\tbf}[1]{\textbf{#1}} %\textbf{}
\newcommand{\century}[1]{$#1^{\textrm{th}}$ century} 
\newcommand{\T}[1]{\ensuremath{T_{\mathbf{#1}}}} 		%T_w
\newcommand{\TP}[1]{\ensuremath{T_{\mathbf{#1}}^{\lambda}}} %T_w partial


\usepackage{tikz}
\usepackage{graphicx}
\usepackage{epstopdf}
\tikzstyle{V}=[draw, structure, fill=structure, circle, inner sep=0pt, inner sep=0pt, minimum size=2pt]

\def\ShiftX{\pgftransformxshift}
\def\ShiftY{\pgftransformyshift}

\newcommand\TikZ[1]{\begin{matrix}\begin{tikzpicture}#1\end{tikzpicture}\end{matrix}}


\def\Over[#1,#2][#3,#4]{ %1,2=start position; 3,4=end position
	\draw   (#1,#2) .. controls ++(0,#4*.5-#2*.5) and ++(0,-#4*.5+#2*.5) .. (#3,#4);}
\def\Cross[#1,#2][#3,#4]{%Mimic over, under follows
	\Over[#3,#2][#1,#4]\Over[#1,#2][#3,#4]}


\newcommand\Mat[9]{
\node at (1,1) {\small #1} ;
\node at (2,1) {\small#2} ;
\node at (3,1) {\small#3} ;
\node at (1,2) {\small#4} ;
\node at (2,2) {\small#5} ;
\node at (3,2) {\small#6} ;
\node at (1,3) {\small#7} ;
\node at (2,3) {\small#8} ;
\node at (3,3) {\small#9} ;
\draw[thick, rounded corners] (.8,.3)--(.3, .3)--(.3,3.7)--(.8,3.7); 
\draw[thick, rounded corners] (3.2,.3)--(3.7, .3)--(3.7,3.7)--(3.2,3.7); 
}
\newcommand\MatB[9]{
\draw[thick, |->] (-6,1.5) -- (0,1.5) node [draw, inner sep=2pt, circle, blue, fill=white,align=center,midway]{$\rho$};
\draw[thick, |->] (-6,3) -- (2,3) node [draw, inner sep=1pt, circle, orange!90!yellow, fill=white,align=center,midway]{$\psi$};
\draw[fill=blue!10, draw=blue!50, rounded corners = 2pt] (.5,2)--(.5,.5)--(2.5,.5)--(2.5,2.5)--(.5,2.5)--(.5,2);
\draw[fill=yellow!20, draw=orange!50, rounded corners = 2pt] (2.5,3)--(2.5,2.5)--(3.5,2.5)--(3.5,3.5)--(2.5,3.5)--(2.5,3);
\node at (1,1) {\small #1} ;
\node at (2,1) {\small#2} ;
\node at (1,2) {\small#4} ;
\node at (2,2) {\small#5} ;
\node at (3,3) {\small#9} ;
\draw[thick, rounded corners = 2pt] (.8,.5)--(.5, .5)--(.5,2.5)--(.8,2.5); 
\draw[thick, rounded corners = 2pt] (2.2,.5)--(2.5, .5)--(2.5,2.5)--(2.2,2.5); 
\draw[thick, rounded corners = 2pt] (2.8,2.5)--(2.5, 2.5)--(2.5,3.5)--(2.8,3.5); 
\draw[thick, rounded corners = 2pt] (3.2,2.5)--(3.5, 2.5)--(3.5,3.5)--(3.2,3.5); 
}

\newcommand\MatC[9]{\ShiftX{10.25cm}
\draw[thick, |->] (-6,1.5) -- (-1.5,1.5) node [draw, inner sep=2pt, circle, blue, fill=white,align=center,midway]{$\rho$};
\draw[thick, |->] (-6,3) -- (2,3) node [draw, inner sep=1pt, circle, orange!90!yellow, fill=white,align=center,midway]{$\psi$};
\draw[fill=blue!10, draw=blue!50, rounded corners = 2pt] (-1,2)--(-1,.5)--(2.5,.5)--(2.5,2.5)--(-1,2.5)--(-1,2);
\draw[fill=yellow!20, draw=orange!50, rounded corners = 2pt] (2.5,3)--(2.5,2.5)--(3.5,2.5)--(3.5,3.5)--(2.5,3.5)--(2.5,3);
\node at (-.125,1) {\tiny #1} ;
\node at (1.625,1) {\tiny #2} ;
\node at (-.125,2) {\tiny #4} ;
\node at (1.625,2) {\tiny#5} ;
\node at (3,3) {\small#9} ;
\draw[thick, rounded corners = 2pt] (-.7,.5)--(-1, .5)--(-1,2.5)--(-.7,2.5); 
\draw[thick, rounded corners = 2pt] (2.2,.5)--(2.5, .5)--(2.5,2.5)--(2.2,2.5); 
\draw[thick, rounded corners = 2pt] (2.8,2.5)--(2.5, 2.5)--(2.5,3.5)--(2.8,3.5); 
\draw[thick, rounded corners = 2pt] (3.2,2.5)--(3.5, 2.5)--(3.5,3.5)--(3.2,3.5); 
}

\def\Blocks{
	\uncover<3>{
		\draw[fill=blue!10, draw=blue!50, rounded corners = 2pt] (.5,2)--(.5,.5)--(2.5,.5)--(2.5,2.5)--(.5,2.5)--(.5,2);
		\draw[fill=yellow!20, draw=orange!50, rounded corners = 2pt] (2.5,3)--(2.5,2.5)--(3.5,2.5)--(3.5,3.5)--(2.5,3.5)--(2.5,3);}}

\newcommand\Perm[3]{
\coordinate (center) at (0,2);
\begin{scope}[scale=1.2, shift=(center)]
\foreach \x in {1,2,3}{
\node[V] (b\x) at (\x,.75) {};
\node[V](t\x) at (\x,-.75) {};
\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[-> ] (b1) -- (t#1);
\draw[->] (b2) -- (t#2);
\draw[->] (b3) -- (t#3);
\end{scope}
}


%For partitions. Takes in a list of row lengths. 
%If you want English convention, you'll need to set yscale=-... as below. 
\newcommand{\Part}[1]{
 \foreach \x [count=\s from 1] in {#1}{
 	{\ifnum\s=1
		\draw (0,\s-1)--(\x,\s-1); 
		\fi}
   \draw (0,\s) to (\x,\s);
   \foreach \y in {0, ..., \x} {\draw (\y,\s)--(\y,\s-1);}
 }}


%For colored partitions. Takes in a list of row lengths and a color. 
 \newcommand{\fPart}[2]{
 \foreach \x [count=\s from 1] in {#1}{
  \filldraw[#2] (0,\s) -- (\x,\s)--(\x,\s-1)--(0,\s-1);
 }
 \foreach \x [count=\s from 1] in {#1}{
 	{\ifnum\s=1
		\draw (0,\s-1)--(\x,\s-1); 
		\fi}
   \draw (0,\s) to (\x,\s);
   \foreach \y in {0, ..., \x} {\draw (\y,\s)--(\y,\s-1);}
 }}

\def\UNIT{.25}
\newcommand{\PART}[1]{
\begin{tikzpicture}[xscale=\UNIT, yscale=\UNIT] 
	\Part{#1}
\end{tikzpicture}
}\newcommand{\gPART}[1]{
\begin{tikzpicture}[xscale=\UNIT, yscale=\UNIT] 
\begin{scope}[black!20]
	\Part{#1}
\end{scope}
\end{tikzpicture}
}
\newcommand{\fPART}[2]{
\begin{tikzpicture}[xscale=\UNIT, yscale=\UNIT]
	\fPart{#1}{#2}
\end{tikzpicture}
}


\def\Scale{.37}





\def\ww{\mathbf{w}}


\title{An Algebraic Approach to Voting Theory}
\author{Zajj Daugherty\\
\includegraphics[width=2in]{ccny}\\
}
\date{}


\begin{document}

\begin{frame}
\begin{center}

\Huge \alert{An Algebraic Approach\\to Voting Theory} 

\vspace{.5in}

\Huge Zajj Daugherty

\bigskip

\includegraphics[width=2in]{ccny}

\bigskip

\Large November 5, 2018


\end{center}
\end{frame}

\begin{frame}
Suppose Alice, Becca, and Carly are running for president of their AWM chapter. The personal preferences of the 54 members are given by
\\ \smallskip
\centerline{$\displaystyle
\begin{array}{r||c|c|c|c|c|c}
1^\text{st}: & A & A & B & B & C & C\\
2^\text{nd}:& B & C & A & C & A & B\\
3^\text{rd}:& C & B & C & A & B & A\\\hline\hline
	& 13	& 0	& 19 & 0	& 17	& 5
\end{array}
$} \medskip

So who should be president? \pause 

\alert{Method 1:} Vote for your first choice.\\ \smallskip
\centerline{\qquad\qquad$\displaystyle
\begin{array}{c|c|c}
	A & B & C \\\hline
	13 &	19 & 22
\end{array} \pause \qquad \text{Carly wins!}\pause 
$} 

\medskip

\alert{Method 2:} Tell us your full ranking, and we'll pair them off. \\\smallskip \pause 
\centerline{\qquad\qquad$\displaystyle
\begin{array}{|c||c||c|}\hline
	A > B & B > C & A > C \\\hline
	30	& 32 & 	32\\\hline\hline
	A < B & B < C & A < C\\\hline
	24	& 22  &  22\\\hline
	\multicolumn{1}{c}{\uncover<6->{\alert{A>B,}}}&
		\multicolumn{1}{c}{\uncover<6->{\alert{B>C,}}}&
		\multicolumn{1}{c}{\uncover<6->{\alert{A>C.}}}
\end{array} \pause\pause \qquad \text{Alice wins!}
$} 

\end{frame}


\begin{frame}
Suppose Alice, Becca, and Carly are running for president of their AWM chapter. The personal preferences of the 54 members are given by
\\ \smallskip
\centerline{$\displaystyle
\begin{array}{r||c|c|c|c|c|c}
1^\text{st}: & A & A & B & B & C & C\\
2^\text{nd}:& B & C & A & C & A & B\\
3^\text{rd}:& C & B & C & A & B & A\\\hline\hline
	& 13	& 0	& 19 & 0	& 17	& 5
\end{array}
$} \medskip

So who should be president? 

\alert{Method 3:} Tell us your full ranking, and we'll run an instant run off. \\\smallskip \pause 
\centerline{ $\displaystyle
\begin{matrix}\text{Round 1:}\\
	\begin{array}{c|c|c}
	A & B & C \\\hline
	13 &	19 & 22
\end{array}\end{matrix}$ \pause \quad Alice loses. \qquad 
\pause $\displaystyle
\begin{matrix}\text{Round 2:}\\
\begin{array}{c|c}
	 B & C \\\hline
	32 & 22
\end{array}\end{matrix}$ \pause \quad Becca wins!\pause } 


\medskip

\alert{Method 4:} Tell us your full ranking, and we'll give points according to the candidates' positions---1  for 1st, $t$  for 2nd, 0  for 3rd.  \\\smallskip \pause 
\centerline{\qquad\qquad$\displaystyle
\begin{array}{c|c|c}
	A & B & C \\\hline\hline
	13 + 36t&	19 + 18t & 22 + 0t
\end{array} \quad (0 \le t \le 1) 
$} 


\end{frame}




\begin{frame}


{\small Suppose Alice, Becca, and Carly are running for president of their AWM chapter. The personal preferences of the 54 members are given by
\\ \smallskip
\centerline{$\displaystyle
\begin{array}{r||c|c|c|c|c|c}
1^\text{st}: & A & A & B & B & C & C\\
2^\text{nd}:& B & C & A & C & A & B\\
3^\text{rd}:& C & B & C & A & B & A\\\hline\hline
	& 13	& 0	& 19 & 0	& 17	& 5
\end{array}
$} \medskip

So who should be president? }

\alert{Method 4:} Tell us your full ranking, and we'll give points according to the candidates' positions---1  for 1st, $t$  for 2nd, 0  for 3rd.  \\\smallskip  
\centerline{\qquad\qquad$\displaystyle
\begin{array}{rc|c|c}
	&A & B & C \\\hline\hline
	(0 \le t \le 1)  &13 + 36t&	19 + 18t & 22 + 0t\\\hline
	t=0: &  13	&19	& \alert{22}\\\hline
	t=0.25: & 22 & \alert{23.5} & 22 \\\hline
	t=0.5: & \alert{31} & 28 & 22 \\\hline
	t=0.75: & \alert{40} & 32.5 & 22\\\hline
	t=1: & \alert{49} & 37 & 22
\end{array}  
$} 


\centerline{$
\TikZ{\draw[thick] (0,0) to (8,0) (9,0) to (10,0); \node at (8.5,0) {$\cdots$};
	\node[left] at (0,0) {$t$};
	\foreach \x in {3,4,6}{\draw[thick] (24/\x-1,.4) to (24/\x-1,-.2) node[below]{\small$1/\x$};}
	\draw[thick] (0,.4) to (0,-.2) node[below]{\small$0$};
	\draw[thick] (10,.4) to (10,-.2) node[below]{\small$1$};
	\node[above] at (1.5, 0) {\small\alert{$C > B > A$}};
	\node[above] at (4, 0) {\small\alert{$B > C > A$}};
	\node[above] at (6, 0) {\small\alert{$B > A > C$}};
	\node[above] at (8.5, 0) {\small\alert{$A > B > C$}};
}$} \smallskip

\end{frame}




\begin{frame}
In 2000, in Florida, 2,912,790 people voted for Bush, 2,912,253 voted for Gore, 97,488 voted for Nader, and 40,575 for other. Neglecting the ``others'', suppose we had asked the rest of the voters for their full rankings of the top three candidates. 
\\ \smallskip
\centerline{$\displaystyle
\begin{array}{r||c|c|c|c|c|c}
1^\text{st}: & B  & G & G & N \\
2^\text{nd}:& G & N & B & G \\
3^\text{rd}:& N  & B & N  & B \\\hline\hline
	& 2.902\text{mil}	& 1.421\text{mil}	& 1.481\text{mil} & 0.118\text{mil}
\end{array}
$} \medskip 

So who should have been president? \pause

\alert{Method 1:} Vote for your first choice.\\ \smallskip
\centerline{\qquad\qquad$\displaystyle
\begin{array}{c|c|c}
	B & G & N \\\hline
	2.90\text{mil} & 2.90\text{mil}	& 0.11\text{mil}	 
\end{array}  \qquad   \text{\alert{Bush won.}}\pause 
$} 

\medskip

\alert{Method 2:} Tell us your full ranking, and we'll pair them off. \\\smallskip  
\centerline{\qquad\qquad$\displaystyle
\begin{array}{|c||c||c|}\hline
	B > G & G > N & B > N \\\hline
	2.90\text{mil} & 5.80\text{mil} & 4.32\text{mil}\\\hline\hline
	B < G & G < N & B < N\\\hline
	3.02\text{mil} & 0.12\text{mil} & 1.60\text{mil} \\\hline
	\multicolumn{1}{c}{{\alert{G>B,}}}&
		\multicolumn{1}{c}{{\alert{G>N,}}}&
		\multicolumn{1}{c}{{\alert{B>N.}}}
\end{array}  \qquad \text{\alert{Gore wins.}}
$} 

\end{frame}



\begin{frame}
In 2000, in Florida, 2,912,790 people voted for Bush, 2,912,253 voted for Gore, 97,488 voted for Nader, and 40,575 for other. Neglecting the ``others'', suppose we had asked the rest of the voters for their full rankings of the top three candidates. 
\\ \smallskip
\centerline{$\displaystyle
\begin{array}{r||c|c|c|c|c|c}
1^\text{st}: & B  & G & G & N \\
2^\text{nd}:& G & N & B & G \\
3^\text{rd}:& N  & B & N  & B \\\hline\hline
	& 2.902\text{mil}	& 1.421\text{mil}	& 1.481\text{mil} & 0.118\text{mil}
\end{array}
$} \medskip 

So who should have been president? 

\alert{Method 3:} Tell us your full ranking, and we'll run an instant run off. \\\smallskip  
\centerline{ \small $\displaystyle
\begin{matrix}\text{Round 1:}\\
	\begin{array}{c|c|c}
	B & G & N \\\hline
	2.90\text{mil}	& 2.90\text{mil}	& 0.12\text{mil}	 
\end{array}\end{matrix}$ \pause ~ Nader loses. \quad 
\pause $\displaystyle
\begin{matrix}\text{Round 2:}\\
\begin{array}{c|c}
	 B & G \\\hline
	2.90\text{mil}	&3.02\text{mil}	
\end{array}\end{matrix}$ \pause ~ Gore wins.\pause } 


\medskip

\alert{Method 4:} Tell us your full ranking, and we'll give points according to the candidates' positions---1  for 1st, $t$  for 2nd, 0  for 3rd.  \\\smallskip \pause 
\centerline{\qquad\qquad$\displaystyle
\begin{array}{c|c|c}
	B & G & N \\\hline\hline
	2.902 + 1.421\ t & 	2.902 + 3.020\ t& 	0.118+ 1.481\ t
\end{array} \quad (0 \le t \le 1) 
$} 


\end{frame}


\begin{frame}


\small In 2000, in Florida, 2,912,790 people voted for Bush, 2,912,253 voted for Gore, 97,488 voted for Nader, and 40,575 for other. Neglecting the ``others'', suppose we had asked the rest of the voters for their full rankings of the top three candidates. 
\\ \smallskip
\centerline{$\displaystyle
\begin{array}{r||c|c|c|c|c|c}
1^\text{st}: & B & G & G & N \\
2^\text{nd}:& G & N & B & G \\
3^\text{rd}:& N  & B & N  & B \\\hline\hline
	& 2.902\text{mil}	& 1.421\text{mil}	& 1.481\text{mil} & 0.118\text{mil}
\end{array}
$} \medskip 

So who should have been president? 

\alert{Method 4:} Tell us your full ranking, and we'll give points according to the candidates' positions---1  for 1st, $t$  for 2nd, 0  for 3rd.  \\\smallskip  
\centerline{$\displaystyle
\begin{array}{rc|c|c}
	&A & B & C \\\hline\hline
	(0 \le t \le 1)  &2.902 + 1.421\ t & 	2.902 + 3.020\ t& 	0.118+ 1.481\ t\\\hline
	t=0: &  \alert{2.90}\text{mil} & 2.90\text{mil} & 0.19\text{mil}\\\hline
	t=0.25: & 3.26\text{mil} & \alert{3.66}\text{mil} & 0.49\text{mil} \\\hline
	t=0.5: &3.61\text{mil} & \alert{4.41}\text{mil} & 0.86\text{mil} \\\hline
	t=0.75: & 3.97\text{mil} & \alert{5.17}\text{mil} & 1.23\text{mil}\\\hline
	t=1: & 4.32\text{mil} & \alert{5.92}\text{mil} & 1.60\text{mil}
\end{array}  
$} 


\centerline{$
\TikZ{\draw[thick] (0,0) to (5.5,0) (6.5,0) to (10,0); \node at (6,0) {$\cdots$};
	\node[left] at (0,0) {$t$};
	\draw[thick] (0,.4) to (0,-.2) node[below]{\small$0$};
	\draw[thick] (2,.4) to (2,-.2) node[below]{\small$.000335$};
	\draw[thick] (10,.4) to (10,-.2) node[below]{\small$1$};
	\node[above] at (1, 0) {\small\alert{$B>G>N$}};
	\node[above] at (6, 0) {\small\alert{$G>B>N$}};
}$} \smallskip

\end{frame}


\begin{frame}
\centerline{
		\includegraphics[width=3cm,valign=t]{borda}
\quad
\begin{minipage}[t]{7.25cm}
\alert{Jean-Charles, Chevalier de Borda}\\
1733--1799\\
Mariner and scientist.\\
1770: formulated a ranked voting system, the ``Borda count''. Used by the French Academy of Sciences, until Napolean.
\end{minipage}}

\medskip
\alert{\hrule}
\medskip

\centerline{
\begin{minipage}[t]{7.25cm}
\alert{Nicolas de Caritat, Marquis de Condorcet}\\
1743--1794\\
Philosopher and mathematician. \\
In 1785, wrote an essay on probability of decisions made on a majority vote, describing  likelihood of good jury outcomes; and Condorcet's paradox, which shows that majority preferences can become intransitive with three or more options
\end{minipage}\quad
\includegraphics[width=3.25cm,valign=t]{condorcet}}


\end{frame}




\begin{frame}
\centerline{
		\includegraphics[width=2.25cm,valign=t]{saari}
\quad
\begin{minipage}[t]{8cm}
\alert{Dr.\ Donald G. Saari}
(1940--)\\
Professor of Mathematics and Economics.\\
1999: Used geometric methods to model voting data as vector spaces, and decompose them based on how they affect various tallying methods. 
\end{minipage}}

\medskip \pause 

\alert{\color{ke}Kernel:} Doesn't affect any fair voting system.\\
\alert{\color{bo}Borda:} Influences both point-based and pairwise systems.\\
\alert{\color{co}Condorcet:} Introduces Condorcet paradox.\\
\alert{\color{re}Reversal:} Influences point-based systems, but not pairwise.

\medskip

\centerline{\begin{tabular}{c|c|c@{}c@{}c|c|c@{}c@{}c}
 	 &\small \color{ke}Kernel&            \multicolumn{3}{c|}{\color{bo}Borda }  &   \color{co}Condorcet           &     \multicolumn{3}{c}{ \color{re}Reversal}                \\
 	&   & \color{bo}$\mbf{b_A}$&\color{bo}$\mbf{b_B}$&\color{bo}$\mbf{b_C}$ 
			&   & \color{re} $\mbf{r_A}$& \color{re}$\mbf{r_B}$& \color{re}$\mbf{r_C}$ \\\hline
	$\begin{array}{c}
		ABC\\
		ACB\\
		BAC\\
		BCA\\
		CAB\\
		CBA
 	\end{array}$
 			&\color{ke}
	$\left(\!\!\!
		\begin{array}{r}
		1\\1\\1\\1\\1\\1
 		\end{array}\!\!\!\right)$
 			&
%B_A
			\color{bo}
			$\left(\!\!\!
				\begin{array}{r}
				1\\1\\0\\-1\\0\\-1
 				\end{array}\!\!\!\right)$
 			&
%B_B 		
			\color{bo}
			$\left(\!\!\!
				\begin{array}{r}
				0\\-1\\1\\1\\-1\\0
 				\end{array}\!\!\!\right)$
 			&
%B_C 		
			\color{bo}
			$\left(\!\!\!
				\begin{array}{r}
				-1\\0\\-1\\0\\1\\1
 				\end{array}\!\!\!\right)$
 			&
			 \color{co}		%C 		
			$\left(\!\!\!
				\begin{array}{r}
				1\\-1\\-1\\1\\1\\-1
 				\end{array}\!\!\!\right)$
 			&
			 \color{re}		%R_A 		
			$\left(\!\!\!
				\begin{array}{r}
				1\\1\\-2\\1\\-2\\1
 				\end{array}\!\!\!\right)$
 			&
			 \color{re} 		%R_B
			$\left(\!\!\!
				\begin{array}{r}
				-2\\1\\1\\1\\1\\-2
 				\end{array}\!\!\!\right)$
 			&
			 \color{re} 		%R_C 		
			$\left(\!\!\!
				\begin{array}{r}
				1\\-2\\1\\-2\\1\\1
 				\end{array}\!\!\!\right)$
	\end{tabular}}


\end{frame}

\begin{frame}


\only<1-2>{{\footnotesize
\centerline{$\displaystyle
\begin{array}{r||c|c|c|c|c|c||c|c|c||c|c|c}
1^\text{st}: & A & A & B & B & C & C 
	& \multicolumn{3}{c||}{\text{Points}}
		& \text{\tiny$A\!>\!B$} &\text{\tiny$B\!>\!C$} 
		& \text{\tiny$C\!>\!A$}\\
2^\text{nd}:& B & C & A & C & A & B 
	& \multicolumn{3}{c||}{\mathbf{w}=(1,t,0)} & \text{vs.} & \text{vs.} & \text{vs.} \\
3^\text{rd}:& C & B & C & A & B & A & A & B & C
				& \text{\tiny$A\!<\!B$} 
				& \text{\tiny$B\!<\!C$} 
				& \text{\tiny$C\!<\!A$}\\\hline\hline
\color{ke}\text{Ker} &\color{ke} 1 &\color{ke} 1 &\color{ke} 1 &\color{ke} 1 &\color{ke} 1 &\color{ke} 1 
		&\color{ke} 2 \!+\! 2t&\color{ke} 2 \!+\! 2t&\color{ke} 2 \!+\! 2t &\color{ke} 0 &\color{ke} 0 &\color{ke} 0\\\hline\hline
\color{bo}\textbf{b}_A &\color{bo} 1 &\color{bo} 1 &\color{bo} 0 &\color{bo} -1 &\color{bo} 0 &\color{bo} -1 &\color{bo} 2	 &\color{bo} -1	&\color{bo}-1 &\color{bo} 4 &\color{bo} 0 &\color{bo} -4 \\\hline
\color{bo} \textbf{b}_B &\color{bo} 0 &\color{bo} -1 &\color{bo} 1 &\color{bo} 1 &\color{bo} -1 &\color{bo} 0 &\color{bo} -1 &\color{bo} 2 &\color{bo} -1 &\color{bo} -4 &\color{bo} 4 &\color{bo} 0\\\hline
\color{bo} \textbf{b}_C &\color{bo} -1 &\color{bo} 0 &\color{bo} -1 &\color{bo} 0 &\color{bo} 1 &\color{bo} 1 &\color{bo} -1 &\color{bo} -1 &\color{bo} 2 &\color{bo} 0 &\color{bo} -4 &\color{bo} 4\\\hline\hline
\color{co}\text{Cond} & \color{co}1 &\color{co} -1 &\color{co} -1 &\color{co} 1 &\color{co} 1 &\color{co} -1 &\color{co} 0 &\color{co} 0 &\color{co} 0 &\color{co} 2 &\color{co} 2 &\color{co} 2\\\hline\hline
\color{re}\textbf{r}_A &\color{re} 1 &\color{re} 1 &\color{re} -2 &\color{re} 1 &\color{re} -2 &\color{re} 1 
			&\color{re} 2\text{-}4t &\color{re} \text{-}1\!+\!2t &\color{re} \text{-}1\!+\!2t  &\color{re} 0 &\color{re} 0 &\color{re} 0\\\hline
\color{re} \textbf{r}_B &\color{re}-2 &\color{re} 1 &\color{re} 1 &\color{re} 1 &\color{re} 1 &\color{re} -2 
			&\color{re} \text{-}1\!+\!2t  &\color{re} 2\text{-}4t &\color{re} \text{-}1\!+\!2t  &\color{re} 0 &\color{re} 0 &\color{re} 0\\\hline
\color{re} \textbf{r}_C &\color{re}1 &\color{re} -2 &\color{re} 1 &\color{re} -2 &\color{re} 1 &\color{re} 1 
			&\color{re} \text{-}1\!+\!2t  &\color{re} \text{-}1\!+\!2t  &\color{re} 2\text{-}4t &\color{re} 0 &\color{re} 0 &\color{re} 0
\end{array}
$}}}\only<3->{
\centerline{$\displaystyle
\begin{array}{r||c|c|c||c|c|c}
& \multicolumn{3}{c||}{\text{Points}}
		&\text{\footnotesize$A\!>\!B$} 
		&\text{\footnotesize$B\!>\!C$} 
		&\text{\footnotesize$C\!>\!A$}\\
& \multicolumn{3}{c||}{\mathbf{w}=(1,t,0)} & \text{vs.} & \text{vs.} & \text{vs.} \\
& A & B & C
				& \text{\footnotesize$A\!<\!B$} 
				& \text{\footnotesize$B\!<\!C$} 
				& \text{\footnotesize$C\!<\!A$}\\\hline\hline
\color{ke}\text{Ker}  
		&\color{ke} 2 + 2t&\color{ke} 2 + 2t&\color{ke} 2 + 2t &\color{ke} 0 &\color{ke} 0 &\color{ke} 0\\\hline\hline
\color{bo}\textbf{b}_A &\color{bo} 2	 &\color{bo} -1	&\color{bo}-1 &\color{bo} 4 &\color{bo} 0 &\color{bo} -4 \\\hline
\color{bo}\textbf{b}_B &\color{bo} -1 &\color{bo} 2 &\color{bo} -1 &\color{bo} -4 &\color{bo} 4 &\color{bo} 0\\\hline
\color{bo}\textbf{b}_C &\color{bo} -1 &\color{bo} -1 &\color{bo} 2 &\color{bo} 0 &\color{bo} -4 &\color{bo} 4\\\hline\hline
\color{co}\text{Cond} &\color{co}  0 &\color{co} 0 &\color{co} 0 &\color{co} 2 &\color{co} 2 &\color{co} 2\\\hline\hline
\color{re}\textbf{r}_A &\color{re}  
			 2 - 4t &\color{re}  - 1+2t &\color{re}  - 1+2t  &\color{re} 0 &\color{re} 0 &\color{re} 0\\\hline
\color{re}\textbf{r}_B &\color{re} 
			  - 1+2t  &\color{re} 2 - 4t &\color{re}  - 1+2t  &\color{re} 0 &\color{re} 0 &\color{re} 0\\\hline
\color{re}\textbf{r}_C &\color{re} 
			  - 1+2t  &\color{re}  - 1+2t  &\color{re} 2 - 4t &\color{re} 0 &\color{re} 0 &\color{re} 0
\end{array}
$}
} \medskip


\alert{Don't worry about negatives}: negative votes are fixed by the kernel. 

\smallskip

\pause

Note: The reversal space is trivial \emph{precisely} when $t = 1/2$.



\pause\pause 
\medskip

\alert{\hrule}
\medskip

\alert{Theorem (Saari '00)} Given a full ranking of $n$ candidates, the reversal space is trivial precisely for weight \\ \smallskip
\centerline{$\displaystyle
\ww = \left(1, \  \frac{n-2}{n-1}, \ \dots, \  \frac{2}{n-1},\  \frac{1}{n-1},\  0\right).
$} \smallskip



\end{frame}



\begin{frame}{Permutations and the symmetric group}
A \alert{permutation} is a bijective (one-to-one and onto) function\\
 \centerline{$\sigma: \{1, \dots, n\} \to \{1, \dots, n\}$.} 

\smallskip

Permutation diagrams:
$$\begin{tikzpicture}[line width=1pt]
\uncover<3->{
	\foreach \x in {1,...,5}{
	\draw[dotted, structure] (\x,0)--(\x,-.5);
	}
}
%%%%%%%%%%%%%
\draw[<-, shorten <=2pt] (1,1.5)--(2,0); 
\draw[<-, shorten <=2pt] (2,1.5)--(4,0); 
\draw[<-, shorten <=2pt] (3,1.5)--(1,0); 
\draw[<-, shorten <=2pt] (4,1.5)--(5,0); 
\draw[<-, shorten <=2pt] (5,1.5)--(3,0); 
\foreach \x in {1,...,5}{
 \filldraw [structure] (\x,1.5) circle (2pt);
 \filldraw [structure] (\x,0) circle (2pt);
\node at (\x, 1.8) {\scriptsize \color{structure} \x};
\uncover<1-2>{  \node at (\x, -.3) {\scriptsize \color{structure} \x};}
}
%%%%%%%%%%%%%
\pgftransformyshift{-2.1cm}
%%%%%%%%%%%%%
\uncover<2->{
	\draw[<-, shorten <=2pt] (1,1.5)--(2,0); 
	\draw[<-, shorten <=2pt] (2,1.5)--(1,0); 
	\draw[<-, shorten <=2pt] (3,1.5)--(4,0); 
	\draw[<-, shorten <=2pt] (4,1.5)--(5,0); 
	\draw[<-, shorten <=2pt] (5,1.5)--(3,0); 
	\foreach \x in {1,...,5}{
		 \filldraw [structure] (\x,1.5) circle (2pt);
		 \filldraw [structure] (\x,0) circle (2pt);
		  \node at (\x, -.3) {\scriptsize \color{structure} \x};
	 }
}
%%%%%%%%%%%%%
\pgftransformyshift{1cm}
\pgftransformxshift{6cm}
%%%%%%%%%%%%%
\uncover<4->{\node at (0,.75) {$=$};
	\draw[<-, shorten <=2pt] (1,1.5)--(1,0); 
	\draw[<-, shorten <=2pt] (2,1.5)--(5,0); 
	\draw[<-, shorten <=2pt] (3,1.5)--(2,0); 
	\draw[<-, shorten <=2pt] (4,1.5)--(3,0); 
	\draw[<-, shorten <=2pt] (5,1.5)--(4,0); 
	\foreach \x in {1,...,5}{
		 \filldraw [structure] (\x,1.5) circle (2pt);
		 \filldraw [structure] (\x,0) circle (2pt);
		  \node at (\x, -.3) {\scriptsize \color{structure} \x};
		  \node at (\x, 1.8) {\scriptsize \color{structure} \x};
	 }
}
\end{tikzpicture}$$
\uncover<2->{Permutations ``multiply'' by stacking and resolving.}

\medskip

\uncover<5->{The \alert{symmetric group} $S_n$ is the group of permutations of $1, \dots, n$ with multiplication given by function composition.}
\end{frame}


\begin{frame}{Some examples:} 

\def\Unit{.5}
$$
\begin{tikzpicture}[scale=\Unit]
\node at (-2,0) {$S_1:$};
\foreach \x in {1}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<-] (t1) -- (b1);
\end{tikzpicture}$$


\hrule
\medskip

$$\begin{tikzpicture}[scale=\Unit]
\node at (-2,0) {$S_2:$};
\foreach \x in {1,2}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b1);
\draw[<-] (t2) -- (b2);
\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=\Unit]
\foreach \x in {1,2}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b2);
\draw[<-] (t2) -- (b1);
\end{tikzpicture}
$$


\hrule
\medskip

$S_3:$


$$\begin{tikzpicture}[scale=\Unit]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b1);
\draw[<-] (t2) -- (b2);
\draw[<-] (t3) -- (b3);
\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=\Unit]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b2);
\draw[<-] (t2) -- (b1);
\draw[<-] (t3) -- (b3);
\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=\Unit]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b1);
\draw[<-] (t2) -- (b3);
\draw[<-] (t3) -- (b2);
\end{tikzpicture}$$
\medskip
$$\begin{tikzpicture}[scale=\Unit]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b2);
\draw[<-] (t2) -- (b3);
\draw[<-] (t3) -- (b1);
\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=\Unit]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b3);
\draw[<-] (t2) -- (b1);
\draw[<-] (t3) -- (b2);
\end{tikzpicture}
\qquad\qquad
\begin{tikzpicture}[scale=\Unit]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};
}
\draw[<- ] (t1) -- (b3);
\draw[<-] (t2) -- (b2);
\draw[<-] (t3) -- (b1);
\end{tikzpicture}$$

\end{frame}

\begin{frame}
A \alert{representation} of a group is a map from the group to a set of matrices that follows same multiplication rules.
\pause

\smallskip
\hrule
\smallskip

Example: Permutation representation of the symmetric group. 

$$
\begin{tikzpicture}[scale=1]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};
\uncover<1-3>{	\node[below, outer sep=3pt, inner sep = 0pt] at (b\x) {\tiny \x};
	\node[above, outer sep=3pt, inner sep = 0pt] at (t\x) {\tiny \x};}
}
\draw[<- ] (t1) -- (b2);
\draw[<-] (t2) -- (b3);
\draw[<-] (t3) -- (b1);
\uncover<4->{
\foreach \x in {1,2,3}{
\node[above] at (t\x) {\small$v_\x$};
\node[below] at (b\x) {\small$v_\x$};
}
\uncover<5->{
	\node[right] at (3.5,0) {$\displaystyle = \begin{pmatrix}  0&1&0\\ 0&0&1\\1&0&0\end{pmatrix}$ };
}
}
\end{tikzpicture}$$
\uncover<3->{Pick a basis for $\QQ^3$: \\
\centerline{$\displaystyle v_1 = \hbox{\scriptsize$\begin{pmatrix} 1\\0\\0 \end{pmatrix}$} \qquad  v_2 =  \hbox{\scriptsize$\begin{pmatrix} 0\\1\\0 \end{pmatrix}$} \qquad v_3 =  \hbox{\scriptsize$\begin{pmatrix} 0\\0\\1 \end{pmatrix}$} $}}\uncover<4->{\noindent Map each permutation to the matrix that permutes the basis vectors in the same way. {\footnotesize(Recall: $i$th col.\ is image of $i$th basis vector)}}



\uncover<6->{
\smallskip
\hrule
\smallskip


Aside: we actually have a representation of the \alert{group ring} \\
\centerline{$\displaystyle \QQ S_n = \left\{ \sum_{\sigma \in S_n} r_\sigma \sigma ~|~ r_\sigma \in \QQ \right\} , \text{ with multiplication like polynomials.} $}}
\end{frame}


%%%%%%%%%%%%%
%%%%%%%%%%%%%
%%%%%%%%%%%%%
%%%%%%%%%%%%%
\begin{frame}
\centerline{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{1}{2}{3}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
	\Mat
	{1}{0}{0}
	{0}{1}{0}
	{0}{0}{1}
\node at (8.7, 0) {};
\end{tikzpicture}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{2}{3}{1}
	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{0}{1}
	{1}{0}{0}
	{0}{1}{0}
\node at (8.7, 0) {};
\end{tikzpicture}}

\medskip

\centerline{{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{2}{1}{3}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{1}{0}
	{1}{0}{0}
	{0}{0}{1}
\node at (8.7, 0) {};
\end{tikzpicture}}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{3}{1}{2}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{1}{0}
	{0}{0}{1}
	{1}{0}{0}
\node at (8.7, 0) {};
\end{tikzpicture}}

\medskip

\centerline{{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{1}{3}{2}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{1}{0}{0}
	{0}{0}{1}
	{0}{1}{0}
\node at (8.7, 0) {};
\end{tikzpicture}}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{3}{2}{1}
	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{0}{1}
	{0}{1}{0}
	{1}{0}{0}
\node at (8.7, 0) {};
\end{tikzpicture}}

~

\uncover<2-3>{For example, 
\only<1-2>{$$\begin{matrix}
		\TikZ{[xscale=\Scale, yscale=-\Scale]\Perm{2}{1}{3}} &*& \TikZ{[xscale=\Scale, yscale=-\Scale]\Perm{2}{1}{3}} &=& \TikZ{[xscale=\Scale, yscale=-\Scale]\Perm{1}{2}{3}}\\
	\TikZ{[xscale=\Scale, yscale=-\Scale]
		\Mat
		{0}{1}{0}
		{1}{0}{0}
		{0}{0}{1}} & * & 
	\TikZ{[xscale=\Scale, yscale=-\Scale]
		\Mat
		{0}{1}{0}
		{1}{0}{0}
		{0}{0}{1}} & = & 
		\TikZ{[xscale=\Scale, yscale=-\Scale]
		\Mat
		{1}{0}{0}
		{0}{1}{0}
		{0}{0}{1}}
		\end{matrix}
		$$}%
\only<3>{$$\begin{matrix}
		\TikZ{[xscale=\Scale, yscale=-\Scale]\Perm{2}{1}{3}} &*& \TikZ{[xscale=\Scale, yscale=-\Scale]\Perm{2}{3}{1}} &=& \TikZ{[xscale=\Scale, yscale=-\Scale]\Perm{1}{3}{2}}\\
	\TikZ{[xscale=\Scale, yscale=-\Scale]
		\Mat
		{0}{1}{0}
		{1}{0}{0}
		{0}{0}{1}} & * & 
	\TikZ{[xscale=\Scale, yscale=-\Scale]
		\Mat
		{0}{0}{1}
		{1}{0}{0}
		{0}{1}{0}} & = & 
		\TikZ{[xscale=\Scale, yscale=-\Scale]
		\Mat
		{1}{0}{0}
		{0}{0}{1}
		{0}{1}{0}}
		\end{matrix}
		$$}}
		
		
	

~

~

~

~

~

\end{frame}

%%%%%%%%%%%%%
%%%%%%%%%%%%%
%%%%%%%%%%%%%
%%%%%%%%%%%%%
\begin{frame}
\def\YBlock{
\draw[fill=blue!10, draw=blue!50, rounded corners = 2pt] (.5+.1,2-.1)--(.5+.1,.5+.1)--(2.5-.1,.5+.1)--(2.5-.1,2.5-.1)--(.5+.1,2.5-.1)--(.5+.1,2-.1);
\draw[fill=yellow!20, draw=orange!50, rounded corners = 2pt] (2.5+.1,3-.1)--(2.5+.1,2.5+.1)--(3.5-.1,2.5+.1)--(3.5-.1,3.5-.1)--(2.5+.1,3.5-.1)--(2.5+.1,3-.1);
\draw[fill=red!20, draw=red!50, rounded corners = 2pt] (2.5+.1,2-.1)--(2.5+.1,.5+.1)--(3.5-.1,.5+.1)--(3.5-.1,2.5-.1)--(2.5+.1,2.5-.1)--(2.5+.1,2-.1);
\draw[fill=red!20, draw=red!50, rounded corners = 2pt] (.5+.1,3-.1)--(.5+.1,2.5+.1)--(2.5-.1,2.5+.1)--(2.5-.1,3.5-.1)--(.5+.1,3.5-.1)--(.5+.1,3-.1);
}
\centerline{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{1}{2}{3}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
	\Mat
	{1}{0}{0}
	{0}{1}{0}
	{0}{0}{1}
\node at (8.7, 0) {};
\uncover<3->{	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
	\uncover<7->{\YBlock}
	\Mat
	{1}{0}{0}
	{0}{1}{0}
	{0}{0}{1}}
\end{tikzpicture}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{2}{3}{1}
	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{0}{1}
	{1}{0}{0}
	{0}{1}{0}
\node at (8.7, 0) {};
\uncover<4->{	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
	\uncover<7->{\YBlock}
\Mat
	{0}{-1}{0}
	{1}{-1}{0}
	{0}{0}{1}}
\end{tikzpicture}}

\medskip

\centerline{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{2}{1}{3}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{1}{0}
	{1}{0}{0}
	{0}{0}{1}
\node at (8.7, 0) {};
\uncover<5->{
	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
	\uncover<7->{\YBlock}
\Mat
	{-1}{1}{0}
	{0}{1}{0}
	{0}{0}{1}}
\end{tikzpicture}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{3}{1}{2}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{1}{0}
	{0}{0}{1}
	{1}{0}{0}
\node at (8.7, 0) {};
\uncover<6->{	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
	\uncover<7->{\YBlock}
\Mat
	{-1}{1}{0}
	{-1}{0}{0}
	{0}{0}{1}}
\end{tikzpicture}}

\medskip

\centerline{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{1}{3}{2}
\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{1}{0}{0}
	{0}{0}{1}
	{0}{1}{0}
\node at (8.7, 0) {};
\uncover<6->{		\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
	\uncover<7->{\YBlock}
\Mat
	{1}{0}{0}
	{1}{-1}{0}
	{0}{0}{1}}
\end{tikzpicture}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{3}{2}{1}
	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\Mat
	{0}{0}{1}
	{0}{1}{0}
	{1}{0}{0}
\node at (8.7, 0) {};
\uncover<6->{		\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
	\uncover<7->{\YBlock}
\Mat
	{0}{-1}{0}
	{-1}{0}{0}
	{0}{0}{1}}
\end{tikzpicture}}


Notice that the permutation representation has an \alert{invariant subspace} $\QQ\{v_1 + v_2 + v_3\}$, since 
$$M (v_1 + v_2 + v_3) = v_1 + v_2 + v_3 $$
for all permutation matrices $M$.




\uncover<2->{Change to basis

$$w_1 = v_1 - v_2, \qquad w_2 = v_2 - v_3, \qquad \alert{w_3 = v_1 + v_2 + v_3}$$}

\end{frame}



%%%%%%%%%%%%%
%%%%%%%%%%%%%
%%%%%%%%%%%%%
%%%%%%%%%%%%%
\begin{frame}
\def\GBlock{
\draw[fill=green!10, draw=green!50!blue, rounded corners = 2pt] (.5,2)--(.5,.5)--(3.5,.5)--(3.5,3.5)--(.5,3.5)--(.5,2);
}
\centerline{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{1}{2}{3}
\uncover<1-3>{	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\GBlock
	\Mat
	{1}{0}{0}
	{0}{1}{0}
	{0}{0}{1}
\uncover<2-3>{	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
	\Blocks
	\Mat
	{1}{0}{0}
	{0}{1}{0}
	{0}{0}{1}}}
\uncover<4-6>{
	\MatB
	{1}{0}{0}
	{0}{1}{0}
	{0}{0}{1}}
\end{tikzpicture}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{2}{3}{1}
\uncover<1-3>{	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\GBlock
\Mat
	{0}{0}{1}
	{1}{0}{0}
	{0}{1}{0}}
\uncover<2-3>{	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
\Blocks
\Mat
	{0}{-1}{0}
	{1}{-1}{0}
	{0}{0}{1}}
\uncover<4-6>{
\MatB
	{0}{-1}{0}
	{1}{-1}{0}
	{0}{0}{1}}
\end{tikzpicture}}

\medskip

\centerline{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{2}{1}{3}
\uncover<1-3>{	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\GBlock
\Mat
	{0}{1}{0}
	{1}{0}{0}
	{0}{0}{1}
\uncover<2-3>{	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
\Blocks
\Mat
	{-1}{1}{0}
	{0}{1}{0}
	{0}{0}{1}}}
\uncover<4-6>{
\MatB
	{-1}{1}{0}
	{0}{1}{0}
	{0}{0}{1}}
\end{tikzpicture}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{3}{1}{2}
\uncover<1-3>{	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\GBlock
\Mat
	{0}{1}{0}
	{0}{0}{1}
	{1}{0}{0}}
\uncover<2-3>{	\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
\Blocks
\Mat
	{-1}{1}{0}
	{-1}{0}{0}
	{0}{0}{1}}
\uncover<4-6>{
\MatB
	{-1}{1}{0}
	{-1}{0}{0}
	{0}{0}{1}}
\end{tikzpicture}}

\medskip

\centerline{\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{1}{3}{2}
\uncover<1-3>{	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\GBlock
\Mat
	{1}{0}{0}
	{0}{0}{1}
	{0}{1}{0}}
\uncover<2-3>{		\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
\Blocks
\Mat
	{1}{0}{0}
	{1}{-1}{0}
	{0}{0}{1}}
\uncover<4-6>{
\MatB
	{1}{0}{0}
	{1}{-1}{0}
	{0}{0}{1}}
\end{tikzpicture}
\hfill
\begin{tikzpicture}[xscale=\Scale, yscale=-\Scale]
\Perm{3}{2}{1}
\uncover<1-3>{	\ShiftX{3.75cm}\node at (1,2) {$\mapsto$};\ShiftX{1.5cm}
\GBlock
\Mat
	{0}{0}{1}
	{0}{1}{0}
	{1}{0}{0}}
\uncover<2-3>{		\ShiftX{3.5cm}\node at (1,2) {$\sim$};\ShiftX{1.5cm}	
\Blocks
\Mat
	{0}{-1}{0}
	{-1}{0}{0}
	{0}{0}{1}}
\uncover<4-6>{
\MatB
	{0}{-1}{0}
	{-1}{0}{0}
	{0}{0}{1}
}
\end{tikzpicture}}

Start with the {\color{green!70!blue}permutation representation $P$} with basis $\{v_1, v_2, v_3\}$.\\
\uncover<2->{Change to basis
$$w_1 = v_1 - v_2, \qquad w_2 = v_2 - v_3, \qquad w_3 = v_1 + v_2 + v_3$$}\uncover<5->{We say 
{\color{green!70!blue}$P$} is isomorphic to the sum of two smaller representations: 
\centerline{${\color{green!70!blue}P} \cong {\color{blue}\rho} \oplus {\color{orange!90!yellow}\psi}$}}
\uncover<6->{We say $\rho$ and $\psi$ are \alert{simple} because neither has any invariant subspaces.}
\end{frame}






%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%
\begin{frame}{Some combinatorics.}

Let $n$ be a non-negative integer. \\
A \alert{partition $\lambda$} of $n$ is a non-ordered list of positive integers which sum to $n$. 

\bigskip 

Example: the partitions of 3 are $(3)$, $(2,1)$, and $(1,1,1)$. 

\bigskip \pause

We draw partitions as $n$ boxes left-justified, where the \alert{parts} are the number of boxes in a row (reading from the bottom):

$$\begin{tikzpicture}[xscale=.5, yscale=.5]
\node[left] at (-.5,2) {$\lambda = (5,4,4,2) = $};
\Part{5,4,4,2}
\end{tikzpicture}$$




\end{frame}




%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%
\begin{frame}


{
\def\One{2}
\def\Two{3}
\def\TwoA{4}
\def\TwoB{5}
\def\Three{6}
\def\Four{7}
\def\DefA{8}
\def\ExAa{9}
\def\ExAb{10}
\def\ExAc{11}
\def\ExAd{12}
\def\RepsA{13}
\def\RepsB{14}


\begin{center}
\begin{tikzpicture}[xscale=3*\UNIT, yscale=-4.5*\UNIT]
%Sets the coordinates for the partitions of 0 to 5:
	\coordinate (0) at (0,.4);
	\coordinate (11) at (0,1.2);
	\coordinate (21) at (-1,2);\coordinate (22) at (1,2);
	\foreach \x in {1, ..., 3}{\coordinate (3\x) at (-4+2*\x,3);}
	\foreach \x in {1, ..., 5}{\coordinate (4\x) at (-6+2*\x,4.5);}
%edges in lattice:
\uncover<\One->{\draw (0)--(11);}
\uncover<\Two->{
	\draw (11)--(21) (11)--(22);}
	\uncover<\TwoB->{
	\draw (21)--(31) (21)--(32);}
	\uncover<\Three->{\draw (22)--(32) (22)--(33);}
\uncover<\Four->{	
	\draw (31)--(41) (31)--(42) (32)--(42)  (32)--(43) (32)--(44) (33)--(44)  (33)--(45);}
\uncover<\ExAb>{ \draw[thick, red] (0)--(11)--(21)--(31)--(42);}
\uncover<\ExAc>{ \draw[thick, red] (0)--(11)--(21)--(32)--(42);}
\uncover<\ExAd>{ \draw[thick, red] (0)--(11)--(22)--(32)--(42);}
%partitions in lattice:
\begin{scope}[every node/.style={fill=white}]
	\node at (0) {$\emptyset$};
\uncover<\One->{	
	\node at (11) {\PART{1}};}
\uncover<\Two->{
	\node at (22) {\PART{1,1}};
	\node at (21) {\PART{2}};
	\only<\TwoA-\TwoB>{\node at (21) {\fPART{2}{red!30}};}
	}
\uncover<\Three->{
	\node at (33) {\PART{1,1,1}};}
\uncover<\TwoB->{	
	\node at (32) {\PART{2,1}};
	\node at (31) {\PART{3}};}
\uncover<\Four->{
	\node at (45) {\PART{1,1,1,1}};
	\node at (44) {\PART{2,1,1}};
	\node at (43) {\PART{2,2}};
	\node at (42) {\PART{3,1}};
	\node at (41) {\PART{4}};}
\uncover<\ExAa-\ExAd>{
	\node at (42) {\fPART{3,1}{red!30}};
}
\uncover<\ExAb>{
	\node at (11) {\fPART{1}{red!30}};
	\node at (21) {\fPART{2}{red!30}};
	\node at (31) {\fPART{3}{red!30}};}
\uncover<\ExAc>{
	\node at (11) {\fPART{1}{red!30}};
	\node at (21) {\fPART{2}{red!30}};
	\node at (32) {\fPART{2,1}{red!30}};}
\uncover<\ExAd>{
	\node at (11) {\fPART{1}{red!30}};
	\node at (22) {\fPART{1,1}{red!30}};
	\node at (32) {\fPART{2,1}{red!30}};}
\uncover<\RepsA->{
	\node at (31) {\fPART{3}{yellow!30}};
	\node at (32) {\fPART{2,1}{blue!30}};
	\node at (33) {\fPART{1,1,1}{red!30}};}
\end{scope}
\uncover<\RepsA->{\node at (-4,3) {$S_3:$};}
\uncover<\Four->{\foreach \x in {-4,0,4} {\node at (\x , 5.1) {$\vdots$}; }}
\node[below right] at (-6,.4) {\alert{Young's lattice:}};
\end{tikzpicture}
\end{center}


\uncover<\DefA->{\alert{$\lambda$-Tableau}: a path from $\emptyset$ down to a partition $\lambda$. \\}
\uncover<\RepsA->{\alert{Theorem 1}: (Up to isomorphism) the simple $S_n$-representations are \alert{indexed} by partitions of $n$.\\}
\uncover<\RepsB->{\alert{Theorem 2}: If $\lambda$ is a partition of $n$, then the corresponding representation has basis indexed by $\lambda$-tableaux, and matrices determined by other combinatorial data about those paths.}


}\end{frame}


%%%%%%%%%%%%
%%%%%%%%%%%%
%%%%%%%%%%%%
%%%%%%%%%%%%
\begin{frame}

\begin{center}
\begin{tikzpicture}[xscale=3*\UNIT, yscale=-4.5*\UNIT]
%Sets the coordinates for the partitions of 0 to 5:
	\coordinate (00) at (-2,.4);
	\coordinate (01) at (0,.4);
	\coordinate (02) at (2,.4);
	\foreach \x in {0, ..., 2}{\coordinate (1\x) at (-2+2*\x,1.2);}
	\foreach \x in {0, ..., 3}{\coordinate (2\x) at (-3+2*\x,2);}
	\foreach \x in {0, ..., 4}{\coordinate (3\x) at (-4+2*\x,3);}
	\foreach \x in {1, ..., 5}{\coordinate (4\x) at (-6+2*\x,4.5);}
	\draw[very thin, black!20] (21)--(31) (22)--(33) (31)--(41) (31)--(42) (32)--(42)  (32)--(43) (32)--(44) (33)--(44)  (33)--(45);
%edges in lattice:
	\draw[thick, blue] (01)--(11)--(21) (11)--(22) (21)--(32) (22)--(32);
	\draw[thick, orange] (00)--(10)--(20)--(30);
	\draw[thick, red] (02)--(12)--(23)--(34);
%partitions in lattice:
\begin{scope}[every node/.style={fill=white}]
	\node at (33) {\gPART{1,1,1}};
	\node at (31) {\gPART{3}};
	\node at (45) {\gPART{1,1,1,1}};
	\node at (44) {\gPART{2,1,1}};
	\node at (43) {\gPART{2,2}};
	\node at (42) {\gPART{3,1}};
	\node at (41) {\gPART{4}};
\end{scope}
\begin{scope}[every node/.style={fill=white}]
	\node at (00) {\color{orange}$\emptyset$};
	\node at (01) {\color{blue}$\emptyset$};
	\node at (02) {\color{red}$\emptyset$};
	\node at (10) {\fPART{1}{yellow!30}};
	\node at (20) {\fPART{2}{yellow!30}};
	\node at (30) {\fPART{3}{yellow!30}};
	\node at (11) {\fPART{1}{blue!30}};
	\node at (21) {\fPART{2}{blue!30}};
	\node at (22) {\fPART{1,1}{blue!30}};
	\node at (32) {\fPART{2,1}{blue!30}};
	\node at (12) {\fPART{1}{red!30}};
	\node at (23) {\fPART{1,1}{red!30}};
	\node at (34) {\fPART{1,1,1}{red!30}};
\end{scope}
\foreach \x in {-4,0,4} {\node[white] at (\x , 5.1) {$\vdots$}; }
\end{tikzpicture}
\end{center}


\alert{$\lambda$-Tableau}: a path from $\emptyset$ down to a partition $\lambda$. \\
\alert{Theorem 1}: (Up to isomorphism) the simple $S_n$-representations are \alert{indexed} by partitions of $n$.\\
\alert{Theorem 2}: If $\lambda$ is a partition of $n$, then the corresponding representation has basis indexed by $\lambda$-tableaux, and matrices determined by other combinatorial data about those paths.

\end{frame}


\begin{frame}{Why do \emph{we} care about representations of $S_n$?}

\centerline{$\displaystyle
\begin{tikzpicture}[scale=.75]
\foreach \x in {1,2,3}{
	\node[V] (t\x) at (\x,.75) {};
	\node[V](b\x) at (\x,-.75) {};}
\draw[<- ] (t1) -- (b2);
\draw[<-] (t2) -- (b3);
\draw[<-] (t3) -- (b1);
\only<1>{\foreach \x/\y in {1/{v_1},2/{v_2},3/{v_3}}{
\node[above] at (t\x) {\small$\y$};
\node[below] at (b\x) {\small$\y$};}}
\only<2->{\foreach \x/\y in {1/A,2/B,3/C}{
\node[above] at (t\x) {\small$\y$};
\node[below] at (b\x) {\small$\y$};}}
	\node[right] at (3.5,0) {$\displaystyle = \begin{pmatrix}  0&1&0\\ 0&0&1\\1&0&0\end{pmatrix}$ };
\end{tikzpicture}
$} \smallskip
Pick a basis for $\QQ^3$: \\
\centerline{$\displaystyle 
	\only<1>{v_1}\only<2->{A} = \hbox{\scriptsize$\begin{pmatrix} 1\\0\\0 \end{pmatrix}$} \qquad  
	\only<1>{v_2}\only<2->{B} =  \hbox{\scriptsize$\begin{pmatrix} 0\\1\\0 \end{pmatrix}$} \qquad 
	\only<1>{v_3}\only<2->{C} =  \hbox{\scriptsize$\begin{pmatrix} 0\\0\\1 \end{pmatrix}$} $}
\noindent Map each permutation to the matrix that permutes the basis vectors in the same way. 

\medskip

\pause \pause 
We use the permutation representation to model the \alert{outcome space}. For example, the vector \\ \smallskip
\centerline{$\displaystyle
(13, 19, 22) = 13A + 19 B + 22 C
$} \smallskip
means A, B, and C got 13, 19, and 22 votes, respectively. 

\pause \medskip

\alert{Theorem.} The permutation representation decomposes into one simple $1$-dimensional (\alert{trivial}) representation and one simple $(n-1)$-dimensional (\alert{reflection}) representation.




\end{frame}


\begin{frame}

The permutation representation  models the \alert{outcome space}. \\
More: all voting data spaces are symmetric group ``\alert{modules}''.

\smallskip

In other words:
\centerline{\alert{\large Permutations naturally move around voting and outcome spaces.}}  

\smallskip

(Permute the candidate's names, or their places on the ballot.)

\pause
\medskip

\hrule

\medskip

Tally functions (how you add up the vote) are ``\alert{$S_n$-module homomorphisms}'', i.e.\ maps from the voter data to the outcome space that preserve
\begin{enumerate}[$\bullet$]
\item addition,\\
\uncover<3->{\alert{\small \sl If individual precincts add up votes, and then combine results, that should be the same as if the tallying happened all in one place.}}
\item scaling, and\\
\uncover<3->{\alert{\small \sl If \underline{everyone's} vote counted 5 times, the outcome should be the same.}}
\item permutations.\\
\uncover<3->{\alert{\small \sl Changing the order that candidates appear on the ballot ideally shouldn't change the outcome.}}
\end{enumerate}


\end{frame}



\begin{frame}{Big representation theory theorems}

\alert{Maschke's Theorem:} All $S_n$ modules decompose uniquely(ish) into simple modules.


\medskip\pause

\alert{Schur's Lemma:} If $\varphi: M \to N$ is a  $S_n$-module homormophism, then on each simple piece of $M$, $\varphi$ is either an isomorphism (is bijective) or trivial (sends everything to 0). 
 
 \medskip\pause
 
 
 \alert{Example:} The space of possible votes in a 3-way race with full-rankings is \\ \smallskip
\centerline{$\displaystyle
\fPART{3}{yellow!30} \quad \oplus \quad \fPART{2,1}{blue!30} \quad \oplus \quad \fPART{2,1}{blue!30}\quad \oplus \quad \fPART{1,1,1}{red!30}
$} \smallskip
\pause 
\centerline{
{\color{ke}Kernel} $\oplus$ {\color{bo}Borda}
			$\oplus$ {\color{re}Reversal}
			$\oplus$ {\color{co}Condorcet}
} \smallskip
 
 \pause The space of possible outcomes  in a 3-way race is \\ \smallskip
\centerline{$\displaystyle
\fPART{3}{yellow!30} \oplus \fPART{2,1}{blue!30}
$} \smallskip
\pause 
\centerline{
{\color{ke}Ties} $\oplus$ {\color{bo}Relative positions}
} \smallskip\pause 

First result: If you decide a winner based on a points system, Condorcet cycles get lost in the tally.
\end{frame}



\begin{frame}
 
 \alert{Example:} The space of possible votes in a 3-way race with full-rankings is \\ \smallskip
\centerline{$\displaystyle
\fPART{3}{yellow!30} \quad \oplus \quad \fPART{2,1}{blue!30} \quad \oplus \quad \fPART{2,1}{blue!30}\quad \oplus \quad \fPART{1,1,1}{red!30}
$} \smallskip
 
\centerline{
{\color{ke}Kernel} $\oplus$ {\color{bo}Borda}
			$\oplus$ {\color{re}Reversal}
			$\oplus$ {\color{co}Condorcet}
} \smallskip
 
 \pause The space of possible outcomes of a pairwise comparison (e.g.\ how many times is $A>B$, how many times is $B>A$, \dots) in a 3-way race is \\ \smallskip
\centerline{$\displaystyle
\fPART{3}{yellow!30} \quad \oplus \quad \fPART{2,1}{blue!30} \quad \oplus \quad \fPART{2,1}{blue!30}\quad \oplus \quad \fPART{1,1,1}{red!30}\ .
$} \smallskip\pause 
But by further analysis, one can compute that the image is at most \\\smallskip
\centerline{$\displaystyle
\fPART{3}{yellow!30} \quad \oplus \quad \fPART{2,1}{blue!30}\quad \oplus \quad \fPART{1,1,1}{red!30}\ .
$} \smallskip
In fact, the information lost is precisely the ``{\color{re} reversal}'' space. 

\end{frame}


\begin{frame}
 Collect full rankings of preferences for $n$ candidates\dots
 
 \smallskip
 
\begin{tikzpicture}
 	\node[draw = structure, rounded corners] (Pr) at (0,0) {	
	\begin{minipage}{1.5in}
	Votes\\
	\scriptsize
	$\TikZ{[scale=.25, rounded corners=0]
				\draw[fill = yellow!30](0,0) rectangle (4,1);
				\draw (1,0) to (1,1) (3,0) to (3,1);
				\node at (2,.5){\tiny$\cdots$};}
	+
	(n\!-\!1)\TikZ{[scale=.25, rounded corners=0]
				\draw[fill = blue!30](0,0) rectangle (4,1);
				\draw[fill = blue!30] (1,0) to (1,1) (3,0) to (3,1) (0,1) to (0,2) to (1,2) to (1,1);
				\node at (2,.5){\tiny$\cdots$};}$\\
	$+ (2n-6)\TikZ{[scale=.25, rounded corners=0]\draw(0,0) rectangle (4,1);
				\draw (1,0) to (1,1) (3,0) to (3,1) (0,1) to (0,2) to (2,2) to (2,1)
				(1,1) to (1,2);
				\node at (2,.5){\tiny$\cdots$};}
	+ \cdots + \TikZ{[scale=.25, rounded corners=0]\draw(0,0) rectangle (1,4);
				\draw (0,1) to (1,1) (0,3) to (1,3);
				\node at (.5,2.5){\tiny$\vdots$};}$\\
	(Lots of stuff)
	\end{minipage}};
	\node[draw = structure, rounded corners] (Pa) at (7,0) {	
	\begin{minipage}{1.2in}
	\small Pairwise outcomes
	
	\medskip
	
	\scriptsize
	$\TikZ{[scale=.25, rounded corners=0]
				\draw[fill = yellow!30](0,0) rectangle (4,1);
				\draw (1,0) to (1,1) (3,0) to (3,1);
				\node at (2,.5){\tiny$\cdots$};}
	+
	2\ \TikZ{[scale=.25, rounded corners=0]
				\draw[fill = blue!30](0,0) rectangle (4,1);
				\draw[fill = blue!30] (1,0) to (1,1) (3,0) to (3,1) (0,1) to (0,2) to (1,2) to (1,1);
				\node at (2,.5){\tiny$\cdots$};}$\\
	$+ 2\ \TikZ{[scale=.25, rounded corners=0]\draw(0,0) rectangle (4,1);
				\draw (1,0) to (1,1) (3,0) to (3,1) (0,1) to (0,2) to (2,2) to (2,1)
				(1,1) to (1,2);
				\node at (2,.5){\tiny$\cdots$};}
	+\TikZ{[scale=.25, rounded corners=0]\draw(0,0) rectangle (4,1);
				\draw (1,0) to (1,1) (3,0) to (3,1) (0,1) to (0,3) to (1,3) to (1,1)
				(0,2) to (1,2);
				\node at (2,.5){\tiny$\cdots$};}$
	\end{minipage}};
 
 \node[draw = structure, rounded corners] (Ta) at (7,-4) {	
	\begin{minipage}{1in}
	\small Final tally
	
	\medskip
	
	\scriptsize
	$\TikZ{[scale=.25, rounded corners=0]
				\draw[fill = yellow!30](0,0) rectangle (4,1);
				\draw (1,0) to (1,1) (3,0) to (3,1);
				\node at (2,.5){\tiny$\cdots$};}
	+
	\ \TikZ{[scale=.25, rounded corners=0]
				\draw[fill = blue!30](0,0) rectangle (4,1);
				\draw[fill = blue!30] (1,0) to (1,1) (3,0) to (3,1) (0,1) to (0,2) to (1,2) to (1,1);
				\node at (2,.5){\tiny$\cdots$};}$
	\end{minipage}};
	\draw[very thick, structure, ->, shorten >=3mm]
		 (Pr) to node[above, sloped] {assign points}(Ta);
	\draw[very thick, structure, ->, shorten >=3mm] 
			(Pr) to node[above] {compare pairs} (Pa);
	\draw[very thick, structure, ->, shorten >=3mm] 
			(Pa) to node[above, sloped] {tally pairs}(Ta);
\uncover<2->{
\node at (1,-4) {
	\begin{minipage}{2.5in}
	\alert{Goal 1:} Find a weighting for the points system that agrees as much as possible with the pairwise voting system.
	\end{minipage}};}
 \end{tikzpicture}
 
 \smallskip
 
 \pause \pause 
 
 \alert{Result 1 (Saari, \textbf{D.}):} The point-based system that agrees most with the pairwise outcomes is the (modified) Borda count, with weight 
 
\centerline{$\displaystyle
\ww = \only<1-3>{\hbox{$\left(1, \  \frac{n-2}{n-1}, \ \dots, \  \frac{2}{n-1},\  \frac{1}{n-1},\  0\right)$}}\only<4->{\left(n-1, \ n-2, \dots,\  1,\  0\right)}
$} 
 (as expected).
 
 \end{frame}
 
 
 
 \begin{frame}{Other results\dots}
 
 \alert{Partial rankings  (\textbf{D.}\ '05):} Ask voters to rank their top $k$ choices (more practical if there are \emph{many} choices). \pause Then the points system that agrees most with the pairwise outcomes is the natural analogue to the  Borda count, with weight 
 \\ \smallskip
\centerline{$\displaystyle n-i \qquad$ 
		for the $i$th candidate ($1 \leq i \leq k$), and} \smallskip
\centerline{$\displaystyle \frac{1}{2}(n-k-1)$  \quad for the last $n-k$ candidates. 
} \smallskip
(Average the remaining points amongst the last-place candidates.)


\pause 
 For example, if you ask for the top 3 out of 20, the points are $19, 18, 17, 8, \dots, 8$.
 \smallskip\pause
 
\alert{[\textbf{D.}, Eustis, Minton, Orrison; '07]}: Notes on ``Approval voting'' (ask voters which candidates they approve of), and ``Effective spaces'' (what kind of voting profiles influence elections).\pause

\medskip
 
 \alert{Committees (Barcelo, Bernstein, Bockting-Conrad, McNichols, Nyman, Viel; '18):} How to tally votes for committees with representation from several departments (using representation theory of $S_m \wr S_n$).
 
 
 
 
 
 \end{frame}
 


\begin{frame}{What do we want, and why do we care?} 


\begin{itemize}
\item Mathematicians: More data preservation is better. 

\bigskip

\item Idealists: Everyone should have a fair say.

\bigskip


\item Pragmatists: Simpler voting systems are easier to implement.

\bigskip


\item Cynics: Stupid things happen when people, en mass, are forced to game their votes.

\bigskip

\item (Over-educated) Conspiracy Theorists: Our voting system is provably about as bad as it can be without \emph{everyone} noticing.


\bigskip

\item Kenneth Arrow: No voting system is ideal, so\dots

\bigskip

\item Mathematicians (again): Oh, come \emph{on}! 
\end{itemize}

\end{frame}



\begin{frame}


\hspace{-.2in}\alert{\Large Some references\dots}

\alert{$\bullet$} Many many publications of Donal Saari, particularly around 1999--2000. Also, ``Decisions and Elections; Explaining the Unexpected'', Cambridge University Press, 2001.

\medskip


\alert{$\bullet$} ``Voting, the symmetric group, and representation theory'', by \textbf{D.}, Eustis, Minton, and Orrison. American Mathematical Monthly 116 (2009), no.\ 8, 667--687.

\medskip

\alert{$\bullet$} ``Algebraic voting theory and representations of  $S_m \wr S_n$'', by Barcelo, Bernstein, Bockting-Conrad, McNichols, Nyman, Viel. (preprint: 	arXiv:1807.03743)


\medskip

\alert{$\bullet$} ``How not to be wrong'', by Jordan Ellenberg. \\
Chapter 17: ``There is no such thing as public opinion.''



\bigskip

\bigskip

{\footnotesize \sl And even though our system is non-ideal as is\dots}

\smallskip

\centerline{\alert{\Large Go vote tomorrow!}}

\smallskip

\centerline{\alert{\Large http://vote.nyc.ny.us}}


\end{frame}

\end{document}

