Discrete mathematics Books

Book SynopsisThe first part of this book introduces the Schubert Cells and varieties of the general linear group Gl (k^(r+1)) over a field k according to Ehresmann geometric way. Smooth resolutions for these varieties are constructed in terms of Flag Configurations in k^(r+1) given by linear graphs called Minimal Galleries. In the second part, Schubert Schemes, the Universal Schubert Scheme and their Canonical Smooth Resolution, in terms of the incidence relation in a Tits relative building are constructed for a Reductive Group Scheme as in Grothendieck''s SGAIII. This is a topic where algebra and algebraic geometry, combinatorics, and group theory interact in unusual and deep ways.Table of ContentsGrassmannians and Flag Varieties. Schubert Cell Decomposition of Grassmannians and Flag Varieties. Resolution of Singularities of a Schubert Variety. The Singular Locus of a Schubert Variety. The Flag Complex. Configurations and Galleries Varieties. Configurations Varieties as Galleries Varieties. The Coxeter Complex. Minimal Generalized Galleries in a Coxeter Complex. Minimal Generalized Galleries in a Reductive Group Building. Parabolic Subgroups in a Reductive Group Scheme. Associated Schemes to the Relative Building. Incidence Type Schemes of the Relative Building. Smooth Resolutions of Schubert Schemes. Contracted Products and Galleries Configurations Schemes. Functoriality of Schubert Schemes Smooth Resolutions and Base Changes. About the Coxeter Complex. Generators and Relations and the Building of a Reductive Group.

Read more less

Book SynopsisA Bridge to Higher Mathematics is more than simply another book to aid the transition to advanced mathematics. The authors intend to assist students in developing a deeper understanding of mathematics and mathematical thought. The only way to understand mathematics is by doing mathematics. The reader will learn the language of axioms and theorems and will write convincing and cogent proofs using quantifiers. Students will solve many puzzles and encounter some mysteries and challenging problems. The emphasis is on proof. To progress towards mathematical maturity, it is necessary to be trained in two aspects: the ability to read and understand a proof and the ability to write a proof. The journey begins with elements of logic and techniques of proof, then with elementary set theory, relations and functions. Peano axioms for positive integers and for natural numbers follow, in particular mathematical and other forms of induction. Next Trade ReviewThis is one of the shorter books for a course that introduces students to the concept of mathematical proofs. The brevity is due to the "bare-bones" nature of the treatment. The number of topics covered, the number of examples, and the number of exercises are not smaller than what appears in competing textbooks; what is shorter is the text that one finds between theorems, lemmas, examples, and exercises. Besides the topics found in similar textbooks (i.e., proof techniques, logic, set theory, relations, and functions), there are chapters on (very) elementary number theory, combinatorial counting techniques, and Peano axioms on the set of positive integers. Several chapters are devoted to the construction of various kinds of numbers, such as integers, rationals, real numbers, and complex numbers. Answers to around half the exercises are included at the end of the book, and a few have complete solutions. This reviewer finds the book more enjoyable than the average competing textbook. --M. Bona, University of FloridaTable of ContentsElements of logicTrue and false statementsLogical connectives and truth tablesLogical equivalenceQuantifiersProofs: Structures and strategiesAxioms, theorems and proofsDirect proofContrapositive proofProof by equivalent statementsProof by casesExistence proofsProof by counterexampleProof by mathematical inductionElementary Theory of Sets. FunctionsAxioms for set theoryInclusion of setsUnion and intersection of setsComplement, difference and symmetric difference of setsOrdered pairs and the Cartersian productFunctionsDefinition and examples of functionsDirect image, inverse imageRestriction and extension of a functionOne-to-one and onto functionsComposition and inverse functions*Family of sets and the axiom of choiceRelationsGeneral relations and operations with relationsEquivalence relations and equivalence classesOrder relations*More on ordered sets and Zorn's lemmaAxiomatic theory of positive integersPeano axioms and additionThe natural order relation and subtractionMultiplication and divisibilityNatural numbersOther forms of inductionElementary number theoryAboslute value and divisibility of integersGreatest common divisor and least common multipleIntegers in base 10 and divisibility testsCardinality. Finite sets, infinite setsEquipotent setsFinite and infinite setsCountable and uncountable setsCounting techniques and combinatoricsCounting principlesPigeonhole principle and parityPermutations and combinationsRecursive sequences and recurrence relationsThe construction of integers and rationals Definition of integers and operationsOrder relation on integersDefinition of rationals, operations and orderDecimal representation of rational numbersThe construction of real and complex numbersThe Dedekind cuts approachThe Cauchy sequences approachDecimal representation of real numbersAlgebraic and transcendental numbersComples numbersThe trigonometric form of a complex number

Read more less

Book SynopsisThe book reviews inequalities for weighted entry sums of matrix powers. Applications range from mathematics and CS to pure sciences. It unifies and generalizes several results for products and powers of sesquilinear forms derived from powers of Hermitian, positive-semidefinite, as well as nonnegative matrices. It shows that some inequalities are valid only in specific cases. How to translate the Hermitian matrix results into results for alternating powers of general rectangular matrices? Inequalities that compare the powers of the row and column sums to the row and column sums of the matrix powers are refined for nonnegative matrices. Lastly, eigenvalue bounds and derive results for iterated kernels are improved.Table of ContentsIntroduction. Notation and Basic Facts. Motivation. Diagonalization and Spectral Decomposition. Undirected Graphs / Hermitian Matrices. General Results. Restricted Graph Classes. Directed Graphs / Nonsymmetric. Walks and Alternating Walks in Directed Graphs. Powers of Row and Column Sums. Applications. Bounds for the Largest Eigenvalue. Iterated Kernels. Conclusion. Bibliography. Index.

Read more less

Book SynopsisHighly technical monograph in which the authors, writing on the basis of their own recent research for the benefit of expert readers, describe a general theory of stochastic integration equations. First published in 1990.Table of ContentsIntroduction, Nonlinear Stochastic Integrators, Stochastic Calculus, Dependence on the initial Conditions and Flows.

Read more less

Book SynopsisThis book presents articles of L.V. Kantorovich on the descriptive theory of sets and function and on functional analysis in semi-ordered spaces, to demonstrate the unity of L.V. Kantorovich's creative research. It also includes two papers on the extension of Hilbert space.

Read more less

Book SynopsisDas Buch bietet einen idealen Einstieg in die Mathematik: Jedes Kapitel beginnt mit konkreten und vertrauten Begriffen oder Situationen. Davon ausgehend abstrahieren die Autoren schrittweise bis sie zu den Begriffen der modernen Mathematik kommen. Dabei wird auf Anwendungen mit einem engen Bezug zur Informatik wie etwa Routenplaner oder Codierungstheorie eingegangen. Das Buch ist so angelegt, dass jeder der drei Teile (Algebra, Analysis und Diskrete Strukturen) unabhängig voneinander gelesen und verstanden werden kann.Trade ReviewAus den Rezensionen: “Das vorliegende Buch bietet eine klassische Einführung in die für Informatiker relevante Bereiche der Mathematik: Algebra ... Analysis ... Diskrete Strukturen ... Insgesamt handelt es sich um eine nette Bereicherung der aktuellen Literatur zu diesem Thema und ich kann es nur jedem Interessierten empfehlen.“ (G. TESCHL, Monatshefte für Mathematik, October/2010, Vol. 161, Issue 3, S. 335)Table of ContentsAlgebra.- Zahlen.- Lineare Algebra.- Analysis.- Reelle Zahlen und Folgen.- Funktionen.- Diskrete Strukturen.- Diskrete Mathematik.- Grundlagen der Mathematik.

Read more less

