Combinatorics: The Rota Way

Last updated

Combinatorics: The Rota Way is a mathematics textbook on algebraic combinatorics, based on the lectures and lecture notes of Gian-Carlo Rota in his courses at the Massachusetts Institute of Technology. It was put into book form by Joseph P. S. Kung and Catherine Yan, two of Rota's students, [1] [2] and published in 2009 by the Cambridge University Press in their Cambridge Mathematical Library book series, listing Kung, Rota, and Yan as its authors (ten years posthumously in the case of Rota). [3] The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries. [4]

Contents

Topics

Combinatorics: The Rota Way has six chapters, densely packed with material: [5] each could be "a basis for a course at the Ph.D. level". [6] Chapter 1, "Sets, functions and relations", also includes material on partially ordered sets, lattice orders, entropy (formulated in terms of partitions of a set), and probability. [1] [3] [6] The topics in Chapter 2, "Matching theory", as well as matchings in graphs, include incidence matrices, submodular set functions, independent matchings in matroids, the Birkhoff–von Neumann theorem on the Birkhoff polytope of Doubly stochastic matrices, and the Gale–Ryser theorem on tomography of (0,1) matrices. [1] [3] Chapter 3 returns to partially ordered sets and lattices, including material on Möbius functions of incidence algebras, Sperner's theorem on antichains in power sets, special classes of lattices, valuation rings, and Dilworth's theorem on partitions into chains. [1]

One of the things Rota became known for, in the 1970s, was the revival of the umbral calculus as a general technique for the formal manipulation of power series and generating functions, [3] and this is the subject of Chapter 4. Other topics in this chapter include Sheffer sequences of polynomials, and the Riemann zeta function and its combinatorial interpretation. [1] [6] Chapter 5 concerns symmetric functions and Rota–Baxter algebras, including symmetric functions over finite fields. [1] Chapter 6, "Determinants, matrices, and polynomials", concludes the book with material including the roots of polynomials, the Grace–Walsh–Szegő theorem, the spectra of totally positive matrices, and invariant theory formulated in terms of the umbral calculus. [1] [6]

Each chapter concludes with a discussion of the history of the problems it covers, and pointers to the literature on these problems. Also included at the end of the book are solutions to some of the "exercises" provided at the ends of each chapter, [1] each of which could be (and often is) the basis of a research publication, [6] and which connect the material from the chapters to some of its applications. [5]

Audience and reception

Combinatorics: The Rota Way is too advanced for undergraduates, but could be used as the basis for one or more graduate-level mathematics courses. [6] However, even as a practicing mathematician in combinatorics, reviewer Jennifer Quinn found the book difficult going, despite the many topics of interest to her that it covered. She writes that she found herself "unsatisfied as a reader", "bogged down in technical details", and missing a unified picture of combinatorics as Rota saw it, [7] even though a unified picture of combinatorics was exactly what Rota often pushed for in his own research. [3] [5] Quinn nevertheless commends the book as "a fine reference" for some beautiful mathematics. [7]

Like Quinn, John Mount complains that parts of the book are unmotivated and lacking in examples and applications, "like a compressed Bourbaki treatment of discrete mathematics". He also writes that some of the exercises, such as one asking for a reproof of the Robertson–Seymour theorem on graph minors (without a guide to its original proof, which extended over a series of approximately 20 papers) are "needlessly cruel". However, he recommends Combinatorics: The Rota Way to students and researchers who have already seen the topics it presents, as a second source "for an alternate and powerful treatment of the topic". [5] Alessandro Di Bucchianico also writes that he is "not entirely positive" about the book, complaining about its "endless rows of definitions, statements, and proofs" without a connecting thread or motivation. He concludes that, although it is a good book for finding a clear description of Rota's favorite pieces of mathematics and their proofs, it is missing the enthusiasm and sense of unity that Rota himself brought to the subject. [2]

On the other hand, Michael Berg reviews the book more positively, calling its writing "crisp and elegant", its exercises deep, "important and fascinating", its historical asides "fun", and the overall book "simply too good to pass up". [4]

Related Research Articles

Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics and from evolutionary biology to computer science.

In mathematics before the 1970s, the term umbral calculus referred to the surprising similarity between seemingly unrelated polynomial equations and certain "shadowy" techniques used to "prove" them. These techniques were introduced by John Blissard and are sometimes called Blissard's symbolic method. They are often attributed to Édouard Lucas, who used the technique extensively.

Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures.

Garrett Birkhoff American mathematician (1911–1996)

Garrett Birkhoff was an American mathematician. He is best known for his work in lattice theory.

The Birkhoff polytopeBn is the convex polytope in RN whose points are the doubly stochastic matrices, i.e., the n × n matrices whose entries are non-negative real numbers and whose rows and columns each add up to 1. It is named after Garrett Birkhoff.

