\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\usepackage{tikz}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}
            
\input{preamble.tex}

\begin{document}

\homework{4: Posets, Convolution, and M\"obius Functions}{Due Friday, Week 6}

In this HW set, there are \textbf{two} sections: a \textbf{noncollaboration} section and a \textbf{collaboration} section.  For the noncollaboration section, use only your notes/class notes, and don't work with others.  For the collaboration section, work as normal!  

\section{Non-Collaboration Section}

Do the one problem below!
\begin{enumerate}
\item Take any finite poset $P = (X, <)$ on $|X| = n$ elements.  An \textbf{linear extension} of $P$ is any bijective map $f: P \to \{1,2,\ldots n\}$ such that if $x < y \in P,$ then $f(x) < f(y).$

Prove that any finite poset has a linear extension.
\end{enumerate}



\section{Collaboration Section}

Do \textbf{two} of the four problems below!
 
\begin{enumerate}





\item Consider the convolution $f * g$, the \textbf{convolution} of any two functions $f,g \in \mathbb{A}(P)$:
\begin{align*}
(f * g)(x,y) = \sum_{z: x \leq z \leq y} f(x,z)\cdot g(z,y).
\end{align*}
\begin{enumerate}
\item Prove that convolution is \textbf{associative}:\ that is, for any $f,g,h \in \mathbb{A}(P)$, prove that $f*(g*h) = (f*g)*h$.
\item Is convolution \textbf{commutative}?  That is:\ for any poset $P$ and $f,g \in \mathbb{A}(P)$, can you prove that $f*g = g*f$?  Or can you find a poset $P$ and functions $f, g \in \mathbb{A}(P)$ such that $f*g \neq g*f$?
\end{enumerate}


\item In class on Monday / in the notes online now, we proved the following theorem:
\begin{thm}
Let $P$ be any poset, and let $r$ be any function $P \to \mathbb{R}$.    Suppose that $P$ has a unique minimal element: that is, there is some $m \in P$ such that for all $x \in P, m < x$.  Define the function $s: P \to \mathbb{R}$ as follows: for any $a \in P$, set
\begin{align*}
s(a) = \sum_{x \leq a} r(x).
\end{align*}
Then we can ``invert'' the formula above: that is, for any $a \in P$, we have
\begin{align*}
r(a) = \sum_{x \leq a} s(x) \mu(x,a).
\end{align*}
\end{thm}

There is a ``flipped'' version of this theorem, where we assume our poset has a unique maximal element:

\begin{thm}
Let $P$ be any poset with a unique maximal element: that is, there is some $M \in P$ such that for all $x \in P, M > x$.  Let $r$ be any function $P \to \mathbb{R}$.  

Define the function $s: P \to \mathbb{R}$ as follows: for any $a \in P$, set
\begin{align*}
s(a) = \sum_{x \geq a} r(x).
\end{align*}
Then we can ``invert'' the formula above: that is, for any $a \in P$, we have
\begin{align*}
r(a) = \sum_{x \geq a} s(x) \mu(a,x).
\end{align*}
\end{thm}
Prove this theorem!

\item Given a poset $P$, a \textbf{chain} in $P$ is any subset $C \subseteq P$ such that any two elements in $C$ are comparable:\ that is, for any $x, y \in C$, we either have $x<y ,x=y$ or $x>y$.


Take any finite poset $P$.   Let $\delta$ be the Kronecker delta function and $\zeta$ be the zeta function on $P$, as defined in class.  For any $a, b \in P$, define the function $\eta$ as follows:
\begin{align*}
\eta(a,b) = \zeta(a,b) - \delta(a,b).
\end{align*}
Show that $\eta^k(a,b)$ is equal to the number of chains of length $k$ whose smallest element is $a$ and largest element is $b$.  (The \textbf{length} of a chain is the number of elements past the first in the chain: that is, the length of the chain $x < y$ is 1, the length of the chain $x  < y < z$ is 2, the length of the chain $x < y < z < w$ is 3\ldots)

\item Take any finite poset $P$ on $n$ elements, and any linear extension $l: P \to \{1, \ldots n\}$ of $P$.  Use this linear extension to label the elements of $P$ as $\{x_1, \ldots x_n\}$, where $l(x_i) = i$.  

Given any map $f \in \mathbb{A}(P)$, define the $n \times n$ matrix $A_f$ as follows:
\begin{align*}
A_f(i,j) = f(x_i, x_j).
\end{align*}
Show that for any two maps $f, g \in \mathbb{A}(P)$,
\begin{align*}
A_f \cdot A_g = A_{f * g}.
\end{align*}
(In other words:\ the definition of convolution we're using here actually comes from matrix multiplication!)
\end{enumerate}
\end{document}

