Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

November 30, 2019

Random Permutations (Part 5)

Posted by John Baez

To go further in understanding the properties of random permutations, we need to use ‘bivariate’ generating functions — that is, generating functions involving 2 variables. Here’s a good introduction to these:

  • Phillipe Flajolet and Robert Sedgewick, Analytic Combinatorics, Part III: Combinatorial Parameters and Multivariate Generating Functions.

I will try to explain these in a way that takes advantage of Joyal’s work on species. Then I’ll use them to tackle this puzzle from Part 3.

Puzzle 5. What is the expected number of cycles in a random permutation of an nn-element set?

Posted at 2:41 AM UTC | Permalink | Followups (6)

November 25, 2019

Random Permutations (Part 4)

Posted by John Baez

Last time I listed a bunch of facts designed to improve our mental picture of a typical randomly chosen permutation. Many of these facts are fun to prove using generating functions. But one has a more elementary proof.

Namely: a random permutation of a large finite set has an almost 70% chance of having a single cycle that contains at least half the elements!

This really solidifies my image of a typical permutation of a large finite set. It consists of one big cycle involving most of the elements… and the rest, which is a typical permutation of the remaining smaller set.

Posted at 8:27 PM UTC | Permalink | Followups (5)

November 24, 2019

Random Permutations (Part 3)

Posted by John Baez

I’m trying to understand what a random permutation of a large set is typically like. While I’ve been solving some puzzles that shed a bit of light on this question, I now realize there are some other puzzles that would help more!

Posted at 11:12 PM UTC | Permalink | Followups (5)

Topics in Category Theory: A Spring School

Posted by Tom Leinster

guest post by Emily Roff

Topics in Category Theory: A Spring School will be taking place on March 11th–13th 2020 at the International Centre for Mathematical Sciences (ICMS) in Edinburgh, Scotland. The idea of the meeting is to gather together PhD students and junior researchers who use category-theoretic ideas or techniques in their work, and to provide a forum to learn about important themes in contemporary category theory, from experts and from each other.

Edinburgh at dusk

Posted at 9:26 PM UTC | Permalink | Followups (1)

Random Permutations (Part 2)

Posted by John Baez

Here’s a somewhat harder pair of problems on random permutations, with beautiful answers.

Posted at 2:43 AM UTC | Permalink | Followups (33)

Random Permutations (Part 1)

Posted by John Baez

I’m going to solve some problems on random permutations in my combinatorics class, to illustrate some of the ideas on species and generating functions, but also to bring in some ideas from complex analysis.

In all these problems we choose permutations randomly from S nS_n, with each permutation having probability 1/n!1/n! of being chosen.

I’ll start with one that’s easy, given the stuff I’ve already explained in class.

Posted at 1:39 AM UTC | Permalink | Followups (4)

November 23, 2019

The Golomb-Dickman Constant

Posted by John Baez

I’m falling in love with random permutations. There’s something both simple and fairly deep about them. I like to visualize a random permutation as a “gas of cycles”, governed by the laws of statistical mechanics. I haven’t gotten very with this analogy yet. But I’m learning a lot of fun stuff.

Posted at 12:11 AM UTC | Permalink | Followups (7)

November 19, 2019

Chair in Pure Mathematics at Sheffield

Posted by Simon Willerton

Here at the University of Sheffield we are advertising a Professorship in Pure Mathematics. The application deadline is 12 January 2020.

The research in pure maths is clustered around Topology, Number Theory, and Algebra and Geometry. People with interests allied to those of the Café are strongly encouraged to apply!

Please don’t hesitate to contact Sarah Whitehouse or me if you have any questions or would like to chat informally about this position.

Posted at 12:51 PM UTC | Permalink | Post a Comment

November 18, 2019

Total Maps of Turing Categories

Posted by John Baez

guest post by Adam Ó Conghaile and Diego Roque

We continue the 2019 Applied Category Theory School with a discussion of the paper Total maps of Turing categories by Cockett, Hofstra and Hrubeš. Thank you to Jonathan Gallagher for all the great help in teaching our group, to Pieter Hofstra for suggesting and coordinating the project and to Daniel Cicala and Jules Hedges for running this seminar.

Posted at 10:42 PM UTC | Permalink | Followups (6)

November 16, 2019

Geodesic Spheres and Gram Matrices

Posted by Tom Leinster

This is a short weekend diversion, containing nothing profound.

Any sphere in n\mathbb{R}^n can be given the geodesic metric, where the distance between two points is defined to be the length of the arc of a great circle between them. It’s not a big surprise that the same is true in any real inner product space XX: for instance, the unit sphere S(X)S(X) centred at the origin can be given a geodesic metric in a natural way. This defines a functor

S:IPSMS S: \mathbf{IPS} \to \mathbf{MS}

from inner product spaces to metric spaces, where in both cases the maps are not-necessarily-surjective isometries.

What’s more interesting is that it’s not quite as straightforward to prove as you might imagine. One way to do it leads into the topic of Gram matrices, as I’ll explain.

Posted at 11:12 PM UTC | Permalink | Followups (18)

November 15, 2019

Doubles for Monoidal Categories

Posted by John Baez

guest post by Fosco Loregian and Bryce Clarke

This post belongs to the series of the Applied Category Theory Adjoint School 2019 posts. It is the result of the work of the group “Profunctor optics” led by Bartosz Milewski, and constitutes a theoretical preliminary to the real meat, i.e. the discussion of Riley’s paper Categories of Optics by Mario Roman and Emily Pillmore (hi guys! We did our best to open you the way!)

In the following post, we first introduce you to the language of co/ends. Then we deconstruct this paper by Pastro and Street:

Our goal is to make its main result (almost) straightforward: Tambara modules can be characterized as particular profunctors, precisely those that interact well with a monoidal action on their domain. For a fixed category XX, these endoprofunctors form the Kleisli category of a monad on Prof(X,X)Prof(X,X).

Posted at 4:59 PM UTC | Permalink | Followups (3)