Computational Complexity of Counting and Sampling provides readers with comprehensive and detailed coverage of the subject of computational complexity. It is primarily geared toward researchers in enumerative combinatorics, discrete mathematics, and theoretical computer science. The book covers the following topics: Counting and sampling problems that are solvable in polynomial running time, including holographic algorithms; #P-complete counting problems; and approximation algorithms for counting and sampling. First, it opens with the basics, such as the theoretical computer science background and dynamic programming algorithms. Later, the book expands its scope to focus on advanced topics, like stochastic approximations of counting discrete mathematical objects and holographic algorithms. After finishing the book, readers will agree that the subject is well covered, as the book starts with the basics and gradually explores the more complex aspects of the topic. Features: Each chapter includes exercises and solutions Ideally written for researchers and scientists Covers all aspects of the topic, beginning with a solid introduction, before shifting to computational complexity's more advanced features, with a focus on counting and sampling

This is the concluding volume of the second edition of the standard text on design theory. Since the first edition there has been extensive development of the theory and this book has been thoroughly rewritten to reflect this. In particular the growing importance of discrete mathematics to many parts of engineering and science have made designs a useful tool for applications, and this fact has been acknowledged here with the inclusion of an additional chapter on applications. It is suitable for advanced courses and as a reference work, not only for researchers in discrete mathematics or finite algebra, but also for those working in computer and communications engineering and other mathematically oriented disciplines. Exercises are included throughout, and the book concludes with an extensive and updated bibliography of well over 1800 items.

This volume constitutes the refereed proceedings of the 11th International Workshop on Combinatorial Image Analysis, IWCIA 2006, held in Berlin, June 2006. The book presents 34 revised full papers together with two invited papers, covering topics including combinatorial image analysis; grammars and models for analysis and recognition of scenes and images; combinatorial topology and geometry for images; digital geometry of curves and surfaces; algebraic approaches to image processing, and more.

During 1996-97 MSRI held a full academic-year program on combinatorics, with special emphasis on its connections to other branches of mathematics, such as algebraic geometry, topology, commutative algebra, representation theory, and convex geometry. The rich combinatorial problems arising from the study of various algebraic structures are the subject of this book, which features work done or presented at the program's seminars. The text contains contributions on matroid bundles, combinatorial representation theory, lattice points in polyhedra, bilinear forms, combinatorial differential topology and geometry, Macdonald polynomials and geometry, enumeration of matchings, the generalized Baues problem, and Littlewood-Richardson semigroups. These expository articles, written by some of the most respected researchers in the field, present the state of the art to graduate students and researchers in combinatorics as well as in algebra, geometry, and topology.

The theme of this book is the study of the distribution of integer powers modulo a prime number. It provides numerous new, sometimes quite unexpected, links between number theory and computer science as well as to other areas of mathematics. Possible applications include (but are not limited to) complexity theory, random number generation, cryptography, and coding theory. The main method discussed is based on bounds of exponential sums. Accordingly, the book contains many estimates of such sums, including new estimates of classical Gaussian sums. It also contains many open questions and proposals for further research.

The British Combinatorial Conference is one of the most well-known meetings for combinatorialists. This volume collects the invited talks from the 1999 conference held at the University of Kent, and together these span a broad range of combinatorial topics. The nine talks are from: S. Ball, J. Dinitz, M. Dyer, K. Metsch, J. Pach, R. Thomas, C. Thomassen, N. Wormald, plus a special contribution from W. T. Tutte. All researchers into combinatorics will find that this volume is an outstanding and up-to-date resource.

This book is the first volume in a two-volume set, which will provide the complete proof of classification of two important classes of geometries, closely related to each other: Petersen and tilde geometries. There is an infinite family of tilde geometries associated with nonsplit extensions of symplectic groups over a field of two elements. Besides that there are twelve exceptional Petersen and tilde geometries. These exceptional geometries are related to sporadic simple groups, including the famous Monster group and this volume gives a construction for each of the Petersen and tilde geometries that provides an independent existence proof for the corresponding automorphism group. Important applications of Petersen and tilde geometries are considered, including the so-called Y-presentations for the Monster and related groups, and a complete identification of Y-groups is given. This is an essential purchase for researchers in finite group theory, finite geometries and algebraic combinatorics.

