Combinatorics and graph theory Books

Book SynopsisMathematics of Tabletop Gamesprovides a bridge between mathematics and hobby tabletop gaming. Instead of focusing on games mathematicians play, such as nim and chomp, this book starts with the tabletop games played by avid gamers and hopes to address the question: which field of mathematics concerns itself with this situation?Readers interested in either mathematics or tabletop games will find this book an engaging way to begin exploring the other topic or the connection between the topics.Features Presents an entry-level exposition of interesting mathematical concepts that are not commonly taught outside of upper-level mathematics courses Acts as a resource for mathematics instructors who wish to provide new examples of standard mathematical concepts Features material that may help game designers and developers make design decisions about game mechanisms Provides working Python code that can be used to sol

Read more less

Book SynopsisA textbook suitable for undergraduate courses. The materials are presented very explicitly so that students will find it very easy to read. A wide range of examples, about 500 combinatorial problems taken from various mathematical competitions and exercises are also included.Trade Review"This book should be a must for all mathematicians who are involved in the training of Mathematical Olympiad teams, but it will also be a valuable source of problems for university courses." Mathematical ReviewsTable of ContentsPermutations and combinations; binomial coefficients and multinomial coefficients; the Pigeonhole principle and Ramsey numbers; the principle of inclusion and exclusion; generating functions; recurrence relations.

Read more less

Book SynopsisDiscrete Mathematics with Ducks, Second Edition is a gentle introduction for students who find the proofs and abstractions of mathematics challenging. At the same time, it provides stimulating material that instructors can use for more advanced students. The first edition was widely well received, with its whimsical writing style and numerous exercises and materials that engaged students at all levels. The new, expanded edition continues to facilitate effective and active learning. It is designed to help students learn about discrete mathematics through problem-based activities. These are created to inspire students to understand mathematics by actively practicing and doing, which helps students better retain what they've learned. As such, each chapter contains a mixture of discovery-based activities, projects, expository text, in-class exercises, and homework problems. The author's lively and friendly writing style is apTable of ContentsPreface for Instructors and Other TeachersPreface for Students and Other LearnersTheme: The Basics1 Counting and Proofs2 Sets and Logic3 Graphics and Functions4 Induction5 Algorithms with CiphersTheme I Supplement6 Binomial Coefficients and Pascal’s Triangle7 Balls and Boxes and PIE: Counting Techniques8 Recurrences9 Cutting Up Food: Counting and GeometryIII Theme: Graph Theory10 Trees11 Euler’s Formula and Applications12 Graph Traversals13 Graph ColoringTheme III Supplement: Problems on the Theme of Graph TheoryIV Other Material14 Probability and Expectation15 Fun with Cardinality16 Number Theory17 Computational ComplexityA Solutions to Check Yourself ProblemsB Solutions to Bonus Check-Yourself ProblemsC The Greek Alphabet and Some Uses for Some LettersD List of SymbolsBibliographyIndex

Read more less

Book SynopsisMagic tricks can be easy to perform and have an interesting mathematical foundation. In this rich, colourfully illustrated volume, Ehrhard Behrends presents around 30 card tricks and number games that are easy to learn, with no prior knowledge required. This is maths as you've never experienced it before: entertaining and fun!Table of Contents You can count on it Let's mix it up! Optimally packaged information: Coding Chance makes magic Appendix References.

Read more less

Book SynopsisTrade Review"Visualizing Music provides a rich visual overview of the discipline of music theory while offering practical suggestions for scholars."—Timothy Koozin, Moores School of Music, University of HoustonTable of ContentsPrefaceAcknowledgmentsAccessing Audiovisual MaterialsIntroductionPart 1: Preliminaries1. Leveraging the Power of the Brain2. The Role of Metaphor3. Multivariate Images4. Telling a Story5. Facilitating Comparison6. Information Layers7. Information Integration8. Making Every Part of an Image Count9. Presenting Tabular Data10. Small Multiples11. Using Color12. Additional General Principles13. Case Study: Western NotationPart 2: Musical Spaces14. Pitch Spaces15. Collections, Scales, and Modes16. The Circle of Fifths17. The Tonnetz18. Atonal Spaces19. Symmetrical Pitch Structures20. Tonal Hierarchy, Tendency, Progression21. The Overtone SeriesPart 3: Musical Time22. Basic Durations23. Unmeasured Musical Time24. Musically Measured Musical Time25. Externally Measured Musical Time (Performance Timing)26. ProportionPart 4: Pitch, Texture, Timbre, Form27. Textual Representations of Pitch28. Piano Roll Notation29. Alternate Notational Systems30. Tuning and Temperament31. Microtuning32. Timbre33. Texture34. Voice Leading35. Schematic and Procedural Representations36. Formal Models37. Pitch-Class Set Tables38. Instrument Ranges39. TranslationsPart 5: Music Analysis40. Lutosławksi's Jeux Venitiens41. Annotating Musical Scores42. Thematic Analysis43. Contour Analysis44. Tonal Plans45. Symmetry in Music Analysis46. Rhythmic Analysis47. Formal Analysis48. Hierarchy in Music49. Serialism50. Corpus Studies51. Musical Chronologies, Influences, and Styles52. AnimationPart 6: Visualization in the Professional Realm53. Conference Handouts54. Presentation Slide Shows55. Conference Posters56. Print Publication57. The Essential Visualization ToolboxEpilogueBibliographyIndex

Read more less

Book SynopsisAbout our author Richard A. Brualdi is Bascom Professor of Mathematics, Emeritus at the University of Wisconsin - Madison. He served as Chair of the Department of Mathematics from 1993-1999. His research interests lie in matrix theory and combinatorics/graph theory. Professor Brualdi is the author or co-author of 6 books, and has published extensively. He is one of the editors-in-chief of the journal Linear Algebra and its Applications and of the journal Electronic Journal of Combinatorics. He is a member of the American Mathematical Society, the Mathematical Association of America, the International Linear Algebra Society, and the Institute for Combinatorics and its Applications. He is also a Fellow of the Society for Industrial and Applied Mathematics.Table of Contents 1. What is Combinatorics? 2. The Pigeonhole Principle 3. Permutations and Combinations 4. Generating Permutations and Combinations 5. The Binomial Coefficients 6. The Inclusion-Exclusion Principle and Applications 7. Recurrence Relations and Generating Functions 8. Special Counting Sequences 9. Systems of Distinct Representatives 10. Combinatorial Designs 11. Introduction to Graph Theory 12. More on Graph Theory 13. Digraphs and Networks 14. Pólya Counting

Read more less

Book SynopsisMultilayer networks has become a central topic in Network Science. The book presents a comprehensive account of this emerging field. Multilayer networks are formed by several networks and include social networks, financial markets, multi-modal transportation systems, infrastructures, molecular networks, and the brain.Table of ContentsPart I: Single and multilayer networks 1: Complex systems as multilayer networks Part II: Single networks 2: The structure of single networks 3: The dynamics on single networks Part III: Multilayer networks 4: Multilayer networks in nature, society and infrastructures 5: The mathematical definition 6: Basic structural properties 7: Structural correlations of multiplex networks 8: Communities 9: Centrality measures 10: Multilayer network models 11: Interdependent multilayer networks 12: Classical percolation, generalized percolation and cascades 13: Epidemic spreading 14: Diffusion 15: Synchronization, non-linear dynamics and control 16: Opinion dynamics and game theory Appendix A: The Barabasi Albert model: the master equation Appendix B: Entropy and null models of single networks Appendix C: Growing multiplex networks: the master equation Appendix D: Percolation of interdependent networks Appendix E: Directed percolation of interdependent networks Appendix F: Immunization strategies on multiplex networks Appendix G: Spectrum of the Supra-Laplacian Part I: Single and multilayer networks 1: Complex systems as multilayer networks Part II: Single networks 2: The structure of single networks 3: The dynamics on single networks Part III: Multilayer networks 4: Multilayer networks in nature, society and infrastuctures 5: The mathematical definition 6: Basic structural properties 7: Structural correlations of multiplex networks 8: Communities 9: Centrality measures 10: Multilayer network models 11: Interdependent multilayer networks 12: Classical percolation, generalized percolation and cascades 13: Epidemic spreading 14: Diffusion 15: Synchronization, non-linear dynamics and control 16: Opinion dynamics and game theory Appendix A: The Barabasi Albert model: the master equation Appendix B: Entropy and null models of single networks Appendix C: Growing multiplex networks: the master equation Appendix D: Percolation of interdependent networks Appendix E: Directed percolation of interdependent networks Appendix F: Immunization strategies on multiplex networks Appendix G: Spectrum of the Supra-Laplacian

