Discrete mathematics Books

Book SynopsisStarts with necessary information about matrices, algebras, and groups. This title then proceeds to representations of finite groups. It includes several chapters dealing with representations and characters of symmetric groups and the closely related theory of symmetric polynomials.Table of ContentsMatrices Algebras Groups The Frobenius algebra The symmetric group Immanants and $S$-functions $S$-functions of special series The calculation of the characters of the symmetric group Group characters and the structure of groups Continuous matrix groups and invariant matrices Groups of unitary matrices Appendix Bibliography Supplementary bibliography Index.

Read more less

Book SynopsisOne of the most active areas in mathematics is the topic of 'additive combinatorics'. This book brings together key researchers from different areas, sharing their insights in articles meant to inspire mathematicians coming from various backgrounds.Table of ContentsAn introduction to additive combinatorics by A. Granville Elementary additive combinatorics by J. Solymosi Many additive quadruples by A. Balog An old new proof of Roth's theorem by E. Szemeredi Bounds on exponential sums over small multiplicative subgroups by P. Kurlberg Montreal notes on quadratic Fourier analysis by B. Green Ergodic methods in additive combinatorics by B. Kra The ergodic and combinatorial approaches to Szemeredi's theorem by T. Tao Cardinality questions about sumsets by I. Z. Ruzsa Open problems in additive combinatorics by E. S. Croot III and V. F. Lev Some problems related to sum-product theorems by M.-C. Chang Lattice points on circles, squares in arithmetic progressions and sumsets of squares by J. Cilleruelo and A. Granville Problems in additive number theory. I by M. B. Nathanson Double and triple sums modulo a prime by K. Gyarmati, S. Konyagin, and I. Z. Ruzsa Additive properties of product sets in fields of prime order by A. A. Glibichuk and S. V. Konyagin Many sets have more sums than differences by G. Martin and K. O'Bryant Devenport's constant for groups of the form $\mathbb{Z}_3\oplus\mathbb{Z}_3\oplus\mathbb{Z}_{3d}$ by G. Browmik and J.-C. Schlage-Puchta Some combinatorial group invariants and their generalizations with weights by S. D. Adhikari, R. Balasubramanian, and P. Rath.

Read more less

Book SynopsisFocuses on integrable systems and symmetries presents new results on applications of symmetries and integrability techniques to the case of equations defined on the lattice. This relatively new field has many applications, for example, in describing the evolution of crystals and molecular systems defined on lattices.Table of Contents Introduction Integrability and symmetries of nonlinear differential and difference equations in two independent variables Symmetries as integrability criteria Construction of lattice equations and their Lax pair Transformation groups for quad lattice equations Algebraic entropy of the nonautonomous Boll equations Translation from Russian of R. I. Yamilov, ''On the classification of discrete eqautions'', reference [841] No quad-graph equation can have a generalized symmetry given by the narita-Itoh-Bogoyavlensky equation Bibliography Subject Index

Read more less

Book SynopsisContains a collection of mathematical applications of linear algebra, mainly in combinatorics, geometry, and algorithms. Each chapter covers a single main result with motivation and full proof, and assumes only a modest background in linear algebra. The topics include Hamming codes, the matrix-tree theorem, the Lovász bound on the Shannon capacity, and a counterexample to Borsuk's conjecture.Trade ReviewFinding examples of "linear algebra in action" that are both accessible and convincing is difficult. Thirty-three Miniatures is an attempt to present some usable examples. . . . For me, the biggest impact of the book came from noticing the tools that are used. Many linear algebra textbooks, including the one I use, delay discussion of inner products and transpose matrices till later in the course, which sometimes means they don't get discussed at all. Seeing how often the transpose matrix shows up in Matousek's miniatures made me realize space must be made for it. Similarly, the theorem relating the rank of the product of two matrices to the ranks of the factors plays a big role here. Most linear algebra instructors would benefit from this kind of insight. . . . Thirty-three Miniatures would be an excellent book for an informal seminar offered to students after their first linear algebra course. It may also be the germ of many interesting undergraduate talks. And it's fun as well." - Fernando Q. Gouvêa, MAA Reviews"[This book] is an excellent collection of clever applications of linear algebra to various areas of (primarily) discrete/combinatiorial mathematics. ... The style of exposition is very lively, with fairly standard usage of terminologies and notations. ... Highly recommended." - ChoiceTable of Contents Preface Notation Fibonacci numbers, quickly Fibonacci numbers, the formula The clubs of Oddtown Same-size intersections Error-correcting codes Odd distances Are these distances Euclidean? Packing complete bipartite graphs Equiangular lines Where is the triangle? Checking matrix multiplication Tiling a rectangle by squares Three Petersens are not enough Petersen, Hoffman–Singleton, and maybe 57 Only two distances Covering a cube minus one vertex Medium-size intersection is hard to avoid On the difficulty of reducing the diameter The end of the small coins Walking in the yard Counting spanning trees In how many ways can a man tile a board? More bricks—more walls? Perfect matchings and determinants Turning a ladder over a finite field Counting compositions Is it associative? The secret agent and umbrella Shannon capacity of the union: a tale of two fields Equilateral sets Cutting cheaply using eigenvectors Rotating the cube Set pairs and exterior products Index

Read more less

Book SynopsisTable of ContentsAutomated theorem proving: a quarter century review by D. W. Loveland Citation to Hao Wang Computer theorem proving and artificial intelligence by H. Wang Citation to Lawrence Wos and Steven Winker Open questions solved with the assistance of AURA by L. Wos and S. Winker Some automatic proofs in analysis by W. W. Bledsoe Proof-checking, theorem-proving, and program verification by R. S. Boyer and J. S. Moore A mechanical proof of the turing completeness of pure LISP by R. S. Boyer and J. S. Moore Automating higher-order logic by P. B. Andrews, D. A. Miller, E. L. Cohen, and F. Pfenning Abelian group unification algorithms for elementary terms by D. Lankford, G. Butler, and B. Brady Combining satisfiability procedures by equality sharing by G. Nelson On the decision problem and the mechanization of theorem-proving in elementary geometry by W. Wen-Tsun Some recent advances in mechanical theorem-proving of geometries by W. Wen-Tsun Proving elementary geometry theorems using Wu's algorithm by S.-C. Chou Automated theory formation in mathematics by D. B. Lenat Student use of an interactive theorem prover by J. McDonald and P. Suppes.

Read more less

Book SynopsisContains the proceedings of the first DIMACS workshop. This work covers topics including multicommodity flows, graph matchings and colorings, the traveling salesman problem, integer programming and complexity theory. It is suitable for researchers in combinatorics and combinatorial optimization.Table of ContentsMatrix cones, projection representations, and stable set polyhedra by L. Lovasz and A. Schrijver A generalization of Lovasz's $\theta$ function by G. Narasimhan and R. Manber On cutting planes and matrices by A. M. H. Gerards Random volumes in the $n$-cube by M. E. Dyer, A. Furedi, and C. McDiarmid Test sets for integer programs, $\forall \exists$ sentences by R. Kannan Solvable classes of generalized traveling salesman problems by S. N. Kabadi and R. Chandrasekaran Handles and teeth in the symmetric traveling salesman polytope by D. Naddef On the complexity of branch and cut methods for the traveling salesman problem by W. Cook and M. Hartmann Existentially polytime theorems by K. Cameron and J. Edmonds The width-length inequality and degenerate projective planes by A. Lehman On Lehman's width-length characterization by P. D. Seymour Applications of polyhedral combinatorics to multicommodity flows and compact surfaces by A. Schrijver Vertex-disjoint simple paths of given homotopy in a planar graph by A. Frank and A. Schrijver On disjoint homotopic paths in the plane by A. Frank On the complexity of the disjoint paths problem (extended abstract) by M. Middendorf and F. Pfeiffer The paths-selection problem by M. Middendorf and F. Pfeiffer Planar multicommodity flows, max cut, and the Chinese postman problem by F. Barahona The cographic multiflow problem: An epilogue by A. Sebo Exact edge-colorings of graphs without prescribed minors by O. Marcotte On the chromatic index of multigraphs and a conjecture of Seymour, (II) by O. Marcotte Spanning trees of different weights by A. Schrijver and P. D. Seymour.