The Mathematics of Chip-firing is a solid introduction and overview of the growing field of chip-firing. It offers an appreciation for the richness and diversity of the subject. Chip-firing refers to a discrete dynamical system - a commodity is exchanged between sites of a network according to very simple local rules. Although governed by local rules, the long-term global behavior of the system reveals fascinating properties. The Fundamental properties of chip-firing are covered from a variety of perspectives. This gives the reader both a broad context of the field and concrete entry points from different backgrounds. Broken into two sections, the first examines the fundamentals of chip-firing, while the second half presents more general frameworks for chip-firing. Instructors and students will discover that this book provides a comprehensive background to approaching original sources. Features: Provides a broad introduction for researchers interested in the subject of chip-firing The text includes historical and current perspectives Exercises included at the end of each chapter About the Author: Caroline J. Klivans received a BA degree in mathematics from Cornell University and a PhD in applied mathematics from MIT. Currently, she is an Associate Professor in the Division of Applied Mathematics at Brown University. She is also an Associate Director of ICERM (Institute for Computational and Experimental Research in Mathematics). Before coming to Brown she held positions at MSRI, Cornell and the University of Chicago. Her research is in algebraic, geometric and topological combinatorics.

The Mathematics of Chip-firing is a solid introduction and overview of the growing field of chip-firing. It offers an appreciation for the richness and diversity of the subject. Chip-firing refers to a discrete dynamical system - a commodity is exchanged between sites of a network according to very simple local rules. Although governed by local rules, the long-term global behavior of the system reveals fascinating properties. The Fundamental properties of chip-firing are covered from a variety of perspectives. This gives the reader both a broad context of the field and concrete entry points from different backgrounds. Broken into two sections, the first examines the fundamentals of chip-firing, while the second half presents more general frameworks for chip-firing. Instructors and students will discover that this book provides a comprehensive background to approaching original sources. Features: Provides a broad introduction for researchers interested in the subject of chip-firing The text includes historical and current perspectives Exercises included at the end of each chapter About the Author: Caroline J. Klivans received a BA degree in mathematics from Cornell University and a PhD in applied mathematics from MIT. Currently, she is an Associate Professor in the Division of Applied Mathematics at Brown University. She is also an Associate Director of ICERM (Institute for Computational and Experimental Research in Mathematics). Before coming to Brown she held positions at MSRI, Cornell and the University of Chicago. Her research is in algebraic, geometric and topological combinatorics.

Thisvolumeconsistsofpapersselectedfromthe presentationsgivenatthe Int- national Workshop and Symposium on "Applications of Graph Transformation with Industrial Relevance" (AGTIVE 2003). The papers underwent up to two additional reviews. This volume contains the revised versions of these papers. AGTIVE2003wasthesecondeventoftheGraphTransformationcommunity. The aim of AGTIVE is to unite people from research and industry interested in the application of Graph Transformation to practical problems. The ?rst wo- shoptookplaceatKerkrade,TheNetherlands.Theproceedingsappearedasvol. 1779ofSpringer-Verlags'sLectureNotesinComputerScienceseries.Thissecond workshop, AGTIVE 2003, was held in historic Charlottesville, Virginia, USA. Graphs constitute well-known, well-understood, and frequently used means to depict networks of related items in di?erent application domains. Various typesofgraphtransformationapproaches- alsocalledgraphgrammarsorgraph rewriting systems - have been proposed to specify, recognize, inspect, modify, anddisplaycertainclassesofgraphsrepresentingstructuresofdi?erentdomains. Research activities based on Graph Transformations (GT for short) cons- tute a well-established scienti?c discipline within Computer Science. The int- national GT research community is quite active and has organized international workshops and the conference ICGT 2002. The proceedings of these events, a three volume handbook on GT, and books on speci?c approaches as well as big application projects give a good documentation about research in the GT ?eld (see the list at the end of the proceedings). The intention of all these activities has been (1) to bring together the - ternational community in a viable scienti?c discussion, (2) to integrate di?erent approaches, and (3) to build a bridge between theory and practice.