Read more less

Book SynopsisThis is a complete reworking of the out-of-print first volume of a three-volume treatise on finite projective spaces. There are numerous articles in journals, but this is the only extended work in the area. It also includes a comprehensive bibliography of more than 3000 items.Trade ReviewThe first edition of this work appeared in 1979, and was immediately recognized as an outstanding contribution to the field of finite geometry; the present volume is a complete revision of the earlier work...The book can serve as the text for a basic course...or as a detailed reference work for all topics in spaces of dimension two...The work is an indispensable aid to all workers in finite geometry, from beginning students to advanced researchers. * Short Book Reviews *...A complete reworking [of the first edition]. As before, the volume is concisely but clearly written, and contains a wealth of interesting material...the new trilogy, comprising the 1998, 1986 and 1991 volumes, looks set to be the standard reference work on projective spaces over finite fields for many years to come. * Bulletin of the London Mathematical Society *'Snap it up !' Bulletin London mathematical SocietyTable of Contents1. Finite fields ; 2. Projective spaces and algebraic varieties ; 3. Subspaces ; 4. Partitions ; 5. Canonical forms for varieties and polarities ; 6. The line ; 7. First properties of the plane ; 8. Ovals ; 9. Arithmetic of arcs of degree two ; 10. Arcs in ovals ; 11. Cubic curves ; 12. Arcs of higher degree ; 13. Blocking sets ; 14. Small planes ; Appendix ; Notation ; References

Read more less

Book SynopsisThis monograph sets out a body of mathematical theory for finite graphs with nodes placed randomly in Euclidean space and edges added to connect points that are close to each other. As an alternative to classical random graph models, these geometric graphs are relevant to the modelling of real-world networks having spatial content, arising in numerous applications such as wireless communications, parallel processing, classification, epidemiology, astronomy, and the internet. Aimed at graduate students and researchers in probability, combinatorics, statistics, and theoretical computer science, it covers topics such as edge and component counts, vertex degrees, cliques, colourings, connectivity, giant component phenomena, vertex ordering and partitioning problems. It also illustrates and extends the application to geometric probability of modern techniques including Stein''s method, martingale methods and continuum percolation.Trade ReviewThe book is suitable to design a graduate course in random geometric graphs. Its scope stretches far beyond geometric probability and includes exciting material from Poisson approximation, percolation and statistical physics. This elegantly written monograph belongs to the collection of important books vital for every probabilist. * Zentralblatt MATH *Table of Contents1. Introduction ; 2. Probabilistic ingredients ; 3. Subgraph and component counts ; 4. Typical vertex degrees ; 5. Geometrical ingredients ; 6. Maximum degree, cliques and colourings ; 7. Minimum degree: laws of large numbers ; 8. Minimum degree: convergence in distribution ; 9. Percolative ingredients ; 10. Percolation and the largest component ; 11. The largest component for a binomial process ; 12. Ordering and partitioning problems ; 13. Connectivity and the number of components ; References ; Index

Read more less

Book SynopsisThis concise introduction to the subject emphasizes the various classes of regular semigroups. More than 150 exercises, accompanied by references to the relevant research literature, direct readers to areas not explicitly covered in the text.Trade ReviewThe author succeeds admirably in his goal of providing an introduction to semigroup theory suitable for graduate students and non-specialists. At the same time, specialists will also find much to attract them. The book is highly readable, and the author takes pain to lead the reader gently through the longer proofs. I am sure that all specialists will want to own a copy of the book, that non-specialists will find it a most attractive and useful book for consulting, and that for many years to come research students will learn their subject from this book. * Bulletin of the London Mathematical Society *The book provides a useful survey of a rapidly developing topic and is suitable for specialists and as an introduction to the subject for non-specialists and graduate students. * Aslib Book Guide, vol.61, no.5, May 1996. *This book will still have its outstanding place as a general introduction to semigroup theory offering both an updated overview of the subject and a suitable entree for the graduate student * Monatshefte fur Mathematik Vol. 124 1997 *With this well-written and well-organised book I think the author has ensured that "Howie" will continue to be a byword for semigroup books * Edinburgh Mathematical Society 1997 *Table of Contents1. Introductory ideas ; 2. Green's equivalences; regular semigroups ; 3. 0-simple semigroups ; 4. Completely regular semigroups ; 5. Inverse semigroups ; 6. Other classes of regular semigroups ; 7. Free semigroups ; 8. Semigroup amalgams ; References ; List of symbols

Read more less

Book SynopsisTriple systems are among the simplest combinatorial designs. They have applications in coding theory, cryptography, computer science, statistcs, and many other areas. This book provides the first systematic and comprehensive treatment of triple systems. It gives an accurate picture of an incredibly rich and vibrant area of combinatorial mathematics.Table of ContentsHistorical introduction ; 1. Design-theoretic fundamentals ; 2. Existence: direct methods ; 3. Existence:recursive methods ; 4. Isomorphism and invariants ; 5. Enumeration ; 6. Subsystems and holes ; 7. Automorphisms I: small groups ; 8. Automorphisms II: large groups ; 9. Leaves and partial tripls systems ; 10. Excesses and coverings ; 11. Embedding and its variants ; 12. Neighbourhoods ; 13. Configurations ; 14. Intersections ; 15. Large sets and partitions ; 16. Support sizes ; 17. Independent sets ; 18. Chromatic number ; 19. Chromatic index and resolvability ; 20. Orthogonal resolutions ; 21. Nested and derived triple systems ; 22. Decomposability ; 23. Directed triple systems ; 24. Mendelsohn triple systems ; Bibliographies ; Index

Read more less

Book SynopsisGraph connectivities and submodular functions are two widely applied and fast developing fields of combinatorial optimization. This book not only includes the most recent results, but also highlights several surprising connections between diverse topics within combinatorial optimization. It offers a unified treatment of developments in the concepts and algorithmic methods of the area, starting from basic results on graphs, matroids and polyhedral combinatorics, through the advanced topics of connectivity issues of graphs and networks, to the abstract theory and applications of submodular optimization. Difficult theorems and algorithms are made accessible to graduate students in mathematics, computer science, operations research, informatics and communication. The book is not only a rich source of elegant material for an advanced course in combinatorial optimization, but it also serves as a reference for established researchers by providing efficient tools for applied areas like infocomTrade ReviewThe title of the book is wisely chosen: it deals, among other subjects, with graph connectivity, and it provides connections between graph theoretical results and underlying combinatorial structures...The book is readable for students, researchers, possibly also practitioners. * Mathematical Reviews *Table of ContentsPART I - BASIC COMBINATORIAL OPTIMIZATION; PART II - HIGHER-ORDER CONNECTIONS; PART III - SEMIMODULAR OPTIMIZATION

Read more less

