Problem 1.

Let $\mathcal{M}$ be a matroid of rank $k$ on the set $X$. Recall that a set $A \subset X$ is independent if it is a subset of some basis of $\mathcal{M}$.
(a) Let $S \subset X$ be a nonempty subset. Show that the maximal (under inclusion) independent subsets of $S$ all have the same cardinality.
(b) Show that these maximal independent subsets form a matroid $\left.\mathcal{M}\right|_S$ on $S$.

Problem 2.

A poset $P$ is graded (in the sense of the previous pset) if and only if we can assign an integer $\rho(x)$, called the rank, to each $x \in P$ so that if $x \lessdot y$ then $\rho(y)=\rho(x)+1$. (You may assume this.)

Let $P$ be a finite graded poset with a $\hat{0}$ and $\hat{1}$. We say that $P$ is Eulerian if each interval $[s, t]$ where $s<t$ has the same number of elements with odd rank as elements with even rank.
(a) What do intervals of length 2 (that is, $[s, t]$ where $\rho(t)=\rho(s)+2$ ) in Eulerian posets look like?
(b) Verify that the Boolean algebra $B_n$ is Eulerian.
(c) Prove that a poset is Eulerian if and only if the Mobius function is given by $\mu(s, t)=(-1)^{\rho(t)-\rho(s)}$.

Problem 3.

Let $\mathcal{A}$ be the hyperplane arrangement consisting of the $n$ hyperplanes $x_i=0$ in $\mathbb{R}^n$, for $i=1,2, \ldots, n$.
(a) Show that the intersection poset $L(\mathcal{A})$ is isomorphic to the Boolean algebra.
(b) Compute the Mobius function of $L(\mathcal{A})$.
(c) Compute the characteristic polynomial of $\mathcal{A}$.

Problem 4.

Let $G$ be a simple graph on $[n]$ and let $\mathcal{A}_G$ denote the corresponding graphical arrangement in $\mathbb{R}^n$. Prove that when $G$ has no cycles, the poset $L\left(\mathcal{A}_G\right)$ is isomorphic to a Boolean algebra. Deduce a formula for the number of regions and bounded regions in $\mathcal{A}_G$ in this case.

Problem 5.

Let $\mathcal{A}$ be the hyperplane arrangement in $\mathbb{R}^n$ consisting of all hyperplanes $x_i=x_j$ for $i \neq j$ and the hyperplanes $x_i=0$ for $i=1,2, \ldots, n$. Prove that
$$\chi_{\mathcal{A}}(t)=(t-1)(t-2)(t-3) \cdots(t-n) .$$

Coordinates:

Towne 315, Tu-Th, 10:30:12:00noon

Instructors:

Jean H. Gallier, GRW 476, 8-4405, [email protected]

Jean : TBA

Textbook:

There will be no official textbook(s). We will use material from several sources and some class notes, including

•  Algebra, Topology, Differential Calculus, and Optimization Theory (manuscript) (html)
•  Fundamentals of Linear Algebra and Optimization; Some Notes (pdf)
•  Notes on Differential Geometry and Lie Groups   (html)

html

[   Grade (Homeworks, Exams)   |  Additional Resources   |  Syllabus   |  Slides and Notes   ]

Expect to be held to high standards, and conversely! In addition to transparencies, we will distribute lecture notes. Please, read the course notes regularly, and start working early on the problems sets. They will be hard! Take pride in your work. Be clear, rigorous, neat, and concise. Preferably, use a good text processor, such as LATEX, to write up your solutions.

It is forbidden to use solutions of problems posted on the internet. If you use resources other than the textbook (or the recommended textbooks) or the class notes, you must cite these references.

Plagiarism Policy

I assume that you are all responsible adults.
Copying old solutions verbatim or blatantly isomorphic solutions are easily detectable.
DO NOT copy solutions from old solution sheets, from books, from solutions posted on the internet, or from friend!
Either credit will be split among the perpetrators, or worse!

Back to Gallier Homepage