Cellular automata can be viewed both as computational models and modelling systems of real processes. This volume emphasises the first aspect. In articles written by leading researchers, sophisticated massive parallel algorithms (firing squad, life, Fischer's primes recognition) are treated. Their computational power and the specific complexity classes they determine are surveyed, while some recent results in relation to chaos from a new dynamic systems point of view are also presented. Audience: This book will be of interest to specialists of theoretical computer science and the parallelism challenge.

This book has grown out of graduate courses given by the author at Southern Illinois University, Carbondale, as well as a series of seminars delivered at Curtin University of Technology, Western Australia. The book is intended to be used both as a textbook at the graduate level and also as a professional reference. The topic of one-factorizations fits into the theory of combinatorial designs just as much as it does into graph theory. Factors and factorizations occur as building blocks in the theory of designs in a number of places. Our approach owes as much to design theory as it does to graph theory. It is expected that nearly all readers will have some background in the theory of graphs, such as an advanced undergraduate course in Graph Theory or Applied Graph Theory. However, the book is self-contained, and the first two chapters are a thumbnail sketch of basic graph theory. Many readers will merely skim these chapters, observing our notational conventions along the way. (These introductory chapters could, in fact, enable some instructors to Ilse the book for a somewhat eccentric introduction to graph theory.) Chapter 3 introduces one-factors and one-factorizations. The next two chapters outline two major application areas: combinatorial arrays and tournaments. These two related areas have provided the impetus for a good deal of study of one-factorizations.

Bayesian decision theory is known to provide an effective framework for the practical solution of discrete and nonconvex optimization problems. This book is the first to demonstrate that this framework is also well suited for the exploitation of heuristic methods in the solution of such problems, especially those of large scale for which exact optimization approaches can be prohibitively costly. The book covers all aspects ranging from the formal presentation of the Bayesian Approach, to its extension to the Bayesian Heuristic Strategy, and its utilization within the informal, interactive Dynamic Visualization strategy. The developed framework is applied in forecasting, in neural network optimization, and in a large number of discrete and continuous optimization problems. Specific application areas which are discussed include scheduling and visualization problems in chemical engineering, manufacturing process control, and epidemiology. Computational results and comparisons with a broad range of test examples are presented. The software required for implementation of the Bayesian Heuristic Approach is included. Although some knowledge of mathematical statistics is necessary in order to fathom the theoretical aspects of the development, no specialized mathematical knowledge is required to understand the application of the approach or to utilize the software which is provided. Audience: The book is of interest to both researchers in operations research, systems engineering, and optimization methods, as well as applications specialists concerned with the solution of large scale discrete and/or nonconvex optimization problems in a broad range of engineering and technological fields. It may be used as supplementary material for graduate level courses.

Random Generation of Trees is about a field on the crossroads between computer science, combinatorics and probability theory. Computer scientists need random generators for performance analysis, simulation, image synthesis, etc. In this context random generation of trees is of particular interest. The algorithms presented here are efficient and easy to code. Some aspects of Horton--Strahler numbers, programs written in C and pictures are presented in the appendices. The complexity analysis is done rigorously both in the worst and average cases. Random Generation of Trees is intended for students in computer science and applied mathematics as well as researchers interested in random generation.

This volume contains a collection of papers in Analytic and Elementary Number Theory in memory of Professor Paul Erd s, one of the greatest mathematicians of this century. Written by many leading researchers, the papers deal with the most recent advances in a wide variety of topics, including arithmetical functions, prime numbers, the Riemann zeta function, probabilistic number theory, properties of integer sequences, modular forms, partitions, and q-series. Audience: Researchers and students of number theory, analysis, combinatorics and modular forms will find this volume to be stimulating.

The role of Hilbert polynomials in commutative and homological algebra as well as in algebraic geometry and combinatorics is well known. A similar role in differential algebra is played by the differential dimension polynomials. The notion of differential dimension polynomial was introduced by E. Kolchin in 1964 [KoI64]' but the problems and ideas that had led to this notion (and that are reflected in this book) have essentially more long history. Actually, one can say that the differential dimension polynomial describes in exact terms the freedom degree of a dynamic system as well as the number of arbitrary constants in the general solution of a system of algebraic differential equations. The first attempts of such description were made at the end of 19th century by Jacobi [Ja890] who estimated the number of algebraically independent constants in the general solution of a system of linear ordinary differential equations. Later on, Jacobi's results were extended to some cases of nonlinear systems, but in general case the problem of such estimation (that is known as the problem of Jacobi's bound) remains open. There are some generalization of the problem of Jacobi's bound to the partial differential equations, but the results in this area are just appearing. At the beginning of the 20th century algebraic methods in the theory of differen tial equations were actively developed by F. Riquier [RiqlO] and M.

Lectures: T.H. Brylawski: The Tutte polynomial.- D.J.A. Welsh: Matroids and combinatorial optimisation.- Seminars: M. Barnabei, A. Brini, G.-C. Rota: Un introduzione alla teoria delle funzioni di M bius.- A. Brini: Some remarks on the critical problem.- J. Oxley: On 3-connected matroids and graphs.- R. Peele: The poset of subpartitions and Cayley 's formula for the complexity of a complete graph.- A. Recski: Engineering applications of matroids.- T. Zaslavisky: Voltage-graphic matroids.

This textbook illuminates the field of discrete mathematics with examples, theory, and applications of the discrete volume of a polytope. The authors have weaved a unifying thread through basic yet deep ideas in discrete geometry, combinatorics, and number theory. We encounter here a friendly invitation to the field of "counting integer points in polytopes," and its various connections to elementary finite Fourier analysis, generating functions, the Frobenius coin-exchange problem, solid angles, magic squares, Dedekind sums, computational geometry, and more. With 250 exercises and open problems, the reader feels like an active participant.

Networked computers are ubiquitous, and are subject to attack, misuse, and abuse. One method to counteracting this cyber threat is to provide security analysts with better tools to discover patterns, detect anomalies, identify correlations, and communicate their findings. Visualization for computer security (VizSec) researchers and developers are doing just that. VizSec is about putting robust information visualization tools into the hands of human analysts to take advantage of the power of the human perceptual and cognitive processes in solving computer security problems. This volume collects the papers presented at the 4th International Workshop on Computer Security - VizSec 2007.

Decision makers in managerial and public organizations often encounter de cision problems under conflict or competition, because they select strategies independently or by mutual agreement and therefore their payoffs are then affected by the strategies of the other decision makers. Their interests do not always coincide and are at times even completely opposed. Competition or partial cooperation among decision makers should be considered as an essen tial part of the problem when we deal with the decision making problems in organizations which consist of decision makers with conflicting interests. Game theory has been dealing with such problems and its techniques have been used as powerful analytical tools in the resolution process of the decision problems. The publication of the great work by J. von Neumann and O. Morgen stern in 1944 attracted attention of many people and laid the foundation of game theory. We can see remarkable advances in the field of game theory for analysis of economic situations and a number of books in the field have been published in recent years. The aim of game theory is to specify the behavior of each player so as to optimize the interests of the player. It then recommends a set of solutions as strategies so that the actions chosen by each decision maker (player) lead to an outcome most profitable for himself or her self."

This book features articles written by some of the most prominent leading applied mathematicians as well as young and promising ones. The common objective of these articles is to present an important issue which is currently widely discussed in scientific investigation with major human, economic or ecological implications. Each article is as deep as an expert lecture but is also self-contained, so that even isolated scientists with limited resources can profit greatly from it.

The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3-7,2008.Althoughthiswouldbeareasontolookback, wewouldratherliketolook forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All - pers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the eld: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network ows and connectivity, approximation algorithms and mat- matical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combi- torial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an activeresearcharea, butthisbookalsocontainsmanynewresults.Highlightingmany of the currently most interesting research directions in combinatorial optimization, we hope that this book constitutes a good basis for future research in these area

Coding theory and cryptography allow secure and reliable data transmission, which is at the heart of modern communication. Nowadays, it is hard to find an electronic device without some code inside. Grobner bases have emerged as the main tool in computational algebra, permitting numerous applications, both in theoretical contexts and in practical situations.

This book is the first book ever giving a comprehensive overview on the application of commutative algebra to coding theory and cryptography. For example, all important properties of algebraic/geometric coding systems (including encoding, construction, decoding, list decoding) are individually analysed, reporting all significant approaches appeared in the literature. Also, stream ciphers, PK cryptography, symmetric cryptography and Polly Cracker systems deserve each a separate chapter, where all the relevant literature is reported and compared. While many short notes hint at new exciting directions, the reader will find that all chapters fit nicely within a unified notation."

Additive combinatorics is a relatively recent term coined to comprehend the developments of the more classical additive number theory, mainly focussed on problems related to the addition of integers. Some classical problems like the Waring problem on the sum of k-th powers or the Goldbach conjecture are genuine examples of the original questions addressed in the area. One of the features of contemporary additive combinatorics is the interplay of a great variety of mathematical techniques, including combinatorics, harmonic analysis, convex geometry, graph theory, probability theory, algebraic geometry or ergodic theory.

This book gathers the contributions of many of the leading researchers in the area and is divided into three parts. The two first parts correspond to the material of the main courses delivered, Additive combinatorics and non-unique factorizations, by Alfred Geroldinger, and Sumsets and structure, by Imre Z. Ruzsa. The third part collects the notes of most of the seminars which accompanied the main courses, and which cover a reasonably large part of the methods, techniques and problems of contemporary additive combinatorics.

Random matrix theory has developed in the last few years, in connection with various fields of mathematics and physics. These notes emphasize the relation with the problem of enumerating complicated graphs, and the related large deviations questions. Such questions are also closely related with the asymptotic distribution of matrices, which is naturally defined in the context of free probability and operator algebra.
The material of this volume is based on a series of nine lectures given at the Saint-Flour Probability Summer School 2006. Lectures were also given by Maury Bramson and Steffen Lauritzen.

The book treats four mathematical concepts which play a fundamental role in many different areas of mathematics: symbolic sums, recurrence (difference) equations, generating functions, and asymptotic estimates. Their key features, in isolation or in combination, their mastery by paper and pencil or by computer programs, and their applications to problems in pure mathematics or to "real world problems" (e.g. the analysis of algorithms) are studied. The book is intended as an algorithmic supplement to the bestselling "Concrete Mathematics" by Graham, Knuth and Patashnik.

The application of geometric algebra to the engineering sciences is a young, active subject of research. The promise of this field is that the mathematical structure of geometric algebra together with its descriptive power will result in intuitive and more robust algorithms.

This book examines all aspects essential for a successful application of geometric algebra: the theoretical foundations, the representation of geometric constraints, and the numerical estimation from uncertain data. Formally, the book consists of two parts: theoretical foundations and applications. The first part includes chapters on random variables in geometric algebra, linear estimation methods that incorporate the uncertainty of algebraic elements, and the representation of geometry in Euclidean, projective, conformal and conic space. The second part is dedicated to applications of geometric algebra, which include uncertain geometry and transformations, a generalized camera model, and pose estimation.

Graduate students, scientists, researchers and practitioners will benefit from this book. The examples given in the text are mostly recent research results, so practitioners can see how to apply geometric algebra to real tasks, while researchers note starting points for future investigations. Students will profit from the detailed introduction to geometric algebra, while the text is supported by the author's visualization software, CLUCalc, freely available online, and a website that includes downloadable exercises, slides and tutorials.

Includes a rich variety of exercises to accompany the exposition of Coxeter groups

Coxeter groups have already been exposited from algebraic and geometric perspectives, but this book will be presenting the combinatorial aspects of Coxeter groups

Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures.

Results and Algorithms New to the Second Edition:

• Cancellation results
• A quadratic recognition algorithm for partial cubes
• Results on the strong isometric dimension
• Computing the Wiener index via canonical isometric embedding
• Connectivity results
• A fractional version of Hedetniemi's conjecture
• Results on the independence number of Cartesian powers of vertex-transitive graphs
• Verification of Vizing's conjecture for chordal graphs
• Results on minimum cycle bases
• Numerous selected recent results, such as complete minors and nowhere-zero flows

The second edition of this classic handbook provides a thorough introduction to the subject and an extensive survey of the field. The first three parts of the book cover graph products in detail. The authors discuss algebraic properties, such as factorization and cancellation, and explore interesting and important classes of subgraphs. The fourth part presents algorithms for the recognition of products and related classes of graphs. The final two parts focus on graph invariants and infinite, directed, and product-like graphs. Sample implementations of selected algorithms and other information are available on the book's website, which can be reached via the authors? home pages.

These notes are devoted to the study of some classical problems in the Geometry of Banach spaces. The novelty lies in the fact that their solution relies heavily on techniques coming from Descriptive Set Theory. Thecentralthemeisuniversalityproblems.Inparticular, thetextprovides an exposition of the methods developed recently in order to treat questions of the following type: (Q) LetC be a class of separable Banach spaces such that every space X in the classC has a certain property, say property (P). When can we ?nd a separable Banach space Y which has property (P) and contains an isomorphic copy of every member ofC? We will consider quite classical properties of Banach spaces, such as "- ing re?exive," "having separable dual," "not containing an isomorphic copy of c," "being non-universal," etc. 0 It turns out that a positive answer to problem (Q), for any of the above mentioned properties, is possible if (and essentially only if) the classC is "simple." The "simplicity" ofC is measured in set theoretic terms. Precisely, if the classC is analytic in a natural "coding" of separable Banach spaces, then we can indeed ?nd a separable space Y which is universal for the class C and satis?es the requirements imposed above.

Honesty in voting, it turns out, is not always the best policy. Indeed, in the early 1970s, Allan Gibbard and Mark Satterthwaite, building on the seminal work of Nobel laureate Kenneth Arrow, proved that with three or more alternatives there is no reasonable voting system that is non-manipulable; voters will always have an opportunity to benefit by submitting a disingenuous ballot. The ensuing decades produced a number of theorems of striking mathematical naturality that dealt with the manipulability of voting systems. This 2005 book presents many of these results from the last quarter of the twentieth century, especially the contributions of economists and philosophers, from a mathematical point of view, with many new proofs. The presentation is almost completely self-contained, and requires no prerequisites except a willingness to follow rigorous mathematical arguments. Mathematics students, as well as mathematicians, political scientists, economists and philosophers will learn why it is impossible to devise a completely unmanipulable voting system.

Scheduled transportation networks give rise to very complex and large-scale networkoptimization problems requiring innovative solution techniques and ideas from mathematical optimization and theoretical computer science. Examples of scheduled transportation include bus, ferry, airline, and railway networks, with the latter being a prime application domain that provides a fair amount of the most complex and largest instances of such optimization problems. Scheduled transport optimization deals with planning and scheduling problems over several time horizons, and substantial progress has been made for strategic planning and scheduling problems in all transportation domains.

This state-of-the-art survey presents the outcome of an open call for contributions asking for either research papers or state-of-the-art survey articles. We received 24 submissions that underwent two rounds of the standard peer-review process, out of which 18 were finally accepted for publication.

The volume is organized in four parts: Robustness and Recoverability, Robust Timetabling and Route Planning, Robust Planning Under Scarce Resources, and Online Planning: Delay and Disruption Management.

"This is a delightful little paperback which presents a day-by-day transcription of a course taught jointly by P lya and Tarjan at Stanford University...One can count on [P lya and Tarjan] for new insights and a fresh outlook. Both instructors taught by presenting a succession of examples rather than by presenting a body of theory...[The book] is very well suited as supplementary material for any introductory class on combinatorics; as such, it is very highly recommended. Finally, for all of us who like the topic and delight in observing skilled professionals at work, this book is entertaining and, yes, instructive, reading."

Mathematical Reviews (Review of the original hardcover edition)

"The mathematical community welcomes this book as a final contribution to honour the teacher G. P lya."

Zentralblatt MATH (Review of the original hardcover edition)

This book constitutes the refereed proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2009, held in Pittsburgh, PA, USA, in May 2009.

The 20 revised full papers and 10 extended abstracts presented together with 2 invited talks were carefully reviewed and selected from 65 submissions. The papers describe current research in the fields of constraint programming, artificial intelligence, and operations research and present new techniques or new applications in combinatorial optimization, thus exploring ways of solving large-scale, practical optimization problems through integration and hybridization of the fields' different techniques.

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.