Book SynopsisPraise for the First EditionLuck, Logic, and White Lies teaches readers of all backgrounds about the insight mathematical knowledge can bring and is highly recommended reading among avid game players, both to better understand the game itself and to improve one's skills. Midwest Book ReviewThe best book I''ve found for someone new to game math is Luck, Logic and White Lies by Jörg Bewersdorff. It introduces the reader to a vast mathematical literature, and does so in an enormously clear manner. . . Alfred Wallace, Musings, Ramblings, and Things Left UnsaidThe aim is to introduce the mathematics that will allow analysis of the problem or game. This is done in gentle stages, from chapter to chapter, so as to reach as broad an audience as possible . . . Anyone who likes games and has a taste for analytical thinking will enjoy this book. Peter Fillmore, CMS NotesLuck, Logic, and Trade Review"The book presents mathematical explanation of problems related to playing games of chance, combinatorial and strategic games, with descriptions of their historical perspectives and recreational aspects. [. . .] The author notes that people play games investigating the unknown outcomes, in amusement and hope of winning in conditions of uncertainty caused by three possible mechanisms: chance, a large number of combinations of various moves, and different states of information among the individual players. Respectively, the games can be divided to three classes: games of chance (e.g., dice, cards, roulette) where the random processes dominate the players decisions; combinatorial games (chess, go) where the uncertainty rests on the multiplicity of possible moves; and strategic games (rock-paper-scissors) where the players’ uncertainty arises from imperfect information. Many games have mixed features (backgammon, poker, skat), and the degree of influence of the three main causes of uncertainty defines specifics of each game. The book introduces mathematical methods developed for description and solutions of games: the games of chance can be analyzed with the help of probability theory, the combinatorial games are considered by variety of methods used in particular problems, and the strategic games are studied by the game theory models for decision-making in the interactive optimizing economic processes. The book is organized in four parts containing 51 chapters on various topics.[. . .] All topics are illustrated by multiple figures and numerical tables. [. . .] It can be useful to instructors, students, and readers wishing to extend understanding of the games’ intrinsic features needed to improve ability to win in actual playing."- Stan Lipovetsky, Technometrics"As the title indicates, Bewersdorff’s book is intended to span the mathematics of games in general – not only games of chance but also including strategic and skill games. The author covers all the big categories of games – casino, tournament, and house or social games. In fact, the skill-strategic dimension of the games balanced with the chance-uncertainty dimension is the central element around which the author presents games as an important field of application of mathematics; he takes them as a good opportunity to advocate for the beauty and power of mathematics. To that point, the book is written so as to be both popular and scholarly, and these attributes are not at all inconsistent with each other for such a general topic, content, and style. [. . .] The book leaves the impression of its author’s being a skilled advocate of the unlimited power of mathematics, shown through the examples of games. Not only is mathematics able to describe the games and the way we play them, but it is entitled to address fundamental questions beyond the problem-solving aspects of games and gaming. It is mainly game theory and probability theory that grant mathematics such a virtue. [. . .] Although the chapters can mostly be read independent of each other, and the mathematical content is not systematized throughout the book, the mathematically-inclined reader can put things together to have an objective overview of one of the most interesting fields in application of mathematics – games – which themselves shaped the development of mathematics."– International Gambling Studies"The author provides a great deal of insight into a wide variety of games, all inspected from a mathematical point of view. He develops the prerequisites mathematically, so that someone with a good high-school background in mathematics and a willingness to learn will be able to build up the necessary tools for successful play. Moreover, the author’s arguments are often very detailed, so that even a novice can easily follow them. The numerous diagrams also help.I find Bewersdorff's writing to be clear and detailed. He has taken care in the presentation of the ideas. The book, the size of which has now grown to 568 pages, provides a great deal of information, and the reader can easily pick and choose topics of interest without having to absorb the entire treatise. The level of Mathematical skill needed, however, does vary greatly from chapter to chapter. When necessary, the reader can make use of previous chapters to develop the required background to proceed. To the prospective reader, good luck, and may your play be a winning one!"– The Mathematical IntelligencerThis book, successor to the first edition (2005) and translated from the 7th German edition, treats games of chance (“luck”), combinatorial games (“logic”), and games of strategy (bluff, or “white lies”). The first part develops succinctly the needed theory of probability and investigates the nature of randomness. The second part explores minimax optimization, Grundy values, Conway’s theory of games, and complexity theory. The third part is based on the fact that in a symmetric two-person zero-sum game, the players are guaranteed optimal mixed strategies; for some games, finding such strategies can be done by linear programming. This edition adds a fourth part that investigates measuring the proportion of skill in a game, with particular application to poker. The reader needs to be comfortable with algebra and summation signs, and infinite series make appearances; end-of-chapter notes and footnotes contribute further mathematical depth.– Mathematics Magazine, MAA"Exceptionally well written, organized and presented, Luck, Logic, and White Lies: The Mathematics of Games is a unique and unreservedly recommended addition to professional, community, college, and university library Game Theory & Mathematics collections."– Midwest Books Review"A great variety of games are analyzed in an accessible way. The treatment of blackjack, in particular, is superb."– Stewart Ethier, Professor Emeritus, University of Utah and author of The Doctrine of Chances: Probabilistic Aspects of Gambling "People play games for fun and for profit. To become better at a game, you need to study it. In Luck, Logic and White Lies, Jörg Bewersdorff takes you, almost imperceptibly, from the history of numerous concrete games to their mathematical analysis. This touches upon a wide range of techniques, not only in mathematics, but also in computing and psychology. If you get the hang of it, you can apply these techniques to other areas of life, such as business, economics, biology, and sociology."– Tom Verhoeff, Dept. Math & CS, Eindhoven University of TechnologyPraise for the First Edition"Luck, Logic, and White Lies teaches readers of all backgrounds about the insight mathematical knowledge can bring and is highly recommended reading among avid game players, both to better understand the game itself and to improve one's skills."– Midwest Book Review"The best book I've found for someone new to game math is Luck, Logic and White Lies by Jörg Bewersdorff. It introduces the reader to a vast mathematical literature, and does so in an enormously clear manner. . ."– Alfred Wallace, Musings, Ramblings, and Things Left Unsaid"The aim is to introduce the mathematics that will allow analysis of the problem or game. This is done in gentle stages, from chapter to chapter, so as to reach as broad an audience as possible [. . .] Anyone who likes games and has a taste for analytical thinking will enjoy this book."– Peter Fillmore, CMS NotesTable of ContentsI. Games of Chance. 1. Dice and Probability. 2. Waiting for a Double. 3. Tips on Playing the Lottery: More Equal Than Equal? 4. A Fair Division: But How? 5. The Red and the Black: The Law of Large Numbers. 6. Asymmetric Dice: Are They Worth Anything? 7. Probability and Geometry. 8. Chance and Mathematical Certainty: Are They Reconcilable? 9. In Quest of the Equiprobable. 10. Winning the Game: Probability and Value. 11. Which Die Is Best? 12. A Die Is Tested. 13. The Normal Distribution: A Race to the Finish! 14. And Not Only at Roulette: The Poisson Distribution. 15. When Formulas Become Too Complex: The Monte Carlo Method. 16. Markov Chains and the Game Monopoly. 17 Blackjack: A Las Vegas Fairy Tale. II. Combinatorial Games. 18. Which Move Is Best? 19. Chances of Winning and Symmetry. 20. A Game for Three. 21. Nim: The Easy Winner! 22. Lasker Nim: Winning Along a Secret Path. 23. Black-and-White Nim: To Each His (or Her) Own. 24. A Game with Dominoes: Have We Run Out of Space Yet? 25. Go: A Classical Game with a Modern Theory. 26. Misere Games: Loser Wins! 27. The Computer as Game Partner. 28. Can Winning Prospects Always Be Determined? 29. Games and Complexity: When Calculations Take Too Long. 30. A Good Memory and Luck: And Nothing Else? 31. Backgammon: To Double or Not to Double? 32. Mastermind: Playing It Safe. III. Strategic Games. 33. Rock–Paper–Scissors: The Enemy's Unknown Plan. 34. Minimax Versus Psychology: Even in Poker? 35. Bluffing in Poker: Can It Be Done Without Psychology? 36. Symmetric Games: Disadvantages Are Avoidable, but How? 37. Minimax and Linear Optimization: As Simple as Can Be. 38. Play It Again, Sam: Does Experience Make Us Wiser? 39. Le Her: Should I Exchange? 40. Deciding at Random: But How? 41. Optimal Play: Planning Efficiently. 42. Baccarat: Draw from a Five? 43. Three-Person Poker: Is It a Matter of Trust? 44 QUAAK! Child's Play? 45 Mastermind: Color Codes and Minimax. 46. A Car, Two Goats–and a Quizmaster. IV. Epilogue: Chance, Skill, and Symmetry. 47. A Player's Inuence and Its Limits. 48. Games of Chance and Games of Skill. 49. In Quest of a Measure. 50. Measuring the Proportion of Skill. 51. Poker: The Hotly Debated Issue.

Read more less

