\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amssymb}

%\usepackage[textheight=8.5in, margin=1.6in]{geometry}
\usepackage[total={6in,8in}]{geometry}

\usepackage{tikz}
\tikzstyle{ball} = [circle,shading=ball, ball color=black,
    minimum size=1mm,inner sep=1.3pt]

%\usepackage{graphicx}

\usepackage{enumitem}
\setlist[enumerate]{leftmargin=*}

\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Span}{\mathrm{Span}}
\DeclareMathOperator{\rk}{\mathrm{rank}}
\DeclareMathOperator{\trace}{\mathrm{tr}}
\DeclareMathOperator{\im}{\mathrm{im}}
\DeclareMathOperator{\Sym}{\mathrm{Sym}}
\DeclareMathOperator{\Hom}{\mathrm{Hom}}

\newcounter{problem}
\renewcommand \thesection {\theproblem}
\newenvironment{prob}[1][]
{
  \refstepcounter{problem}\par\medskip
  \def\myArg{#1}
  \ifx\myArg\empty
    \noindent \textsc{Problem~\theproblem.} \rmfamily
  \else
    \noindent \textsc{Problem~\theproblem\ (\textnormal{#1}).} \rmfamily
  \fi
}
{
  \medskip

}

\parskip = 0.05in
\parindent = 0.0in

\pagestyle{empty}

\begin{document}
\centerline{Math 372  Homework for Wednesday, Week 4}
\bigskip

\begin{prob}
  Let $H$ be a subgroup of $\mathfrak{S}_n$ acting on $2^{[n]}$ as in class.  If
  $\mathcal{O}$ and $\mathcal{O}'$ are two orbits of this action, define
  $\mathcal{O}\leq\mathcal{O}'$ if there exists $x\in\mathcal{O}$ and
  $y\in\mathcal{O}'$ such that $x\leq y$, i.e., $x$ is a subset of $y$.  Prove
  that~$\leq$ is a partial ordering on the set of orbits (thus making $B_n/H$
  into a poset).
\end{prob}

\begin{prob}
    Let $G = \{\iota,\pi\}$ be a group of order two (with identity element
    $\iota$).  Let $G$ act on $\{1, 2, 3, 4\}$ by $\pi\cdot 1 = 2$, $\pi \cdot 2
    = 1$, $\pi\cdot 3 = 3$, $\pi\cdot 4 = 4$.  Draw the Hasse diagram for the
    quotient poset $B_4/G$.
\end{prob}

\begin{prob}
  A $(0, 1)$-necklace of length $n$ and weight $i$ is a circular arrangement of
  $i$ $1$’s and $n-i$ $0$’s. For instance, the $(0, 1)$-necklaces of length $6$ and
  weight $3$ are (writing a circular arrangement linearly) $000111$, $001011$,
  $010011$, and $010101$. (Cyclic shifts of a linear word represent the same
  necklace, e.g., $000111$ is the same as $110001$.) Let $N_n$ denote the set of
  all $(0, 1)$-necklaces of length $n$. Define a partial order on $N_n$ by letting
  $u\leq v$ if we can obtain $v$ from $u$ by changing some $0$’s to $1$’s. It’s easy
  to see (you may assume it) that $N_n$ is graded of rank $n$, with the rank
  of a necklace being its weight.
  
  Use Theorem 5.8 to show that $N_n$ is rank-symmetric, rank-unimodal, and
  Sperner.
\end{prob}

\begin{prob} In Example 5.4~(b) in our text contains a drawing of the Hasse
  diagram of $B_5/G$, where $G$ is generated by the cycle $(1, 2, 3, 4, 5)$.
  Using the vertex labels used in that drawing, compute explicitly
  $\widehat{U}_2(\mathcal{O}_{12})$ and $\widehat{U}_2(\mathcal{O}_{13})$ as linear combinations of $123$
  and $124$, where $\widehat{U}_2$ is defined as in the proof of Theorem~5.8.
  What is the matrix of $\widehat{U}_2$ with respect to the standard
  (lexicographically ordered) bases for $(B_5/G)_2$ and $(B_5/G)_3$? 
\end{prob}

\begin{prob} (An unusual chip-firing game.) Let~$G=(V,E)$ be a graph.  A
  \emph{chip configuration} on $G$ is the assignment of a nonnegative integer to
  each vertex~$v\in V$.  Think of the integer as specifying a number of
  \emph{chips} to place on each vertex.  Say a vertex is \emph{unstable} if it
  has~$2$ or more chips.  In that case, we can \emph{fire} the vertex by
  removing~$2$ chips from it and adding~$1$ chip to each of its neighbors
  (vertices connected to it by an edge).  A chip configuration is \emph{stable}
  if it has no unstable vertices.  Sometimes, by consecutively firing a finite
  list of vertices, a chip configuration can be transformed into a stable
  configuration, in which case we say the configuration is \emph{stabilizable}.
  For instance, the following configuration is stabilizable (integers above
  vertices represent numbers of chips):
  \begin{center}
    \begin{tikzpicture}
      \node[ball,label={left:$1$}] at (0,0) (1) {};
      \node[ball,label={below:$2$}] at (1,0) (2) {};
      \node[ball,label={below:$0$}] at (2,0) (3) {};
      \node[ball,label={above:$0$}] at (1.5,0.866) (4) {};
      \draw (1)--(2)--(3)--(4)--(2);
    \end{tikzpicture}
  \end{center}
  Here is a stabilization (with the vertex to be fired indicated by putting a bar
  above its number of chips):
  \begin{center}
    \begin{tikzpicture}
      \node[ball,label={left:$2$}] at (0,0) (1) {};
      \node[ball,label={below:$\bar{2}$}] at (1,0) (2) {};
      \node[ball,label={below:$0$}] at (2,0) (3) {};
      \node[ball,label={above:$0$}] at (1.5,0.866) (4) {};
      \draw (1)--(2)--(3)--(4)--(2);
      \begin{scope}[xshift=5cm]
        \node[ball,label={left:$\bar{3}$}] at (0,0) (1) {};
        \node[ball,label={below:$0$}] at (1,0) (2) {};
        \node[ball,label={below:$1$}] at (2,0) (3) {};
        \node[ball,label={above:$1$}] at (1.5,0.866) (4) {};
        \draw (1)--(2)--(3)--(4)--(2);
      \end{scope}
      \begin{scope}[xshift=10cm]
        \node[ball,label={left:$1$}] at (0,0) (1) {};
        \node[ball,label={below:$1$}] at (1,0) (2) {};
        \node[ball,label={below:$1$}] at (2,0) (3) {};
        \node[ball,label={above:$1$}] at (1.5,0.866) (4) {};
        \draw (1)--(2)--(3)--(4)--(2);
      \end{scope}
      \draw[->] (2.8,0.3)--(3.8,0.3);
      \draw[->] (7.8,0.3)--(8.8,0.3);
    \end{tikzpicture}
  \end{center}
  One may check that the following configuration is unstabilizable:
  \begin{center}
    \begin{tikzpicture}
      \node[ball,label={left:$3$}] at (0,0) (1) {};
      \node[ball,label={below:$2$}] at (1,0) (2) {};
      \node[ball,label={below:$0$}] at (2,0) (3) {};
      \node[ball,label={above:$0$}] at (1.5,0.866) (4) {};
      \draw (1)--(2)--(3)--(4)--(2);
    \end{tikzpicture}
  \end{center}
  On the other hand, \emph{every} configuration on a path graph (vertices connected
  by a line of edges) is stabilizable.  For instance, on scratch paper, show that
  the following configuration for the path graph with four vertices,~$P_4$, is
  stabilizable:
  \begin{center}
    \begin{tikzpicture}
      \node[ball,label={above:$100$}] at (0,0) (1) {};
      \node[ball,label={above:$100$}] at (1,0) (2) {};
      \node[ball,label={above:$100$}] at (2,0) (3) {};
      \node[ball,label={above:$100$}] at (3,0) (4) {};
      \draw (1)--(2)--(3)--(4);
    \end{tikzpicture}
  \end{center}
  For this problem, find a graph~$G$ that is not a path graph having the property that
  every configuration on~$G$ is stabilizable.  [For more of a challenge, find an
  infinite family of such graphs.  For even more of a challenge, classify all such
  graphs.]
\end{prob}
\end{document}