Algebraic combinatorics Area of combinatorics

Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. The theorem can be interpreted as providing a one-to-one correspondence between distributive lattices and partial orders, between quasi-ordinal knowledge spaces and preorders, or between finite topological spaces and preorders. It is named after Garrett Birkhoff, who published a proof of it in 1937.

The mathematical field of combinatorics was studied to varying degrees in numerous ancient societies. Its study in Europe dates to the work of Leonardo Fibonacci in the 13th century AD, which introduced Arabian and Indian ideas to the continent. It has continued to be studied in the modern era.

Norman Linstead Biggs is a leading British mathematician focusing on discrete mathematics and in particular algebraic combinatorics.

Leonid Mirsky was a Russian-British mathematician who worked in number theory, linear algebra, and combinatorics. Mirsky's theorem is named after him.

Analytic Combinatorics is a book on the mathematics of combinatorial enumeration, using generating functions and complex analysis to understand the growth rates of the numbers of combinatorial objects. It was written by Philippe Flajolet and Robert Sedgewick, and published by the Cambridge University Press in 2009. It won the Leroy P. Steele Prize in 2019.

Catherine Huafei Yan is a professor of mathematics at Texas A&M University interested in algebraic combinatorics.

Hazel Perfect was a British mathematician specialising in combinatorics.

Henry Crapo (mathematician) American-Canadian mathematician (1932–2019)

Henry Howland Crapo was an American-Canadian mathematician who worked in algebraic combinatorics. Over the course of his career, he held positions at several universities and research institutes in Canada and France. He is noted for his work in matroid theory and lattice theory.

<i>Computing the Continuous Discretely</i>

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra is an undergraduate-level textbook in geometry, on the interplay between the volume of convex polytopes and the number of lattice points they contain. It was written by Matthias Beck and Sinai Robins, and published in 2007 by Springer-Verlag in their Undergraduate Texts in Mathematics series. A second edition was published in 2015, and a German translation of the first edition by Kord Eickmeyer, Das Kontinuum diskret berechnen, was published by Springer in 2008.

Algebra and Tiling: Homomorphisms in the Service of Geometry is a mathematics textbook on the use of group theory to answer questions about tessellations and higher dimensional honeycombs, partitions of the Euclidean plane or higher-dimensional spaces into congruent tiles. It was written by Sherman K. Stein and Sándor Szabó, and published by the Mathematical Association of America as volume 25 of their Carus Mathematical Monographs series in 1994. It won the 1998 Beckenbach Book Prize, and was reprinted in paperback in 2008.

<i>The Mathematics of Chip-Firing</i>

The Mathematics of Chip-Firing is a textbook in mathematics on chip-firing games and abelian sandpile models. It was written by Caroline Klivans, and published in 2018 by the CRC Press.

Introduction to Lattices and Order is a mathematical textbook on order theory by Brian A. Davey and Hilary Priestley. It was published by the Cambridge University Press in their Cambridge Mathematical Textbooks series in 1990, with a second edition in 2002. The second edition is significantly different in its topics and organization, and was revised to incorporate recent developments in the area, especially in its applications to computer science. The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries.

Independence Theory in Combinatorics: An Introductory Account with Applications to Graphs and Transversals is an undergraduate-level mathematics textbook on the theory of matroids. It was written by Victor Bryant and Hazel Perfect, and published in 1980 by Chapman & Hall.

References

  1. 1 2 3 4 5 6 7 8 Tomescu, Ioan, zbMATH , Zbl   1159.05002 {{citation}}: CS1 maint: untitled periodical (link)
  2. 1 2 Di Bucchianico, Alessandro (2011), "Boekbesprekingen" (PDF), Nieuw Archief voor Wiskunde (in Dutch), 5 (12): 148
  3. 1 2 3 4 5 Biggs, Norman (April 2011), Bulletin of the London Mathematical Society , 43 (3): 613–614, doi:10.1112/blms/bdr016 {{citation}}: CS1 maint: untitled periodical (link)
  4. 1 2 Berg, Michael (April 2009), "Review", MAA Reviews, Mathematical Association of America
  5. 1 2 3 4 Mount, John (June 2010), "Review", ACM SIGACT News , 41 (2): 14, doi:10.1145/1814370.1814374, S2CID   33869826
  6. 1 2 3 4 5 6 Ferrari, Luca (2011), MathSciNet , MR   2483561 {{citation}}: CS1 maint: untitled periodical (link)
  7. 1 2 Quinn, Jennifer J. (2012), American Mathematical Monthly , 119 (6): 530, doi:10.4169/amer.math.monthly.119.06.530, JSTOR   10.4169/amer.math.monthly.119.06.530, S2CID   218549555 {{citation}}: CS1 maint: untitled periodical (link)
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.