Book SynopsisAlgebra und Diskrete Mathematik gehören zu den wichtigsten mathematischen Grundlagen der Informatik. In diese mathematischen Teilgebiete führt Band 1 des zweibändigen Lehrbuchs umfassend ein. Dabei ermöglichen klar herausgearbeitete Lösungsalgorithmen, viele Beispiele und ausführliche Beweise einen raschen Zugang zum Thema. Die umfangreiche Sammlung von Übungsaufgaben hilft bei der Erarbeitung des Stoffs und zeigt darüber hinaus, welche unterschiedlichen Anwendungsmöglichkeiten es gibt. Die 3. Auflage wurde korrigiert und erweitert.Table of ContentsTeil I Grundbegriffe der Mathematik und Algebraische Strukturen.- Teil II Lineare Algebra und analytische Geometrie.- Teil III Numerische Algebra und Kombinatorik.- Teil IV Übungsaufgaben.

Read more less

Book SynopsisA clear and lucid bottom-up approach to the basic principles of evolutionary algorithms Evolutionary algorithms (EAs) are a type of artificial intelligence. EAs are motivated by optimization processes that we observe in nature, such as natural selection, species migration, bird swarms, human culture, and ant colonies. This book discusses the theory, history, mathematics, and programming of evolutionary optimization algorithms. Featured algorithms include genetic algorithms, genetic programming, ant colony optimization, particle swarm optimization, differential evolution, biogeography-based optimization, and many others. Evolutionary Optimization Algorithms: Provides a straightforward, bottom-up approach that assists the reader in obtaining a clear?but theoretically rigorous?understanding of evolutionary algorithms, with an emphasis on implementation Gives a careful treatment of recently developed EAs?including opposition-based learning, artiTable of ContentsAcknowledgments xxi Acronyms xxiii List of Algorithms xxvii Part I: Introduction to Evolutionary Optimization 1 Introduction 1 2 Optimization 11 Part II: Classic Evolutionary Algorithms 3 Generic Algorithms 35 4 Mathematical Models of Genetic Algorithms 63 5 Evolutionary Programming 95 6 Evolution Strategies 117 7 Genetic Programming 141 8 Evolutionary Algorithms Variations 179 Part III: More Recent Evolutionary Algorithms 9 Simulated Annealing 223 10 Ant Colony Optimization 241 11 Particle Swarm Optimization 265 12 Differential Evolution 293 13 Estimation of Distribution Algorithms 313 14 Biogeography-Based Optimization 351 15 Cultural Algorithms 377 16 Opposition-Based Learning 397 17 Other Evolutionary Algorithms 421 Part IV: Special Type of Optimization Problems 18 Combinatorial Optimization 449 19 Constrained Optimization 481 20 Multi-Objective Optimization 517 21 Expensive, Noisy and Dynamic Fitness Functions 563 Appendices A Some Practical Advice 607 B The No Free Lunch Theorem and Performance Testing 613 C Benchmark Optimization Functions 641 References 685 Topic Index 727

Read more less

Book SynopsisTrade Review"I want to share with everybody my enjoyment of this excellent textbook."---Narciso Marti-Oliet, European Math Society"Those teaching computer scientists who take discrete mathematics alongside other mathematics modules such as linear algebra and calculus (as is the case with the CS20 students at Harvard), and who need a book with an emphasis on proof, will likely and this book a very good choice for their students."---London Mathematical Society, Glenn Hawe

Read more less

Book SynopsisUses the theory of stable marriage to introduce and illustrate a variety of important concepts and techniques of computer science and mathematics: data structures, control structures, combinatorics, probability, analysis, algebra, and especially the analysis of algorithms.Trade ReviewThis short book will provide extremely enjoyable reading to anyone with an interest in discrete mathematics and algorithm design. Mathematical Reviews Anyone would enjoy reading this book. If one had to learn French first, it would be worth the effort. Computing ReviewsTable of ContentsIntroduction, definitions, and examples Existence of a stable matching: the fundamental algorithm Principle of deferred decisions: coupon collecting Theoretical developments: application to the shortest path Searching a table by hashing; mean behavior of thefundamental algorithm Implementing the fundamental algorithm Research problems Annotated bibliography Appendix A. Later developments Appendix B. Solutions to exercises Index.

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 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 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

Book SynopsisThis set includes Finite Mathematics: Models and Applications & Solutions Manual to accompany Finite Mathematics: Models and Applications Finite Mathematics: Models and Applications emphasizes cross-disciplinary applications that relate mathematics to everyday life. The book provides a unique combination of practical mathematical applications to illustrate the wide use of mathematics in fields ranging from business, economics, finance, management, operations research, and the life and social sciences. The book features coverage including: Algebra Skills; Mathematics of Finance; Matrix Algebra; Geometric Solutions; Simplex Methods; Application Models; Set and Probability Relationships; Random Variables and Probability Distributions; Markov Chains; Mathematical Statistics; Enrichment in Finite MathematicsTable of ContentsPreface ix About the Authors xi 1 Linear Equations and Mathematical Concepts 1 1.1 Solving Linear Equations 2 1.2 Equations of Lines and Their Graphs 7 1.3 Solving Systems of Linear Equations 15 1.4 The Numbers 𝜋 and e 21 1.5 Exponential and Logarithmic Functions 24 1.6 Variation 32 1.7 Unit Conversions and Dimensional Analysis 38 2 Mathematics of Finance 47 2.1 Simple and Compound Interest 47 2.2 Ordinary Annuity 55 2.3 Amortization 59 2.4 Arithmetic and Geometric Sequences 63 3 Matrix Algebra 71 3.1 Matrices 72 3.2 Matrix Notation, Arithmetic, and Augmented Matrices 78 3.3 Gauss–Jordan Elimination 89 3.4 Matrix Inversion and Input–Output Analysis 100 4 Linear Programming – Geometric Solutions 116 Introduction 116 4.1 Graphing Linear Inequalities 117 4.2 Graphing Systems of Linear Inequalities 121 4.3 Geometric Solutions to Linear Programs 125 5 Linear Programming – Simplex Method 136 5.1 The Standard Maximization Problem (SMP) 137 5.2 Tableaus and Pivot Operations 142 5.3 Optimal Solutions and the Simplex Method 149 5.4 Dual Programs 161 5.5 Non-SMP Linear Programs 167 6 Linear Programming – Application Models 182 7 Set and Probability Relationships 203 7.1 Sets 204 7.2 Venn Diagrams 210 7.3 Tree Diagrams 216 7.4 Combinatorics 221 7.5 Mathematical Probability 231 7.6 Bayes’ Rule and Decision Trees 245 8 Random Variables and Probability Distributions 259 8.1 Random Variables 259 8.2 Bernoulli Trials and the Binomial Distribution 265 8.3 The Hypergeometric Distribution 273 8.4 The Poisson Distribution 279 9 Markov Chains 285 9.1 Transition Matrices and Diagrams 286 9.2 Transitions 291 9.3 Regular Markov Chains 295 9.4 Absorbing Markov Chains 304 10 Mathematical Statistics 314 10.1 Graphical Descriptions of Data 315 10.2 Measures of Central Tendency and Dispersion 323 10.3 The Uniform Distribution 331 10.4 The Normal Distribution 334 10.5 Normal Distribution Applications 348 10.6 Developing and Conducting a Survey 363 11 Enrichment in Finite Mathematics 371 11.1 Game Theory 372 11.2 Applications in Finance and Economics 385 11.3 Applications in Social and Life Sciences 394 11.4 Monte Carlo Method 403 11.5 Dynamic Programming 422 Answers to Odd Numbered Exercises 439 Using Technology 502 Glossary 506 Index 513

Read more less

Book SynopsisIntroduces symbolic dynamics from a perspective of topological dynamical systems. After introducing symbolic and topological dynamics, the core of the book consists of discussions of subshifts of positive entropy, of zero entropy, other non-shift minimal action on the Cantor set, and the ergodic properties of these systems.Table of Contents First examples and general properties of subshifts Topological dynamics Subshifts of positive entropy Subshifts of zero entropy Further minimal Cantor systems Methods from ergodic theory Automata and linguistic complexity Miscellaneous background topics Solutions to exercises Bibliography Index

Read more less