Read more less

Book SynopsisTrade ReviewWritten by an eminent expert as the first monograph on this topic, this book can be recommended to anybody working on large networks and their applications in mathematics, computer science, social sciences, biology, statistical physics or chip design." - Zentralblatt Math"This is an amazing book: readable, deep, and lively. It sets out this emerging area, makes connections between old classical graph theory and graph limits, and charts the course of the future." - Persi Diaconis, Stanford University"It is always exciting when a mathematical theory turns out to be connected to a variety of other topics. This is the case with the recently developed subject of graph limits, which exhibits tight relations with a wide range of areas including statistical physics, analysis, algebra, extremal graph theory, and theoretical computer science. The book Large Networks and Graph Limits contains a comprehensive study of this active topic and an updated account of its present status. The author, Laszls Lovasz, initiated the subject, and together with his collaborators has contributed immensely to its development during the last decade. This is a beautiful volume written by an outstanding mathematician who is also an excellent expositor." - Noga Alon, Tel Aviv University, Israel"Modern combinatorics is by no means an isolated subject in mathematics, but has many rich and interesting connections to almost every area of mathematics and computer science. The research presented in Lovasz's book exemplifies this phenomenon by taking one of the most quintessentially combinatorial of objects--the finite graph--and through the process of taking limits of sequences of such graphs, reveals and clarifies connections to measure theory, analysis, statistical physics, metric geometry, spectral theory, property testing, algebraic geometry, and even Hilbert's tenth and seventeenth problems. Indeed, this book presents a wonderful opportunity for a student in combinatorics to explore other fields of mathematics, or conversely for experts in other areas of mathematics to become acquainted with some aspects of graph theory." - Terence Tao, University of California, Los Angeles, CA"László Lovász has written an admirable treatise on the exciting new theory of graph limits and graph homomorphisms, an area of great importance in the study of large networks. It is an authoritative, masterful text that reflects Lovász's position as the main architect of this rapidly developing theory. The book is a must for combinatorialists, network theorists, and theoretical computer scientists alike." - Bela Bollobas, Cambridge University, UKTable of Contents Preface Part 1. Large graphs: An informal introduction Very large networks Large graphs in mathematics and physics Part 2. The algebra of graph homomorphisms Notation and terminology Graph parameters and connection matrices Graph homomorphisms Graph algebras and homomorphism functions Part 3. Limits of dense graph sequences Kernels and graphons The cut distance Szemerédi partitions Sampling Convergence of dense graph sequences Convergence from the right On the structure of graphons The space of graphons Algorithms for large graphs and graphons Extremal theory of dense graphs Multigraphs and decorated graphs Part 4. Limits of bounded degree graphs Graphings Convergence of bounded degree graphs Right convergence of bounded degree graphs On the structure of graphings Algorithms for bounded degree graphs Part 5. Extensions: A brief survey Other combinatorial structures Appendix A Bibliography Author index Subject index Notation index

Read more less

Book SynopsisTrade ReviewThis is one among the beautiful books on the subject of difference sets that I came across in the field of mathematics and especially in combinatorics because of its lucid style and simplicity...The present book overviews these subjects if not exhaustively but impressively with required theorems sometimes with full proofs and sometimes with comprehensive explanations and required examples. By the study of this book, one gains an opportunity to further explore the subject with confidence in different angles enriching one's vision for further research with the orientation of applications in the real-life situations as the authors mention such lines as well...This book lays a good foundation for the study of difference sets together with the subjects related to it and prepares the students for further extensive research." - Ratnakaram Nava Mohan, Zentralblatt MATH"It is a welcome addition to all undergraduate libraries." - CHOICE"This book would seem tailor-made as a text for a senior seminar or capstone course. It is clearly written, emphasizes motivation, contains lots of examples, has a good bibliography and contains a respectable number of exercises at the end of each chapter. ... Reading this book taught me some nice mathematics that I didn't know before, and it did so in an interesting, enjoyable way." - MAA ReviewsTable of ContentsTable of Contents: Introduction Designs Automorphisms of designs Introducing difference sets Bruck-Ryser-Chowla theorem Multipliers Necessary group conditions Difference sets from geometry Families from Hadamard matrices Representation theory Group characters Using algebraic number theory Applications Background Notation Hints and solutions to selected exercises Bibliography Index Index of parameters

Read more less

Book SynopsisThoroughly revised, updated, expanded, and reorganized to serve as a primary text for mathematics courses, Introduction to Set Theory, Third Edition covers the basics: relations, functions, orderings, finite, countable, and uncountable sets, and cardinal and ordinal numbers. It also provides five additional self-contained chapters, consolidates the material on real numbers into a single updated chapter affording flexibility in course design, supplies end-of-section problems, with hints, of varying degrees of difficulty, includes new material on normal forms and Goodstein sequences, and adds important recent ideas including filters, ultrafilters, closed unbounded and stationary sets, and partitions.Trade Review"The book remains an excellent text for a senior undergraduate or first-year graduate level course. There is sufficient material for instructors of widely differing views to assemble one-semester courses. . ..the chapter on the axiom of choice is particularly strong. "---Mathematical Reviews ". . .a fine text. . ..The proofs are both elegant and readable. "---American Mathematical Monthly ". . .offers many benefits including. . .interesting applications of abstract set theory to real analysis. . .enriching standard classroom material. "---L'Enseignement mathematique ". . .an excellent and much needed book. . .Especially valuable are a number of remarks sprinkled throughout the text which afford a glimpse of further developments. "---The Mathematical Intelligencer "The authors show that set theory is powerful enough to serve as an underlying framework for mathematics by using it to develop the beginnings of the theory of natural, rational, and real numbers. "---Quarterly Review of Applied Mathematics ". . .In the third edition, Chapter 11 has been expanded, and four new chapters have been added. "---Mathematical ReviewsTable of ContentsSets; relations, functions and orderings; natural numbers; finite, countable and uncountable sets; cardinal numbers; ordinal numbers; alephs; the axiom of choice; arithmetic of cardinal numbers; sets of real numbers; filters and ultrafilters; combinatorial set theory; large cardinals; the axiom of foundation; the axiomatic set theory.

Read more less

