Search

This volume contains nine survey articles by the invited speakers of the 30th British Combinatorial Conference, held at Queen Mary University of London in July 2024. Each article provides an overview of recent developments in a current hot research topic in combinatorics. Topics covered include: Latin squares, Erdős covering systems, finite field models, sublinear expanders, cluster expansion, the slice rank polynomial method, and oriented trees and paths in digraphs. The authors are among the world's foremost researchers on their respective topics but their surveys are accessible to nonspecialist readers: they are written clearly with little prior knowledge assumed and with pointers to the wider literature. Taken together these surveys give a snapshot of the research frontier in contemporary combinatorics, helping researchers and graduate students in mathematics and theoretical computer science to keep abreast of the latest developments in the field.

This book endeavors to deepen our understanding of lattice path combinatorics, explore key types of special sequences, elucidate their interconnections, and concurrently champion the author's interpretation of the “combinatorial spirit”.The author intends to give an up-to-date introduction to the theory of lattice path combinatorics, its relation to those special counting sequences important in modern combinatorial studies, such as the Catalan, Schröder, Motzkin, Delannoy numbers, and their generalized versions. Brief discussions of applications of lattice path combinatorics to symmetric functions and connections to the theory of tableaux are also included. Meanwhile, the author also presents an interpretation of the'combinatorial spirit'(i.e.,'counting without counting', bijective proofs, and understanding combinatorics from combinatorial structures internally, and more), hoping to shape the development of contemporary combinatorics.Lattice Path Combinatorics and Special Counting Sequences: From an Enumerative Perspective will appeal to graduate students and advanced undergraduates studying combinatorics, discrete mathematics, or computer science.

View the abstract.

In their preface, the editors describe algebraic combinatorics as the area of combinatorics concerned with exact, as opposed to approximate, results and which puts emphasis on interaction with other areas of mathematics, such as algebra, topology, geometry, and physics. It is a vibrant area, which saw several major developments in recent years. The goal of the 2022 conference Open Problems in Algebraic Combinatorics 2022 was to provide a forum for exchanging promising new directions and ideas. The current volume includes contributions coming from the talks at the conference, as well as a few other contributions written specifically for this volume. The articles cover the majority of topics in algebraic combinatorics with the aim of presenting recent important research results and also important open problems and conjectures encountered in this research. The editors hope that this book will facilitate the exchange of ideas in algebraic combinatorics.

The original goal of writing this book was to introduce the reader to the tools of combinatorics from an applied point of view. This third edition of Applied Combinatorics was substantially rewritten. There are many new examples and exercises. References throughout the book to modern literature and real applications, a key feature of the book, have been updated and expanded. The exposition continues to be updated with each new edition, as the first edition was published 40 years ago.The emphasis on applications from computer science, genetics, experimental design, chemistry, scheduling, voting, and other topics remains a central feature of the book. Unique to the literature is that entire sections focus on applications such as switching functions, the use of enzymes to uncover unknown RNA chains, searching and sorting problems of information retrieval, construction of error-correcting codes, counting of chemical compounds, calculation of power in voting situations, and uses of Fibonacci numbers. There are entire sections on applications of recurrences involving convolutions, applications of eulerian chains, and applications of generating functions.The book continues to be based on the authors'philosophy that the best way to learn mathematics is through problem solving. Combinatorics can be a wonderful mechanism for introducing students to proofs. However, the book is not designed for an introduction to proofs course. The authors treat proofs as rather informal, and many of the harder proofs in the book are optional.Applied Combinatorics, Third Edition is divided into four parts. The first part introduces the basic tools of combinatorics and their applications. The remaining three parts are organized around the three basic problems of combinatorics: the counting problem, the existence problem, and the optimization problem.Most of the book is written for a first course on the topic at the undergraduate level. On the other hand, at a fast pace, there is more than enough material for a challenging graduate course. This book first appeared when courses on combinatorics were rare. We are pleased to think that, through its use, the book has helped to establish a key course in many colleges and universities throughout the world. We hope that this new edition will remain a valuable tool for instructors and students alike

