Johan Wästlund

Johan Wästlund

I'm a researcher at the Department of Mathematical Sciences, Chalmers University of Technology. My research interests, some of which are reflected in my list of publications, include discrete probability, game theory, and the foundations of mathematics.

Some relatively recent stuff

Rigorous computer analysis of the Chow-Robbins game (with Olle Häggström, to appear in The American Mathematical Monthly).

Replica symmetry of the minimum matching, Annals of Mathematics 175 (2012), 1061-1091.

Maharaja Nim, Wythoff's Queen meets the Knight (with Urban Larsson).

From heaps of matches to the limits of computability (with Urban Larsson).

Mean field matching and traveling salesman problems in pseudo-dimension 1 (with Giorgio Parisi).

Talks

On February 23 2012 I gave a talk in the workshop Bridging statistical physics and optimization, inference and learning in Les Houches, France.

On December 6, 2010, Donald Knuth gave his traditional Christmas Tree Lecture, this time about some of my work, explaining the curious appearance of the number pi in Stirling's approximation of n! and in the asymptotics of the Catalan numbers. The lecture was broadcast online (depriving me of a couple of hours of sleep), and is available under "Computer Musings" here.

Talk on Games, optimization and phase transitions in the workshop/school on Statistical physics of complexity, optimization and systems biology, Les Houches, March 7-12 2010.

Video of a talk at Microsoft Research, October 2009.

I gave a talk at the conference Physics of Algorithms, Santa Fe, New Mexico, August 31-September 4, 2009.

I gave talks at the CRM workshops on Combinatorics, Randomization, Algorithms and Probability and New directions in random spatial processes within the program on Challenges and Perspectives in Probability, Montreal, May 2009.

Invited talk at the conference Parisi 60, Wandering with Curiosity in Complex Landscapes. A scientific conference in honor of Giorgio Parisi for his 60th birthday, Rome, September 8-10, 2008.

Invited talk at the German Open Conference on Probability and Statistics, Aachen, March 4-7 2008.

Invited talk at the conference Common Concepts in Statistical Physics and Computer Science, ICTP, Trieste, Italy, July 2-6 2007.

Invited talk on Combinatorial optimization in the mean field model at the conference Fourth Colloquium on Mathematics and Computer Science, Algorithms, Trees, Combinatorics and Probabilities September 18-22, 2006, Institut Élie Cartan, Nancy, France.

Slides (in Swedish) from a talk given on May 10, 2007 about the Angel Problem.

Slides in English from a similar talk given in Göteborg May 22, 2007.

Presentation från populärvetenskaplig dag, Linköping, oktober 2007.

PhD students

Martin Hessler (PhD 2009, Optimization, Matroids and Error-Correcting Codes)

Ragnar Freij, (PhD 2012, Topics in algorithmic, enumerative and geometric combinatorics)

Urban Larsson (licentiate 2009, Sequences and games generalizing the combinatorial game of Wythoff Nim).

Some research papers

Optimization in random models

Replica symmetry of the minimum matching, Annals of Mathematics 175 (2012), 1061-1091.

Mean field matching and traveling salesman problems in pseudo-dimension 1 (with Giorgio Parisi).

Edge cover and polymatroid flow problems (with Martin Hessler), Electronic Journal of Probability 15 (2010), 2200-2219.

The blind passenger and the assignment problem, Combinatorics, Probability and Computing 20 (2011), 467-480.

Concentration of the cost of a random matching problem (with Martin Hessler).

The mean field traveling salesman and related problems, Acta Mathematica 204:1 (2010), 91-150.

An easy proof of the zeta(2) limit in the random assignment problem, Electronic Communications in Probability 14 (2009), 261-269.

Random matching problems on the complete graph, Electronic Communications in Probability 13 (2008), 258-265.

Random assignment and shortest path problems, Invited paper in Proceedings of the Fourth Colloquium on Mathematics and Computer Science, Algorithms, Trees, Combinatorics and Probabilities, September 18-22, 2006, Institut Élie Cartan, Nancy, France (DMTCS proc. AG, 2006, 31-38).

Addendum to ''The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph'' (with Svante Janson). Random Structures and Algorithms vol. 28 no. 4 (2006), 511-512.

A Proof of a Conjecture of Buck, Chan and Robbins on the Expected Value of the Minimum Assignment, Random Structures and Algorithms (26) 1-2 (2005), 237-251. There has been no transfer of copyright to Wiley Periodicals Inc., despite what is stated in the article. Feel free to distribute it anyway you like for commercial as well as educational purposes:)

A Proof of Parisi's conjecture on the random assignment problem (with S. Linusson), Probability Theory and Related Fields 128 (2004), 419-440.