The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed account of newer topics, including Szemer\'edi's Regularity Lemma and its use, Shelah's extension of the Hales-Jewett Theorem, the precise nature of the phase transition in a random graph process, the connection between electrical networks and random walks on graphs, and the Tutte polynomial and its cousins in knot theory. In no other branch of mathematics is it as vital to tackle and solve challenging exercises in order to master the subject. To this end, the book contains an unusually large number of well thought-out exercises: over 600 in total. Although some are straightforward, most of them are substantial, and others will stretch even the most able reader.

The book is devoted to the study of classical combinatorial structures such as random graphs, permutations, and systems of random linear equations in finite fields. The author shows how the application of the generalized scheme of allocation in the study of random graphs and permutations reduces the combinatorial problems to classical problems of probability theory on the summation of independent random variables. He offers recent research by Russian mathematicians, including a discussion of equations containing an unknown permutation, and the first English-language presentation of techniques for solving systems of random linear equations in finite fields. These new results will interest specialists in combinatorics and probability theory and will also be useful to researchers in applied areas of probabilistic combinatorics such as communication theory, cryptology, and mathematical genetics.

a ~Networka (TM) is a heavily overloaded term, so that a ~network analysisa (TM) means different things to different people. Specific forms of network analysis are used in the study of diverse structures such as the Internet, interlocking directorates, transportation systems, epidemic spreading, metabolic pathways, the Web graph, electrical circuits, project plans, and so on. There is, however, a broad methodological foundation which is quickly becoming a prerequisite for researchers and practitioners working with network models.

From a computer science perspective, network analysis is applied graph theory. Unlike standard graph theory books, the content of this book is organized according to methods for specific levels of analysis (element, group, network) rather than abstract concepts like paths, matchings, or spanning subgraphs. Its topics therefore range from vertex centrality to graph clustering and the evolution of scale-free networks.

In 15 coherent chapters, this monograph-like tutorial book introduces and surveys the concepts and methods that drive network analysis, and is thus the first book to do so from a methodological perspective independent of specific application areas.

ICGT 2004 was the 2nd International Conference on Graph Transformation, following the ?rst one in Barcelona (2002), and a series of six international workshops on graph grammars with applications in computer science between 1978 and 1998. ICGT 2004 was held in Rome (Italy), Sept. 29 Oct. 1, 2004 under the auspices of the European Association for Theoretical Computer S- ence (EATCS), the European Association of Software Science and Technology (EASST), and the IFIP WG 1.3, Foundations of Systems Speci?cation. The scope of the conference concerned graphical structures of various kinds (like graphs, diagrams, visual sentences and others) that are useful when - scribing complex structures and systems in a direct and intuitive way. These structures are often augmented with formalisms that add to the static descr- tion a further dimension, allowing for the modelling of the evolution of systems via all kinds of transformations of such graphical structures. The ?eld of graph transformation is concerned with the theory, applications, and implementation issues of such formalisms. The theory is strongly related to areas such as graph theory and graph - gorithms, formal language and parsing theory, the theory of concurrent and distributed systems, formal speci?cation and veri?cation, logic, and semantics. The application areas include all those ?elds of computer science, information processing, engineering, andthe naturalsciences wherestatic anddynamicm- elling using graphical structures and graph transformations, respectively, play important roles. In many of these areas tools based on graph transformation technology have been implemented and used."

Bipartite graphs are perhaps the most basic of objects in graph theory, both from a theoretical and practical point of view. Until now, they have been considered only as a special class in some wider context. This work deals solely with bipartite graphs, providing traditional material as well as many new and unusual results. The authors illustrate the theory with many applications, especially to problems in timetabling, chemistry, communication networks and computer science. The material is accessible to any reader with a graduate understanding of mathematics and will be of interest to specialists in combinatorics and graph theory.