Divided into twelve chapters, this volume is an introduction to Graph Theory and Combinatorics and their Applications. It presents its content in a simple way, and contains a wide variety of applications to real world Science and Engineering problems. Definitions and theories are discussed with the help of examples. At the end of each chapter, a revision section is included, which incorporates multiple choice questions and will be highly useful for students undergoing competitive exams.

Detailed review of optimization from first principles, supported by rigorous math and computer science explanations and various learning aids Supported by rigorous math and computer science foundations, Combinatorial and Algorithmic Mathematics: From Foundation to Optimization provides a from-scratch understanding to the field of optimization, discussing 70 algorithms with roughly 220 illustrative examples, 160 nontrivial end-of-chapter exercises with complete solutions to ensure readers can apply appropriate theories, principles, and concepts when required, and Matlab codes that solve some specific problems. This book helps readers to develop mathematical maturity, including skills such as handling increasingly abstract ideas, recognizing mathematical patterns, and generalizing from specific examples to broad concepts. Starting from first principles of mathematical logic, set-theoretic structures, and analytic and algebraic structures, this book covers both combinatorics and algorithms in separate sections, then brings the material together in a final section on optimization. This book focuses on topics essential for anyone wanting to develop and apply their understanding of optimization to areas such as data structures, algorithms, artificial intelligence, machine learning, data science, computer systems, networks, and computer security. Combinatorial and Algorithmic Mathematics includes discussion on: Propositional logic and predicate logic, set-theoretic structures such as sets, relations, and functions, and basic analytic and algebraic structures such as sequences, series, subspaces, convex structures, and polyhedraRecurrence-solving techniques, counting methods, permutations, combinations, arrangements of objects and sets, and graph basics and propertiesAsymptotic notations, techniques for analyzing algorithms, and computational complexity of various algorithmsLinear optimization and its geometry and duality, simplex and non-simplex algorithms for linear optimization, second-order cone programming, and semidefinite programming Combinatorial and Algorithmic Mathematics is an ideal textbook resource on the subject for students studying discrete structures, combinatorics, algorithms, and optimization. It also caters to scientists across diverse disciplines that incorporate algorithms and academics and researchers who wish to better understand some modern optimization methodologies.

View the abstract.

One-Cocycles and Knot Invariants is about classical knots, i.e., smooth oriented knots in 3-space. It introduces discrete combinatorial analysis in knot theory in order to solve a global tetrahedron equation. This new technique is then used to construct combinatorial 1-cocycles in a certain moduli space of knot diagrams. The construction of the moduli space makes use of the meridian and the longitude of the knot. The combinatorial 1-cocycles are therefore lifts of the well-known Conway polynomial of knots, and they can be calculated in polynomial time. The 1-cocycles can distinguish loops consisting of knot diagrams in the moduli space up to homology. They give knot invariants when they are evaluated on canonical loops in the connected components of the moduli space. They are a first candidate for numerical knot invariants which can perhaps distinguish the orientation of knots.

View the abstract.

The monograph is dedicated to exploring combinatorial point configurations derived from mapping a set of combinatorial configurations into Euclidean space. Various methods for this mapping, along with the typology and properties of the resultant configurations, are presented. In addition, the study revolves around combinatorial polytopes defined as convex hulls of combinatorial point configurations. The primary focus lies in examining multipermutation and partial multipermutation point configurations alongside their associated combinatorial polytopes known as multipermutohedra and partial multipermutohedra. Our theoretical contributions are substantiated through the proof of theorems and supporting auxiliary statements. Examples and illustrations are included to enhance the comprehension of the material.

This book gives a lively development of the mathematics needed to answer the question, “How many times should a deck of cards be shuffled to mix it up?” The shuffles studied are the usual ones that real people use: riffle, overhand, and smooshing cards around on the table. The mathematics ranges from probability (Markov chains) to combinatorics (symmetric function theory) to algebra (Hopf algebras). There are applications to magic tricks and gambling along with a careful comparison of the mathematics to the results of real people shuffling real cards. The book explores links between shuffling and higher mathematics—Lie theory, algebraic topology, the geometry of hyperplane arrangements, stochastic calculus, number theory, and more. It offers a useful springboard for seeing how probability theory is applied and leads to many corners of advanced mathematics. The book can serve as a text for an upper division course in mathematics, statistics, or computer science departments and will be appreciated by graduate students and researchers in mathematics, statistics, and computer science, as well as magicians and people with a strong background in mathematics who are interested in games that use playing cards.