Completing a (k-1)-Assignment Combinatorics, Probability and Computing, Volume 16, Issue 04, July 2007, pp 621-629. Despite what is claimed, Cambridge University Press cannot have full copyright to this publication since I as an author have never agreed to this.

Less official, partially overlapping with other publications

Replica Symmetry and Combinatorial Optimization.

Optimization in mean field models. Extended abstract related to my talk at ICTP in Trieste July 2, 2007.

The travelling salesman problem in the stochastic mean field model.

The Limit in the Mean Field Bipartite Travelling Salesman Problem.

The variance and higher moments in the random assignment problem, Linköping Studies in Mathematics No. 8 (2005). Rejected by Random Structures and Algorithms on the grounds that the publisher Wiley Periodicals Inc. claims exclusive copyright to published articles.

Evaluation of Janson's constant for the variance in the random minimum spanning tree problem, Linköping Studies in Mathematics No. 7 (2005). Rejected by Random Structures and Algorithms on the grounds that the publisher Wiley Periodicals Inc. claims exclusive copyright to published articles.

A simple proof of the Parisi and Coppersmith-Sorkin formulas for the random assignment problem, Linköping Studies in Mathematics No. 6 (2005).

Exact formulas and limits for a class of random optimization problems. Linköping Studies in Mathematics, No. 5 (2005).

A generalization of the random assignment problem (with S. Linusson). ArXiv:math.CO/0006146.

Other papers in discrete probability

Rigorous computer analysis of the Chow-Robbins game (with Olle Häggström).

The Phase Transition for Dyadic Tilings (with Omer Angel, Alexander Holroyd, Gady Kozma and Peter Winkler).

Partially ordered secretaries (with Ragnar Freij), Electronic Communications in Probability 15 (2010), 504-507.

When only the last one will do.

Combinatorics

Enumeration of derangements with descents in prescribed positions (with Niklas Eriksen and Ragnar Freij), The Electronic Journal of Combinatorics 16 (2009), #R32.

Dense packing of patterns in a permutation (with H. Eriksson, K. Eriksson and S. Linusson), FPSAC 2002, Melbourne, Australia. An updated version was published in Annals of Combinatorics, 11 (2007), 459-470.

Sorting a bridge hand (with H. Eriksson, K. Eriksson, J. Karlander and L. Svensson), Discrete Mathematics 241 (2001) 289-300.

Games

The strange algebra of combinatorial games.

A weaker winning angel.

Two-Person Symmetric Whist, The Electronic Journal of Combinatorics 12 (2005), #R44. See also Linköping Studies in Mathematics No. 4 (2005).

A Solution of Two-Person Single-Suit Whist, The Electronic Journal of Combinatorics 12 (2005), #R43. See also Linköping Studies in Mathematics No. 3 (2005) for some technical stuff that didn't make it into the official publication.

Geometry

Perfect packings of squares using the stack-pack strategy, Discrete and Computational Geometry 29: 625-631 (2003).

A smaller sleeping bag for a baby snake (with J. Håstad and S. Linusson), Discrete Comput Geom 26:173-181 (2001).

Partitions of R3 into curves (with Mattias Jonsson, from my PhD thesis), also published in Mathematica Scandinavica 83 (1998) 192-204.

Other

An elementary proof of Wallis' product formula for pi, The American Mathematical Monthly, December 2007. See also Linköping Studies in Mathematics No. 2 (2005).

Summing inverse squares by euclidean geometry.

Functions arising by coin flipping. An earlier version was included in my PhD thesis, but I was later informed that the main result had been obtained by M. S. Keane and G. L. O'Brien already in 1994. Anyway, since several people have asked me about this paper over the years, here it is.

Various other publications

I was pleased to discover that I have written a chapter in the book Biscuits of Number Theory.

Slump och sannolikheter. Avsnitt i boken Problemlösning är #1 av David Berglund.

Higher Order Throw-Ins, The Bridge World Online, November 2005.

Debattartikel om open access

Ta ställning för open access! Universitetsläraren 15, 2007.

Course on Random optimization problems

Fall 2008 I gave a course on Random Optimization Problems. These lecture notes are still being updated.

Coauthors

Omer Angel, Niklas Eriksen, Henrik Eriksson, Kimmo Eriksson, Ragnar Freij, Martin Hessler, Johan Håstad, Alexander Holroyd, Olle Häggström, Svante Janson, Mattias Jonsson, Johan Karlander, Gady Kozma, Urban Larsson, Giorgio Parisi, Lars Svensson, Peter Winkler.
Johan Wästlund