Book SynopsisPresents an introductory and up-to-date course on game theory addressed to mathematicians and economists, and to other scientists having a basic mathematical background. The book is self-contained, providing a formal description of the classic game-theoretic concepts together with rigorous proofs of the main results in the field.Table of Contents Introduction to decision theory Strategic games Extensive games Games with incomplete information Fundamentals of cooperative games Applications of cooperative games Bibliography Notations Index Index of solution concepts Subject index.

Read more less

Book SynopsisDiscrete Convex Analysis is a novel paradigm for discrete optimization that combines the ideas in continuous optimization (convex analysis) and combinatorial optimization (matroid/submodular function theory) to establish a unified theoretical framework for nonlinear discrete optimization. The study of this theory is expanding with the development of efficient algorithms and applications to a number of diverse disciplines like matrix theory, operations research, and economics.This self-contained book is designed to provide a novel insight into optimization on discrete structures and should reveal unexpected links among different disciplines. It is the first and only English-language monograph on the theory and applications of discrete convex analysis.Table of Contents List of Figures Notation Preface Chapter 1: Introduction to the Central Concepts Chapter 2: Convex Functions with Combinatorial Structures Chapter 3: Convex Analysis, Linear Programming, and Integrality Chapter 4: M-Convex Sets and Submodular Set Functions Chapter 5: L-Convex Sets and Distance Functions Chapter 6: M-Convex Functions Chapter 7: L-Convex Functions Chapter 8: Conjugacy and Duality Chapter 9: Network Flows Chapter 10: Algorithms Chapter 11: Application to Mathematical Economics Chapter 12: Application to Systems Analysis by Mixed Matrices Bibliography Index.

Read more less

Book SynopsisThis book discusses the role of proofs in mathematics and computer science. In mathematics, a proof involves validating a proposition through logical deductions from axioms. Computer scientists focus on demonstrating program accuracy, given the increasing error susceptibility of software. A community of specialists aims to enhance program precision, extending to verifying computer processor chips for leading manufacturers. Creating mathematical models to affirm program validity is an active study area. A proof, in this context, involves a sequence of logical deductions from axioms and established statements, leading to the desired proposition. While crafting proofs may seem daunting, standard templates offer a framework. Some templates can be interconnected, providing both high-level structure and detailed guidance. The Principle of Mathematical Induction is applied to validate algorithms without computer reliance. Sets underpin modern mathematics and software engineering, introduced with language and typical tasks. Primary set operations' understanding enables proof techniques for functions, relations, and graphs, validating algorithms for specific tasks. The book delves into language describing element collections and sets, providing proof templates for comprehension and construction. The book covers common set operations, introduces additional proof templates, and addresses numbering elements and the Principle of Mathematical Induction. This exploration deepens the understanding of mathematical proofs and their role in computer science applications.Table of Contents Chapter 1 Mathematical Logic and Proofs Chapter 2 Basic Mathematics on the Real Numbers Chapter 3 Fundamental Mathematical Objects Chapter 4 Modular Arithmetic and Polynomials Chapter 5 Mathematical Functions Chapter 6 Linear Algebra in Mathematics Chapter 7 Mathematical Graphs Chapter 8 Mathematical Counting and Combinatorics Chapter 9 Discrete Probability in Mathematics Chapter 10 Recurrence Relations

Read more less

Book SynopsisThe primary aim of this book is to present a coherent introduction to graph theory, suitable as a textbook for advanced undergraduate and beginning graduate students in mathematics and computer science. It provides a systematic treatment of the theory of graphs without sacrificing its intuitive and aesthetic appeal. Commonly used proof techniques are described and illustrated. The book also serves as an introduction to research in graph theory.Trade Reviewdeveloped by Paul Seymour and Neil Robertson and followers), which certainly now deserves a monographic treatment of its own. Summing up: Recommended. Lower-division undergraduate through professional collections. CHOICE This book is a follow-on to the authors' 1976 text, Graphs with Applications. What began as a revision has evolved into a modern, first-class, graduate-level textbook reflecting changes in the discipline over the past thirty years... This text hits the mark by appearing in Springer’s Graduate Texts in Mathematics series, as it is a very rigorous treatment, compactly presented, with an assumption of a very complete undergraduate preparation in all of the standard topics. While the book could ably serve as a reference for many of the most important topics in graph theory, it fulfills the promise of being an effective textbook. The plentiful exercises in each subsection are divided into two groups, with the second group deemed "more challenging". Any exercises necessary for a complete understanding of the text have also been marked as such. There is plenty here to keep a graduate student busy, and any student would learn much in tackling a selection of the exercises... Not only is the content of this book exceptional, so too is its production. The high quality of its manufacture, the crisp and detailed illustrations, and the uncluttered design complement the attention to the typography and layout. Even in simple black and white with line art, it is a beautiful book. SIAM Book Reviews "A text which is designed to be usable both for a basic graph theory course … but also to be usable as an introduction to research in graph theory, by including more advanced topics in each chapter. There are a large number of exercises in the book … . The text contains drawings of many standard interesting graphs, which are listed at the end." (David B. Penman, Zentralblatt MATH, Vol. 1134 (12), 2008) MathSciNet Reviews "The present volume is intended to serve as a text for "advanced undergraduate and beginning graduate students in mathematics and computer science" (p. viii). It is well suited for this purpose. The writing is fully accessible to the stated groups of students, and indeed is not merely readable but is engaging… Even a complete listing of the chapters does not fully convey the breadth of this book… For researchers in graph theory, this book offers features which parallel the first Bondy and Murty book: it provides well-chosen terminology and notation, a multitude of especially interesting graphs, and a substantial unsolved problems section…One-hundred unsolved problems are listed in Appendix A, a treasure trove of problems worthy of study… (In short) this rewrite of a classic in graph theory stands a good chance of becoming a classic itself." "The present volume is intended to serve as a text for ‘advanced undergraduate and beginning graduate students in mathematics and computer science’ … . The writing is fully accessible to the stated groups of students, and indeed is not merely readable but is engaging. The book has many exercise sets, each containing problems … ." (Arthur M. Hobbs, Mathematical Reviews, Issue 2009 C) "A couple of fantastic features: Proof techniques: I love these nutshelled essences highlighted in bordered frames. They look like pictures on the wall and grab the view of the reader. Exercises: Their style, depth and logic remind me of Lovász’ classical exercise book. Also the fact that the name of the author is bracketed after the exercise…Figures: Extremely precise and high-tech…The book contains very recent results and ideas. It is clearly an up-to-date collection of fundamental results of graph theory…All-in-all, it is a marvelous book." (János Barát, Acta Scientiarum Mathematicarum, Vol. 75, 2009)Table of ContentsGraphs.- Subgraphs.- Connected Graphs.- Trees.- Nonseparable Graphs.- Tree-Search Algorithms.- Flows in Networks.- Complexity of Algorithms.- Connectivity.- Planar Graphs.- The Four-Colour Problem.- Stable Sets and Cliques.- The Probabilistic Method.- Vertex Colourings.- Colourings of Maps.- Matchings.- Edge Colourings.- Hamilton Cycles.- Coverings and Packings in Directed Graphs.- Electrical Networks.- Integer Flows and Coverings.

Read more less

Book SynopsisThis practically-oriented textbook presents an accessible introduction to discrete mathematics through a substantial collection of classroom-tested exercises. Each chapter opens with concise coverage of the theory underlying the topic, reviewing the basic concepts and establishing the terminology, as well as providing the key formulae and instructions on their use. This is then followed by a detailed account of the most common problems in the area, before the reader is invited to practice solving such problems for themselves through a varied series of questions and assignments.Topics and features: provides an extensive set of exercises and examples of varying levels of complexity, suitable for both laboratory practical training and self-study; offers detailed solutions to many problems, applying commonly-used methods and computational schemes; introduces the fundamentals of mathematical logic, the theory of algorithms, Boolean algebra, graph theory, sets, relations, functions, and combinatorics; presents more advanced material on the design and analysis of algorithms, including asymptotic analysis, and parallel algorithms; includes reference lists of trigonometric and finite summation formulae in an appendix, together with basic rules for differential and integral calculus.This hands-on study guide is designed to address the core needs of undergraduate students training in computer science, informatics, and electronic engineering, emphasizing the skills required to develop and implement an algorithm in a specific programming language.Table of ContentsFundamentals of Mathematical Logic Set Theory Relations and Functions Combinatorics Graphs Boolean Algebra Complex Numbers Recurrence Relations Concept of an Algorithm, Correctness of Algorithms Turing Machine Asymptotic Analysis Basic Algorithms Parallel Algorithms

