\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}}

\parskip = 0.05in
\parindent = 0.0in

\pagestyle{empty}

\begin{document}
\centerline{Math 372  Homework 2}
\bigskip

Note: Exercise numbers refer to the 2013 edition of our text.

\begin{enumerate}
  \item[] {\bf Chapter 3, exercise 6.} Show that if $u$ and $v$ are two vertices
    of a connected graph~$G$, then we need not have $H(u, v) = H(v, u)$, where
    $H$ denotes access (hitting) time. What if $G$ is also assumed to be regular?
  \item[] {\bf Chapter 3, exercise 7.}
  Let $u$ and $v$ be distinct vertices of the complete graph~$K_n$. Show that
  $H(u, v) = n-1$.
 \item[] {\bf Chapter 4, exercise 1.}
   Draw Hasse diagrams of the 16 nonisomorphic four-element posets.
For a more interesting challenge, draw also the 63 five-element posets.
Those with lots of time to kill, draw the 318 six-element posets,
2045 seven-element posets, the 16999 eight-element posets, up to
4483130665195087 sixteen-element posets.
  \item[] {\bf Chapter 4, exercise 2a.}
      Let $P$ be a finite poset and $f\colon P\to P$ an order-preserving
      bijection. I.e., $f$ is a bijection (one-to-one and onto), and if $x\leq y$
      in~$P$ then $f(x)\leq f(y)$. Show that $f$ is an automorphism of $P$,
      i.e., $f^{-1}$ is order-preserving. (Try to use simple algebraic
      reasoning, though it’s not necessary to do so.)
  \item[] {\bf Chapter 4, exercise 4abc.}
  Let $q$ be a prime power, and let $F_q$ denote the finite field with $q$
  elements. Let $V := V_n(q):=F^n_q$ , the $n$-dimensional vector space over~$F_q$
  of $n$-tuples of elements of $F_q$ . Let $B_n(q)$ denote the poset of all
  subspaces of $V$, ordered by inclusion. It’s easy to see that $B_n(q)$ is
  graded of rank $n$, the rank of a subspace of $V$ being its dimension.
  \begin{enumerate} 
    \item Draw the Hasse diagram of $B_3(2)$. (It has $16$ elements.)
    \item Show that the number of elements of $B_n(q)$ of rank $k$ is given
      by the {\em $q$-binomial coefficient}
      \[
	\mathbf{\binom{n}{k}}=\frac{(q^n-1)(q^{n-1}-1)\cdots(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\cdots(q-1)}.
      \]
  \item Show that $B_n(q)$ is rank-symmetric.
\end{enumerate}
\end{enumerate}
\end{document}


