The Surprising Mathematics of Longest Increasing Subsequences

The Surprising Mathematics of Longest Increasing Subsequences was published by Cambridge University Press in 2015. The book is available for purchase or as a free download (PDF, 3.8MB):



Book errata (PDF, updated January 15, 2021)

Courses based on the book

Reviews and endorsements
  • "The story of longest monotone subsequences in permutations has been, for six decades, one of the most beautiful in mathematics, ranging from the very pure to the applied and featuring many terrific mathematicians, starting with Erdős-Szekeres's 'happy end theorem' and continuing through the Tracy-Widom distribution and the breakthrough of Baik-Deift-Johansson. With its connections to many areas of mathematics, to the Riemann hypothesis, and to high-energy physics we cannot foresee where the story is heading. Dan Romik tells the tale thus far - and teaches its rich multifaceted mathematics, a blend of probability, combinatorics, analysis, and algebra - in a wonderful way."

    -Gil Kalai, Hebrew University
  • "How long is the longest increasing subsequence in a random permutation? This innocent-looking combinatorial problem has surprisingly rich connections to diverse mathematical areas: Poisson processes and Last-passage percolation, growth processes and random matrices, Young diagrams and special functions … Its solution weaves together some highlights of nineteenth- and twentieth-century mathematics, yet continues to have growing impact in the twenty-first. Dan Romik's excellent book makes these exciting developments available to a much wider mathematical audience than ever before. The minimal prerequisites ensure that the reader will also encounter mathematical tools that have stood the test of time and can be applied to many other concrete problems. This is a wonderful story of the unity of mathematics, and Romik’s enthusiasm for it shines through."

    -Yuval Peres, Principal Researcher, Microsoft Research
  • "This is a marvelously readable book that coaches the reader toward an honest understanding of some of the deepest results of modern analytic combinatorics. It is written in a friendly but rigorous way, complete with exercises and historical sidebars. The central result is the famous Baik-Deift-Johansson theorem that determines the asymptotic distribution of the length of the longest increasing subsequence of a random permutation, but many delicious topics are covered along the way. Anyone who is interested in modern analytic combinatorics will want to study this book. The time invested will be well rewarded - both by enjoyment and by the acquisition of a powerful collection of analytical tools."

    -J. Michael Steele, University of Pennsylvania
  • "Mathematics books that concentrate on a problem, rather than on a technique or a subfield, are relatively rare but can be a wonderfully exciting way to dive into research. Here we have the felicitous combination of an extraordinarily fascinating and fruitful problem and a literate tour guide with a terrific eye for the best proof. More like a detective story than a text, this elegant volume shows how a single wise question can open whole new worlds."

    -Peter Winkler, Dartmouth College
  • "[...] the author did a great service to the community of specialists to by having written this book. It will be a great reference material [...]"

    -Miklós Bóna, University of Florida (read his full review on MAA Reviews)
  • "This is a very good book about one of the richest mathematical problems of the second half of the 20th century. [...] This book provides an enjoyable way for advanced graduate students and researchers to learn about the tools used in solving the longest increasing subsequence problem, and to understand the connections between different areas of mathematics. [...]"

    -Sergi Elizalde, Dartmouth College (read his full review on MathSciNet Mathematical Reviews)
  • "The author has written a wonderful book, both in terms of the subject matter covered as well as the style and presentation of the book. Inspite of choosing one question, on which to base an entire book on, the text is never boring and is a very important addition to the literature in analytic combinatorics. [...] The book as a whole, is a wonderful addition for the specialists as well as the motivated non-specialist. [...]"

    -Manjil Pratim Saikia (University of Vienna) (read his full review on zbMATH)