Read more less

Book SynopsisContinuing the theme of the previous volumes, these seminar notes reflect general trends in the study of Geometric Aspects of Functional Analysis, understood in a broad sense. Two classical topics represented are the Concentration of Measure Phenomenon in the Local Theory of Banach Spaces, which has recently had triumphs in Random Matrix Theory, and the Central Limit Theorem, one of the earliest examples of regularity and order in high dimensions. Central to the text is the study of the Poincaré and log-Sobolev functional inequalities, their reverses, and other inequalities, in which a crucial role is often played by convexity assumptions such as Log-Concavity. The concept and properties of Entropy form an important subject, with Bourgain's slicing problem and its variants drawing much attention. Constructions related to Convexity Theory are proposed and revisited, as well as inequalities that go beyond the Brunn–Minkowski theory. One of the major current research directions addressed is the identification of lower-dimensional structures with remarkable properties in rather arbitrary high-dimensional objects. In addition to functional analytic results, connections to Computer Science and to Differential Geometry are also discussed. Table of Contents- Jean Bourgain: In Memoriam. - A Generalized Central Limit Conjecture for Convex Bodies. - The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding. - Two-Sided Estimates for Order Statistics of Log-Concave Random Vectors. - Further Investigations of Rényi Entropy Power Inequalities and an Entropic Characterization of s-Concave Densities. - Small Ball Probability for the Condition Number of Random Matrices. - Concentration of the Intrinsic Volumes of a Convex Body. - Two Remarks on Generalized Entropy Power Inequalities. - On the Geometry of Random Polytopes. - Reciprocals and Flowers in Convexity. - Moments of the Distance Between Independent Random Vectors. - The Alon–Milman Theorem for Non-symmetric Bodies. - An Interpolation Proof of Ehrhard’s Inequality. - Bounds on Dimension Reduction in the Nuclear Norm. - High-Dimensional Convex Sets Arising in Algebraic Geometry. - Polylog Dimensional Subspaces of lN/∞. - On a Formula for the Volume of Polytopes.

Read more less

Book SynopsisIn the present era dominated by computers, graph theory has come into its own as an area of mathematics, prominent for both its theory and its applications. One of the richest and most studied types of graph structures is that of the line graph, where the focus is more on the edges of a graph than on the vertices. A subject worthy of exploration in itself, line graphs are closely connected to other areas of mathematics and computer science. This book is unique in its extensive coverage of many areas of graph theory applicable to line graphs. The book has three parts. Part I covers line graphs and their properties, while Part II looks at features that apply specifically to directed graphs, and Part III presents generalizations and variations of both line graphs and line digraphs.Line Graphs and Line Digraphs is the first comprehensive monograph on the topic. With minimal prerequisites, the book is accessible to most mathematicians and computer scientists who have had an introduction graph theory, and will be a valuable reference for researchers working in graph theory and related fields.Table of ContentsPart I Line Graphs.- 1 Fundamentals of Line Graphs.- 2 Line Graph Isomorphisms.- 3 Characterization of Line Graphs.- 4 Spectral Properties of Line Graphs.- 5 Planarity of Line Graphs.- 6 Connectivity of Line Graphs.- 7 Tranversability in Line Graphs.- 8 Colorability in Line Graphs.- 9 Distance and Transitivity in Line Graphs.- Part II Line Digraphs.- 10 Fundamentals of Line Digraphs.- 11 Characterizations of Line Digraphs.- 12 Iterated Line Digraphs.- Part III Generalizations.- 13 Total Graphs and Total Digraphs.- 14 Path Graphs and Path Digraphs.- 15 Super Line Graphs and Super Line Digraphs.- 16 Line Graphs of Signed Graphs.- 17 The Krausz Dimension of Graph.- Reference. Index of Names.- Index of Definitions.

Read more less

This textbook discusses the design and implementation of basic algebraic graph algorithms, and algebraic graph algorithms for complex networks, employing matroids whenever possible. The text describes the design of a simple parallel matrix algorithm kernel that can be used for parallel processing of algebraic graph algorithms. Example code is presented in pseudocode, together with case studies in Python and MPI. The text assumes readers have a background in graph theory and/or graph algorithms.

Read more less

Book SynopsisThis textbook covers a diversity of topics in graph and network theory, both from a theoretical standpoint, and from an applied modelling point of view. Mathematica® is used to demonstrate much of the modelling aspects. Graph theory and model building tools are developed in tandem with effective techniques for solving practical problems via computer implementation. The book is designed with three primary readerships in mind. Individual syllabi or suggested sequences for study are provided for each of three student audiences: mathematics, applied mathematics/operations research, and computer science. In addition to the visual appeal of each page, the text contains an abundance of gems. Most chapters open with real-life problem descriptions which serve as motivation for the theoretical development of the subject matter. Each chapter concludes with three different sets of exercises. The first set of exercises are standard and geared toward the more mathematically inclined reader. Many of these are routine exercises, designed to test understanding of the material in the text, but some are more challenging. The second set of exercises is earmarked for the computer technologically savvy reader and offer computer exercises using Mathematica. The final set consists of larger projects aimed at equipping those readers with backgrounds in the applied sciences to apply the necessary skills learned in the chapter in the context of real-world problem solving. Additionally, each chapter offers biographical notes as well as pictures of graph theorists and mathematicians who have contributed significantly to the development of the results documented in the chapter. These notes are meant to bring the topics covered to life, allowing the reader to associate faces with some of the important discoveries and results presented. In total, approximately 100 biographical notes are presented throughout the book. The material in this book has been organized into three distinct parts, each with a different focus. The first part is devoted to topics in network optimization, with a focus on basic notions in algorithmic complexity and the computation of optimal paths, shortest spanning trees, maximum flows and minimum-cost flows in networks, as well as the solution of network location problems. The second part is devoted to a variety of classical problems in graph theory, including problems related to matchings, edge and vertex traversal, connectivity, planarity, edge and vertex coloring, and orientations of graphs. Finally, the focus in the third part is on modern areas of study in graph theory, covering graph domination, Ramsey theory, extremal graph theory, graph enumeration, and application of the probabilistic method.Table of ContentsPreface.- List of Algorithms.- List of Bibliographical Notes.- Part 1. Topics in network optimisation.- 1. An introduction to graphs.- 2. Graph connectedness.- 3. Algorithmic complexity.- 4. Optimal paths.- 5. Trees.- 6. Location problems.- 7. Maximum flow networks.- 8. Minimum-cost network flows.- Part 2. Topics in classical graph theory.- 9. Matchings.- 10. Eulerian graphs.- 11. Hamiltonian graphs.- 12. Graph connectivity.- 13. Planarity.- 14. Graph colouring.- 15. Oriented graphs. Part 3. Topics in modern graph theory.- 16. Domination in graphs.- 17. Ramsey Theory.- 18. Extremal graph theory.- 19. Graph enumeration.- 20. The probabilistic method.- Index.

Read more less