Book SynopsisFocused on the mathematical foundations of social media analysis, Graph-Based Social Media Analysis provides a comprehensive introduction to the use of graph analysis in the study of social and digital media. It addresses an important scientific and technological challenge, namely the confluence of graph analysis and network theory with linear algebra, digital media, machine learning, big data analysis, and signal processing. Supplying an overview of graph-based social media analysis, the book provides readers with a clear understanding of social media structure. It uses graph theory, particularly the algebraic description and analysis of graphs, in social media studies.The book emphasizes the big data aspects of social and digital media. It presents various approaches to storing vast amounts of data online and retrieving that data in real-time. It demystifies complex social media phenomena, such as information diffusion, marketing and recommendationTable of ContentsGraphs in Social and Digital Media. Mathematical Preliminaries: Graphs and Matrices. Algebraic Graph Analysis. Web Search Based on Ranking. Label Propagation and Information Diffusion in Graphs. Graph-Based Pattern Classification and Dimensionality Reduction. Matrix and Tensor Factorization with Recommender System Applications. Multimedia Social Search Based on Hypergraph Learning. Graph Signal Processing in Social Media. Big Data Analytics for Social Networks. Semantic Model Adaptation for Evolving Big Social Data. Big Graph Storage, Processing and Visualization.

Read more less

Book SynopsisThis book is devoted to efficient pairing computations and implementations, useful tools for cryptographers working on topics like identity-based cryptography and the simplification of existing protocols like signature schemes.As well as exploring the basic mathematical background of finite fields and elliptic curves, Guide to Pairing-Based Cryptography offers an overview of the most recent developments in optimizations for pairing implementation. Each chapter includes a presentation of the problem it discusses, the mathematical formulation, a discussion of implementation issues, solutions accompanied by code or pseudocode, several numerical results, and references to further reading and notes. Intended as a self-contained handbook, this book is an invaluable resource for computer scientists, applied mathematicians and security professionals interested in cryptography.Table of ContentsIntroduction. Mathematical Background. Pairings. Pairing-Friendly Elliptic Curves. Miller's Algorithm. Arithmetic of Finite Fields. Final Exponentiation. Algorithms. Software Implementation. Hardware Implementation.

Read more less

Book SynopsisThe new 6th edition of Applied Combinatorics builds on the previous editions with more in depth analysis of computer systems in order to help develop proficiency in basic discrete math problem solving. As one of the most widely used book in combinatorial problems, this edition explains how to reason and model combinatorically while stressing the systematic analysis of different possibilities, exploration of the logical structure of a problem, and ingenuity. Although important uses of combinatorics in computer science, operations research, and finite probability are mentioned, these applications are often used solely for motivation. Numerical examples involving the same concepts use more interesting settings such as poker probabilities or logical games. This book is designed for use by students with a wide range of ability and maturity (sophomores through beginning graduate students). The stronger the students, the harder the exercises that can be assigned. The booTable of ContentsPrelude xi Part One Graph Theory 1 Chapter 1 Elements of Graph Theory 3 1.1 Graph Models 3 1.2 Isomorphism 14 1.3 Edge Counting 24 1.4 Planar Graphs 31 1.5 Summary and References 44 Supplementary Exercises 45 Chapter 2 Covering Circuits and Graph Coloring 49 2.1 Euler Cycles 49 2.2 Hamilton Circuits 56 2.3 Graph Coloring 68 2.4 Coloring Theorems 77 2.5 Summary and References 86 Supplement: Graph Model for Instant Insanity 87 Supplement Exercises 92 Chapter 3 Trees and Searching 93 3.1 Properties of Trees 93 3.2 Search Trees and Spanning Trees 103 3.3 The Traveling Salesperson Problem 113 3.4 Tree Analysis of Sorting Algorithms 121 3.5 Summary and References 125 Chapter 4 Network Algorithms 127 4.1 Shortest Paths 127 4.2 Minimum Spanning Trees 131 4.3 Network Flows 135 4.4 Algorithmic Matching 153 4.5 The Transportation Problem 164 4.6 Summary and References 174 Part Two Enumeration 177 Chapter 5 General Counting Methods for Arrangements and Selections 179 5.1 Two Basic Counting Principles 179 5.2 Simple Arrangements and Selections 189 5.3 Arrangements and Selections with Repetitions 206 5.4 Distributions 214 5.5 Binomial Identities 226 5.6 Summary and References 236 Supplement: Selected Solutions to Problems in Chapter 5 237 Chapter 6 Generating Functions 249 6.1 Generating Function Models 249 6.2 Calculating Coefficients of Generating Functions 256 6.3 Partitions 266 6.4 Exponential Generating Functions 271 6.5 A Summation Method 277 6.6 Summary and References 281 Chapter 7 Recurrence Relations 283 7.1 Recurrence Relation Models 283 7.2 Divide-and-Conquer Relations 296 7.3 Solution of Linear Recurrence Relations 300 7.4 Solution of Inhomogeneous Recurrence Relations 304 7.5 Solutions with Generating Functions 308 7.6 Summary and References 316 Chapter 8 Inclusion–Exclusion 319 8.1 Counting with Venn Diagrams 319 8.2 Inclusion–Exclusion Formula 328 8.3 Restricted Positions and Rook Polynomials 340 8.4 Summary and Reference 351 Part Three Additional Topics 353 Chapter 9 Polya’s Enumeration Formula 355 9.1 Equivalence and Symmetry Groups 355 9.2 Burnside’s Theorem 363 9.3 The Cycle Index 369 9.4 Polya’s Formula 375 9.5 Summary and References 382 Chapter 10 Games with Graphs 385 10.1 Progressively Finite Games 385 10.2 Nim-Type Games 393 10.3 Summary and References 400 Postlude 401 Appendix 415 A.1 Set Theory 415 A.2 Mathematical Induction 420 A.3 A Little Probability 423 A.4 The Pigeonhole Principle 427 A.5 Computational Complexity and NP-Completeness 430 Glossary of Counting and Graph Theory Terms 435 Bibliography 439 Solutions To Odd-Numbered Problems 441 Index 475

Read more less

Book SynopsisThe material has been extensively class-tested for over ten years at both the author's own university and other institutions. The book is uniquely organized into two main sections, one on Fibonacci Numbers and one on Catalan Numbers, each containing subsections that explore related topics in intricate detail.Table of ContentsPreface xi Part One The Fibonacci Numbers 1. Historical Background 3 2. The Problem of the Rabbits 5 3. The Recursive Definition 7 4. Properties of the Fibonacci Numbers 8 5. Some Introductory Examples 13 6. Compositions and Palindromes 23 7. Tilings: Divisibility Properties of the Fibonacci Numbers 33 8. Chess Pieces on Chessboards 40 9. Optics, Botany, and the Fibonacci Numbers 46 10. Solving Linear Recurrence Relations: The Binet Form for Fn 51 11. More on α and β: Applications in Trigonometry, Physics, Continued Fractions, Probability, the Associative Law, and Computer Science 65 12. Examples from Graph Theory: An Introduction to the Lucas Numbers 79 13. The Lucas Numbers: Further Properties and Examples 100 14. Matrices, The Inverse Tangent Function, and an Infinite Sum 113 15. The gcd Property for the Fibonacci Numbers 121 16. Alternate Fibonacci Numbers 126 17. One Final Example? 140 Part Two The Catalan Numbers 18. Historical Background 147 19. A First Example: A Formula for the Catalan Numbers 150 20. Some Further Initial Examples 159 21. Dyck Paths, Peaks, and Valleys 169 22. Young Tableaux, Compositions, and Vertices and Arcs 183 23. Triangulating the Interior of a Convex Polygon 192 24. Some Examples from Graph Theory 195 25. Partial Orders, Total Orders, and Topological Sorting 205 26. Sequences and a Generating Tree 211 27. Maximal Cliques, a Computer Science Example, and the Tennis Ball Problem 219 28. The Catalan Numbers at Sporting Events 226 29. A Recurrence Relation for the Catalan Numbers 231 30. Triangulating the Interior of a Convex Polygon for the Second Time 236 31. Rooted Ordered Binary Trees, Pattern Avoidance, and Data Structures 238 32. Staircases, Arrangements of Coins, The Handshaking Problem, and Noncrossing Partitions 250 33. The Narayana Numbers 268 34. Related Number Sequences: The Motzkin Numbers, The Fine Numbers, and The Schröder Numbers 282 35. Generalized Catalan Numbers 290 36. One Final Example? 296 Solutions for the Odd-Numbered Exercises 301 Index 355

Read more less

