Thursday, September 27, 2012

Counting permutations: an open question

Nati Linial is giving a talk in Lille. As I am typing, he is stating an elegant combinatorial result and open problem, that I had never seen before.

One dimension ({0,1} n*n matrix with exactly one 1 per row or column): The number of permutations satisfies Stirling's formula: it's [(1+o(1)(n/e)]^n

Two dimensions ({0,1} n*n*n matrix with exactly one 1 per row, column or shaft): The number of Latin squares, as seen from Van Lint and Wilson's book, is [(1+o(1))(n/e^2)]^{n^2}.

Conjecture: in d dimensions, it's [(1+o(1))(n/e^d)]^{n^d}

Linial and Zur Luria proved the "less than or equal to" side. The "greater than or equal to" is still open.

2 comments:

  1. Is there some natural heuristic that suggests why this should be the correct bound?

    ReplyDelete
    Replies
    1. To answer my own question, I guess one way of thinking about it is as follows.

      Fix one direction, and place one 1 uniformly and independently at random on each of the n^d parallel lines in that direction. For each of the dn^d lines not in the fixed direction, there's an approximately 1/e chance that the line contains exactly one 1 (the limiting distribution is Poisson with mean 1).

      These events aren't independent for different lines, but they should me "nearly" independent in some sense (placing one 1 on one line doesn't have too much impact on the possible locations of 1's on other lines). So you might expect the probability every line contains exactly one 1 to be roughly e^{-d n^d}.

      Delete