Book SynopsisThis proceedings volume gathers selected, revised papers presented at the 51st Southeastern International Conference on Combinatorics, Graph Theory and Computing (SEICCGTC 2020), held at Florida Atlantic University in Boca Raton, USA, on March 9-13, 2020. The SEICCGTC is broadly considered to be a trendsetter for other conferences around the world – many of the ideas and themes first discussed at it have subsequently been explored at other conferences and symposia.The conference has been held annually since 1970, in Baton Rouge, Louisiana and Boca Raton, Florida. Over the years, it has grown to become the major annual conference in its fields, and plays a major role in disseminating results and in fostering collaborative work.This volume is intended for the community of pure and applied mathematicians, in academia, industry and government, working in combinatorics and graph theory, as well as related areas of computer science and the interactions among these fields.Table of ContentsRatio Balancing Numbers(Bartz et al).- An Unexpected Digit Permutation from Multiplying in any Number Base(Qu et al).- A & Z Sequences for Double Riordan Arrays (Branch et al).- Constructing Clifford Algebras for Windmill and Dutch Windmill Graphs; A New Proof of The Friendship Theorem(Myers).- Finding Exact Values of a Character Sum (Peart et al).- On Minimum Index Stanton 4-cycle Designs (Bunge et al).- k-Plane Matroids and Whiteley’s Flattening Conjectures (Servatius et al).- Bounding the edge cover of a hypergraph (Shahrokhi).- A Generalization on Neighborhood Representatives (Holliday).- Harmonious Labelings of Disconnected Graphs involving Cycles and Multiple Components Consisting of Starlike Trees(Abueida et al).- On Rainbow Mean Colorings of Trees (Hallas et al).- Examples of Edge Critical Graphs in Peg Solitaire (Beeler et al).- Regular Tournaments with Minimum Split Domination Number and Cycle Extendability (Factor et al).- Independence and Domination of Chess Pieces on Triangular Boards and on the Surface of a Tetrahedron(Munger et al).- Efficient and Non-efficient Domination of Z-stacked Archimedean Lattices (Paskowitz et al).- On subdivision graphs which are 2-steps Hamiltonian graphs and hereditary non 2-steps Hamiltonian graphs (Lee et al).- On the Erd}os-S_os Conjecture for graphs with circumference at most k + 1 (Heissan et al).- Regular graph and some vertex-deleted subgraph (Egawa et al).- Connectivity and Extendability in Digraphs (Beasle).-On the extraconnectivity of arrangement graphs (Cheng et al).- k-Paths of k-Trees(Bickle).-Rearrangement of the Simple Random Walk(Skyers et al).- On the Energy of Transposition Graphs(DeDeo).- A Smaller Upper Bound for the (4; 82) Lattice Site Percolation Threshold(Wierman).

Read more less

Book SynopsisThis book constitutes the refereed proceedings of the 15th International Conference on Graph Transformation, ICGT 2022, which took place Nantes, France in July 2022.The 10 full papers and 1 tool paper presented in this book were carefully reviewed and selected from 19 submissions. The conference focuses on describing new unpublished contributions in the theory and applications of graph transformation as well as tool presentation papers that demonstrate main new features and functionalities of graph-based tools.Table of ContentsTheoretical Advances.- Application Domains.- Tool Presentation.

Read more less

Book SynopsisThis book constitutes the proceedings of the 16th International Conference on Algorithmic Aspects in Information and Management, AAIM 2022, which was held online during August 13-14, 2022. The conference was originally planned to take place in Guangzhou, China, but changed to a virtual event due to the COVID-19 pandemic.The 41 regular papers included in this book were carefully reviewed and selected from 59 submissions. Table of ContentsAn improvement of the bound on the odd chromatic number of 1-planar graphs.- AoI Minimizing of Wireless Rechargeable Sensor Network based on Trajectory Optimization of Laser-Charged UAV.- Monotone k-Submodular Knapsack Maximization: An Analysis of the Greedy+Singleton Algorithm.- The constrained parallel-machine scheduling problem with divisible processing times and penalties.- Energy-constrained Geometric Covering Problem.- Fast searching on $k$-combinable graphs.- Three Algorithms for Converting Control Flow Statements from Python to XD-M.- Class Ramsey numbers involving induced graphs.- An Approximation Algorithm for the Clustered Path Travelling Salesman Problem.- Hyperspectral Image Reconstruction for SD-CASSI systems based on Residual Attention Network.- Improved Approximation Algorithm for the Asymmetric Prize-Collecting TSP.- Injective edge coloring of power graphs and necklaces.- Guarantees for Maximization of $k$-Submodular Functions with a Knapsack and a Matroid Constraint.- Incremental SDN Deployment to Achieve Load Balance in ISP Networks.- Approximation scheme for single-machine rescheduling with job delay and rejection.- Defense of Scapegoating Attack in Network Tomography.- A Binary Search Double Greedy Algorithm for Non-monotone DR-submodular Maximization.- Streaming Adaptive Submodular Maximization.- Constrained Stochastic Submodular Maximization with State-Dependent Costs.- Online early work maximization problem on two hierarchical machines with buffer or rearrangements.- Polynomial time algorithm for k-vertex-edge dominating problem in interval graphs.- Adaptive Competition-based Diversified-profit Maximization with Online Seed Allocation.- Collaborative Service Caching in Mobile Edge Nodes.- A Decentralized Auction Framework with Privacy Protection in Mobile Crowdsourcing.- On-line single machine scheduling with release dates and submodular rejection penalties.- Obnoxious Facility Location Games with Candidate Locations.- Profit Maximization for Multiple Products in Community-based Social Networks.- MCM: A Robust Map Matching Method by Tracking Multiple Road Candidates.- Security on Ethereum: Ponzi Scheme Detection in Smart Contract.- Cyclically orderable generalized Petersen graphs.- The r-dynamic chromatic number of planar graphs without special short cycles.- Distance Labeling of the Halved Folded $n$-Cube.- Signed network embedding based on muti-attention mechanism.- Balanced Graph Partitioning based on Mixed 0-1 Linear Programming and Iteration Vertex Relocation Algorithm.- Partial inverse min-max spanning tree problem under the weighted bottleneck Hamming distance.- Mixed Metric Dimension of Some Plane Graphs.- The Optimal Dynamic Rationing Policy in the Stock-Rationing Queue.- Pilot Pattern Design with Branch and Bound in PSA-OFDM System.- Bicriteria Algorithms for Maximizing the Difference Between Submodular Function and Linear Function under Noise.- On the Transversal Number of k-Uniform Connected Hypergraphs.- Total coloring of planar graphs without some adjacent cycles.

Read more less

Book SynopsisThis textbook aims to point out the most important principles of data analysis from the mathematical point of view. Specifically, it selected these questions for exploring: Which are the principles necessary to understand the implications of an application, and which are necessary to understand the conditions for the success of methods used? Theory is presented only to the degree necessary to apply it properly, striving for the balance between excessive complexity and oversimplification. Its primary focus is on principles crucial for application success. Topics and features: Focuses on approaches supported by mathematical arguments, rather than sole computing experiences Investigates conditions under which numerical algorithms used in data science operate, and what performance can be expected from them Considers key data science problems: problem formulation including optimality measure; learning and generalization in relationships to training set size and number of free parameters; and convergence of numerical algorithms Examines original mathematical disciplines (statistics, numerical mathematics, system theory) as they are specifically relevant to a given problem Addresses the trade-off between model size and volume of data available for its identification and its consequences for model parametrization Investigates the mathematical principles involves with natural language processing and computer vision Keeps subject coverage intentionally compact, focusing on key issues of each topic to encourage full comprehension of the entire book Although this core textbook aims directly at students of computer science and/or data science, it will be of real appeal, too, to researchers in the field who want to gain a proper understanding of the mathematical foundations “beyond” the sole computing experience.Table of Contents1. Data Science and its Tasks.- 2. Application Specific Mappings and Measuring the Fit to Data.- 3. Data Processing by Neural Networks.- 4. Learning and Generalization.- 5. Numerical Algorithms for Network Learning.- 6. Specific Problems of Natural Language Processing.- 7. Specific Problems of Computer Vision.

Read more less