Book SynopsisEmphasizing the creative nature of mathematics, this conversational textbook guides students through the process of discovering a proof as they transition to advanced mathematics. Using several strategies, students will develop the thinking skills needed to tackle mathematics when there is no clear algorithm or recipe to follow.Trade Review'Every student in the sciences should be exposed to the basic language of modern mathematics, and standard courses such as calculus or linear algebra do not play this role. The ideal textbook for such a course should not attempt to be encyclopedic and should not assume special prerequisites. It should cover a carefully chosen selection of topics efficiently, engagingly, thoroughly, without being overbearing. Fuchs' text fits this description admirably. The level is right, the math is rock solid, the writing is very pleasant. The book talks to the reader, without ever sounding patronizing. A vast selection of problems, many including solutions, will be splendidly helpful both in a classroom setting and for self-study.' Paolo Aluffi, Florida State University'This well-written text strikes a good balance between conciseness and clarity. Students are led from looking more deeply into familiar topics, such as the quadratic formula, to an understanding of the nature, structure, and methods of proof. The examples and problems are a strong point. I look forward to teaching from it.' Eric Gottlieb, Rhodes College'Fuchs' text is an excellent addition to the 'transitions to proof' literature. I will use it when I next teach such a course. Except for the excellent 'Additional Topics' sections, the content is standard, but the spiraling presentation and helpful narrative around proofs are what truly elevate this text. Fuchs has made every attempt to connect the structure and rigor of mathematics with the intuition of the student. For example, the notion of function arises in three different chapters, with two increasingly rigorous 'provisional definitions,' before a complete definition is given within a wider discussion of relations. I anticipate this approach resonating with students. Fuchs' Chapter 3, which introduces logic and proof strategies, is the most usable presentation of the material I have seen or used. The practice of mathematics and mathematical thinking is communicated well, while opportunities for confusion and obfuscation via a blizzard of symbols are minimized.' Ryan Grady, Montana State University'This book is a must-have resource for an undergraduate mathematics student or interested reader to learn the fundamental topics in how to prove things. The text is thorough and of top quality, yet it is conversational and easy to absorb. Maybe the most important quality, it offers advice about how to approach problems, making it perfect for an introduction to proofs class.' Andrew McEachern, York University, Canada'This is a great choice of textbook for any course introducing undergraduates to mathematical proofs. What makes this book stand out are the early chapters, as well as the 'Additional Topics,' both with accompanying exercises. The book begins by gently introducing proof-based thinking by posing well-motivated prompts and exercises concerning familiar arithmetic of real numbers and the integers. It then introduces fields as a playground to practice working with axioms and drawing (sometimes surprising) conclusions from them. The book proceeds with introducing formal logic, mathematical induction, set theory, and relations on sets. The book's design nicely enables framing classes around a choice sampling among the abundant exercises. The book's 'Additional Topics' can serve to engage those students with a brimming imagination and who are already familiar with basic notions of proofs.' David Ayala, Montana State University'Fuchs' Introduction to Proofs and Proof Strategies is an excellent textbook choice for an undergraduate proof-writing course. The author takes a friendly and conversational approach, giving many worked examples throughout each section. Furthermore, each section is replete with exercises for the reader, along with fully worked solutions at chapter's end. This is exactly the 'get your hands dirty' approach students and readers will benefit greatly from!' Frank Patane, Samford University'The book Introduction to Proofs and Proof Strategies by Shay Fuchs takes the problem-solving approach to the forefront by accompanying the reader in the construction and deconstruction of proofs through numerous examples and challenging exercises. The fundamental principles of mathematics are introduced in a creative and innovative way, making learning an enjoyable journey.' Roberto Bruni, Università di Pisa'This textbook is easy to read and designed to enhance students' problem-solving skills in their first year of university. The book really stands out due to the variety and quality of exercises at the end of each chapter. The latter chapters dive into more advanced topics for interested students.' Marina Tvalavadze, University of Toronto MississaugaTable of ContentsContents; Preface; Part I. Core Material; 1. Numbers, Quadratics and Inequalities; 2. Sets, Functions and the Field Axioms; 3. Informal Logic and Proof Strategies; 4. Mathematical Induction; 5. Bijections and Cardinality; 6. Integers and Divisibility; 7. Relations; Part II. Additional Topics; 8. Elementary Combinatorics; 9. Preview of Real Analysis – Limits and Continuity; 10. Complex Numbers; 11. Preview of Linear Algebra; Notes; References; Index.

Read more less

Book SynopsisRichard Stanley's two-volume basic introduction to enumerative combinatorics has become the standard guide to the topic for students and experts alike. This updated edition provides the only comprehensive high-level treatment of enumerative combinatorics, including the theory of symmetric functions, with over 150 new exercises and solutions.Trade Review'This is one of the great books; readable, deep and full of gems. It brings algebraic combinatorics to life. I teach out of it and feel that if I can get my students to 'touch Stanley' I have given them a gift for life.' Persi Diaconis, Stanford University'It is wonderful to celebrate the completion of the second edition of Richard Stanley's Enumerative Combinatorics, one of the finest mathematical works of all time. He has added nearly 200 exercises, together with their answers, to what was already a uniquely masterful summary of a vast and beautiful theory. When paired with the second edition of Volume 1, his two classic volumes will surely be a timeless treasure for generations to come.' Donald E. Knuth, Stanford University'An updated classic with a mesmerizing array of interconnected examples. Through Stanley's masterful exposition, the current and future generations of mathematicians will learn the inherent beauty and pleasures of enumeration.' June Huh, Princeton University'I have used Richard Stanley's books on Enumerative Combinatorics numerous times for the combinatorics classes I have taught. This new edition contains many new exercises, which will no doubt be extremely useful for the next generation of combinatorialists.' Anne Schilling, University of California, Davis'Richard Stanley's Enumerative Combinatorics, in two volumes, is an essential reference for researchers and graduate students in the field of enumeration. Volume 2, newly revised, includes comprehensive coverage of composition and inversion of generating functions, exponential and algebraic generating functions, and symmetric functions. The treatment of symmetric functions is especially noteworthy for its thoroughness and accessibility. Engaging problems and solutions, and detailed historical notes, add to the value of this book. It provides an excellent introduction to the subject for beginners while also offering advanced researchers new insights and perspectives.' Ira Gessel, Brandeis UniversityTable of ContentsPreface to Second Edition; Preface; 5. Trees and the Composition of Generating Functions; 6. Algebraic Generating Functions; 7. Symmetric Functions; Appendices: References; Index.

Read more less

Book SynopsisThis graduate level textbook covers classical and modern developments in graph theory and additive combinatorics, presenting arguments as a cohesive whole. Students will appreciate the chapter summaries, many figures and exercises, as well as the complementary set of lecture videos freely available through MIT OpenCourseWare.Trade Review'Yufei Zhao does great mathematics and has an uncanny ability to explain the deepest results with clear understandable prose. For anyone interested in the seminal ideas (and their interrelationships) of recent decades - pseudorandomness, graphons, graph regularity, to name a few - this is the book to read and savor.' Joel Spencer, New York University'This impeccable book should quickly become a classic text in discrete maths. A huge selection of topics is treated elegantly, with beautiful illustrations, and in just the `right' amount of detail to arouse the interest of the reader and leave them well placed to find out more. In particular, the second half of the book is a superb introduction to additive combinatorics, which I will happily recommend to any student in this area.' Ben Green, Oxford University'This charming text gives an accessible introduction to the connected topics of extremal graph theory and modern additive combinatorics. The focus is very strongly on presenting intuition and restricting attention to the simplest possible instances of methods or classes of results, rather than aiming for maximal generality or the strongest statements; instead, references are given for further reading, or for the proofs of important theorems that are only stated here. Being highly suitable for advanced undergraduates or beginning graduate students, it fills a niche that is currently not occupied by other texts in these highly active areas of current mathematical research.' Terry Tao, University of California, Los Angeles'A valuable and readable unified treatment of a fast-moving area of combinatorics from one of the world's experts - sure to become a standard resource.' Jordan Ellenberg, University of Wisconsin-Madison'Yufei Zhao's book is a wonderful book about graph theory, additive combinatorics, and their surprising connections, involving a major theme of modern mathematics: the interplay between structure and randomness. In both areas, the book can take the curious reader, whether an advanced undergraduate or a professional mathematician, on a joyous journey from the very basics to state-of-the-art research. Yufei Zhao himself is a major player in modern research in both these areas and his presentation is a tour de force.' Gil Kalai, Hebrew University of Jerusalem and Reichman University'This is a beautiful treatment of extremal graph theory and additive combinatorics, focusing on the fruitful interplay between the two. The book covers the classical results as well as recent developments in this active area. It is a fascinating manuscript that would appeal to students and researchers with an interest in discrete mathematics, theoretical computer number theory, and related areas.' Noga Alon, Princeton University'This is a wonderful, well-written account of additive combinatorics from the graph theoretic perspective. Zhao skillfully ties in this approach to the usual statements and gives a thorough development of the subject. This book is indispensable for any serious researcher in this area. Beginners will find a thorough account of the subject with plenty of motivation. The more experienced reader will appreciate the authors' insights and elegant development of some difficult ideas.' Andrew Granville, University of MontréalTable of ContentsPreface; Notation and Conventions; Appetizer: triangles and equations; 1. Forbidding a subgraph; 2. Graph regularity method; 3. Pseudorandom graphs; 4. Graph limits; 5. Graph homomorphism inequalities; 6. Forbidding 3-term arithmetic progressions; 7. Structure of set addition; 8. Sum-product problem; 9. Progressions in sparse pseudorandom sets; References; Index.

Read more less