This text presents six mini-courses, all devoted to interactions between representation theory of algebras, homological algebra, and the new ever-expanding theory of cluster algebras. The interplay between the topics discussed in this text will continue to grow and this collection of courses stands as a partial testimony to this new development. The courses are useful for any mathematician who would like to learn more about this rapidly developing field; the primary aim is to engage graduate students and young researchers. Prerequisites include knowledge of some noncommutative algebra or homological algebra. Homological algebra has always been considered as one of the main tools in the study of finite-dimensional algebras. The strong relationship with cluster algebras is more recent and has quickly established itself as one of the important highlights of today's mathematical landscape. This connection has been fruitful to both areas-representation theory provides a categorification of cluster algebras, while the study of cluster algebras provides representation theory with new objects of study. The six mini-courses comprising this text were delivered March 7-18, 2016 at a CIMPA (Centre International de Mathematiques Pures et Appliquees) research school held at the Universidad Nacional de Mar del Plata, Argentina. This research school was dedicated to the founder of the Argentinian research group in representation theory, M.I. Platzeck. The courses held were: Advanced homological algebra Introduction to the representation theory of algebras Auslander-Reiten theory for algebras of infinite representation type Cluster algebras arising from surfaces Cluster tilted algebras Cluster characters Introduction to K-theory Brauer graph algebras and applications to cluster algebras

This volume presents the proceedings of the 10th International Workshop on Combinatorial Image Analysis, held December 1 3, 2004, in Auckland, New Zealand. Prior meetings took place in Paris (France, 1991), Ube (Japan, 1992), Washington DC (USA, 1994), Lyon (France, 1995), Hiroshima (Japan, 1997), Madras (India, 1999), Caen (France, 2000), Philadelphia (USA, 2001), and - lermo (Italy, 2003). For this workshop we received 86 submitted papers from 23 countries. Each paper was evaluated by at least two independent referees. We selected 55 papers for the conference. Three invited lectures by Vladimir Kovalevsky (Berlin), Akira Nakamura (Hiroshima), and Maurice Nivat (Paris) completed the program. Conference papers are presented in this volume under the following topical part titles: discrete tomography (3 papers), combinatorics and computational models (6), combinatorial algorithms (6), combinatorial mathematics (4), d- ital topology (7), digital geometry (7), approximation of digital sets by curves and surfaces (5), algebraic approaches (5), fuzzy image analysis (2), image s- mentation (6), and matching and recognition (7). These subjects are dealt with in the context of digital image analysis or computer vision."

This volume consists of the refereed papers presented at the Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT 2003), held on September 13 16, 2003 at ITB, Bandung, Indonesia. This conf- ence can also be considered as a series of the Japan Conference on Discrete and Computational Geometry (JCDCG), which has been held annually since 1997. The ?rst ?ve conferences of the series were held in Tokyo, Japan, the sixth in Manila, the Philippines, in 2001, and the seventh in Tokyo, Japan in 2002. The proceedings of JCDCG 1998, JCDCG 2000 and JCDCG 2002 were p- lished by Springer as part of the series Lecture Notes in Computer Science: LNCS volumes 1763, 2098 and 2866, respectively. The proceedings of JCDCG 2001 were also published by Springer as a special issue of the journal Graphs and Combinatorics, Vol. 18, No. 4, 2002. TheorganizersaregratefultotheDepartmentofMathematics, InstitutTek- logi Bandung (ITB) and Tokai University for sponsoring the conference. We also thank all program committee members and referees for their excellent work. Our big thanks to the principal speakers: Hajo Broersma, Mikio Kano, Janos Pach andJorgeUrrutia.Finally, ourthanksalsogoestoallourcolleagueswhoworked hard to make the conference enjoyable and successful. August 2004 Jin Akiyama Edy Tri Baskoro Mikio Kano Organization The Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT) 2003 was organized by the Department of Mathematics, InstitutTeknologiBandung(ITB)IndonesiaandRIED, TokaiUniversity, Japan

The combinatorial theory of species, introduced by Joyal in 1980, provides a unified understanding of the use of generating functions for both labeled and unlabeled structures as well as a tool for the specification and analysis of these structures. This key reference presents the basic elements of the theory and gives a unified account of its developments and applications. The authors offer a modern introduction to the use of various generating functions, with applications to graphical enumeration, Polya Theory and analysis of data structures in computer science, and to other areas such as special functions, functional equations, asymptotic analysis, and differential equations.

This self-contained book examines results on transfinite graphs and networks achieved through a continuing research effort during the past several years. These new results, covering the mathematical theory of electrical circuits, are different from those presented in two previously published books by the author, Transfiniteness for Graphs, Electrical Networks, and Random Walks and Pristine Transfinite Graphs and Permissive Electrical Networks.