Book SynopsisGenerating function (GF) is a mathematical technique to concisely represent a known ordered sequence into a simple continuous algebraic function in dummy variable(s). This Second Edition introduces commonly encountered generating functions (GFs) in engineering and applied sciences, such as ordinary GF (OGF), exponential GF (EGF), as also Dirichlet GF (DGF), Lambert GF (LGF), Logarithmic GF (LogGF), Hurwitz GF (HGF), Mittag-Lefler GF (MLGF), etc. This book is intended mainly for beginners in applied science and engineering fields to help them understand single-variable GFs and illustrate how to apply them in various practical problems. Specifically, the book discusses probability GFs (PGF), moment and cumulant GFs (MGF, CGF), mean deviation GFs (MDGF), survival function GFs (SFGF), rising and falling factorial GFs, factorial moment, and inverse factorial moment GFs. Applications of GFs in algebra, analysis of algorithms, bioinformatics, combinatorics, economics, finance, genomics, geometry, graph theory, management, number theory, polymer chemistry, reliability, statistics and structural engineering have been added to this new edition. This book is written in such a way that readers who do not have prior knowledge of the topic can easily follow through the chapters and apply the lessons learned in their respective disciplines.Table of ContentsTypes of Generating Functions.- Operations on Generating Functions.- Generating Functions in Statistics.- Applications of Generating Functions.- Bibliography.

Read more less

Book SynopsisThis book provides an elementary introduction, complete with detailed proofs, to the celebrated tilings of the plane discovered by Sir Roger Penrose in the '70s. Quasi-periodic tilings of the plane, of which Penrose tilings are the most famous example, started as recreational mathematics and soon attracted the interest of scientists for their possible application in the description of quasi-crystals. The purpose of this survey, illustrated with more than 200 figures, is to introduce the curious reader to this beautiful topic and be a reference for some proofs that are not easy to find in the literature. The volume covers many aspects of Penrose tilings, including the study, from the point of view of Connes' Noncommutative Geometry, of the space parameterizing these tilings.Table of ContentsIntroduction.- Tilings and puzzles.- Robinson triangles.- Penrose tilings.- De Bruijn’s pentagrids.- The noncommutative space of Penrose tilings.-Some useful formulas.

Read more less

Book SynopsisThis book is ideal for a first or second year discrete mathematics course for mathematics, engineering, and computer science majors. The author has extensively class-tested early conceptions of the book over the years and supplements mathematical arguments with informal discussions to aid readers in understanding the presented topics. “Safe” – that is, paradox-free – informal set theory is introduced following on the heels of Russell’s Paradox as well as the topics of finite, countable, and uncountable sets with an exposition and use of Cantor’s diagonalisation technique. Predicate logic “for the user” is introduced along with axioms and rules and extensive examples. Partial orders and the minimal condition are studied in detail with the latter shown to be equivalent to the induction principle. Mathematical induction is illustrated with several examples and is followed by a thorough exposition of inductive definitions of functions and sets. Techniques for solving recurrence relations including generating functions, the O- and o-notations, and trees are provided. Over 200 end of chapter exercises are included to further aid in the understanding and applications of discrete mathematics. Table of ContentsElementary Informal Set Theory.- Safe Set Theory.- Relations and Functions.- A Tiny Bit of Informal Logic.- Inductively Defined Sets and Structural Induction.- Recurrence Equations.- Trees and Graphs.

Read more less

Book SynopsisThis book constitutes the refereed proceedings of the 24th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2023, held in Madison, WI, USA, during June 21–23, 2023. The 33 full papers presented were carefully reviewed and selected from 119 submissions. IPCO is under the auspices of the Mathematical Optimization Society, and it is an important forum for presenting present recent developments in theory, computation, and applications. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.

Read more less

Book SynopsisThis volume constitutes the proceedings of the 9th International Conference on Variable Neighborhood Search, ICVNS 2023, held in Abu Dhabi, United Arab Emirates, in October 2022.The 11 full papers presented in this volume were carefully reviewed and selected from 29 submissions. The papers describe recent advances in methods and applications of variable neighborhood search.Table of ContentsA metaheuristic approach for solving Monitor Placement Problem.- A VNS-based heuristic for the minimum number of resources under a perfect schedule.- BVNS for Overlapping Community Detection.- A Simulation-Based Variable Neighborhood Search Approach for Optimizing Cross-Training Policies.- Multi-Objective Variable Neighborhood Search for improving software modularity.- An Effective VNS for Delivery Districting.- BVNS for the Minimum Sitting Arrangement problem in a cycle.- Assigning Multi-Skill Confgurations to Multiple Servers with a Reduced VNS.- Multi-Round Infuence Maximization: A Variable Neighborhood Search Approach.- A VNS based heuristic for a 2D Open Dimension Problem.- BVNS for the bi-objective multi row equal facility layout problem.

Read more less

Book SynopsisThis book constitutes the refereed proceedings of the 17th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom (IJTCS-FAW 2023), consisting of the 17th International Conference on Frontier of Algorithmic Wisdom (FAW) and the 4th International Joint Conference on Theoretical Computer Science (IJTCS), held in Macau, China, during August 14–18, 2023.FAW started as the Frontiers of Algorithmic Workshop in 2007 at Lanzhou, China, and was held annually from 2007 to 2021 and published archival proceedings. IJTCS, the International joint theoretical Computer Science Conference, started in 2020, aimed to bring in presentations covering active topics in selected tracks in theoretical computer science. To accommodate the diversified new research directions in theoretical computer science, FAW and IJTCS joined their forces together to organize an event for information exchange of new findings and work of enduring value in the field. The 21 full papers included in this book were carefully reviewed and selected from 34 submissions. They were organized in topical sections as follows: algorithmic game theory; algorithms and data structures; combinatorial optimization; and computational economics.Table of ContentsUnderstanding the Relationship Between Core Constraints and Core-Selecting Payment Rules in Combinatorial Auctions.- An Improved Analysis of the Greedy+Singleton Algorithm for k-Submodular Knapsack Maximization.- Generalized Sorting with Predictions Revisited.- Eliciting Truthful Reports with Partial Signals in Repeated Games.- On the NP-hardness of two scheduling problems under linear constraints.- On the Matching Number of k-Uniform Connected Hypergraphs with Maximum Degree.- Max-Min Greedy Matching Problem: Hardness for the Adversary and Fractional Variant.- Approximate Core Allocations for Edge Cover Games.- Random Approximation Algorithms for Monotone k-Submodular Function Maximization with Size Constraints.- Additive Approximation Algorithms for Sliding Puzzle.- Differential Game Analysis for Cooperation Models in Automotive Supply Chain under Low-Carbon Emission Reduction Policies.- Adaptivity Gap for Influence Maximization with Linear Threshold Model on Trees.- Physically Verifying the First Nonzero Term in a Sequence: Physical ZKPs for ABC End View and Goishi Hiroi.- Mechanism Design in Fair Sequencing.- Red-Blue Rectangular Annulus Cover Problem.- Applying Johnson's Rule in Scheduling Multiple Parallel Two-Stage Flowshops.- The Fair k-Center with Outliers Problem: FPT and Polynomial Approximations.- Constrained Graph Searching on Trees.- EFX Allocations Exist for Binary Valuations.- Maximize Egalitarian Welfare for Cake Cutting.- Stackelberg Strategies on Epidemic Containment Games.

Read more less