Book SynopsisContains a wealth of information previously scattered in research journals, conference proceedings and technical reports. Identifies more than 200 unsolved problems. Every problem is stated in a self-contained, extremely accessible format, followed by comments on its history, related results and literature.Table of ContentsPlanar Graphs. Graphs on Higher Surfaces. Degrees. Critical Graphs. The Conjectures of Hadwiger and Hajos. Sparse Graphs. Perfect Graphs. Geometric and Combinatorial Graphs. Algorithms. Constructions. Edge Colorings. Orientations and Flows. Chromatic Polynomials. Hypergraphs. Infinite Chromatic Graphs. Miscellaneous Problems. Indexes.

Read more less

Book SynopsisDescribes various analytical techniques and systems for the development, validation, quality control, purification, and physicochemical testing of combinatorial libraries. This book provides coverage of applications of Nuclear Magnetic Resonance (NMR), liquid chromatography/mass spectrometry (LC/MS), and Fourier Transform Infrared (FTIR).Trade Review"…a timely and valuable volume that would be an excellent addition to university libraries and the collections of individuals…" (E-STREAMS, February 2005) "...a useful book for chemists entering the field from either analytical or synthetic organic chemistry backgrounds.” (Angewandte Chemie International Edition, September 6, 2004) "This useful volume is a worthwhile addition to institute libraries as well as to the libraries students and researchers who are working in analytical chemistry, medicinal chemistry, organic chemistry, biotechnology…" (Energy Sources, August 2004)Table of ContentsPreface. Contributors. PART I: ANALYSIS FOR FEASIBILITY AND OPTIMIZATION OF LIBRARY SYNTHESIS. Chapter 1. Quantitative Analysis in Organic Synthesis with NMR (L. Lucas & C. Larive). Chapter 2. 19F Gel-phase NMR Spectroscopy for Reaction Monitoring and Quantification of Resin Loading (J. Salvino). Chapter 3. The Application of Single-Bead FTIR and Color Test for Reaction Monitoring and Building Block Validation in Combinatorial Library Sysnthesis(J. Cournoyer, et al.). Chapter 4. HR-MAS NMR Analysis of Compounds Attached to Polymer Supports (M. Guinó & Y. de Miguel). Chapter 5. Multivariate Tools for Real-Time Monitoring and Optimization of Combinatorial Materials and Process Conditions (R. Potyrailo, et al.). Chapter 6. Mass Spectrometry and Soluble Polymeric Supports (C. Enjalbal, et al.). PART II: HIGH-THROUGHPUT ANALYSIS FOR LIBRARY QUALITY CONTROL. Chapter 7. High-Throughput NMR Techniques for Combinatorial Chemical Library Analysis (T. Hou & D. Raftery). Chapter 8. Micellar Electrokinetic Chromatography as a Tool for Combinatorial Chemistry Analysis: Theory and Applications (P. Simms). Chapter 9. Characterization of Split-Pool Encoded Combinatorial Libraries (J. Zhang & W. Fitch). PART III: HIGH-THROUGHPUT PURIFICATION TO IMPROVE LIBRARY QUALITY. Cha pter 10. Strategies and Methods for Purifying Organic Compounds and Combinatorial Libraries (J. Zhao, et al.). Chapter 11. HTP of Combinatorial Chemistry Libraries (J. Hochlowski). Chapter 12. Practical HPLC in High Throughput Analysis and Purification (H. Gumm & R. God). PART IV: ANALYSIS FOR COMPOUND STABILITY AND DRUGABILITY. Chapter 13. Organic Compound Stability in Large, Diverse Phatmaceutical Screening Collection (K. Morand & X. Cheng). Chapter 14. Quartz Crystal Microbalance in Biomolecular Recognition (M. Tseng, et al.). Chapter 15. High-Throughput Physicochemical Profiling: Potential and Limitations (B. Faller). Chapter 16. Solubility in the Design of Combinatorial Libraries (C. Lipinski). Chapter 17. High-Throughput Determination of Log D Values by LC/MS Method (J. Villena, et al.). Index.

Read more less

Book SynopsisComplete coverage of the prediction approach to survey sampling in a single resource Prediction theory has been extremely influential in survey sampling for nearly three decades, yet research findings on this model-based approach are scattered in disparate areas of the statistical literature.Trade Review"Valliant...is joined...to dispel the perception of dichotomy between mainstream statistics...and survey sampling..." (SciTech Book News, Vol. 24, No. 4, December 2000) "The vast majority of the book is devoted to prediction of a population mean or total, and as such it forms a cohesive and comprehensive treatment of the subject." (Mathematical Reviews, Issue 2001j) "A highly recommended book which is an essential read for all research workers in this area." (Short Book Reviews - Publication of the Int. Statistical Institute, December 2001) "This book is a welcome addition to the subject of survey sampling." (Zentralblatt MATH, Vol. 964, 2001/14)Table of ContentsIntroduction to Prediction Theory. Prediction Theory Under the General Linear Model. Bias-Robustness. Robustness and Efficiency. Variance Estimation. Stratified Populations. Models with Qualitative Auxiliaries. Clustered Populations. Robust Variance Estimation in Two-Stage Cluster Sampling. Alternative Variance Estimation Methods. Special Topics and Open Questions. Appendices. Bibliography. Answers to Select Exercises. Indexes.

Read more less

Book SynopsisDiscrete optimization models are used to tackle a wide variety of problems in many fields, including operations research, management science, engineering, and mathematics. Written by two internationally recognized integer programming experts, this book presents the mathematical foundations, theory, and algorithms of discrete optimization methods.Table of ContentsFOUNDATIONS. The Scope of Integer and Combinatorial Optimization. Linear Programming. Graphs and Networks. Polyhedral Theory. Computational Complexity. Polynomial-Time Algorithms for Linear Programming. Integer Lattices. GENERAL INTEGER PROGRAMMING. The Theory of Valid Inequalities. Strong Valid Inequalities and Facets for Structured Integer Programs. Duality and Relaxation. General Algorithms. Special-Purpose Algorithms. Applications of Special- Purpose Algorithms. COMBINATORIAL OPTIMIZATION. Integral Polyhedra. Matching. Matroid and Submodular Function Optimization. References. Indexes.

Read more less

Book SynopsisCombinatorics deals with ways of arranging and distributing mathematical objects, and involves ideas from geometry, algebra and analysis. The theory has broad applications, including codes, circuit design and algorithm complexity. Graph theory, enumeration, external problems, projective geometry, designs, colourings and codes, amongst others, are dealt with in a unified way.Trade Review'Both for the professional with a passing interest in combinatorics and for the students for whom it is primarily intended, this is a valuable book.' The Times Higher Education Supplement'… it will no doubt become a standard choice among the many texts on combinatorics … fascinating … it is highly recommended reading.' Dieter Jungnichel, Zentralblatt MATH'This well written textbook can be highly recommended to any student of combinatorics and, because of its breadth, has many new things to tell researchers in the field also.' EMS'This is a fascinating introduction to almost all aspects of combinatorics. Plenty of interesting problems, concrete examples, useful notes and references complement the main text. This book can be highly recommended to everyone interested in combinatorics.' Monatshefe für Mathematik'… becoming a modern classic … every good student should progress to this book at some stage: it is a wonderful source of elegant proofs and tantalising examples. No-one will find it easy, but every budding or established combinatorialist will be enriched by it … This text is unashamedly and impressively mathematical; it will challenge and inform every reader and is a very significant achievement.' The Mathematical GazetteTable of ContentsPreface; 1. Graphs; 2. Trees; 3. Colorings of graphs and Ramsey's theorem; 4. Turán's theorem and extremal graphs; 5. Systems of distinct representatives; 6. Dilworth's theorem and extremal set theory; 7. Flows in networks; 8. De Bruijn sequences; 9. The addressing problem for graphs; 10. The principle of inclusion and exclusion: inversion formulae; 11. Permanents; 12. The Van der Waerden conjecture; 13. Elementary counting: Stirling numbers; 14. Recursions and generating functions; 15. Partitions; 16. (0,1)-matrices; 17. Latin squares; 18. Hadamard matrices, Reed-Muller codes; 19. Designs; 20. Codes and designs; 21. Strongly regular graphs and partial geometries; 22. Orthogonal Latin squares; 23. Projective and combinatorial geometries; 24. Gaussian numbers and q-analogues; 25. Lattices and Möbius inversion; 26. Combinatorial designs and projective geometries; 27. Difference sets and automorphisms; 28. Difference sets and the group ring; 29. Codes and symmetric designs; 30. Association schemes; 31. Algebraic graph theory: eigenvalue techniques; 32. Graphs: planarity and duality; 33. Graphs: colorings and embeddings; 34. Electrical networks and squared squares; 35. Pólya theory of counting; 36. Baranyai's theorem; Appendices; Name index; Subject index.

