Combinatorial species

Just last month, I took my Ph.D. qualifying exam at Berkeley. It was a grueling three-hour oral exam, but from it came a gemstone that simply must be shared!

The very first question I was asked was from my advisor, Mark Haiman: ``Enumerate [count] the labeled plane trees on $n$ vertices.’’

More precisely, let $n$ be a positive integer, and define a labeled plane tree to be a tree with vertices labeled $1,2,\ldots,n$, along with a cyclic ordering of the branches attached to each vertex. (The name ``plane tree’’ refers to the fact that the orderings of the branches determine an embedding of the tree into Euclidean space up to homotopy equivalence.) For instance, say we had the following trees drawn in the plane:

They are isomorphic as graphs but not as plane trees, because the branches around the vertex $1$ have different clockwise cyclic orderings.

So how do we count these trees?

What happens in characteristic p?

There is a reason that the real numbers and complex numbers are so popular. They have the nice property that $1+1+1+\cdots+1$ is not equal to zero, no matter how many times you add $1$ to itself.

Strange things happen in fields of prime characteristic $p\neq 0$, such as the field $\mathbb{Z}/p\mathbb{Z}$ of integers taken modulo $p$. In these fields, $1+1+\cdots+1=0$ for any number of $1$’s which is a multiple of $p$. We get non-intuitive but strangely beautiful identities like $(x+y)^p=x^p+y^p$, since the coefficient $\binom{p}{i}$ is divisible by $p$ for $1\le i\le p-1$.

And, we get a representation of the symmetric group which is indecomposable but not irreducible. Allow me to explain.

TeXStudio

First post in several weeks; term has hit. But in the midst of the hustle and bustle of the start of the semester, I’ve discovered a gemstone within the mathematical software world that was too good not to share: TeXStudio.

I discovered it while preparing for the “LaTeX Tricks” seminar this week, which I am organizing as part of the UC Berkeley Toolbox Seminar. (The seminar is looking to be quite exciting if you’re in the area - we will have a variety of speakers give 10-minute talks on their favorite LaTeX tool or package. It will be this Wednesday from 2:30-4PM in room 891 Evans Hall.)

Equilateral triangles in the complex plane

I came across an exercise in Ahlfors’ Complex Analysis the other day that got me thinking. The exercise asked to prove that the complex numbers $a$, $b$, and $c$ form the vertices of an equilateral triangle if and only if $a^2+b^2+c^2=ab+bc+ca.$ It struck me as quite a nice, simple, and symmetric condition.

My first instinct, in going about proving this, was to see if the condition was translation invariant, so that one of the points can be moved to the origin. Indeed, if we subtract a constant $z$ from each of $a,b,c$ the equation becomes $(a-z)^2+(b-z)^2+(c-z)^2=(a-z)(b-z)+(b-z)(c-z)+(c-z)(a-z),$ which simplifies to the original equation after expanding each term. So, we can assume without loss of generality that $a=0$, and we wish to show that $0$, $b$, and $c$ form the vertices of an equilateral triangle if and only if $b^2+c^2=bc$.

The 3x+1 problem!

I have exciting news today: The first ever joint paper by Monks, Monks, Monks, and Monks has been accepted for publication in Discrete Mathematics.

These four Monks’s are my two brothers, my father, and myself. We worked together last summer on the notorious $3x+1$ conjecture (also known as the Collatz conjecture), an open problem which is so easy to state that a child can understand the question, and yet it has stumped mathematicians for over 70 years.