Book SynopsisThis text provides the current state of knowledge on, arguably, one of the most attractive and mysterious mathematical objects: the Monster group. Some 20 experts here share their expertise in this exciting field. Ideal for researchers and graduate students working in Combinatorial Algebra, Group theory and related areas.Trade Review'Describing the Monster group mathematical structures is the culmination of decades of work. Just as the largest Mathieu group framed the 24-dimensional Leech lattice, so also that lattice is the foundation for constructing the Moonshine Module and the Monster algebra, through which the Monster has become central in a theory with deep connections to modern physics. The first part of the book is a collection of five papers on the Monster and other algebraic structures, presented by international leaders in the area providing an outsider with the necessary content and concepts. It presents an account of the current status of the theory and available computational tools for studying the Monster and its algebras. The machinery for developing Majorana theory and axial algebras underpinning the Monster is based on Algebraic Combinatorics, to which the second part of this collection is devoted.' Cheryl Praeger, Emeritus Professor, University of Western Australia''Monstrous Moonshine', an unexpected correspondence involving the largest sporadic simple group, the classical modular function, and conformal field theory, was one of the greatest discoveries of the twentieth century. The modern approach, pioneered by Alexander Ivanov, involves Majorana algebras; the theory is clearly explained here. Among other jewels in the book is a geometric discussion of the Freudenthal - Tits 'magic square', linking the exceptional Lie algebras with the real, complex, quaternion and octonion number fields.' Peter Cameron, University of St AndrewsTable of ContentsPart I. The Monster: 1. Lectures on vertex algebras Atsushi Matsuo; 2. 3-Transposition groups arising in vertex operator algebras Hiroshi Yamauchi; 3. On holomorphic vertex operator algebras of central charge 24 Ching Hung Lam; 4. Maximal 2-local subgroups of the Monster and Baby Monster Ulrich Meierfrankenfeld and Sergey Shpectorov; 5. The future of Majorana theory II Alexander A. Ivanov; Part II. Algebraic Combinatorics: 6. The geometry of Freudenthal-Tits magic square Hendrik Van Maldegham; 7. On generation of polar Grassmanisns Ilaria Cardinali, Lucca Giuzzi and Antonio Pasini; 8. Ovoidal maximal subspaces of polar spaces Antonio Pasini and Hendrik Van Maldegham; 9. On the behaviour of regular unipotent elements from subsystem subgroups of type A_n with special highest weights Tatsiana S. Busel and Irina D. Suprunenko; 10. Some remarks on the parameter c_2 for a distance-regular graph with classical parameters Jack H. Koolen, Jongyook Park and Qianqian Yang; 11. Distance-regular graphs, the subconstituent algebra, and the q-polynomial property Paul Terwilliger; 12. Terwilliger algebras and the Weisfeiler-Leman stabilization Tatsuro Ito; 13. Extended doubling of self-complementary strongly regular graphs and an analogue for digraphs Takuya Ikuta and Akihiro Munemasa; 14. Using GAP package for research in graph theory, design theory and finite geometries Leonard H. Soicher.

Read more less

Book Synopsis

Read more less

Book SynopsisIntended for first- or second-year graduate students in mathematics, as well as researchers working in algebraic geometry or combinatorics, this text introduces techniques that are essential in several areas of modern mathematics. With numerous exercises and examples, it covers the core notions and applications of equivariant cohomology.Trade Review'This book is a much-needed introduction to a powerful and central tool in algebraic geometry and related subjects. The authors are masters of clarity and rigor. The important theorems and examples are thoroughly explained, and illuminated with well-chosen exercises. This book is an essential companion for anyone wanting to understand group actions in algebraic geometry.' Ravi Vakil, Stanford University'Equivariant Cohomology is a tool from algebraic topology that becomes available when groups act on spaces. In Algebraic geometry, the groups are algebraic groups, including tori, and typical spaces are toric varieties and homogeneous varieties such as Grassmannians and flag varieties. This book introduces and studies equivariant cohomology (actually equivariant Chow groups) from the perspective of algebraic geometry, beginning with the artful replacement of Borel's classifying spaces by Totaro's finite-dimensional approximations. After developing the main properties of equivariant Chow groups, including localization and GKM theory, the authors investigate equivariant Chow groups of toric varieties and flag varieties, and the equivariant classes of Schubert varieties. Reflecting the interests of the authors, special attention is paid to Schubert calculus and the links between degeneracy loci and equivariant cohomology. The text also serves as an introduction to flag varieties, their Schubert varieties, and the calculus of Schubert classes in equivariant cohomology.' Frank Sottile, Texas A&M University'Equivariant Cohomology in Algebraic Geometry by David Anderson and William Fulton offers a comprehensive, accessible exploration of the development, standard examples, and recent contributions in this fascinating field. The authors have successfully struck a balance between rigor and approachability, making it an excellent resource for young researchers in the field. The book's real strength lies in its application to toric varieties and Schubert varieties across various settings, including Grassmannians, flag varieties, degeneracy loci, and extensions to other classical types and Kac–Moody groups. The authors' treatment of Bott-Samelson desingularizations of Schubert varieties is particularly noteworthy, displaying elegance and coherence within the context of the book's material. With over 450 pages of content, Equivariant Cohomology in Algebraic Geometry offers a comprehensive resource for researchers and scholars. It is poised to become a standard reference in the field, leaving a lasting impact on the flourishing area of research for years to come.' Sara Billey, University of WashingtonTable of Contents1. Preview; 2. Defining equivariant cohomology; 3. Basic properties; 4. Grassmannians and flag varieties; 5. Localization I; 6. Conics; 7. Localization II; 8. Toric varieties; 9. Schubert calculus on Grassmannians; 10. Flag varieties and Schubert polynomials; 11. Degeneracy loci; 12. Infinite-dimensional flag varieties; 13. Symplectic flag varieties; 14. Symplectic Schubert polynomials; 15. Homogeneous varieties; 16. The algebra of divided difference operators; 17. Equivariant homology; 18. Bott–_Samelson varieties and Schubert varieties; 19. Structure constants; A. Algebraic topology; B. Specialization in equivariant Borel–_Moore homology; C. Pfaffians and Q-polynomials; D. Conventions for Schubert varieties; E. Characteristic classes and equivariant cohomology; References; Notation index; Subject index.

Read more less

Book SynopsisThis concise and self-contained introduction builds up the spectral theory of graphs from scratch, including linear algebra and the theory of polynomials. Covering several types of graphs, it provides the mathematical foundation needed to understand and apply spectral insight to real-world communications systems and complex networks.Table of ContentsSymbols; 1. Introduction; Part I. Spectra of Graphs: 2. Algebraic graph theory; 3. Eigenvalues of the adjacency matrix; 4. Eigenvalues of the Laplacian Q; 5. Effective resistance matrix; 6. Spectra of special types of graphs; 7. Density function of the eigenvalues; 8. Spectra of complex networks; Part II. Eigensystem: 9. Topics in linear algebra; 10. Eigensystem of a matrix; Part III. Polynomials: 11. Polynomials with real coefficients; 12. Orthogonal polynomials; References; Index.

Read more less

Book SynopsisThe Traveling Salesman Problem (TSP) is a central topic in discrete mathematics and theoretical computer science. It has been one of the driving forces in combinatorial optimization. The design and analysis of better and better approximation algorithms for the TSP has proved challenging but very fruitful. This is the first book on approximation algorithms for the TSP, featuring a comprehensive collection of all major results and an overview of the most intriguing open problems. Many of the presented results have been discovered only recently, and some are published here for the first time, including better approximation algorithms for the asymmetric TSP and its path version. This book constitutes and advances the state of the art and makes it accessible to a wider audience. Featuring detailed proofs, over 170 exercises, and 100 color figures, this book is an excellent resource for teaching, self-study, and further research.

Read more less

Book SynopsisPrimal heuristics guarantee that feasible, high-quality solutions are provided at an early stage of the solving process, and thus are essential to the success of mixed-integer programming (MIP). By helping prove optimality faster, they allow MIP technology to extend to a wide variety of applications in discrete optimization. This first comprehensive guide to the development and use of primal heuristics within MIP technology and solvers is ideal for computational mathematics graduate students and industry practitioners. Through a unified viewpoint, it gives a unique perspective on how state-of-the-art results are integrated within the branch-and-bound approach at the core of the MIP technology. It accomplishes this by highlighting all the required knowledge needed to push the heuristic side of MIP solvers to their limit and pointing out what is left to do to improve them, thus presenting heuristic approaches for MIP as part of the MIP solving process.