Book SynopsisThis book provides a comprehensive algebraic treatment of hypergroups, as defined by F. Marty in 1934. It starts with structural results, which are developed along the lines of the structure theory of groups. The focus then turns to a number of concrete classes of hypergroups with small parameters, and continues with a closer look at the role of involutions (modeled after the definition of group-theoretic involutions) within the theory of hypergroups. Hypergroups generated by involutions lead to the exchange condition (a genuine generalization of the group-theoretic exchange condition), and this condition defines the so-called Coxeter hypergroups. Coxeter hypergroups can be treated in a similar way to Coxeter groups. On the other hand, their regular actions are mathematically equivalent to buildings (in the sense of Jacques Tits). A similar equivalence is discussed for twin buildings. The primary audience for the monograph will be researchers working in Algebra and/or Algebraic Combinatorics, in particular on association schemes.Table of Contents1 Basic Facts : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11.1 Neutral Elements and Inverse Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Complex Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Thin Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5 Groups and Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.6 Actions of Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.7 Hypergroups Admitting Regular Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.8 Association Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Closed Subsets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 272.1 Basic Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.2 Dedekind Modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.3 Generating Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4 Commutators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.5 Conjugation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.6 The Thin Radical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.7 Foldings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 Elementary Structure Theory: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 473.1 Centralizers and Normalizers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.2 Su cient Conditions for Normality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.3 Strong Normality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.4 Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593.5 Computations in Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.6 Homomorphisms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.7 The Homomorphism Theorem and the Isomorphism Theorems . . . . . . . . . . 714 Subnormality and Thin Residues : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 794.1 Subnormal Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.2 Composition Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834.3 The Thin Residue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884.4 Thin Residues of Thin Residues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.5 Residually Thin Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944.6 Finite Residually Thin Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 974.7 Solvable Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045 Tight Hypergroups : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1075.1 Tight Hypergroup Elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075.2 The Set S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1115.3 The Sets a b \ Fc and Sa;b(Fc) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1135.4 The Sets bf1b  \ Fa and Sb;(f1;:::;fn)(Fa) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1175.5 Structure Constants of Finite Tight Hypergroups . . . . . . . . . . . . . . . . . . . . . 1225.6 Rings Arising from Certain Finite Tight Hypergroups . . . . . . . . . . . . . . . . . 1265.7 Finite Metathin Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.8 Finite Metathin Hypergroups with Restricted Thin Residue . . . . . . . . . . . . 1326 Involutions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1376.1 Basic Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.2 Cosets of Closed Subsets Generated by an Involution, I . . . . . . . . . . . . . . . . 1426.3 Cosets of Closed Subsets Generated by an Involution, II . . . . . . . . . . . . . . . 1456.4 Cosets of Closed Subsets Generated by an Involution, III . . . . . . . . . . . . . . . 1476.5 Length Functions De ned by Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . 1526.6 Hypergroups Generated by Two Distinct Involutions . . . . . . . . . . . . . . . . . . 1566.7 Dichotomy and the Exchange Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1616.8 Projective Hypergroups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1647 Hypergroups with a Small Number of Elements : : : : : : : : : : : : : : : : : : : : : : 1717.1 Hypergroups of Cardinality at Most 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1727.2 Non-Symmetric Hypergroups of Cardinality 4 . . . . . . . . . . . . . . . . . . . . . . . . 1797.3 Hypergroups of Cardinality 6 with a Non-Normal Closed Subset, I . . . . . . 1907.4 Hypergroups of Cardinality 6 with a Non-Normal Closed Subset, II . . . . . . 2027.5 Non-Normal Closed Subsets Missing Four Elements . . . . . . . . . . . . . . . . . . . 2157.6 Non-Normal Closed Subsets Missing Four Elements and Thin Elements . . 2218 Constrained Sets of Involutions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2238.1 Basic Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2248.2 Constrained Sets of Involutions and Cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . 2288.3 Constrained Sets of Involutions and the Thin Radical . . . . . . . . . . . . . . . . . . 2308.4 Constrained Sets of Involutions and Dichotomy . . . . . . . . . . . . . . . . . . . . . . . 2338.5 Constrained Sets of Non-Thin Involutions and Dichotomy . . . . . . . . . . . . . . 2398.6 Constrained Sets of Involutions and Foldings . . . . . . . . . . . . . . . . . . . . . . . . . 2448.7 Dichotomic Constrained Sets of Involutions and Foldings . . . . . . . . . . . . . . . 2489 Coxeter Sets of Involutions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2519.1 General Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2529.2 The Sets V1(U) for Subsets U of Coxeter Sets V of Involutions . . . . . . . . . . 2569.3 The Sets V����1(U) for Subsets U of Coxeter Sets V of Involutions . . . . . . . . . 2639.4 Sets of Subsets of Coxeter Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . . . . 2659.5 Spherical Coxeter Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2689.6 Subsets of Spherical Coxeter Sets of Involutions . . . . . . . . . . . . . . . . . . . . . . . 2739.7 Coxeter Sets of Involutions and Foldings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2779.8 Coxeter Sets of Involutions and Their Coxeter Numbers . . . . . . . . . . . . . . . . 2809.9 Coxeter Sets of Involutions and Type Preserving Bijections . . . . . . . . . . . . . 28610 Regular Actions of (Twin) Coxeter Hypergroups: : : : : : : : : : : : : : : : : : : : : 29310.1 Buildings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29310.2 Twin Buildings, I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29810.3 Twin Buildings, II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30110.4 Regular Actions of Coxeter Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30510.5 Regular Actions of Twin Coxeter Hypergroups . . . . . . . . . . . . . . . . . . . . . . . . 315References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 333

Read more less