Read more less

Book SynopsisA treatment of cutting-edge research on the distribution modulo one of sequences and related topics, much of it from the last decade. There are numerous exercises to aid student understanding of the topic, and researchers will appreciate the notes at the end of each chapter, extensive references and open problems.Trade Review"The reader may learn a lot from this book about various techniques used i this subject over many years (e.g., classical and metrical Diophantine approximation, combinatorics on words) and, in addition, find the proofs of some very recent results." - Arturas Dubickas, Mathematical ReviewsTable of Contents1. Distribution modulo one; 2. On the fractional parts of powers of real numbers; 3. On the fractional parts of powers of algebraic numbers; 4. Normal numbers; 5. Further explicit constructions of normal and non-normal numbers; 6. Normality to different bases; 7. Diophantine approximation and digital properties; 8. Digital expansion of algebraic numbers; 9. Continued fraction expansions and beta-expansions; 10. Conjectures and open problems; A. Combinatorics on words; B. Some elementary lemmata; C. Measure theory; D. Continued fractions; E. Diophantine approximation; F. Recurrence sequences; References; Index.

Read more less

Book SynopsisThis is an introductory text for graduate students, or anyone using the theory of graph spectra, that assumes only a little knowledge of graph theory and linear algebra. The authors include developments in the field, exercises, spectral data, detailed proofs and an extensive bibliography.Table of ContentsPreface; 1. Introduction; 2. Graph operations and modifications; 3. Spectrum and structure; 4. Characterizations by spectra; 5. Structure and one eigenvalue; 6. Spectral techniques; 7. Laplacians; 8. Additional topics; 9. Applications; Appendix; Bibliography; Index of symbols; Index.

Read more less

Book SynopsisCombinatorica, an extension to the popular computer algebra system Mathematica®, is the most comprehensive software available for teaching and research applications of discrete mathematics. This definitive reference/user's guide provides examples of all 450 Combinatorica functions in action, along with tutorial text on the mathematical and algorithmic theory.Trade ReviewReview of the hardback: 'This book is the definite reference guide to Combinatorica … it is more than just a reference since it has all the necessary theory to comprehend the concepts … It is a very readable edition full of graphical and stimulating approaches to combinatorics and graph theories … This is a great resource for the acknowledgment of beautiful patterns and important properties of graphs and other combinatorial objects … This book is highly recommended. it is well organized, and readable textbook for beginners and intermediate students.' Leonardo On-lineTable of Contents1. Combinatorica: an explorer's guide; 2. Permutations and combinations; 3. Algebraic combinatorics; 4. Partitions, compositions and Young tableaux; 5. Graph representation; 6. Generating graphs; 7. Properties of graphs; 8. Algorithmic graph theory.

Read more less

Book SynopsisAdditive combinatorics is the theory of counting additive structures in sets. This theory has seen exciting developments and dramatic changes in direction in recent years thanks to its connections with areas such as number theory, ergodic theory and graph theory. This graduate-level 2006 text will allow students and researchers easy entry into this fascinating field. Here, the authors bring together in a self-contained and systematic manner the many different tools and ideas that are used in the modern theory, presenting them in an accessible, coherent, and intuitively clear manner, and providing immediate applications to problems in additive combinatorics. The power of these tools is well demonstrated in the presentation of recent advances such as SzemerÃdi's theorem on arithmetic progressions, the Kakeya conjecture and Erdos distance problems, and the developing field of sum-product estimates. The text is supplemented by a large number of exercises and new results.Trade Review'The book under review is a vital contribution to the literature, and it has already become required reading for a new generation of students as well as for experts in adjacent areas looking to learn about additive combinatorics. … This was very much a book that needed to be written at the time it was, and the authors are to be highly commended for having done so in such an effective way.' Bulletin of the American Mathematical Society'The book gathers diverse important techniques used in additive combinatorics, and its main advantage is that it is written in a very readable and easy to understand style. The authors try very successfully to develop all the necessary background material … [which] makes the book useful not only to graduate students, but also to researchers who are interested to learn more about the variety of diverse tools and ideas applied in this fascinating subject.' Zentralblatt MATHTable of ContentsPrologue; 1. The probabilistic method; 2. Sum set estimates; 3. Additive geometry; 4. Fourier-analytic methods; 5. Inverse sum set theorems; 6. Graph-theoretic methods; 7. The Littlewood–Offord problem; 8. Incidence geometry; 9. Algebraic methods; 10. Szemerédi's theorem for k = 3; 11. Szemerédi's theorem for k > 3; 12. Long arithmetic progressions in sum sets; Bibliography; Index.

Read more less

Book SynopsisCombinatorics is a book whose main theme is the study of subsets of a finite set. It gives a thorough grounding in the theories of set systems and hypergraphs, while providing an introduction to matroids, designs, combinatorial probability and Ramsey theory for infinite sets. The gems of the theory are emphasized: beautiful results with elegant proofs. The book developed from a course at Louisiana State University and combines a careful presentation with the informal style of those lectures. It should be an ideal text for senior undergraduates and beginning graduates.Table of ContentsFrontispiece; Preface; 1. Notation; 2. Representing sets; 3. Sperner systems; 4. The Littlewood - Offord problem; 5. Shadows; 6. Random sets; 7. Intersecting hypergraphs; 8. The Turán problem; 9. Saturated hypergraphs; 10. Well-separated systems; 11. Helly families; 12. Hypergraphs with a given number of disjoint edges; 13. Intersecting families; 14. Factorizing complete hypergraphs; 15. Weakly saturated hypergraphs; 16. Isoperimetric problems; 17. The trace of a set system; 18. Partitioning sets of vectors; 19. The four functions theorem; 20. Infinite ramsey theory; References; Index.

Read more less

Book SynopsisIncluding many algorithms described in simple terms, this book stresses common techniques (such as generating functions and recursive construction) that underlie the great variety of subject matter.Trade Review"Cameron covers an impressive amount of material in a relatively small space...an outstanding supplement to other texts..." M. Henle, Choice"...used as a text at the senior or graduate level and is an excellent reference....The range of topics is very good." The UMAP JournalTable of ContentsPreface; 1. What is combinatorics?; 2. On numbers and counting; 3. Subsets, partitions, permutations; 4. Recurrence relations and generating functions; 5. The principle of inclusion and exclusion; 6. Latin squares and SDRs; 7. Extremal set theory; 8. Steiner triple theory; 9. Finite geometry; 10. Ramsey's theorem; 11. Graphs; 12. Posets, lattices and matroids; 13. More on partitions and permutations; 14. Automorphism groups and permutation groups; 15. Enumeration under group action; 16. Designs; 17. Error-correcting codes; 18. Graph colourings; 19. The infinite; 20. Where to from here?; Answers to selected exercises; Bibliography; Index.

Read more less

Book SynopsisA thoroughly revised and updated version of the popular textbook on abstract algebra. The material is introduced with clarity and reference to problems and concepts that students will easily understand. With many examples and exercises, it will serve as the ideal introduction to this important and ubiquitous subject.Trade Review'This book is a lucid introduction to the subject which would make a suitable text for a one-semester course in the undergraduate program. It is very useful to everybody who want to understand the concepts of algebra and group theory and their relation to applications, particularly in computer science.' Zentralblatt MATHTable of Contents1. Number theory; 2. Sets, functions and relations; 3. Logic and mathematical argument; 4. Examples of groups; 5. Group theory and error-correcting codes; 6. Polynomials.

Read more less