Read more less

Book SynopsisThis book has enjoyed considerable use and appreciation during its first four editions. With hundreds of students having learned out of early editions, the author continues to find ways to modernize and maintain a unique presentation.What sets the book apart is the excellent writing style, exposition, and unique and thorough sets of exercises. This edition offers a more instructive preface to assist instructors on developing the course they prefer. The prerequisites are more explicit and provide a roadmap for the course. Sample syllabi are included.As would be expected in a fifth edition, the overall content and structure of the book are sound.This new edition offers a more organized treatment of axiomatics. Throughout the book, there is a more careful and detailed treatment of the axioms of set theory. The rules of inference are more carefully elucidated.Additional new features include: An emphasis on the artTrade ReviewThe great strength of the book overall and of the chapters I read is a very accessible writing style, and extremely good exercises. The mix of discussion of advanced topics alongside the presentation of more elementary material is excellent. This is a product of having a highly accomplished and knowledgeable mathematician writing a textbook intended for not-so-advanced students.--David Walnut, George Washington UniversityTable of Contents1. Basic Logic 2. Methods of Proof 3. Set Theory 4. Relations and Functions 5. Group Theory 6. Number Systems 7. More on the Real Number System 8. A Glimpse of Topology 9. Elementary Number Theory 10. Zero-Knowledge Proofs and Cryptography 11. An Example of an Axiomatic Theory

Read more less

Book SynopsisThis book is the very first one in the English language entirely dedicated to the Lambert W function, its generalizations, and its applications. One goal is to promote future research on the topic. The book contains all the information one needs when trying to find a result. The most important formulas and results are framed. The Lambert W function is a multi-valued inverse function with plenty of applications in areas like molecular physics, relativity theory, fuel consumption models, plasma physics, analysis of epidemics, bacterial growth models, delay differential equations, fluid mechanics, game theory, statistics, study of magnetic materials, and so on.The first part of the book gives a full treatise of the W function from theoretical point of view.The second part presents generalizations of this function which have been introduced by the need of applications where the classical W function is insufficient.The third part presents a large number of app

Read more less

Book Synopsis

Read more less

Book SynopsisBasics of Ramsey Theory serves as a gentle introduction to Ramsey theory for students interested in becoming familiar with a dynamic segment of contemporary mathematics that combines ideas from number theory and combinatorics. The core of the of the book consists of discussions and proofs of the results now universally known as Ramsey's theorem, van der Waerden's theorem, Schur's theorem, Rado's theorem, the HalesJewett theorem, and the Happy End Problem of Erdos and Szekeres. The aim is to present these in a manner that will be challenging but enjoyable, and broadly accessible to anyone with a genuine interest in mathematics.Features Suitable for any undergraduate student who has successfully completed the standard calculus sequence of courses and a standard first (or second) year linear algebra course Filled with visual proofs of fundamental theorems Contains numerous exercises (with their solutions) acceTable of Contents1. Introduction: Pioneers and Trailblazers. 1.1. Complete Disorder is Impossible. 1.2 Paul Erdős. 1.3. Frank Plumpton Ramsey. 1.4 Ramsey Theory. 2. Ramsey’s Theorem. 2.1. The Pigeonhole Principle. 2.2. Acquaintances and Strangers. 2.3. Ramsey’s Theorem for Graphs. 2.4. Ramsey’s Theorem: Infinite Case. 2.5. Ramsey’s Theorem: General Case. 2.6. Exercises. 3. van der Waerden’s Theorem. 3.1. Bartel van der Waerden. 3.2. van der Waerden’s Theorem: 3–Term Arithmetic Progressions. 3.3. Proof of van der Waerden’s Theorem. 3.4. van der Waerden’s Theorem: How Far and Where? 3.5. van der Waerden’s Theorem: Some Related Questions. 3.6. Exercises. 4. Schur’s Theorem and Rado’s Theorem. 4.1 Issai Schur. 4.2. Schur’s Theorem. 4.3. Richard Rado. 4.4 Rado’s Theorem. 4.5. Exercises. 5. The Hales–Jewett Theorem. 5.1. Combinatorial Lines. 5.2. Generalized Tic–Tac–Toe Game. 5.3. The Hales–Jewett Theorem. 5.4. Exercises. 6. Happy End Problem. 6.1. The Happy End Problem: Triangles, Quadrilaterals, and Pentagons. 6.2. The Happy End Problem – General Case. 6.3. Erdős–Szekeres’ Upper and Lower Bounds. 6.4. Progress on the Conjecture OF Erdős and Szekeres. 6.5. Exercises. 7. Solutions.

Read more less

The Baseball Mysteries: Challenging Puzzles for Logical Detectives is a book of baseball puzzles, logical baseball puzzles. To jump in, all you need is logic and a casual fan's knowledge of the game. The puzzles are solved by reasoning from the rules of the game and a few facts.The logic in the puzzles is like legal reasoning. A solution must argue from evidence (the facts) and law (the rules). Unlike legal arguments, however, a solution must reach an unassailable conclusion.There are many puzzle books. But there's nothing remotely like this book. The puzzles here, while rigorously deductive, are firmly attached to actual events, to struggles that are reported in the papers every day.The puzzles offer a unique and scintillating connection between abstract logic and gritty reality.Actually, this book offers the reader an unlimited number of puzzles. Once you've solved a few of the challenges here, every boxscore you see in the pap

Read more less

Book SynopsisIn this book, various numerical methods are discussed in a comprehensive way. It delivers a mixture of theory, examples and MATLAB practicing exercises to help the students in improving their skills. To understand the MATLAB programming in a friendly style, the examples are solved. The MATLAB codes are mentioned in the end of each topic. Throughout the text, a balance between theory, examples and programming is maintained.Key Features Methods are explained with examples and codes System of equations has given full consideration Use of MATLAB is learnt for every method This book is suitable for graduate students in mathematics, computer science and engineering.Table of Contents1. Common Commands Used in Matlab. 2. System of Linear Equations. 3. Polynomial Interpolation. 4. Root Finding Methods. 5. Numerical Integration. 6. Solution of Initial Value Problems. 7. Boundary Value Problems.

Read more less

Book SynopsisGraphs & Digraphs, Seventh Edition masterfully employs student-friendly exposition, clear proofs, abundant examples, and numerous exercises to provide an essential understanding of the concepts, theorems, history, and applications of graph theory. This classic text, widely popular among students and instructors alike for decades, is thoroughly streamlined in this new, seventh edition, to present a text consistent with contemporary expectations.Changes and updates to this edition include: A rewrite of four chapters from the ground up Streamlining by over a third for efficient, comprehensive coverage of graph theory Flexible structure with foundational Chapters 16 and customizable topics in Chapters 711 Incorporation of the latest developments in fundamental graph theory Statements of recent groundbreaking discoveries, even if proofs are beyond scope Completely reorganized chapters on traversability, connectiviTable of Contents1 Graphs 1.1 Fundamentals 1.2 Isomorphism 1.3 Families of graphs 1.4 Operations on graphs 1.5 Degree sequences 1.6 Path and cycles 1.7 Connected graphs and distance 1.8 Trees and forests 1.9 Multigraphs and pseudographs 2 Digraphs 2.1 Fundamentals 2.2 Strongly connected digraphs 2.3 Tournaments 2.4 Score sequences 3 Traversability 3.1 Eulerian graphs and digraphs 3.2 Hamiltonian graphs 3.3 Hamiltonian digraphs 3.4 Highly hamiltonian graphs 3.5 Graph powers 4 Connectivity 4.1 Cut-vertices, bridges, and blocks 4.2 Vertex connectivity 4.3 Edge-connectivity 4.4 Menger's theorem 5 Planarity 5.1 Euler's formula 5.2 Characterizations of planarity 5.3 Hamiltonian planar graphs 5.4 The crossing number of a graph 6 Coloring 6.1 Vertex coloring 6.2 Edge coloring 6.3 Critical and perfect graphs 6.4 Maps and planar graphs 7 Flows 7.1 Networks 7.2 Max-flow min-cut theorem 7.3 Menger's theorems for digraphs 7.4 A connection to coloring 8 Factors and covers 8.1 Matchings and 1-factors 8.2 Independence and covers 8.3 Domination 8.4 Factorizations and decompositions 8.5 Labelings of graphs 9 Extremal graph theory 9.1 Avoiding a complete graph 9.2 Containing cycles and trees 9.3 Ramsey theory 9.4 Cages and Moore graphs 10 Embeddings 10.1 The genus of a graph 10.2 2-Cell embeddings of graphs 10.3 The maximum genus of a graph 10.4 The graph minor theorem 11 Graphs and algebra 11.1 Graphs and matrices 11.2 The automorphism group 11.3 Cayley color graphs 11.4 The reconstruction problem