Book SynopsisThis volume constitutes the thoroughly refereed proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2023. The 33 full papers presented in this volume were carefully reviewed and selected from a total of 116 submissions. The WG 2022 workshop aims to merge theory and practice by demonstrating how concepts from graph theory can be applied to various areas in computer science, or by extracting new graph theoretic problems from applications.Table of ContentsProportionally Fair Matching with Multiple Groups.- Reconstructing Graphs from Connected Triples.- Parameterized Complexity of Vertex Splitting to Pathwidth at most 1.- Odd Chromatic Number of Graph Classes.- Deciding the Erdos-P osa property in 3-connected digraphs.- New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth.- Computational Complexity of Covering Colored Mixed Multigraphswith Degree Partition Equivalence Classes of Size at Most Two.- Cutting Barnette graphs perfectly is hard.- Metric dimension parameterized by treewidth in chordal graphs.- Efficient Constructions for the Gyori-Lovasz Theorem on Almost Chordal Graphs.- Generating faster algorithms for d-Path Vertex Cover.- A new width parameter of graphs based on edge cuts: -edge-crossing width.- Snakes and Ladders: a Treewidth Story.- Parameterized Results on Acyclic Matchings with Implications for Related Problems.- P-matchings Parameterized by Treewidth.- Algorithms and hardness for Metric Dimension on digraphs.- Degreewidth : a New Parameter for Solving Problems on Tournaments.- Approximating Bin Packing with Con ict Graphs via Maximization Techniques.- i-Metric Graphs: Radius, Diameter and all Eccentricities.- Maximum edge colouring problem on graphs that exclude a xed minor.- Bounds on Functionality and Symmetric Di erence { Two Intriguing Graph Parameters.- Cops and Robbers on Multi-layer Graphs.- Parameterized Complexity of Broadcasting in Graphs.- Turan's Theorem Through Algorithmic Lens.- On the Frank number and nowhere-zero ows on graphs.- On the minimum number of arcs in 4-dicritical oriented graphs.- Tight Algorithms for Connectivity Problems Parameterized byModular-Treewidth.

Read more less

Book SynopsisThis book constitutes the proceedings of the 49th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2024, held in Cochem, Germany, in February 2024. The 33 full papers presented in this book were carefully reviewed and selected from 81 submissions. The book also contains one invited talk in full paper length. They focus on original research and challenges in foundations of computer science including algorithms, AI-based methods, computational complexity, and formal models.Table of ContentsThe Information Extraction Framework of Document Spanners - A Very Informal Survey.- Generalized Distance Polymatrix Games.- Relaxed agreement forests.- On the Computational Complexity of Generalized Common Shape Puzzles.- Fractional Bamboo Trimming and Distributed Windows Scheduling.- New support size bounds and proximity bounds for integer linear programming.- On the Parameterized Complexity of Minus Domination.- Exact and Parameterized Algorithms for Choosability.- Parameterized Algorithms for Covering by Arithmetic Progressions.- Row-column combination of Dyck words.- Group Testing in Arbitrary Hypergraphs and Related Combinatorial Structures.- On the parameterized complexity of the Perfect Phylogeny problem.- Data reduction for directed feedback vertex set on graphs without long induced cycles.- Visualization of Bipartite Graphs in Limited Window Size.- Outerplanar and Forest Storyplans.- The Complexity of Cluster Vertex Splitting and Company.- Morphing Graph Drawings in the Presence of Point Obstacles.- Word-Representable Graphs from a Word’s Perspective.- Removable Online Knapsack with Bounded Size Items.- The Complexity of Online Graph Games.- Faster Winner Determination Algorithms for (Colored) Arc Kayles.- Automata Classes Accepting Languages Whose Commutative Closure is Regular.- Shortest Characteristic Factors of a Deterministic Finite Automaton and Computing Its Positive Position Run by Pattern Set Matching.- Query Learning of Minimal Deterministic Symbolic Finite Automata Separating Regular Languages.- Apportionment with Thresholds: Strategic Campaigns Are Easy in the Top-Choice But Hard in the Second-Chance Mode.- Local Certification of Majority Dynamics.- Complexity of Spherical Equations in Finite Groups.- Positive Characteristic Sets for Relational Pattern Languages.- Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs.- The Weighted HOM-Problem over Fields.- Combinatorics of block-parallel automata networks.- On the piecewise complexity of words and periodic words.- Distance Labeling for Families of Cycles.- On the induced problem for fixed-template CSPs.

Read more less

Book Synopsis- Mathematics and computer science in the information revolution.- NLP and some research results in Senegal.- On absolute valued algebras with nonzero central element.- On algebraic algebras without divisors of zero satisfying (xp, xq, xr) = 0.- Computing minimal free resolutions over monomial semirings with coefficients in D-A rings.- Schur complement and inequalities of eigenvalues on block Hadamard product.- A perturbed Mann-type algorithm for zeros of maximal monotone mappings.- On Rickart and Baer semimodules.- Completion fractions modules of filtered modules over non-necessarily commutative filtered rings.- On S-lifting semimodules over semirings.- A contribution to the study of a class of noncommutative ideals admitting finite Gröbner bases.- Construction of numbers with the same normality properties as a given number. - Robustness of imputation methods with backpropagation algorithm in nonlinear multiple regression.- A better random forest classifier: Labels guided Mondrian forest.- Remote sensing of artisanal mines buried in the ground by infrared thermography using UAV.- Implementation of EdDSA in the Ethereum blockchain.- Vulnerability prediction of web applications from source code based on machine learning and deep learning: Where are we at?.- Business process management and process mining on the large: Overview, challenges and research directions.

Read more less

Book Synopsis

Read more less

Book SynopsisThe starting point for this monograph is the previously unknown connection between the Continuum Hypothesis and the saturation of the non-stationary ideal on ω1; and the principle result of this monograph is the identification of a canonical model in which the Continuum Hypothesis is false. This is the first example of such a model and moreover the model can be characterized in terms of maximality principles concerning the universal-existential theory of all sets of countable ordinals. This model is arguably the long sought goal of the study of forcing axioms and iterated forcing but is obtained by completely different methods, for example no theory of iterated forcing whatsoever is required. The construction of the model reveals a powerful technique for obtaining independence results regarding the combinatorics of the continuum, yielding a number of results which have yet to be obtained by any other method. This monograph is directed to researchers and advanced graduate students in Set Theory. The second edition is updated to take into account some of the developments in the decade since the first edition appeared, this includes a revised discussion of Ω-logic and related matters.

Read more less

Book SynopsisThis monograph provides a self-contained introduction to symmetric functions and their use in enumerative combinatorics. It is the first book to explore many of the methods and results that the authors present. Numerous exercises are included throughout, along with full solutions, to illustrate concepts and also highlight many interesting mathematical ideas.The text begins by introducing fundamental combinatorial objects such as permutations and integer partitions, as well as generating functions. Symmetric functions are considered in the next chapter, with a unique emphasis on the combinatorics of the transition matrices between bases of symmetric functions. Chapter 3 uses this introductory material to describe how to find an assortment of generating functions for permutation statistics, and then these techniques are extended to find generating functions for a variety of objects in Chapter 4. The next two chapters present the Robinson-Schensted-Knuth algorithm and a method for proving Pólya’s enumeration theorem using symmetric functions. Chapters 7 and 8 are more specialized than the preceding ones, covering consecutive pattern matches in permutations, words, cycles, and alternating permutations and introducing the reciprocity method as a way to define ring homomorphisms with desirable properties.Counting with Symmetric Functions will appeal to graduate students and researchers in mathematics or related subjects who are interested in counting methods, generating functions, or symmetric functions. The unique approach taken and results and exercises explored by the authors make it an important contribution to the mathematical literature.Trade Review“This book provides a current survey of techniques and applications of symmetric functions to enumeration theory, with emphasis on the combinatorics of the transition matrices between bases. … Each chapter ends with a substantial number of exercises along with full solutions, as well as accurate bibliographic notes. The book is definitely a very interesting addition to the literature on the subject.” (Domenico Senato, Mathematical Reviews, February, 2017)“Though the authors target graduate students, advanced undergraduates will also surely have the necessary prerequisites, easily grasp the book's goals, and find many chapters accessible. … Summing Up: Recommended. Upper-division undergraduates through professionals/practitioners.” (D. V. Feldman, Choice, Vol. 53 (12), September, 2016)Table of ContentsPreface.- Permutations, Partitions, and Power Series.- Symmetric Functions.- Counting with the Elementary and Homogeneous.- Counting with a Nonstandard Basis.- Counting with RSK.- Counting Problems that Involve Symmetry.- Consecutive Patterns.- The Reciprocity Method.- Appendix: Transition Matrices.- References.- Index.

Read more less

Book SynopsisThis book is an elegant and rigorous presentation of integer programming, exposing the subject’s mathematical depth and broad applicability. Special attention is given to the theory behind the algorithms used in state-of-the-art solvers. An abundance of concrete examples and exercises of both theoretical and real-world interest explore the wide range of applications and ramifications of the theory. Each chapter is accompanied by an expertly informed guide to the literature and special topics, rounding out the reader’s understanding and serving as a gateway to deeper study.Key topics include: formulations polyhedral theory cutting planes decomposition enumeration semidefinite relaxations Written by renowned experts in integer programming and combinatorial optimization, Integer Programming is destined to become an essential text in the field.Trade Review“Integer Programming begins by introducing the subject and giving several examples of integer programming problems. … This book would be suitable for a graduate level course on the mathematics of cutting plane methods. … This book might also be of interest as a reference for researchers working in this area. … This book offers a more focused presentation that makes it better suited for use as a textbook.” (Brian Borchers, MAA Reviews, maa.org, December, 2015)“The book is written in a very clear and didactic style. … very useful for mathematically mature undergraduates, graduate students, postdocs, and established researchers who are interested in the techniques. …This is an excellent and impressive book. We wholeheartedly recommend it as a textbook for advanced undergraduate and introductory graduate courses on integer programming.” (Jakub Marecek, Interfaces, Vol. 45 (5), September-October, 2015)“The authors deliver a comprehensive presentation of integer programming. … Everything is presented in a rigorous way, but on the other hand, the form makes it easy to understand for everyone. Each chapter is followed by the exercises, that allow to recall the contents. … the book is an essential text in the field of integer programing, that should be recommended as a very useful textbook for students, but also a valuable introduction for the researchers in this area.” (Marcin Anholcer, zbMATH 1307.90001, 2015)Table of ContentsPreface.- 1 Getting Started.- 2 Integer Programming Models.- 3 Linear Inequalities and Polyhedra.- 4 Perfect Formulations.- 5 Split and Gomory Inequalities.- 6 Intersection Cuts and Corner Polyhedra.- 7 Valid Inequalities for Structured Integer Programs.- 8 Reformulations and Relaxations.- 9 Enumeration.- 10 Semidefinite Bounds.- Bibliography.- Index.

Read more less