This collaborative book presents recent trends on the study of sequences, including combinatorics on words and symbolic dynamics, and new interdisciplinary links to group theory and number theory. Other chapters branch out from those areas into subfields of theoretical computer science, such as complexity theory and theory of automata. The book is built around four general themes: number theory and sequences, word combinatorics, normal numbers, and group theory. Those topics are rounded out by investigations into automatic and regular sequences, tilings and theory of computation, discrete dynamical systems, ergodic theory, numeration systems, automaton semigroups, and amenable groups. This volume is intended for use by graduate students or research mathematicians, as well as computer scientists who are working in automata theory and formal language theory. With its organization around unified themes, it would also be appropriate as a supplemental text for graduate level courses.

This book is the very first one in the English language entirely dedicated to the Lambert W function, its generalizations, and its applications. One goal is to promote future research on the topic. The book contains all the information one needs when trying to find a result. The most important formulas and results are framed. The Lambert W function is a multi-valued inverse function with plenty of applications in areas like molecular physics, relativity theory, fuel consumption models, plasma physics, analysis of epidemics, bacterial growth models, delay differential equations, fluid mechanics, game theory, statistics, study of magnetic materials, and so on. The first part of the book gives a full treatise of the W function from theoretical point of view. The second part presents generalizations of this function which have been introduced by the need of applications where the classical W function is insufficient. The third part presents a large number of applications from physics, biology, game theory, bacterial cell growth models, and so on. The second part presents the generalized Lambert functions based on the tools we had developed in the first part. In the third part familiarity with Newtonian physics will be useful. The text is written to be accessible for everyone with only basic knowledge on calculus and complex numbers. Additional features include the Further Notes sections offering interesting research problems and information for further studies. Mathematica codes are included. The Lambert function is arguably the simplest non-elementary transcendental function out of the standard set of sin, cos, log, etc., therefore students who would like to deepen their understanding of real and complex analysis can see a new "almost elementary" function on which they can practice their knowledge.

This book is the first general and extensive review on the algorithmics and mathematical results of beyond planar graphs. Most real-world data sets are relational and can be modelled as graphs consisting of vertices and edges. Planar graphs are fundamental for both graph theory and graph algorithms and are extensively studied. Structural properties and fundamental algorithms for planar graphs have been discovered. However, most real-world graphs, such as social networks and biological networks, are non-planar. To analyze and visualize such real-world networks, it is necessary to solve fundamental mathematical and algorithmic research questions on sparse non-planar graphs, called beyond planar graphs.This book is based on the National Institute of Informatics (NII) Shonan Meeting on algorithmics on beyond planar graphs held in Japan in November, 2016. The book consists of 13 chapters that represent recent advances in various areas of beyond planar graph research. The main aims and objectives of this book include 1) to timely provide a state-of-the-art survey and a bibliography on beyond planar graphs; 2) to set the research agenda on beyond planar graphs by identifying fundamental research questions and new research directions; and 3) to foster cross-disciplinary research collaboration between computer science (graph drawing and computational geometry) and mathematics (graph theory and combinatorics). New algorithms for beyond planar graphs will be in high demand by practitioners in various application domains to solve complex visualization problems. This book therefore will be a valuable resource for researchers in graph theory, algorithms, and theoretical computer science, and will stimulate further deep scientific investigations into many areas of beyond planar graphs.

This book presents methods for the summation of infinite and finite series and the related identities and inversion relations. The summation includes the column sums and row sums of lower triangular matrices. The convergence of the summation of infinite series is considered. The author's focus is on symbolic methods and the Riordan array approach. In addition, this book contains hundreds summation formulas and identities, which can be used as a handbook for people working in computer science, applied mathematics, and computational mathematics, particularly, combinatorics, computational discrete mathematics, and computational number theory. The exercises at the end of each chapter help deepen understanding. Much of the materials in this book has never appeared before in textbook form. This book can be used as a suitable textbook for advanced courses for high lever undergraduate and lower lever graduate students. It is also an introductory self-study book for re- searchers interested in this field, while some materials of the book can be used as a portal for further research.