This book offers a gentle introduction to Hex, the classic board game created by Piet Hein and popularized by John Nash and Martin Gardner. The first three chapters cover rules, basic strategy, and history. The remaining eight chapters cover a variety of topics: mathematical properties (there are no draws, the first player can win, the acute corner is a losing first move), the related game of Y, winning strategies for small boards, how computers play Hex, and analysis of Random-Move Hex (where one or both players move randomly) and Dark Hex (the imperfect information version of the game, where you can't see your opponent's moves). Did we mention puzzles? There are puzzles in every chapter, with solutions. This book is intended for anyone interested in playing board games or learning some recreational mathematics. It is written for a wide audience and will be enjoyed equally by general readers and professional mathematicians. The book could be used as a textbook or companion resource for a topics course on recreational mathematics or game theory or as a source for undergraduate research questions.

View the abstract.

This book discusses the origin of graph theory from its humble beginnings in recreational mathematics to its modern setting or modeling communication networks, as is evidenced by the World Wide Web graph used by many Internet search engines. The second edition of the book includes recent developments in the theory of signed adjacency matrices involving the proof of sensitivity conjecture and the theory of Ramanujan graphs. In addition, the book discusses topics such as Pick's theorem on areas of lattice polygons and Graham–Pollak's work on addressing of graphs. The concept of graph is fundamental in mathematics and engineering, as it conveniently encodes diverse relations and facilitates combinatorial analysis of many theoretical and practical problems. The text is ideal for a one-semester course at the advanced undergraduate level or beginning graduate level.

This book uses finite field theory as a hook to introduce the reader to a range of ideas from algebra and number theory. It constructs all finite fields from scratch and shows that they are unique up to isomorphism. As a payoff, several combinatorial applications of finite fields are given: Sidon sets and perfect difference sets, de Bruijn sequences and a magic trick of Persi Diaconis, and the polynomial time algorithm for primality testing due to Agrawal, Kayal and Saxena. The book forms the basis for a one term intensive course with students meeting weekly for multiple lectures and a discussion session. Readers can expect to develop familiarity with ideas in algebra (groups, rings and fields), and elementary number theory, which would help with later classes where these are developed in greater detail. And they will enjoy seeing the AKS primality test application tying together the many disparate topics from the book. The pre-requisites for reading this book are minimal: familiarity with proof writing, some linear algebra, and one variable calculus is assumed. This book is aimed at incoming undergraduate students with a strong interest in mathematics or computer science.

Elwyn Berlekamp, John Conway, and Richard Guy wrote ‘Winning Ways for your Mathematical Plays'and turned a recreational mathematics topic into a full mathematical fi eld. They combined set theory, combinatorics, codes, algorithms, and a smattering of other fi elds, leavened with a liberal dose of humor and wit. Their legacy is a lively fi eld of study that still produces many surprises. Despite being experts in other areas of mathematics, in the 50 years since its publication, they also mentored, talked, and played games, giving their time, expertise, and guidance to several generations of mathematicians. This volume is dedicated to Elwyn Berlekamp, John Conway, and Richard Guy. It includes 20 contributions from colleagues that refl ect on their work in combinatorial game theory.

The ever-growing applications and richness of approaches to the Riordan group is captured in this comprehensive monograph, authored by those who are among the founders and foremost world experts in this field. The concept of a Riordan array has played a unifying role in enumerative combinatorics over the last three decades. The Riordan arrays and Riordan group is a new growth point in mathematics that is both being influenced by, and continuing its contributions to, other fields such as Lie groups, elliptic curves, orthogonal polynomials, spline functions, networks, sequences and series, Beal conjecture, Riemann hypothesis, to name several. In recent years the Riordan group has made links to quantum field theory and has become a useful tool for computer science and computational chemistry. We can look forward to discovering further applications to unexpected areas of research. Providing a baseline and springboard to further developments and study, this book may also serve asa text for anyone interested in discrete mathematics, including combinatorics, number theory, matrix theory, graph theory, and algebra.

