Browse

Fibonacci and Lucas sequences are “two shining stars in the vast array of integer sequences,” and because of their ubiquitousness, tendency to appear in quite unexpected and unrelated places, abundant applications, and intriguing properties, they have fascinated amateurs and mathematicians alike. However, Catalan numbers are even more fascinating. Like the North Star in the evening sky, they are a beautiful and bright light in the mathematical heavens. They continue to provide a fertile ground for number theorists, especially, Catalan enthusiasts and computer scientists. Since the publication of Euler's triangulation problem (1751) and Catalan's parenthesization problem (1838), over 400 articles and problems on Catalan numbers have appeared in various periodicals. As Martin Gardner noted, even though many amateurs and mathematicians may know the abc's of Catalan sequence, they may not be familiar with their myriad unexpected occurrences, delightful applications, properties, or the beautiful and surprising relationships among numerous examples. Like Fibonacci and Lucas numbers, Catalan numbers are also an excellent source of fun and excitement. They can be used to generate interesting dividends for students, such as intellectual curiosity, experimentation, pattern recognition, conjecturing, and problem-solving techniques. The central character in the nth Catalan number is the central binomial coefficient. So, Catalan numbers can be extracted from Pascal's triangle. In fact, there are a number of ways they can be read from Pascal's triangle; every one of them is described and exemplified. This brings Catalan numbers a step closer to number-theory enthusiasts, especially.

The history of mathematics is a well-studied and vibrant area of research, with books and scholarly articles published on various aspects of the subject. Yet, the history of combinatorics seems to have been largely overlooked. This book goes some way to redress this and serves two main purposes: it constitutes the first book-length survey of the history of combinatorics, and it assembles, for the first time in a single source, researches on the history of combinatorics that would otherwise be inaccessible to the general reader. Individual chapters have been contributed by sixteen experts. The book opens with an introduction to two thousand years of combinatorics. This is followed by seven chapters on early combinatorics, leading from Indian and Chinese writings on permutations to late-Renaissance publications on the arithmetical triangle. The next seven chapters trace the subsequent story, from Euler’s contributions to such wide-ranging topics as partitions, polyhedra, and latin squares to the 20th-century advances in combinatorial set theory, enumeration, and graph theory. The book concludes with some combinatorial reflections.

This book begins with the resolution of a major open question about the local structure of Bruhat-Tits buildings. It then puts forward an algebraic solution into a geometric context by developing a general fixed point theory for groups acting on buildings of arbitrary type, giving necessary and sufficient conditions for the residues fixed by a group to form a kind of subbuilding or “form” of the original building. At the center of this theory is the notion of a Tits index, a combinatorial version of the notion of an index in the relative theory of algebraic groups. These results are combined at the end to show that every exceptional Bruhat-Tits building arises as a form of a “residually pseudo-split” building. The book concludes with a display of the Tits indices associated with each of these exceptional forms. This is the third and final volume of a trilogy that began with The Structure of Spherical Buildings and The Structure of Affine Buildings.

During the early part of the last century, F. G. Frobenius raised, in his lectures, the following problem (called the Diophantine Frobenius Problem FP): given relatively prime positive integers a1, . . . , an, find the largest natural number (called the Frobenius number and denoted by g(a1, . . . , an)) that is not representable as a nonnegative integer combination of a1, . . . , an. It turned out that the knowledge of g(a1, . . . , an) has been extremely useful to investigate many different problems. A number of methods, from several areas of mathematics, have been used in the hope of finding a formula giving the Frobenius number and algorithms to calculate it. The main intention of this book is to highlight such ‘methods, ideas, viewpoints, and applications’ for as wide an audience as possible. This book aims to provide a comprehensive exposition of what is known today on FP.

John Milnor, best known for his work in differential topology, K-theory, and dynamical systems, is one of only three mathematicians to have won the Fields medal, the Abel prize, and the Wolf prize, and is the only one to have received all three of the Leroy P. Steele prizes. In honor of his eightieth birthday, this book gathers together surveys and papers inspired by Milnor's work, from distinguished experts examining not only holomorphic dynamics in one and several variables, but also differential geometry, entropy theory, and combinatorial group theory. The book contains the last paper written by William Thurston, as well as a short paper by John Milnor himself. Introductory sections put the papers in mathematical and historical perspective, color figures are included, and an index facilitates browsing.

Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing together the highlights of the theory and its many applications. It looks at areas such as graph reconstruction, products, fractional and circular colourings, and constraint satisfaction problems, and has applications in complexity theory, artificial intelligence, telecommunications, and statistical physics. It has a wide focus on algebraic, combinatorial, and algorithmic aspects of graph homomorphisms. A reference list and historical summaries extend the material explicitly discussed. The book contains exercises of varying difficulty. Hints or references are provided for the more difficult exercises.

This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially explosive (NP-hard) discrete problems is a vividly developing field, with a growing list of applications in various contexts such as network analysis or bioinformatics. The book emphasizes algorithmic techniques over computational complexity theory. It is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essentials of parameterized hardness theory with a focus on W[1]-hardness which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology.

Weyl group multiple Dirichlet series are generalizations of the Riemann zeta function. Like the Riemann zeta function, they are Dirichlet series with analytic continuation and functional equations, having applications to analytic number theory. By contrast, these Weyl group multiple Dirichlet series may be functions of several complex variables and their groups of functional equations may be arbitrary finite Weyl groups. Furthermore, their coefficients are multiplicative up to roots of unity, generalizing the notion of Euler products. This book proves foundational results about these series and develops their combinatorics. These interesting functions may be described as Whittaker coefficients of Eisenstein series on metaplectic groups, but this characterization doesn't readily lead to an explicit description of the coefficients. The coefficients may be expressed as sums over Kashiwara's crystals, which are combinatorial analogs of characters of irreducible representations of Lie groups. For Cartan Type A, there are two distinguished descriptions, and if these are known to be equal, the analytic properties of the Dirichlet series follow. Proving the equality of the two combinatorial definitions of the Weyl group multiple Dirichlet series requires the comparison of two sums of products of Gauss sums over lattice points in polytopes. Through a series of surprising combinatorial reductions, this is accomplished. The book includes expository material about crystals, deformations of the Weyl character formula, and the Yang–Baxter equation.