Read more less

Book SynopsisUpdated to reflect current research and extended to cover more advanced topics as well as the basics, Algebraic Number Theory and Fermatâs Last Theorem, Fifth Edition introduces fundamental ideas of algebraic numbers and explores one of the most intriguing stories in the history of mathematicsâthe quest for a proof of Fermatâs Last Theorem. The authors use this celebrated theorem to motivate a general study of the theory of algebraic numbers, initially from a relatively concrete point of view. Students will see how Wilesâs proof of Fermatâs Last Theorem opened many new areas for future work. New to the Fifth Edition Pell's Equation x^2-dy^2=1: all solutions can be obtained from a single `fundamental' solution, which can be found using continued fractions. Galois theory of number field extensions, relating the field structure to that of the group of automorphisms. More material on cyclotomic fields, and some results on cubic fields

Read more less

Book SynopsisDesigned for advanced undergraduate and beginning graduate students in linear or abstract algebra, Advanced Linear Algebra covers theoretical aspects of the subject, along with examples, computations, and proofs. It explores a variety of advanced topics in linear algebra that highlight the rich interconnections of the subject to geometry, algebra, analysis, combinatorics, numerical computation, and many other areas of mathematics.The author begins with chapters introducing basic notation for vector spaces, permutations, polynomials, and other algebraic structures. The following chapters are designed to be mostly independent of each other so that readers with different interests can jump directly to the topic they want. This is an unusual organization compared to many abstract algebra textbooks, which require readers to follow the order of chapters.Each chapter consists of a mathematical vignette devoted to the development of one specific topic.

Read more less

Book SynopsisIn applications of stochastic calculus, there are phenomena that cannot be analyzed through the classical Ità theory. It is necessary, therefore, to have a theory based on stochastic integration with respect to these situations.Theory of Stochastic Integrals aims to provide the answer to this problem by introducing readers to the study of some interpretations of stochastic integrals with respect to stochastic processes that are not necessarily semimartingales, such as Volterra Gaussian processes, or processes with bounded p-variation among which we can mention fractional Brownian motion and Riemann-Liouville fractional process.Features Self-contained treatment of the topic Suitable as a teaching or research tool for those interested in stochastic analysis and its applications Includes original results.

Read more less

Book SynopsisThis book is a concise, selfâcontained treatment of the finite element method and all the computational techniques needed for its efficient use and practical implementation. This book describes the process of transforming the physical problem into a mathematical model, the reduction of the mathematical model to a numerically solvable computational form, and many practical engineering analysis solution techniques applied in various industries.The first edition of this book was published in 2004, two decades ago. Since then, finite element analysis (FEA) has become a fundamental component of product development software tools (CAD, CAE, CAM) used in many industrial fields of engineering, particularly in mechanical and aerospace engineering. It has also become a popular text in computational science in engineering (CSE) and applied mathematics courses in academia, one of the reasons for the new edition.This new edition presents finite element solutions to advanced industr

Read more less

Book SynopsisRichard Stanley's two-volume basic introduction to enumerative combinatorics has become the standard guide to the topic for students and experts alike. This thoroughly revised second edition of Volume 1 includes ten new sections and more than 300 new exercises, most with solutions, reflecting numerous new developments since the publication of the first edition in 1986. The author brings the coverage up to date and includes a wide variety of additional applications and examples, as well as updated and expanded chapter bibliographies. Many of the less difficult new exercises have no solutions so that they can more easily be assigned to students. The material on P-partitions has been rearranged and generalized; the treatment of permutation statistics has been greatly enlarged; and there are also new sections on q-analogues of permutations, hyperplane arrangements, the cd-index, promotion and evacuation and differential posets.Trade Review'… sure to become a standard as an introductory graduate text in combinatorics.' Bulletin of the American Mathematical Society'… will engage from start to finish the attention of any mathematician who will open it at page one.' Gian-Carlo RotaTable of Contents1. What is enumerative combinatorics?; 2. Sieve methods; 3. Partially ordered sets; 4. Rational generating functions.

Read more less

Book SynopsisThe projective and polar geometries that arise from a vector space over a finite field are particularly useful in the construction of combinatorial objects, such as latin squares, designs, codes and graphs. This book provides an introduction to these geometries and their many applications to other areas of combinatorics. Coverage includes a detailed treatment of the forbidden subgraph problem from a geometrical point of view, and a chapter on maximum distance separable codes, which includes a proof that such codes over prime fields are short. The author also provides more than 100 exercises (complete with detailed solutions), which show the diversity of applications of finite fields and their geometries. Finite Geometry and Combinatorial Applications is ideal for anyone, from a third-year undergraduate to a researcher, who wishes to familiarise themselves with and gain an appreciation of finite geometry.Table of Contents1. Fields; 2. Vector spaces; 3. Forms; 4. Geometries; 5. Combinatorial applications; 6. The forbidden subgraph problem; 7. MDS codes; Appendix A. Solutions to the exercises; Appendix B. Additional proofs; Appendix C. Notes and references; References; Index.

Read more less

Book SynopsisFrom social networks such as Facebook, the World Wide Web and the Internet, to the complex interactions between proteins in the cells of our bodies, we constantly face the challenge of understanding the structure and development of networks. The theory of random graphs provides a framework for this understanding, and in this book the authors give a gentle introduction to the basic tools for understanding and applying the theory. Part I includes sufficient material, including exercises, for a one semester course at the advanced undergraduate or beginning graduate level. The reader is then well prepared for the more advanced topics in Parts II and III. A final part provides a quick introduction to the background material needed. All those interested in discrete mathematics, computer science or applied probability and their applications will find this an ideal introduction to the subject.Trade Review'This is a well-planned book that is true to its title in that it is indeed accessible for anyone with just an undergraduate student's knowledge of enumerative combinatorics and probability.' Miklós Bóna, MAA ReviewsTable of ContentsPreface; Part I. Basic Models: 1. Random graphs; 2. Evolution; 3. Vertex degrees; 4. Connectivity; 5. Small subgraphs; 6. Spanning subgraphs; 7. Extreme characteristics; 8. Extremal properties; Part II. Basic Model Extensions: 9. Inhomogeneous graphs; 10. Fixed degree sequence; 11. Intersection graphs; 12. Digraphs; 13. Hypergraphs; Part III. Other Models: 14. Trees; 15. Mappings; 16. k-out; 17. Real-world networks; 18. Weighted graphs; 19. Brief notes on uncovered topics; Part IV. Tools and Methods: 20. Moments; 21. Inequalities; 22. Differential equations method; 23. Branching processes; 24. Entropy; References; Author index; Main index.

Read more less

Book SynopsisCatalan numbers are probably the most ubiquitous sequence of numbers in mathematics. This book gives for the first time a comprehensive collection of their properties and applications to combinatorics, algebra, analysis, number theory, probability theory, geometry, topology, and other areas. Following an introduction to the basic properties of Catalan numbers, the book presents 214 different kinds of objects counted by them in the form of exercises with solutions. The reader can try solving the exercises or simply browse through them. Some 68 additional exercises with prescribed difficulty levels present various properties of Catalan numbers and related numbers, such as Fuss-Catalan numbers, Motzkin numbers, SchrÃder numbers, Narayana numbers, super Catalan numbers, q-Catalan numbers and (q,t)-Catalan numbers. The book ends with a history of Catalan numbers by Igor Pak and a glossary of key terms. Whether your interest in mathematics is recreation or research, you will find plenty of fTable of Contents1. Basic properties; 2. Bijective exercises; 3. Bijective solutions; 4. Additional problems; 5. Solutions to additional problems.

