My thesis!

For the morbidly curious, here's my recently completed PhD thesis, Profiles of large combinatorial structures. (PDF, 1.1 MB, 262 pages (but double-spaced with wide margins)) This is why I haven't been posting!

Abstract: We derive limit laws for random combinatorial structures using singularity analysis of generating functions. We begin with a study of the Boltzmann samplers of Flajolet and collaborators, a useful method for generating large discrete structures at random which is useful both for providing intuition and conjecture and as a possible proof technique. We then apply generating functions and Boltzmann samplers to three main classes of objects: permutations with weighted cycles, involutions, and integer partitions. Random permutations in which each cycle carries a multiplicative weight σ have probability (1-γ)^σ of having a random element be in a cycle of length longer than γn; this limit law also holds for cycles carrying multiplicative weights depending on their length and averaging σ. Such permutations have number of cycles asymptotically normally distributed with mean and variance ~ σ log n. For permutations with weights σ_k = 1/k or σ_k = k, other limit laws are found; the prior have finitely many cycles in expectation, the latter around √n. Compositions of uniformly chosen involutions of [n], on the other hand, have about √n cycles on average. These can be modeled as modified 2-regular graphs. A composition of two random involutions in S_n typically has about n^1/2 cycles, characteristically of length n^1/2. The number of factorizations of a random permutation into two involutions appears to be asymptotically lognormally distributed, which we prove for a closely related probabilistic model. We also consider connections to pattern avoidance, in particular to the distribution of the number of inversions in involutions. Last, we consider integer partitions. Various results on the shape of random partitions are simple to prove in the Boltzmann model. We give a (conjecturally tight) asymptotic bound on the number of partitions p_M(n) in which all part multiplicities lie in some fixed set n, and explore when that asymptotic form satisfies log p_M(n) ~ π√(Cn) for rational C. Finally we give probabilistic interpretations of various pairs of partition identities and study the Boltzmann model of a family of random objects interpolating between partitions and overpartitions.

Thesis margins

What's the point of having two thousand readers if I can't ask a question like this once in a while?

I'm working on the final version of my dissertation -- the one I'll submit to the graduate school next week. The dissertation manual states that no text may appear in the margin area.

LaTeX, on the other hand, keeps wanting to put some pieces of mathematics, which appear inline, in the margins. (Presumably this is because this is "better" than the alternative of having very long inter-word spaces.)

Two questions:
- is there some way to check that nothing's sticking out in the margin? (I thought this is what "overfull \hbox" meant, but the line numbers where those appear aren't the ones where I have this problem.) There are some things that are just barely sticking out into the margin, and with thousands of lines total I don't trust my eye.
- once I find all the places where text protrudes into the margin, is there some way around this other than just inserting \newline every time this problem occurs? This creates its own problems.

I surely can't be the only person who's had this problem, but Google is failing me.

Ash clouds and probability

From the Daily Mail: New ash cloud could delay re-opening of London airports. We have this gem: "Critics said the agency used a scientific model based on 'probability' rather than fact to forecast the spread of the ash cloud." See the Telegraph as well.

What else are they supposed to do? The agency here -- the Met Office, which is the national weather service of the UK -- doesn't know what the ash cloud is going to do. If they waited to see what the cloud does, the planes would already be in the air. It would be too late.

Mathematical relationships search

There's a mathematical relationships search. It will tell you, for example, that academically, Max Noether is the first cousin of Emmy Noether. (Both of their advisors were students of Jacobi.) But Michael Artin and Emil Artin aren't even related.

It's less amusing, of course, when you search for people that aren't related in the standard way. But Paul Erdos is my great-great-great-great-uncle. (You can't search for me yet in the Mathematics Genealogy Project, which is where the data comes from; the link goes to the relationship between Erdos and another student of my advisor.)

This blog needs a new title

The word "probability" does not appear in the Bible, or so we learn from Conservapedia's List of missing words in the Bible.

I can only conclude that Einstein was right, and God does not play dice.

My 27th-generation advisor is Elissaeus Judaeus

Mathematical ancestors of Penn math faculty, from October 1999. (This was the department's 100th anniversary.) This lists the advisor's advisor's advisor's... until historical data that was (easily?) available at that time gave out. The longest-ago person listed on this page is Otto Mencke (Ph. D. 1665, 12 generations from Penn professor Stephen Shatz); most chains die out in the 19th century.

As of right now, the math genealogy project claims to know that my advisor's 26th-generation advisor is Elissaeus Judaeus (who was a student in the 1380s). Most mentions of Judaeus on the Internet seem to be by other people who have discovered this (Judaeus has 77000 or so mathematical descendents). But this post from the person who added him to the database gives some background -- he was for the most part a philosopher, it seems. He is described as "a mysterious figure who may or may not have been a Jew". His student Gemistus Pletho seems a little better understood; Wikipedia says "He was one of the chief pioneers of the revival of Greek learning in Western Europe." It seems that in that time a lot more data has been collected for the 14th through 17th centuries.

(As for me, hopefully in a few weeks it'll be possible to add me to the mathematical genealogy project. I defend on April 15.)

One down, six to go

Perelman has been awarded the Millennium Prize. Press release from the Clay Math Institute.

As Peter Woit points out, no mention of the fate of the million dollars.