Part of Lecture Notes in Logic
Not yet published - available from June 2021
FORMAT: Hardback ISBN: 9781107042841
Constraint Satisfaction Problems (CSPs) are natural computational problems that appear in many areas of theoretical computer science. Exploring which CSPs are solvable in polynomial time and which are NP-hard reveals a surprising link with central questions in universal algebra. This monograph presents a self-contained introduction to the universal-algebraic approach to complexity classification, treating both finite and infinite-domain CSPs. It includes the required background from logic and combinatorics, particularly model theory and Ramsey theory, and explains the recently discovered link between Ramsey theory and topological dynamics and its implications for CSPs. The book will be of interest to graduate students and researchers in theoretical computer science and to mathematicians in logic, combinatorics, and dynamics who wish to learn about the applications of their work in complexity theory.
The first monograph on complexity classification of constraint satisfaction problems
More than 150 examples illustrate the abstract results in concrete applications in mathematics and computer science
Self-contained and accessible to graduate students in theoretical computer science and mathematics
1. Introduction to constraint satisfaction problems
2. Model theory
3. Primitive positive interpretations
4. Countably categorical structures
5. Examples
6. Universal algebra
7. Equality constraint satisfaction problems
8. Datalog
9. Topology
10. Oligomorphic clones
11. Ramsey theory
12. Temporal constraint satisfaction problems
13. Non-dichotomies
14. Conclusion and outlook
References
Index.
Part of London Mathematical Society Lecture Note Series
Not yet published - available from August 2021
FORMAT: Paperback
ISBN: 9781009018883
This volume contains nine survey articles based on plenary lectures given at the 28th British Combinatorial Conference, hosted online by Durham University in July 2021. This biennial conference is a well-established international event, attracting speakers from around the world. Written by some of the foremost researchers in the field, these surveys provide up-to-date overviews of several areas of contemporary interest in combinatorics. Topics discussed include maximal subgroups of finite simple groups, Hasse?Weil type theorems and relevant classes of polynomial functions, the partition complex, the graph isomorphism problem, and Borel combinatorics. Representing a snapshot of current developments in combinatorics, this book will be of interest to researchers and graduate students in mathematics and theoretical computer science.
Includes nine survey articles by world-leading researchers
Summarises recent developments on a variety of hot topics in combinatorics
Broadly accessible to mathematicians and theoretical computer scientists
1. The partition complex: an invitation to combinatorial commutative algebra Karim Adiprasito and Geva Yashfe
2. Hasse-Weil type theorems and relevant classes of polynomial functions Daniele Bartoli
3. Decomposing the edges of a graph into simpler structures Marthe Bonamy
4. Generating graphs randomly Catherine Greenhill
5. Recent advances on the graph isomorphism problem Martin Grohe and Daniel Neuen
6. Extremal aspects of graph and hypergraph decomposition problems Stefan Glock, Daniela Kuhn and Deryk Osthus
7. Borel combinatorics of locally finite graphs Oleg Pikhurko
8. Codes and designs in Johnson graphs with high symmetry Cheryl E. Praeger
9. Maximal subgroups of finite simple groups: classifications and applications Colva M. Roney-Dougal.
Part of Encyclopedia of Mathematics and its Applications
Not yet published - available from July 2021
FORMAT: HardbackISBN: 9781108835596
The wave equation, a classical partial differential equation, has been studied and applied since the eighteenth century. Solving it in the presence of an obstacle, the scatterer, can be achieved using a variety of techniques and has a multitude of applications. This book explains clearly the fundamental ideas of time-domain scattering, including in-depth discussions of separation of variables and integral equations. The author covers both theoretical and computational aspects, and describes applications coming from acoustics (sound waves), elastodynamics (waves in solids), electromagnetics (Maxwell's equations) and hydrodynamics (water waves). The detailed bibliography of papers and books from the last 100 years cement the position of this work as an essential reference on the topic for applied mathematicians, physicists and engineers.
Clear exposition of concepts and methods, making the theory accessible to readers interested in solving time-domain scattering problems
Covers applications in many physical domains, connected by common mathematics
A thorough literature review, from classical work to the present day, allowing readers to put their own work in proper context
1. Acoustics and the Wave Equation
2. Wavefunctions
3. Characteristics and Discontinuities
4. Initial-boundary Value Problems
5. Use of Laplace Transforms
6. Problems with Spherical Symmetry
7. Scattering by a Sphere
8. Scattering Frequencies and the Singularity Expansion Method
9. Integral Representations
10. Integral Equations
References
Citation Index
Index.
Part of Perspectives in Logic
Not yet published - available from July 2021
FORMAT: Hardback
ISBN: 9781108423298
DescriptionContentsResourcesCoursesAbout the Authors
In mathematics, we know there are some concepts - objects, constructions, structures, proofs - that are more complex and difficult to describe than others. Computable structure theory quantifies and studies the complexity of mathematical structures, structures such as graphs, groups, and orderings. Written by a contemporary expert in the subject, this is the first full monograph on computable structure theory in 20 years. Aimed at graduate students and researchers in mathematical logic, it brings new results of the author together with many older results that were previously scattered across the literature and presents them all in a coherent framework, making it easier for the reader to learn the main results and techniques in the area for application in their own research. This volume focuses on countable structures whose complexity can be measured within arithmetic; a forthcoming second volume will study structures beyond arithmetic.
Makes the subject accessible to graduate students and researchers in logic, from the basic concepts to the frontiers of current research
Presents the main results and techniques in computable structure theory together in a coherent framework for the first time in 20 years
Includes new work of the author as well as new perspectives on older results.
1. Structures
2. Relations
3. Existentially-Atomic Models
4. Generic Presentations
5. Degree Spectra
6. Comparing Structures and Classes of Structures
7. Finite-Injury Constructions
8. Computable Categoricity
9. The Jump of a Structure
10. ‡”-Small Classes
Bibliography
Index.
Part of New Mathematical Monographs
Not yet published - available from September 2021
FORMAT: HardbackISBN: 9781107163157
DescriptionContentsResourcesCoursesAbout the Authors
Factorization algebras are local-to-global objects that play a role in classical and quantum field theory that is similar to the role of sheaves in geometry: they conveniently organize complicated information. Their local structure encompasses examples like associative and vertex algebras; in these examples, their global structure encompasses Hochschild homology and conformal blocks. In this second volume, the authors show how factorization algebras arise from interacting field theories, both classical and quantum, and how they encode essential information such as operator product expansions, Noether currents, and anomalies. Along with a systematic reworking of the Batalin?Vilkovisky formalism via derived geometry and factorization algebras, this book offers concrete examples from physics, ranging from angular momentum and Virasoro symmetries to a five-dimensional gauge theory.
Systematically develops the local-to-global structure of observables of a quantum field theory
Examines several different examples: scalar field theories, holomorphic field theories, current algebras, and topological field theories
Revisits and generalizes Noether's theorem as a statement about factorization algebras, including a quantized version of the theorem
1. Introduction and overview
Part I. Classical Field Theory:
2. Introduction to classical field theory
3. Elliptic moduli problems
4. The classical Batalin?Vilkovisky formalism
5. The observables of a classical field theory
Part II. Quantum Field Theory:
6. Introduction to quantum field theory
7. Effective field theories and Batalin?Vilkovisky quantization
8. The observables of a quantum field theory
9. Further aspects of quantum observables
10. Operator product expansions, with examples
Part III. A Factorization Enhancement of Noether's Theorem:
11. Introduction to Noether's theorems
12. Noether's theorem in classical field theory
13. Noether's theorem in quantum field theory
14. Examples of the Noether theorems
Appendix A. Background
Appendix B. Functions on spaces of sections
Appendix C. A formal Darboux lemma
References
Index.
Part of Cambridge Mathematical Textbooks
Not yet published - available from November 2021
FORMAT: Hardback
ISBN: 9781108476546
DescriptionContentsResourcesCoursesAbout the Authors
Active student engagement is key to this classroom-tested combinatorics text, boasting 1200+ carefully designed problems, ten mini-projects, section warm-up problems, and chapter opening problems. The author ? an award-winning teacher ? writes in a conversational style, keeping the reader in mind on every page. Students will stay motivated through glimpses into current research trends and open problems as well as the history and global origins of the subject. All essential topics are covered, including Ramsey theory, enumerative combinatorics including Stirling numbers, partitions of integers, the inclusion-exclusion principle, generating functions, introductory graph theory, and partially ordered sets. Some significant results are presented as sets of guided problems, leading readers to discover them on their own. More than 140 problems have complete solutions and over 250 have hints in the back, making this book ideal for self-study. Ideal for a one semester upper undergraduate course, prerequisites include the calculus sequence and familiarity with proofs.
Promotes discovery, active learning and collaboration with ten mini-projects, warm-up problems in every section, thought-provoking opening chapter problems, and a conversational tone
Allows students to work their way up to the most difficult combinatorics exercises by splitting them up into several smaller problems or addressing a single problem with many steps
Helps students work out the 1200+ problems and familiarize themselves with well-written solutions by including 256 hints, 181 short answers and 142 complete solutions in the back of the book
Includes 'Open Problems and Conjectures' sections that invite the students to explore cutting-edge research in the field
Emphasizes the global origins of combinatorics with historical asides and alternative naming of some familiar mathematical objects
Serves as a text for a one-semester upper-undergraduate course
Preface
Introduction
1. Induction and Recurrence Relations
2. The Pigeonhole Principle and Ramsey Theory
3. Counting, Probability, Balls and Boxes
4. Permutations and Combinations
5. Binomial and Multinomial Coefficients
6. Stirling Numbers
7. Integer Partitions
8. The Inclusion-Exclusion Principle
9. Generating Functions
10. Graph Theory
11. Posets, Matchings, and Boolean Lattices
Appendices
Bibliography
Index.
Part of London Mathematical Society Student Texts
Not yet published - available from October 2021
FORMAT: Hardback ISBN: 9781108843942
FORMAT: Paperback ISBN: 9781108925860
DescriptionContentsResourcesCoursesAbout the Authors
Everyone knows what braids are, whether they be made of hair, knitting wool, or electrical cables. However, it is not so evident that we can construct a theory about them, i.e. to elaborate a coherent and mathematically interesting corpus of results concerning them. This book demonstrates that there is a resoundingly positive response to this question: braids are fascinating objects, with a variety of rich mathematical properties and potential applications. A special emphasis is placed on the algorithmic aspects and on what can be called the 'calculus of braids', in particular the problem of isotopy. Prerequisites are kept to a minimum, with most results being established from scratch. An appendix at the end of each chapter gives a detailed introduction to the more advanced notions required, including monoids and group presentations. Also included is a range of carefully selected exercises to help the reader test their knowledge, with solutions available.
Contains exercises for practice, with solutions available
Explains algorithms in detail, providing pseudo code so readers can experiment themselves
Aims to be as self-contained as possible, explaining results from scratch and discussing background material in the appendices
1. Geometric braids
2. Braid groups
3. Braid monoids
4. The greedy normal form
5. The Artin representation
6. Handle reduction
7. The Dynnikov coordinates
8. A few avenues of investigation
9. Solutions to the exercises
Glossary
References
Index.
Part of Cambridge Monographs on Applied and Computational Mathematics
Not yet published - available from October 2021
FORMAT: Hardback
ISBN: 9781316519103
DescriptionContentsResourcesCoursesAbout the Authors
Structured population models are transport-type equations often applied to describe evolution of heterogeneous populations of biological cells, animals or humans, including phenomena such as crowd dynamics or pedestrian flows. This book introduces the mathematical underpinnings of these applications, providing a comprehensive analytical framework for structured population models in spaces of Radon measures. The unified approach allows for the study of transport processes on structures that are not vector spaces (such as traffic flow on graphs) and enables the analysis of the numerical algorithms used in applications. Presenting a coherent account of over a decade of research in the area, the text includes appendices outlining the necessary background material and discusses current trends in the theory, enabling graduate students to jump quickly into research.
Includes appendices providing any necessary background material and collects results from various fields in one place
Covers results concerning the functional analytic properties of spaces of measures, previously scattered over many papers using different notations
Presents current trends and problems in the theory, allowing young researchers to jump quickly into research
Notation
Introduction
1. Analytical setting
2. Structured population models on state space R+
3. Structured population models on proper spaces
4. Numerical methods for structured population models
5. Recent developments and future perspectives
Appendix A. Topology, compactness and proper spaces
Appendix B. Functional analysis
Appendix C. Bounded Lipschitz and Holder functions
Appendix D. Results on approximation with polynomials
Appendix E. Differential geometry
Appendix F. Measure theory
Appendix G. Weaker topologies on spaces of measures
Appendix H. The Bochner integral
Appendix I. Semigroups
Appendix J. Supplement to Chapter 2
Appendix K. Technical proofs from Chapter 3
References
Index.