Presented in this monograph is the current state-of-the-art in the theory of convex structures. The notion of convexity covered here is considerably broader than the classic one; specifically, it is not restricted to the context of vector spaces. Classical concepts of order-convex sets (Birkhoff) and of geodesically convex sets (Menger) are directly inspired by intuition; they go back to the first half of this century. An axiomatic approach started to develop in the early Fifties. The author became attracted to it in the mid-Seventies, resulting in the present volume, in which graphs appear side-by-side with Banach spaces, classical geometry with matroids, and ordered sets with metric spaces. A wide variety of results has been included (ranging for instance from the area of partition calculus to that of continuous selection). The tools involved are borrowed from areas ranging from discrete mathematics to infinite-dimensional topology.

Although addressed primarily to the researcher, parts of this monograph can be used as a basis for a well-balanced, one-semester graduate course.

Graphs drawn on two-dimensional surfaces have always attracted researchers by their beauty and by the variety of difficult questions to which they give rise. The theory of such embedded graphs, which long seemed rather isolated, has witnessed the appearance of entirely unexpected new applications in recent decades, ranging from Galois theory to quantum gravity models, and has become a kind of a focus of a vast field of research. The book provides an accessible introduction to this new domain, including such topics as coverings of Riemann surfaces, the Galois group action on embedded graphs (Grothendieck's theory of "dessins d'enfants"), the matrix integral method, moduli spaces of curves, the topology of meromorphic functions, and combinatorial aspects of Vassiliev's knot invariants and, in an appendix by Don Zagier, the use of finite group representation theory. The presentation is concrete throughout, with numerous figures, examples (including computer calculations) and exercises, and should appeal to both graduate students and researchers.

This collection of surveys and research papers on recent topics of interest in combinatorics is dedicated to Paul Erdös, who attended the conference and who is represented by two articles in the collection, including one, unfinished, which he was writing on the eve of his sudden death. Erdös was one of the greatest mathematicians of his century and often the subject of anecdotes about his somewhat unusual lifestyle. A new preface, written by friends and colleagues, gives a flavor of his life, including many such stories, and also describes the broad outline and importance of his work in combinatorics and other related fields.

This book combines traditional graph theory with the matroid view of graphs in order to throw light on the mathematical approach to network analysis. The authors examine in detail two dual structures associated with a graph, namely circuits and cutsets. These are strongly dependent on one another and together constitute a third, hybrid, vertex-independent structure called a graphoid, whose study is here termed hybrid graph theory. This approach has particular relevance for network analysis. The first account of the subject in book form, the text includes many new results as well as the synthesizing and reworking of much research done over the past thirty years (historically, the study of hybrid aspects of graphs owes much to the foundational work of Japanese researchers). This work will be regarded as the definitive account of the subject, suitable for all working in theoretical network analysis: mathematicians, computer scientists or electrical engineers.

This book provides a de?nition and study of a knowledge representation and r- soning formalism stemming from conceptual graphs, while focusing on the com- tational properties of this formalism. Knowledge can be symbolically represented in many ways. The knowledge representation and reasoning formalism presented here is a graph formalism - knowledge is represented by labeled graphs, in the graph theory sense, and r- soning mechanisms are based on graph operations, with graph homomorphism at the core. This formalism can thus be considered as related to semantic networks. Since their conception, semantic networks have faded out several times, but have always returned to the limelight. They faded mainly due to a lack of formal semantics and the limited reasoning tools proposed. They have, however, always rebounded - cause labeled graphs, schemas and drawings provide an intuitive and easily und- standable support to represent knowledge. This formalism has the visual qualities of any graphic model, and it is logically founded. This is a key feature because logics has been the foundation for knowledge representation and reasoning for millennia. The authors also focus substantially on computational facets of the presented formalism as they are interested in knowledge representation and reasoning formalisms upon which knowledge-based systems can be built to solve real problems. Since object structures are graphs, naturally graph homomorphism is the key underlying notion and, from a computational viewpoint, this moors calculus to combinatorics and to computer science domains in which the algorithmicqualitiesofgraphshavelongbeenstudied, asindatabasesandconstraint networks

Features: Suitable for PhD candidates and researchers. Requires prerequisites in set theory, general topology and abstract algebra, but is otherwise self-contained.

Comprehensive presentation of both analytic and probabilistic techniques

As a comprehensive survey of the major techniques of average case analysis, this work presents, in detail, both analytic methods used for well-structured algorithms and probabilistic methods used for more structurally complex algorithms. In particular, the applications in the book use algorithms that focus on data structures on sequences, also called strings, which are widely used in computer science, computational biology, and information theory. Specific techniques covered include the inclusion-exclusion principle, the first and second moment methods, the random coding technique, the subadditive ergodic theorem, large deviations, generating functions, complex asymptotic methods, the Mellin transform, and analytic poissonization and depoissonization. Each method is clearly explained and accompanied by related applications and problems involving algorithms on sequences.

Important features of the book include:

• A foreword by well-known expert Dr. Philippe Flajolet, INRIA, France
• Presentation of complex analysis used to solve discrete and probabilistic problems on sequences
• Discussions of Lempel-Ziv data compression-schemes, the string edit problem, pattern matching algorithms, many variations of digital trees, the leader election algorithm, and more
• A chapter devoted to tools used in information theory, particularly the random coding technique and pattern matching approach to data compression
• Application sections in each chapter that illustrate the methods covered
• An extensive bibliography

Graph theory gained initial prominence in science and engineering through its strong links with matrix algebra and computer science. Moreover, the structure of the mathematics is well suited to that of engineering problems in analysis and design. The methods of analysis in this book employ matrix algebra, graph theory and meta-heuristic algorithms, which are ideally suited for modern computational mechanics. Efficient methods are presented that lead to highly sparse and banded structural matrices. The main features of the book include: application of graph theory for efficient analysis; extension of the force method to finite element analysis; application of meta-heuristic algorithms to ordering and decomposition (sparse matrix technology); efficient use of symmetry and regularity in the force method; and simultaneous analysis and design of structures.

High quality meshes play a key role in many applications based on digital modeling and simulation. The finite element method is a paragon for such an approach and it is well known that quality meshes can significantly improve computational efficiency and solution accuracy of this method. Therefore, a lot of effort has been put in methods for improving mesh quality. These range from simple geometric approaches, like Laplacian smoothing, with a high computational efficiency but possible low resulting mesh quality, to global optimization-based methods, resulting in an excellent mesh quality at the cost of an increased computational and implementational complexity. The geometric element transformation method (GETMe) aims to fill the gap between these two approaches. It is based on geometric mesh element transformations, which iteratively transform polygonal and polyhedral elements into their regular counterparts or into elements with a prescribed shape. GETMe combines a Laplacian smoothing-like computational efficiency with a global optimization-like effectiveness. The method is straightforward to implement and its variants can also be used to improve tangled and anisotropic meshes. This book describes the mathematical theory of geometric element transformations as foundation for mesh smoothing. It gives a thorough introduction to GETMe-based mesh smoothing and its algorithms providing a framework to focus on effectively improving key mesh quality aspects. It addresses the improvement of planar, surface, volumetric, mixed, isotropic, and anisotropic meshes and addresses aspects of combining mesh smoothing with topological mesh modification. The advantages of GETMe-based mesh smoothing are demonstrated by the example of various numerical tests. These include smoothing of real world meshes from engineering applications as well as smoothing of synthetic meshes for demonstrating key aspects of GETMe-based mesh improvement. Results are compared with those of other smoothing methods in terms of runtime behavior, mesh quality, and resulting finite element solution efficiency and accuracy. Features: * Helps to improve finite element mesh quality by applying geometry-driven mesh smoothing approaches. * Supports the reader in understanding and implementing GETMe-based mesh smoothing. * Discusses aspects and properties of GETMe smoothing variants and thus provides guidance for choosing the appropriate mesh improvement algorithm. * Addresses smoothing of various mesh types: planar, surface, volumetric, isotropic, anisotropic, non-mixed, and mixed. * Provides and analyzes geometric element transformations for polygonal and polyhedral elements with regular and non-regular limits. * Includes a broad range of numerical examples and compares results with those of other smoothing methods.

Geometric Data Analysis designates the approach of Multivariate Statistics that conceptualizes the set of observations as a Euclidean cloud of points. Combinatorial Inference in Geometric Data Analysis gives an overview of multidimensional statistical inference methods applicable to clouds of points that make no assumption on the process of generating data or distributions, and that are not based on random modelling but on permutation procedures recasting in a combinatorial framework. It focuses particularly on the comparison of a group of observations to a reference population (combinatorial test) or to a reference value of a location parameter (geometric test), and on problems of homogeneity, that is the comparison of several groups for two basic designs. These methods involve the use of combinatorial procedures to build a reference set in which we place the data. The chosen test statistics lead to original extensions, such as the geometric interpretation of the observed level, and the construction of a compatibility region. Features: Defines precisely the object under study in the context of multidimensional procedures, that is clouds of points Presents combinatorial tests and related computations with R and Coheris SPAD software Includes four original case studies to illustrate application of the tests Includes necessary mathematical background to ensure it is self-contained This book is suitable for researchers and students of multivariate statistics, as well as applied researchers of various scientific disciplines. It could be used for a specialized course taught at either master or PhD level.

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

Boolean Structures: Combinatorics, Codification, Representation offers the first analytical and architectural approach to Boolean algebras based combinatorial calculus and codification with applications in IT, quantum information and classification of data.

This book contains fundamental concepts on discrete mathematical structures in an easy to understand style so that the reader can grasp the contents and explanation easily. The concepts of discrete mathematical structures have application to computer science, engineering and information technology including in coding techniques, switching circuits, pointers and linked allocation, error corrections, as well as in data networking, Chemistry, Biology and many other scientific areas. The book is for undergraduate and graduate levels learners and educators associated with various courses and progammes in Mathematics, Computer Science, Engineering and Information Technology. The book should serve as a text and reference guide to many undergraduate and graduate programmes offered by many institutions including colleges and universities. Readers will find solved examples and end of chapter exercises to enhance reader comprehension. Features Offers comprehensive coverage of basic ideas of Logic, Mathematical Induction, Graph Theory, Algebraic Structures and Lattices and Boolean Algebra Provides end of chapter solved examples and practice problems Delivers materials on valid arguments and rules of inference with illustrations Focuses on algebraic structures to enable the reader to work with discrete structures

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

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

This volume provides an up-to-date survey of current research activity in several areas of combinatorics and its applications. These include distance-regular graphs, combinatorial designs, coding theory, spectra of graphs, and randomness and computation. The articles give an overview of combinatorics that will be extremely useful to both mathematicians and computer scientists.

Most coding theory experts date the origin of the subject with the 1948 publication of A Mathematical Theory of Communication by Claude Shannon. Since then, coding theory has grown into a discipline with many practical applications (antennas, networks, memories), requiring various mathematical techniques, from commutative algebra, to semi-definite programming, to algebraic geometry. Most topics covered in the Concise Encyclopedia of Coding Theory are presented in short sections at an introductory level and progress from basic to advanced level, with definitions, examples, and many references. The book is divided into three parts: Part I fundamentals: cyclic codes, skew cyclic codes, quasi-cyclic codes, self-dual codes, codes and designs, codes over rings, convolutional codes, performance bounds Part II families: AG codes, group algebra codes, few-weight codes, Boolean function codes, codes over graphs Part III applications: alternative metrics, algorithmic techniques, interpolation decoding, pseudo-random sequences, lattices, quantum coding, space-time codes, network coding, distributed storage, secret-sharing, and code-based-cryptography. Features Suitable for students and researchers in a wide range of mathematical disciplines Contains many examples and references Most topics take the reader to the frontiers of research

George Andrews is one of the most influential figures in number theory and combinatorics. In the theory of partitions and q-hypergeometric series and in the study of Ramanujan's work, he is the unquestioned leader. To suitably honor him during his 70th birthday year, an International Conference on Combinatory Analysis was held at The Pennsylvania State University during December 5-7, 2008. Three issues of the Ramanujan Journal comprising Volume 23 were published in 2010 as the refereed proceedings of that conference. The Ramanujan Journal was proud to bring out that volume honoring one of its Founding Editors. In view of the great interest that the mathematical community has in the influential work of Andrews, it was decided to republish Volume 23 of The Ramanujan Journal in this book form, so that the refereed proceedings are more readily available for those who do not subscribe to the journal but wish to possess this volume. As a fitting tribute to George Andrews, many speakers from the conference contributed research papers to this volume which deals with a broad range of areas that signify the research interests of George Andrews. In reproducing Volume 23 of The Ramanujan Journal in this book form, we have included two papers-one by Hei-Chi Chan and Shaun Cooper, and another by Ole Warnaar-which were intended for Volume 23 of The Ramanujan Journal, but appeared in other issues. The enormous productivity of George Andrews remains unabated in spite of the passage of time. His immensely fertile mind continues to pour forth seminal ideas year after year. He has two research papers in this volume. May his eternal youthfulness and his magnificent research output continue to inspire and influence researchers in the years ahead.

Discrete Mathematics for Computer Science: An Example-Based Introduction is intended for a first- or second-year discrete mathematics course for computer science majors. It covers many important mathematical topics essential for future computer science majors, such as algorithms, number representations, logic, set theory, Boolean algebra, functions, combinatorics, algorithmic complexity, graphs, and trees. Features Designed to be especially useful for courses at the community-college level Ideal as a first- or second-year textbook for computer science majors, or as a general introduction to discrete mathematics Written to be accessible to those with a limited mathematics background, and to aid with the transition to abstract thinking Filled with over 200 worked examples, boxed for easy reference, and over 200 practice problems with answers Contains approximately 40 simple algorithms to aid students in becoming proficient with algorithm control structures and pseudocode Includes an appendix on basic circuit design which provides a real-world motivational example for computer science majors by drawing on multiple topics covered in the book to design a circuit that adds two eight-digit binary numbers Jon Pierre Fortney graduated from the University of Pennsylvania in 1996 with a BA in Mathematics and Actuarial Science and a BSE in Chemical Engineering. Prior to returning to graduate school, he worked as both an environmental engineer and as an actuarial analyst. He graduated from Arizona State University in 2008 with a PhD in Mathematics, specializing in Geometric Mechanics. Since 2012, he has worked at Zayed University in Dubai. This is his second mathematics textbook.

Matroid theory was invented in the middle of the 1930s by two mathematicians independently, namely, Hassler Whitney in the USA and Takeo Nakasawa in Japan. Whitney became famous, but Nakasawa remained anonymous until two decades ago. He left only four papers to the mathematical community, all of them written in the middle of the 1930s. It was a bad time to have lived in a country that had become as eccentric as possible. Just as Nazism became more and more flamboyant in Europe in the 1930s, Japan became more and more esoteric and fanatical in the same time period. This book explains the little that is known about Nakasawa s personal life in a Japan that had, among other failures, lost control over its military. This book contains his four papers in German and their English translations as well as some extended commentary on the history of Japan during those years. The book also contains 14 photos of him or his family. Although the veil of mystery surrounding Nakasawa s life has only been partially lifted, the work presented in this book speaks eloquently of a tragic loss to the mathematical community."

This is the first exposition of the theory of quasi-symmetric designs, that is, combinatorial designs with at most two block intersection numbers. The authors aim to bring out the interaction among designs, finite geometries, and strongly regular graphs. The book starts with basic, classical material on designs and strongly regular graphs and continues with a discussion of some important results on quasi-symmetric designs. The later chapters include a combinatorial construction of the Witt designs from the projective plane of order four, recent results dealing with a structural study of designs resulting from Cameron's classification theory on extensions of symmetric designs, and results on the classification problem of quasi-symmetric designs. The final chapter presents connections to coding theory.