Over a career that spanned 60 years, Ronald L. Graham (known to all as Ron) made significant contributions to the fields of discrete mathematics, number theory, Ramsey theory, computational geometry, juggling and magical mathematics, and many more. Ron also was a mentor to generations of mathematicians, he gave countless talks and helped bring mathematics to a wider audience, and he held signifi cant leadership roles in the mathematical community. This volume is dedicated to the life and memory of Ron Graham, and includes 20-articles by leading scientists across a broad range of subjects that refl ect some of the many areas in which Ron worked.

View the abstract.

Since the publication of the first edition of this monograph, a generalisation of the Assmus-Mattson theorem for linear codes over finite fields has been developed, two 70-year breakthroughs and a considerable amount of other progress on t-designs from linear codes have been made. This second edition is a substantial revision and expansion of the first edition. Two new chapters and two new appendices have been added, and most chapters of the first edition have been revised.It provides a well-rounded and detailed account of t-designs from linear codes. Most chapters of this book cover the support designs of linear codes. A few chapters deal with designs obtained from linear codes in other ways. Connections among ovals, hyperovals, maximal arcs, ovoids, special functions, linear codes and designs are also investigated. This book consists of both classical and recent results on designs from linear codes.It is intended to be a reference for postgraduates and researchers who work on combinatorics, or coding theory, or digital communications, or finite geometry. It can also be used as a textbook for postgraduates in these subject areas.Related Link(s)

Automatic sequences are sequences over a finite alphabet generated by a finite-state machine. This book presents a novel viewpoint on automatic sequences, and more generally on combinatorics on words, by introducing a decision method through which many new results in combinatorics and number theory can be automatically proved or disproved with little or no human intervention. This approach to proving theorems is extremely powerful, allowing long and error-prone case-based arguments to be replaced by simple computations. Readers will learn how to phrase their desired results in first-order logic, using free software to automate the computation process. Results that normally require multipage proofs can emerge in milliseconds, allowing users to engage with mathematical questions that would otherwise be difficult to solve. With more than 150 exercises included, this text is an ideal resource for researchers, graduate students, and advanced undergraduates studying combinatorics, sequences, and number theory.

View the abstract.

View the abstract.

The interplay between combinatorics and theoretical physics is a recent trend which appears to us as particularly natural, since the unfolding of new ideas in physics is often tied to the development of combinatorial methods, and, conversely, problems in combinatorics have been successfully tackled using methods inspired by theoretical physics. We can thus speak nowadays of an emerging domain of Combinatorial Physics. The interference between these two disciplines is moreover an interference of multiple facets. Its best known manifestation (both to combinatorialists and theoretical physicists) has so far been the one between combinatorics and statistical physics, as statistical physics relies on an accurate counting of the various states or configurations of a physical system. But combinatorics and theoretical physics interact in various other ways. This book is mainly dedicated to the interactions of combinatorics (algebraic, enumerative, analytic) with (commutative and non-commutative) quantum field theory and tensor models, the latter being seen as a quantum field theoretical generalisation of matrix models.

This book is about the combinatorial properties of convex sets, families of convex sets in finite dimensional Euclidean spaces, and finite points sets related to convexity. This area is classic, with theorems of Helly, Carathéodory, and Radon that go back more than a hundred years. At the same time, it is a modern and active field of research with recent results like Tverberg's theorem, the colourful versions of Helly and Carathéodory, and the $(p, q)$ theorem of Alon and Kleitman. As the title indicates, the topic is convexity and geometry, and is close to discrete mathematics. The questions considered are frequently of a combinatorial nature, and the proofs use ideas from geometry and are often combined with graph and hypergraph theory. The book is intended for students (graduate and undergraduate alike), but postdocs and research mathematicians will also find it useful. It can be used as a textbook with short chapters, each suitable for a one- or two-hour lecture. Not much background is needed: basic linear algebra and elements of (hyper)graph theory as well as some mathematical maturity should suffice. This is an elegant, well written, concise treatment of an attractive and active subject, written by an expert who has made important contributions to the area himself. I am sure this will be a successful textbook. —Noga Alon, Princeton University and Tel Aviv University I think this book is a gem. —János Pach, Rényi Institute of Mathematics, Budapest