Read more less

Book SynopsisRichard Stanley's two-volume basic introduction to enumerative combinatorics has become the standard guide to the topic for students and experts alike. This thoroughly revised second edition of Volume 1 includes more than 300 new exercises, many with solutions, updated and expanded chapter bibliographies and substantial new material on permutation statistics.Trade Review'… sure to become a standard as an introductory graduate text in combinatorics.' Bulletin of the American Mathematical Society'… will engage from start to finish the attention of any mathematician who will open it at page one.' Gian-Carlo RotaTable of Contents1. What is enumerative combinatorics?; 2. Sieve methods; 3. Partially ordered sets; 4. Rational generating functions.

Read more less

Book SynopsisRandomized algorithms have become a central part of the algorithms curriculum, based on their increasingly widespread use in modern applications. This book presents a coherent and unified treatment of probabilistic techniques for obtaining high probability estimates on the performance of randomized algorithms. It covers the basic toolkit from the ChernoffâHoeffding bounds to more sophisticated techniques like martingales and isoperimetric inequalities, as well as some recent developments like Talagrand's inequality, transportation cost inequalities and log-Sobolev inequalities. Along the way, variations on the basic theme are examined, such as ChernoffâHoeffding bounds in dependent settings. The authors emphasise comparative study of the different methods, highlighting respective strengths and weaknesses in concrete example applications. The exposition is tailored to discrete settings sufficient for the analysis of algorithms, avoiding unnecessary measure-theoretic details, thus makingTrade ReviewReview of the hardback: 'It is beautifully written, contains all the major concentration results, and is a must to have on your desk.' Richard LiptonReview of the hardback: 'Concentration bounds are at the core of probabilistic analysis of algorithms. This excellent text provides a comprehensive treatment of this important subject, ranging from the very basic to the more advanced tools, including some recent developments in this area. The presentation is clear and includes numerous examples, demonstrating applications of the bounds in analysis of algorithms. This book is a valuable resource for both researchers and students in the field.' Eli Upfal, Brown UniversityReview of the hardback: 'Concentration inequalities are an essential tool for the analysis of algorithms in any probabilistic setting. There have been many recent developments on this subject, and this excellent text brings them together in a highly accessible form.' Alan Frieze, Carnegie Mellon UniversityReview of the hardback: 'The book does a superb job of describing a collection of powerful methodologies in a unified manner; what is even more striking is that basic combinatorial and probabilistic language is used in bringing out the power of such approaches. To summarize, the book has done a great job of synthesizing diverse and important material in a very accessible manner. Any student, researcher, or practitioner of computer science, electrical engineering, mathematics, operations research, and related fields, could benefit from this wonderful book. The book would also make for fruitful classes at the undergraduate and graduate levels. I highly recommend it.' Aravind Srinivasan, SIGACT NewsReview of the hardback: '… the strength of this book is that it is appropriate for both the beginner as well as the experienced researcher in the field of randomized algorithms … The exposition style […] combines informal discussion with formal definitions and proofs, giving first the intuition and motivation for the probabalistic technique at hand. … I highly recommend this book both as an advanced as well as an introductory textbook, which can also serve the needs of an experienced researcher in algorithmics.' Yannis C. Stamatiou, Mathematical ReviewsReviews of the hardback: 'This timely book brings together in a comprehensive and accessible form a sophisticated toolkit of powerful techniques for the analysis of randomized algorithms, illustrating their use with a wide array of insightful examples. This book is an invaluable resource for people venturing into this exciting field of contemporary computer science research.' Prabhakar Ragahavan, Yahoo ResearchTable of Contents1. Chernoff–Hoeffding bounds; 2. Applying the CH-bounds; 3. CH-bounds with dependencies; 4. Interlude: probabilistic recurrences; 5. Martingales and the MOBD; 6. The MOBD in action; 7. Averaged bounded difference; 8. The method of bounded variances; 9. Interlude: the infamous upper tail; 10. Isoperimetric inequalities and concentration; 11. Talagrand inequality; 12. Transportation cost and concentration; 13. Transportation cost and Talagrand's inequality; 14. Log–Sobolev inequalities; Appendix A. Summary of the most useful bounds.

Read more less

