Skip to content
Register Sign in Wishlist

The Surprising Mathematics of Longest Increasing Subsequences

Award Winner

Part of Institute of Mathematical Statistics Textbooks

  • Author: Dan Romik, University of California, Davis
  • Date Published: February 2015
  • availability: Available
  • format: Paperback
  • isbn: 9781107428829

Paperback

Add to wishlist

Other available formats:
Hardback, eBook


Looking for an inspection copy?

Please email academicmarketing@cambridge.edu.au to enquire about an inspection copy of this book

Description
Product filter button
Description
Contents
Resources
Courses
About the Authors
  • In a surprising sequence of developments, the longest increasing subsequence problem, originally mentioned as merely a curious example in a 1961 paper, has proven to have deep connections to many seemingly unrelated branches of mathematics, such as random permutations, random matrices, Young tableaux, and the corner growth model. The detailed and playful study of these connections makes this book suitable as a starting point for a wider exploration of elegant mathematical ideas that are of interest to every mathematician and to many computer scientists, physicists and statisticians. The specific topics covered are the Vershik-Kerov–Logan-Shepp limit shape theorem, the Baik–Deift–Johansson theorem, the Tracy–Widom distribution, and the corner growth process. This exciting body of work, encompassing important advances in probability and combinatorics over the last forty years, is made accessible to a general graduate-level audience for the first time in a highly polished presentation.

    • Includes detailed proofs of all key results
    • Contains many exercises of varying levels of difficulty
    • Covers important subject matter from cutting-edge research
    Read more

    Awards

    • A Choice Outstanding Academic Title 2015

    Reviews & 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 of Jerusalem

    '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

    '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.' 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

    'Timely, authoritative, and unique in its coverage …' D. V. Feldman, Choice

    See more reviews

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity

    ×

    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?

    ×

    Product details

    • Date Published: February 2015
    • format: Paperback
    • isbn: 9781107428829
    • length: 363 pages
    • dimensions: 227 x 152 x 20 mm
    • weight: 0.52kg
    • contains: 3 b/w illus. 94 exercises
    • availability: Available
  • Table of Contents

    1. Longest increasing subsequences in random permutations
    2. The Baik–Deift–Johansson theorem
    3. Erdős–Szekeres permutations and square Young tableaux
    4. The corner growth process: limit shapes
    5. The corner growth process: distributional results
    Appendix: Kingman's subadditive ergodic theorem.

  • Author

    Dan Romik, University of California, Davis
    Dan Romik is Professor of Mathematics at the University of California, Davis.

    Awards

    • A Choice Outstanding Academic Title 2015

Related Books

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email lecturers@cambridge.org

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner www.ebooks.com. Please see the permission section of the www.ebooks.com catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×
warning icon

Turn stock notifications on?

You must be signed in to your Cambridge account to turn product stock notifications on or off.

Sign in Create a Cambridge account arrow icon
×

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

Are you sure you want to delete your account?

This cannot be undone.

Cancel

Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

×
Please fill in the required fields in your feedback submission.
×