Book SynopsisThe aim of this book is to develop the combinatorics of Young tableaux and to show them in action in the algebra of symmetric functions, representations of the symmetric and general linear groups, and the geometry of flag varieties. The first part of the book is a self-contained presentation of the basic combinatorics of Young tableaux, including the remarkable constructions of 'bumping' and 'sliding', and several interesting correspondences. In Part II these results are used to study representations with geometry on Grassmannians and flag manifolds, including their Schubert subvarieties, and the related Schubert polynomials. Much of this material has never appeared in book form.There are numerous exercises throughout, with hints or answers provided. Researchers in representation theory and algebraic geometry as well as in combinatorics will find Young Tableaux interesting and useful; students will find the intuitive presentation easy to follow.Table of ContentsPart I. Calculus Of Tableux: 1. Bumping and sliding; 2. Words: the plactic monoid; 3. Increasing sequences: proofs of the claims; 4. The Robinson-Schensted-Knuth Correspondence; 5. The Littlewood-Richardson rule; 6. Symmetric polynomials; Part II. Representation Theory: 7. Representations of the symmetric group; 8. Representations of the general linear group; Part III. Geometry: 9. Flag varieties; 10. Schubert varieties and polynomials; Appendix A; Appendix B.

Read more less

Book SynopsisCombinatorics on words, or finite sequences, is a field which grew simultaneously within disparate branches of mathematics such as group theory and probability. This classic volume is the first to attempt to present a thorough treatment of this theory.Trade Review' … a thorough treatment of the theory of combinatorics.' Monatshefte für Mathematik'Since the first edition almost fifteen years ago, a new generation of young mathematicians has grown up on reading this book and solving the problems at the end of each chapter, thus deepening the understanding of the results read, analyzing special cases and proving additional results. Furthermore, this monograph is an excellent reference book for those working in this area of mathematics.' Acta Sci. Math.'This is an excellent book, essential for anybody working in the field. Although written by several authors, who constitute the collective author M. Lothaire, the book makes a surprisingly compact impression. As already mentioned, it has all prerequisites for an important reference tool.' EMSTable of Contents1. Words D. Perrin; 2. Square free words and idempotent semigroups J. Berstel and C. Reutenauer; 3. Van der Waerden's theorem J. E. Pin; 4. Repetitive mappings and morphisms G. Pirillo; 5. Factorizations of free monoids D. Perrin; 6. Subwords J. Sakarovitch and I. Simon; 7. Unavoidable irregularities in words M. P. Schützenberger; 8. The critical factorization theorem Choffrut; 9. Equations in words; 10. Rearrangements of words D. Foata; 11. Words and trees R. Cori.

Read more less

Book SynopsisAn introduction to recent developments in algebraic combinatorics and an illustration of how research in mathematics actually progresses.Trade Review'Proofs and Confirmations is one of the most brilliant examples of mathematical exposition that I have encountered, in many years of reading the same. This is not for the faint-hearted, nor is Proofs and Confirmations a book that can be read in an easy chair, like a novel; it demands active participation by the reader. But Bressoud rewards such readers with a panorama of combinatorics today and with renewed awe at the human ability to penetrate the deeply hidden mysteries of pure mathematics.' Herbert S. Wilf, Science'The unexpected twists and turns will hardly be matched in any novel - this book allows us all to share in the excitement … a brilliant book.' Alun O. Morris'I strongly recommend the book as an account of a remarkable mathematical development.' P. J. Cameron, Proceedings of the Edinburgh Mathematical Society'This is an excellent book which can be recommended without hesitation, not only to specialists in the field, but to any mathematician with time to read something interesting and nicely written.' EMSTable of Contents1. The conjecture; 2. Fundamental structures; 3. Lattice paths and plane partitions; 4. Symmetric functions; 5. Hypergeometric series; 6. Explorations; 7. Square ice.

Read more less

Book SynopsisThe rapidly expanding area of algebraic graph theory uses two different branches of algebra to explore various aspects of graph theory: linear algebra (for spectral theory) and group theory (for studying graph symmetry). These areas have links with other areas of mathematics, such as logic and harmonic analysis, and are increasingly being used in such areas as computer networks where symmetry is an important feature. Other books cover portions of this material, but this book is unusual in covering both of these aspects and there are no other books with such a wide scope. Peter J. Cameron, internationally recognized for his substantial contributions to the area, served as academic consultant for this volume, and the result is ten expository chapters written by acknowledged international experts in the field. Their well-written contributions have been carefully edited to enhance readability and to standardize the chapter structure, terminology and notation throughout the book. To help thTrade Review"...highly suitable for an advanced course or seminar series, but should also serve as a useful resource for mathematicians who need to find out about one or more of the topics presented, and it complements other recent texts on a subject of increasing interests and significance." -Mathematical Reviews, Marston ConderTable of ContentsForeword Peter J. Cameron; Introduction; 1. Eigenvalues of graphs Michael Doob; 2. Graphs and matrices Richard A. Brualdi and Bryan L. Shader; 3. Spectral graph theory Dragos Cvetkovic and Peter Rowlinson; 4. Graph Laplacians Bojan Mohar; 5. Automorphism groups Peter J. Cameron; 6. Cayley graphs Brian Alspach; 7. Finite symmetric graphs Cheryle E. Praeger; 8. Strongly regular graphs Peter J. Cameron; 9. Distance-transitive graphs Arjeh M. Cohen; 10. Computing with graphs and groups Leonard H. Soicher.

Read more less

Book SynopsisThis book presents a modern, geometric approach to group theory. An accessible and engaging approach to the subject, with many exercises and figures to develop geometric intuition. Ideal for advanced undergraduates, it will also interest graduate students and researchers as a gentle introduction to geometric group theory.Trade Review'Meier has the rare ability to make complex concepts accessible to novices while simultaneously challenging the experienced. … With well-chosen illustrations and examples, Meier succeeds brilliantly in this unique approach.' SciTech Book News'… totally accessible to undergraduate students and would be a good textbook for an advanced undergraduate course in group theory, or a graduate course in geometric group theory.' Mathematical Review'… an excellent introduction to geometric group theory. … Carefully chosen examples are an essential part of the exposition and they really help to understand general constructions.' EMS NewsletterTable of ContentsPreface; 1. Cayley's theorems; 2. Groups generated by reflections; 3. Groups acting on trees; 4. Baumslag-Solitar groups; 5. Words and Dehn's word problem; 6. A finitely-generated, infinite, Torsion group; 7. Regular languages and normal forms; 8. The Lamplighter group; 9. The geometry of infinite groups; 10. Thompson's group; 11. The large-scale geometry of groups; Bibliography; Index.

Read more less

Book SynopsisTable of Contents*Frontmatter, pg. i*CONTENTS, pg. v*PREFACE, pg. vii*PROBLEMS IN COMBINATORIAL GROUP THEORY, pg. 3*POINCARE DUALITY GROUPS OF DIMENSION TWO ARE SURFACE GROUPS, pg. 35*HOW TO GENERALIZE ONE-RELATOR GROUP THEORY, pg. 53*GRAPHICAL THEORY OF AUTOMORPHISMS OF FREE GROUPS, pg. 79*PEAK REDUCTION AND AUTOMORPHISMS OF FREE GROUPS AND FREE PRODUCTS, pg. 107*NONSINGULAR EQUATIONS OF SMALL WEIGHT OVER GROUPS, pg. 121*GRAPH-THEORETIC LEMMA AND GROUP-EMBEDDINGS, pg. 145*THE TODD-COXETER PROCESS, USING GRAPHS, pg. 157*A SUBGROUP THEOREM FOR PREGROUPS, pg. 163*GROUPS WITH A RATIONAL CROSS-SECTION, pg. 175*ON THE RATIONAL GROWTH OF VIRTUALLY NILPOTENT GROUPS, pg. 185*SJOGREN'S THEOREM FOR DIMENSION SUBGROUPS - THE METABELIAN CASE, pg. 197*ON GROUP PRESENTATIONS, COPRODUCTS AND INVERSES, pg. 213*ON COMPLEXES DOMINATED BY A TWO-COMPLEX, pg. 221*SUBCOMPLEXES OF TWO-COMPLEXES AND PROJECTIVE CROSSED MODULES, pg. 255*LENGTH FUNCTIONS OF GROUP ACTIONS ON A-TREES, pg. 265*RESIDUAL FINITENESS FOR 3-MANIFOLDS, pg. 379*THE NIELSEN-THURSTON THEORY OF SURFACE AUTOMORPHISMS, pg. 397*WHITEHEAD GROUPS OF CERTAIN HYPERBOLIC MANIFOLDS, II, pg. 415*CHARACTERIZATION OF FINITE SUBGROUPS OF THE MAPPING-CLASS GROUP, pg. 433*A SEQUENCE OF PSEUDO-ANOSOV DIFFEOMORPHISMS, pg. 443*DEHN'S ALGORITHM REVISITED, WITH APPLICATIONS TO SIMPLE CURVES ON SURFACES, pg. 451*PATHS OF GEODESICS AND GEOMETRIC INTERSECTION NUMBERS: I, pg. 479*PATHS OF GEODESICS AND GEOMETRIC INTERSECTION NUMBERS: II, pg. 501*SELECTED PROBLEMS, pg. 545*Backmatter, pg. 552