Book SynopsisA concise yet rigorous introduction to logic and discrete mathematics. This book features a unique combination of comprehensive coverage of logic with a solid exposition of the most important fields of discrete mathematics, presenting material that has been tested and refined by the authors in university courses taught over more than a decade. The chapters on logic - propositional and first-order - provide a robust toolkit for logical reasoning, emphasizing the conceptual understanding of the language and the semantics of classical logic as well as practical applications through the easy to understand and use deductive systems of Semantic Tableaux and Resolution. The chapters on set theory, number theory, combinatorics and graph theory combine the necessary minimum of theory with numerous examples and selected applications. Written in a clear and reader-friendly style, each section ends with an extensive set of exercises, most of them provided with complete soluTrade Review"This is a very well-written brief introduction to discrete mathematics that emphasizes logic and set theory and has shorter sections on number theory, combinatorics, and graph theory." (MAA Reviews, 4 January 2016)Table of ContentsList of Boxes xiii Preface xvii Acknowledgements xxi About the Companion Website xxiii 1. Preliminaries 1 1.1 Sets 2 1.1.1 Exercises 7 1.2 Basics of logical connectives and expressions 9 1.2.1 Propositions, logical connectives, truth tables, tautologies 9 1.2.2 Individual variables and quantifiers 12 1.2.3 Exercises 15 1.3 Mathematical induction 17 1.3.1 Exercises 18 2. Sets, Relations, Orders 20 2.1 Set inclusions and equalities 21 2.1.1 Properties of the set theoretic operations 22 2.1.2 Exercises 26 2.2 Functions 28 2.2.1 Functions and their inverses 28 2.2.2 Composition of mappings 31 2.2.3 Exercises 33 2.3 Binary relations and operations on them 35 2.3.1 Binary relations 35 2.3.2 Matrix and graphical representations of relations on finite sets 38 2.3.3 Boolean operations on binary relations 39 2.3.4 Inverse and composition of relations 41 2.3.5 Exercises 42 2.4 Special binary relations 45 2.4.1 Properties of binary relations 45 2.4.2 Functions as relations 47 2.4.3 Reflexive, symmetric and transitive closures of a relation 47 2.4.4 Exercises 49 2.5 Equivalence relations and partitions 51 2.5.1 Equivalence relations 51 2.5.2 Quotient sets and partitions 53 2.5.3 The kernel equivalence of a mapping 56 2.5.4 Exercises 57 2.6 Ordered sets 59 2.6.1 Pre-orders and partial orders 59 2.6.2 Graphical representing posets: Hasse diagrams 61 2.6.3 Lower and upper bounds. Minimal and maximal elements 63 2.6.4 Well-ordered sets 65 2.6.5 Exercises 67 2.7 An introduction to cardinality 69 2.7.1 Equinumerosity and cardinality 69 2.7.2 Exercises 73 2.8 Isomorphisms of ordered sets. Ordinal numbers 75 2.8.1 Exercises 79 2.9 Application: relational databases 80 2.9.1 Exercises 86 3. Propositional Logic 89 3.1 Propositions, logical connectives, truth tables, tautologies 90 3.1.1 Propositions and propositional connectives. Truth tables 90 3.1.2 Some remarks on the meaning of the connectives 90 3.1.3 Propositional formulae 91 3.1.4 Construction and parsing tree of a propositional formula 92 3.1.5 Truth tables of propositional formulae 93 3.1.6 Tautologies 95 3.1.7 A better idea: search for a falsifying truth assignment 96 3.1.8 Exercises 97 3.2 Propositional logical consequence. Valid and invalid propositional inferences 101 3.2.1 Propositional logical consequence 101 3.2.2 Logically sound rules of propositional inference. Logically correct propositional arguments 104 3.2.3 Fallacies of the implication 106 3.2.4 Exercises 107 3.3 The concept and use of deductive systems 109 3.4 Semantic tableaux 113 3.4.1 Exercises 117 3.5 Logical equivalences. Negating propositional formulae 121 3.5.1 Logically equivalent propositional formulae 121 3.5.2 Some important equivalences 123 3.5.3 Exercises 124 3.6 Normal forms. Propositional resolution 126 3.6.1 Conjunctive and disjunctive normal forms of propositional formulae 126 3.6.2 Clausal form. Clausal resolution 129 3.6.3 Resolution-based derivations 130 3.6.4 Optimizing the method of resolution 131 3.6.5 Exercises 132 4. First-Order Logic 135 4.1 Basic concepts of first-order logic 136 4.1.1 First-order structures 136 4.1.2 First-order languages 138 4.1.3 Terms and formulae 139 4.1.4 The semantics of first-order logic: an informal outline 143 4.1.5 Translating first-order formulae to natural language 146 4.1.6 Exercises 147 4.2 The formal semantics of first–order logic 152 4.2.1 Interpretations 152 4.2.2 Variable assignment and term evaluation 153 4.2.3 Truth evaluation games 156 4.2.4 Exercises 159 4.3 The language of first-order logic: a deeper look 161 4.3.1 Translations from natural language into first-order languages 161 4.3.2 Restricted quantification 163 4.3.3 Free and bound variables. Scope of a quantifier 164 4.3.4 Renaming of a bound variable in a formula. Clean formulae 165 4.3.5 Substitution of a term for a variable in a formula. Capture of a variable 166 4.3.6 Exercises 167 4.4 Truth, logical validity, equivalence and consequence in first-order logic 171 4.4.1 More on truth of sentences in structures. Models and countermodels 171 4.4.2 Satisfiability and validity of first-order formulae 172 4.4.3 Logical equivalence in first-order logic 173 4.4.4 Some logical equivalences involving quantifiers 174 4.4.5 Negating first-order formulae 175 4.4.6 Logical consequence in first-order logic 176 4.4.7 Exercises 180 4.5 Semantic tableaux for first-order logic 185 4.5.1 Some derivations using first-order semantic tableau 186 4.5.2 Semantic tableaux for first-order logic with equality 189 4.5.3 Discussion on the quantifier rules and on termination of semantic tableaux 189 4.5.4 Exercises 191 4.6 Prenex and clausal normal forms 195 4.6.1 Prenex normal forms 195 4.6.2 Skolemization 197 4.6.3 Clausal forms 198 4.6.4 Exercises 199 4.7 Resolution in first-order logic 201 4.7.1 Propositional resolution rule in first-order logic 201 4.7.2 Substitutions of terms for variables revisited 201 4.7.3 Unification of terms 202 4.7.4 Resolution with unification in first-order logic 204 4.7.5 Examples of resolution-based derivations 205 4.7.6 Resolution for first-order logic with equality 207 4.7.7 Optimizations of the resolution method for first-order logic 207 4.7.8 Exercises 207 4.8 Applications of first-order logic to mathematical reasoning and proofs 211 4.8.1 Proof strategies: direct and indirect proofs 211 4.8.2 Tactics for logical reasoning 215 4.8.3 Exercises 216 5. Number Theory 219 5.1 The principle of mathematical induction revisited 220 5.1.1 Exercises 222 5.2 Divisibility 224 5.2.1 Basic properties of divisibility 224 5.2.2 Division with a remainder 224 5.2.3 Greatest common divisor 225 5.2.4 Exercises 227 5.3 Computing greatest common divisors. Least common multiples 230 5.3.1 Euclid’s algorithm for computing greatest common divisors 230 5.3.2 Least common multiple 232 5.3.3 Exercises 233 5.4 Prime numbers. The fundamental theorem of arithmetic 236 5.4.1 Relatively prime numbers 236 5.4.2 Prime numbers 237 5.4.3 The fundamental theorem of arithmetic 238 5.4.4 On the distribution of prime numbers 239 5.4.5 Exercises 240 5.5 Congruence relations 243 5.5.1 Exercises 246 5.6 Equivalence classes and residue systems modulo n 248 5.6.1 Equivalence relations and partitions 248 5.6.2 Equivalence classes modulo n. Modular arithmetic 249 5.6.3 Residue systems 250 5.6.4 Multiplicative inverses in ℤn 251 5.6.5 Exercises 251 5.7 Linear Diophantine equations and linear congruences 253 5.7.1 Linear Diophantine equations 253 5.7.2 Linear congruences 254 5.7.3 Exercises 256 5.8 Chinese remainder theorem 257 5.8.1 Exercises 259 5.9 Euler’s function. Theorems of Euler and Fermat 261 5.9.1 Theorems of Euler and Fermat 262 5.9.2 Exercises 264 5.10 Wilson’s theorem. Order of an integer 266 5.10.1 Wilson’s theorem 266 5.10.2 Order of an integer 266 5.10.3 Exercises 267 5.11 Application: public key cryptography 269 5.11.1 About cryptography 269 5.11.2 The idea of public key cryptography 269 5.11.3 The method RSA 270 5.11.4 Exercises 271 6. Combinatorics 274 6.1 Two basic counting principles 275 6.1.1 Exercises 281 6.2 Combinations. The binomial theorem 284 6.2.1 Counting sheep and combinations 284 6.2.2 Some important properties 286 6.2.3 Pascal’s triangle 287 6.2.4 The binomial theorem 287 6.2.5 Exercises 289 6.3 The principle of inclusion–exclusion 293 6.3.1 Exercises 296 6.4 The Pigeonhole Principle 299 6.4.3 Exercises 302 6.5 Generalized permutations, distributions and the multinomial theorem 304 6.5.1 Arranging nondistinct objects 304 6.5.2 Distributions 306 6.5.3 The multinomial theorem 308 6.5.4 Summary 310 6.5.5 Exercises 311 6.6 Selections and arrangements with repetition; distributions of identical objects 312 6.6.1 Selections with repetition 312 6.6.2 Distributions of identical objects 314 6.6.3 Arrangements with repetition 315 6.6.4 Summary 316 6.6.5 Exercises 316 6.7 Recurrence relations and their solution 318 6.7.1 Recurrence relations. Fibonacci numbers 318 6.7.2 Catalan numbers 319 6.7.3 Solving homogeneous linear recurrence relations 322 6.7.4 Exercises 327 6.8 Generating functions 329 6.8.1 Introducing generating functions 329 6.8.2 Computing coefficients of generating functions 332 6.8.3 Exercises 335 6.9 Recurrence relations and generating functions 337 6.9.1 Exercises 341 6.10 Application: classical discrete probability 343 6.10.1 Common sense probability 343 6.10.2 Sample spaces 343 6.10.3 Discrete probability 345 6.10.4 Properties of probability measures 346 6.10.5 Conditional probability and independent events 348 6.10.6 Exercises 352 7. Graph Theory 356 7.1 Introduction to graphs and digraphs 357 7.1.1 Graphs 357 7.1.2 Digraphs 364 7.1.3 Exercises 367 7.2 Incidence and adjacency matrices 370 7.2.1 Exercises 374 7.3 Weighted graphs and path algorithms 377 7.3.1 Dijkstra’s algorithm 378 7.3.2 The Floyd–Warshall algorithm 381 7.3.3 Exercises 383 7.4 Trees 385 7.4.1 Undirected trees 385 7.4.2 Computing spanning trees: Kruskal’s algorithm 388 7.4.3 Rooted trees 390 7.4.4 Traversing rooted trees 392 7.4.5 Exercises 393 7.5 Eulerian graphs and Hamiltonian graphs 395 7.5.1 Eulerian graphs and digraphs 396 7.5.2 Hamiltonian graphs and digraphs 398 7.5.3 Exercises 400 7.6 Planar graphs 404 7.6.1 Exercises 408 7.7 Graph colourings 411 7.7.1 Colourings 411 7.7.2 The four- and five-colour theorems 413 7.7.3 Exercises 414 Index 419

Read more less

Book SynopsisSolutions manual to accompanyTable of ContentsPreface vii About the Companion Website ix 1. Preliminaries 1 2. Sets, Relations, Orders 5 3. Propositional Logic 29 4. First-Order Logic 57 5. Number Theory 99 6. Combinatorics 130 7. Graph Theory 159

Read more less