Two initial chapters present the preliminary theory summarizing all essential ideas needed for the book and will relieve the reader from any need to consult those prior books. Subsequent chapters are devoted entirely to novel results and cover:

* Connectedness ideas---considerably more complicated for transfinite graphs as compared to those of finite or conventionally infinite graphs----and their relationship to hypergraphs

* Distance ideas---which play an important role in the theory of finite graphs---and their extension to transfinite graphs with more complications, such as the replacement of natural-number distances by ordinal-number distances

* Nontransitivity of path-based connectedness alleviated by replacing paths with walks, leading to a more powerful theory for transfinite graphs and networks

Additional features include:

* The use of nonstandard analysis in novel ways that leads to several entirely new results concerning hyperreal operating points for transfinite networks and hyperreal transients on transfinite transmission lines; this use of hyperreals encompasses for the first time transfinite networks and transmission lines containing inductances and capacitances, in addition to resistances

* A useful appendix with concepts from nonstandard analysis used in the book

* May serve as a reference text or as a graduate-level textbook in courses or seminars

Graphs and Networks: Transfinite and Nonstandard will appeal to a diverse readership, including graduate students, electrical engineers, mathematicians, and physicists working on infinite electrical networks. Moreover, the growing and presently substantial number of mathematicians working in nonstandard analysis may well be attracted by the novel application of the analysis employed in the work.

ISBN 0-8176-4292-7

Boundaries and Hulls of Euclidean Graphs: From Theory to Practice presents concepts and algorithms for finding convex, concave and polygon hulls of Euclidean graphs. It also includes some implementations, determining and comparing their complexities. Since the implementation is application-dependent, either centralized or distributed, some basic concepts of the centralized and distributed versions are reviewed. Theoreticians will find a presentation of different algorithms together with an evaluation of their complexity and their utilities, as well as their field of application. Practitioners will find some practical and real-world situations in which the presented algorithms can be used.

This volume presents up-to-date research on finite geometries and designs, a key area in modern applicable mathematics. An introductory chapter discusses topics presented in each of the main chapters, and is followed by articles from leading international figures in this field. These include a discussion of the current state of finite geometry from a group-theoretical viewpoint, and surveys of difference sets and of small embeddings of partial cycle systems into Steiner triple systems. Also presented are successful searches for spreads and packing of designs, rank three geometries with simplicial residues and generalized quadrangles satisfying Veblen's Axiom. In addition, there are articles on new 7-designs, biplanes, various aspects of triple systems, and many other topics. This book will be a useful reference for researchers working in finite geometries, design theory or combinatorics in general.

This volume consists of the papers presented by the invited lecturers at the 16th British Combinatorial Conference. This biennial meeting is one of the most important for combinatorialists, attracting leading figures in the field. This overview of up-to-date research will be a valuable resource for researchers and graduate students.

The first of two companion volumes on anabelian algebraic geometry, this book contains the famous, but hitherto unpublished manuscript 'Esquisse d'un Programme' (Sketch of a Program) by Alexander Grothendieck. This work, written in 1984, fourteen years after his retirement from public life in mathematics, together with the closely connected letter to Gerd Faltings, dating from 1983 and also published for the first time in this volume, describe a powerful program of future mathematics, unifying aspects of geometry and arithmetic via the central point of moduli spaces of curves; it is written in an artistic and informal style. The book also contains several articles on subjects directly related to the ideas explored in the manuscripts; these are surveys of mathematics due to Grothendieck, explanations of points raised in the Esquisse, and surveys on progress in the domains described there.

Paul Erdoes was one of the greatest mathematicians of this century, known the world over for his brilliant ideas and stimulating questions. On the date of his 80th birthday a conference was held in his honour at Trinity College, Cambridge. Many leading combinatorialists attended. Their subsequent contributions are collected here. The areas represented range from set theory and geometry, through graph theory, group theory and combinatorial probability, to randomised algorithms and statistical physics. Erdoes himself was able to give a survey of recent progress made on his favourite problems. Consequently this volume, consisting of in-depth studies at the frontier of research, provides a valuable panorama across the breadth of combinatorics as it is today.