Michael Lugo

I am a fifth-year graduate student in Mathematics at the University of Pennsylvania. My mathematical interests are in combinatorics and probability. My advisor is Robin Pemantle.

Research:

I do research in combinatorics and probability, with a focus on the structures of large random objects.

Papers: [1] Profiles of permutations, Electronic Journal of Combinatorics 16 (2009) #R99. (23 pages).

Abstract: This paper develops an analogy between the cycle structure of, on the one hand, random permutations with cycle lengths restricted to lie in an infinite set S with asymptotic density σ and, on the other hand, permutations selected according to the Ewens distribution with parameter σ In particular we show that the asymptotic expected number of cycles of random permutations of [n] with all cycles even, with all cycles odd, and chosen from the Ewens distribution with parameter 1/2 are all (1/2) log n + O(1), and the variance is of the same order. Furthermore, we show that in permutations of [n] chosen from the Ewens distribution with parameter σ, the probability of a random element being in a cycle longer than γn approaches (1-γ)σ for large n. The same limit law holds for permutations with cycles carrying multiplicative weights with average σ. We draw parallels between the Ewens distribution and the asymptotic-density case and explain why these parallels should exist using permutations drawn from weighted Boltzmann distributions.

[2] The number of cycles of specified normalized length in permutations, preprint, arXiv:0909.2909. (15 pages)

Abstract: We compute the limiting distribution, as n approaches infinity, of the number of cycles of length between γ n and δ n in a permutation of [n] chosen uniformly at random, for constants γ, δ such that 1/(k+1) ≤ γ < δ ≤ 1/k for some integer k. This distribution is supported on {0, 1, ... k} and has 0th, 1st, ..., kth moments equal to those of a Poisson distribution with parameter log (δ/γ). For more general choices of γ, δ we show that such a limiting distribution exists, which can be given explicitly in terms of certain integrals over intersections of hypercubes with half-spaces; these integrals are analytically intractable but a recurrence specifying them can be given. The results herein provide a basis of comparison for similar statistics on restricted classes of permutations.

[3] Cycle structure of compositions of random involutions, preprint, arXiv:0911.3604, 17 pages.

Abstract:: In this article we consider the cycle structure of compositions of pairs of involutions in the symmetric group Sn chosen uniformly at random. These can be modeled as modified 2-regular graphs, giving rise to exponential generating functions. A composition of two random involutions in Sn typically has about n1/2 cycles, and the cycles are characteristically of length n1/2. Compositions of two random fixed-point-free involutions, on the other hand, typically have about log n cycles and are closely related to permutations with all cycle lengths even. 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. This study is motivated by the observation that the number of involutions in [n] is n!1/2 times a subexponential factor; more generally the number of permutations with all cycle lengths in a finite set S is n!1-1/m times a subexponential factor, and the typical number of k-cycles is nearly nk/m/k. Connections to pattern avoidance in involutions are also considered.

Slides for a talk on this material, 28 October 2009 in the UPenn Graduate Student Combinatorics Seminar.

All this material (and much more!) can be found in my PhD thesis, Profiles of large combinatorial structures.

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 Sn typically has about n1/2 cycles, characteristically of length n1/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 pM(n) in which all part multiplicities lie in some fixed set n, and explore when that asymptotic form satisfies log pM(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.

I attend the Combinatorics and Probability Seminar.

In the summer of 2007 I worked in the quantum random walks research group organized by Robin Pemantle.

Teaching:

Job materials:

I am currently looking for a job. You can download my AMS cover sheet, CV, research statement, and teaching statement.

Coursework:

In the Spring 2008 term I took:

• Math 581, Topics in Combinatorics, taught by Marko Petkovsek.
• Math 530, Mathematics of Finance, taught by Jonathan Block.
• CIS 502, Analysis of Algorithms, taught by Sudipto Guha.

In the Fall 2007 term I took:

In the Spring 2007 term I took:

Before this I took some other classes which I have not listed.

Things I've written:

I keep a mathematical blog called God Plays Dice.

Here are some slides for my Pizza Seminar talk on December 5, entitled "Recounting The Rationals". Contact information:

I can be reached by e-mail at mlugo at math dot upenn dot edu. This is generally the best way to reach me.

If you want to send me something by ordinary mail, please send it to:
Michael Lugo
Department of Mathematics
209 South 33rd Street