Combinatorial Nullstellensatz is a novel theorem in algebra introduced by Noga Alon to tackle combinatorial problems in diverse areas of mathematics. This book focuses on the applications of this theorem to graph colouring. A key step in the applications of Combinatorial Nullstellensatz is to show that the coefficient of a certain monomial in the expansion of a polynomial is nonzero. The major part of the book concentrates on three methods for calculating the coefficients: Alon-Tarsi orientation: The task is to show that a graph has an orientation with given maximum out-degree and for which the number of even Eulerian sub-digraphs is different from the number of odd Eulerian sub-digraphs. In particular, this method is used to show that a graph whose edge set decomposes into a Hamilton cycle and vertex-disjoint triangles is 3-choosable, and that every planar graph has a matching whose deletion results in a 4-choosable graph. Interpolation formula for the coefficient: This method is in particular used to show that toroidal grids of even order are 3-choosable, r-edge colourable r-regular planar graphs are r-edge choosable, and complete graphs of order p+1, where p is a prime, are p-edge choosable. Coefficients as the permanents of matrices: This method is in particular used in the study of the list version of vertex-edge weighting and to show that every graph is (2,3)-choosable. It is suited as a reference book for a graduate course in mathematics.

Algebraic combinatorics is the study of combinatorial objects as an extension of the study of finite permutation groups, or, in other words, group theory without groups. In the spirit of Delsarte's theory, this book studies combinatorial objects such as graphs, codes, designs, etc. in the general framework of association schemes, providing a comprehensive overview of the theory as well as pointing out to extensions.

This book addresses recent developments in sign patterns for generalized inverses. The fundamental importance of the fields is obvious, since they are related with qualitative analysis of linear systems and combinatorial matrix theory. The book provides both introductory materials and discussions to the areas in sign patterns for Moore–Penrose inverse, Drazin inverse and tensors. It is intended to convey results to the senior students and readers in pure and applied linear algebra, and combinatorial matrix theory.

Erdős asked how many distinct distances must there be in a set of $n$ points in the plane. Falconer asked a continuous analogue, essentially asking what is the minimal Hausdorff dimension required of a compact set in order to guarantee that the set of distinct distances has positive Lebesgue measure in $R$. The finite field distance problem poses the analogous question in a vector space over a finite field. The problem is relatively new but remains tantalizingly out of reach. This book provides an accessible, exciting summary of known results. The tools used range over combinatorics, number theory, analysis, and algebra. The intended audience is graduate students and advanced undergraduates interested in investigating the unknown dimensions of the problem. Results available until now only in the research literature are clearly explained and beautifully motivated. A concluding chapter opens up connections to related topics in combinatorics and number theory: incidence theory, sum-product phenomena, Waring's problem, and the Kakeya conjecture.

The main goal of our book is to provide easy access to the basic principles and methods that combinatorial calculations are based upon. The rule of product, the identity principle, recurrence relations and inclusion-exclusion principle are the most important of the above. Significant parts of the book are devoted to classical combinatorial structures, such as: ordering (permutations), tuples, and subsets (combinations). A great deal of attention is paid to the properties of binomial coefficients, and in particular, to model proofs of combinatorial identities. Problems concerning some exact combinatorial configurations such as paths in a square, polygonal chains constructed with chords of a circle, trees (undirected graphs with no cycles) etc. are included too. All chapters contain a considerable number of exercises of various complexity, from easy training tasks to complex problems which require decent persistence and skill from the one who dares to solve them. If one aims to passively familiarize oneself with the subject, methods and the most necessary facts of combinatorics, then it may suffice to limit one's study to the main text omitting the exercise part of the book. However, for those who want to immerse themselves in combinatorial problems and to gain skills of active research in that field, the exercise section is rather important. The authors hope that the book will be helpful for several categories of readers. University teachers and professors of mathematics may find somewhat unusual coverage of certain matters and exercises which can be readily applied in their professional work. We believe that certain series of problems may serve as a base for serious creative works and essays. This especially refers to students at pedagogical universities and colleges who need to prepare themselves to the teaching of the basics of combinatorics, mainly building on arithmetic and geometry. Most of the exercises of the book are of this very origin.