Read more less

Book SynopsisApplies model theoretic methods to the study of certain finite permutation groups, the automorphism groups of structures for a fixed finite language with a bounded number of orbits on 4-tuples. This book treats the general case by developing analogs of the model theoretic methods of geometric stability theory.

Read more less

Book SynopsisUses the phenomenon called 'six degrees of separation' as a prelude to a more general exploration: under what conditions can a small world arise in any kind of network? This book is intended for a variety of fields, including physics and mathematics, as well as sociology, economics, and biology.Trade Review"An engaging and informative introduction."--Science "Playfully and clearly written... [Watts] uses examples adroitly, and mixes abstract theory with real-world anecdotes with superb skill... I have not enjoyed reading a book this much in a long time."--Peter Kareiva, Quarterly Review of Biology "[Small Worlds] will be seized on by those seeking a first rough map of this fascinating new mathematical land. Those entering can expect to find some amazing connections between areas of research with apparently nothing in common, such as neurology to business studies. But then, it's a small world."--Robert Matthews, New Scientist "Informally written and aimed at a wide audience, this book shows how mathematics yields new vistas on ubiquitous and seemingly familiar aspects of our world."--ChoiceTable of ContentsPREFACE xiii 1 Kevin Bacon, the Small World, and Why It All Matters 3 PART I STRUCTURE 9 2 An Overview of the Small-World Phenomenon 11 2.1 Social Networks and the Small World 11 2.1.1 A Brief History of the Small World 12 2.1.2 Difficulties with the Real World 20 2.1.3 Reframing the Question to Consider All Worlds 24 2.2 Background on the Theory of Graphs 25 2.2.1 Basic Definitions 25 2.2.2 Length and Length Scaling 27 2.2.3 Neighbourhoods and Distribution Sequences 31 2.2.4 Clustering 32 2.2.5 "Lattice Graphs" and Random Graphs 33 2.2.6 Dimension and Embedding of Graphs 39 3 Big Worlds and Small Worlds: Models of Graphs 41 3.1 Relational Graphs 42 3.1.1 a-Graphs 42 3.1.2 A Stripped-Down Model: B-Graphs 66 3.1.3 Shortcuts and Contractions: Model Invariance 70 3.1.4 Lies, Damned Lies, and (More) Statistics 87 3.2 Spatial Graphs 91 3.2.1 Uniform Spatial Graphs 93 3.2.2 Gaussian Spatial Graphs 98 3.3 Main Points in Review 100 4 Explanations and Ruminations 101 4.1 Going to Extremes 101 4.1.1 The Connected-Caveman World 102 4.1.2 Moore Graphs as Approximate Random Graphs 109 4.2 Transitions in Relational Graphs 114 4.2.1 Local and Global Length Scales 114 4.2.2 Length and Length Scaling 116 4.2.3 Clustering Coefficient 117 4.2.4 Contractions 118 4.2.5 Results and Comparisons with B-Model 120 4.3 Transitions in Spatial Graphs 127 4.3.1 Spatial Length versus Graph Length 127 4.3.2 Length and Length Scaling 128 4.3.3 Clustering 130 4.3.4 Results and Comparisons 132 4.4 Variations on Spatial and Relational Graphs 133 4.5 Main Points in Review 136 5 "It's a Small World after All": Three Real Graphs 138 5.1 Making Bacon 140 5.1.1 Examining the Graph 141 5.1.2 Comparisons 143 5.2 The Power of Networks 147 5.2.1 Examining the System 147 5.2.2 Comparisons 150 5.3 A Worm's Eye View 153 5.3.1 Examining the System 154 5.3.2 Comparisons 156 5.4 Other Systems 159 5.5 Main Points in Review 161 PART II DYNAMICS 163 6 The Spread of Infectious Disease in Structured Populations 165 6.1 A Brief Review of Disease Spreading 166 6.2 Analysis and Results 168 6.2.1 Introduction of the Problem 168 6.2.2 Permanent-Removal Dynamics 169 6.2.3 Temporary-Removal Dynamics 176 6.3 Main Points in Review 180 7 Global Computation in Cellular Automata 181 7.1 Background 181 7.1.1 Global Computation 184 7.2 Cellular Automata on Graphs 187 7.2.1 Density Classification 187 7.2.2 Synchronisation 195 7.3 Main Points in Review 198 8 Cooperation in a Small World: Games on Graphs 199 8.1 Background 199 8.1.1 The Prisoner's Dilemma 200 8.1.2 Spatial Prisoner's Dilemma 204 8.1.3 N-Player Prisoner's Dilemma 206 8.1.4 Evolution of Strategies 207 8.2 Emergence of Cooperation in a Homogeneous Population 208 8.2.1 Generalised Tit-for-Tat 209 8.2.2 Win-Stay, Lose-Shift 214 8.3 Evolution of Cooperation in a Heterogeneous Population 219 8.4 Main Points in Review 221 9 Global Synchrony in Populations of Coupled Phase Oscillators 223 9.1 Background 223 9.2 Kuramoto Oscillators on Graphs 228 9.3 Main Points in Review 238 10 Conclusions 240 NOTES 243 BIBLIOGRAPHY 249 INDEX 257

Read more less

Book SynopsisCovers such topics as: combinatorial arguments and identities, generating functions, graph theory, recursive relations, sums and products, probability, number theory, polynomials, theory of equations, complex numbers in geometry, algorithmic proofs, combinatorial and advanced geometry, functional equations and classical inequalities.Trade ReviewFrom the reviews: "Andreescu's 51 'introductory problems' and 51 'advanced problems,' all novel, would nicely supplement any university course in combinatorics or discrete mathematics. This volume contains detailed solutions, sometimes multiple solutions, for all the problems, and some solutions offer additional twists for further thought . . . " —CHOICE "Another excellent effort towards building combinatorial skills especially for students engaged in mathematical competitions is presented in this book through 102 selected Combinatorial problems." —ZENTRALBLATT MATH "Each solution is given in full, and often with alternative versions as well. Some solutions introduce standard combinatorial tools like inclusion-exclusion, generating functions, and graphs. Others stray into probability, number theory, complex numbers, inequalities and functional equations. The book will be useful for teachers looking for challenging problems for able students and for those preparing for Olympiads." —The MATHEMATICAL GAZETTE "This book contains 102 highly selected combinatorial problems used in the training and testing of the USA International Mathematical Olympiad team. Half of the problems are introductory, while the rest are more difficult. All problems have complete solutions. . . It is not a collection of very difficult, impenetrable questions. Instead, the book gradually builds students' combinatorial skills and techniques. It aims to broaden a student's view of mathematics in perparation for possible participation in mathematical competitions." —IASI POLYTECHNIC MAGAZINE "Both of the two authors serves as a coach of the USA International Mathematical Olympiad (IMO) Team for several years. … the book gradually builds students’ combinatorial skills and techniques. It aims to broaden a student’s view of mathematics in preparation for possible participation in mathematical competitions. … this is a book for problem-solvers. … The present collection of problems and the presented solutions are carefully designed to develop the readers’ problem-solving abilities. … Have fun working on them!" (Péter Hajnal, Acta Scientiarum Mathematicarum, Vol. 69, 2003)Table of ContentsPreface and Introduction * Acknowledgments * Abbreviations and Notations * Introductory Problems * Advanced Problems * Solutions to Introductory Problems * Solutions to Advanced Problems * Glossary * Further Reading

Read more less