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

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

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.

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.

Handbook of Mathematical Induction: Theory and Applications shows how to find and write proofs via mathematical induction. This comprehensive book covers the theory, the structure of the written proof, all standard exercises, and hundreds of application examples from nearly every area of mathematics.

In the first part of the book, the author discusses different inductive techniques, including well-ordered sets, basic mathematical induction, strong induction, double induction, infinite descent, downward induction, and several variants. He then introduces ordinals and cardinals, transfinite induction, the axiom of choice, Zorn s lemma, empirical induction, and fallacies and induction. He also explains how to write inductive proofs.

The next part contains more than 750 exercises that highlight the levels of difficulty of an inductive proof, the variety of inductive techniques available, and the scope of results provable by mathematical induction. Each self-contained chapter in this section includes the necessary definitions, theory, and notation and covers a range of theorems and problems, from fundamental to very specialized.

The final part presents either solutions or hints to the exercises. Slightly longer than what is found in most texts, these solutions provide complete details for every step of the problem-solving process.

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.

Line graphs have the property that their least eigenvalue is greater than or equal to -2, a property shared by generalized line graphs and a finite number of so-called exceptional graphs. This book deals with all these families of graphs in the context of their spectral properties. The authors discuss the three principal techniques that have been employed, namely 'forbidden subgraphs', 'root systems' and 'star complements'. They bring together the major results in the area, including the recent construction of all the maximal exceptional graphs. Technical descriptions of these graphs are included in the appendices, while the bibliography provides over 250 references. This will be an important resource for all researchers with an interest in algebraic graph theory.

With the advent of digital computers more than half a century ago, - searchers working in a wide range of scienti?c disciplines have obtained an extremely powerful tool to pursue deep understanding of natural processes in physical, chemical, and biological systems. Computers pose a great ch- lenge to mathematical sciences, as the range of phenomena available for rigorous mathematical analysis has been enormously expanded, demanding the development of a new generation of mathematical tools. There is an explosive growth of new mathematical disciplines to satisfy this demand, in particular related to discrete mathematics. However, it can be argued that at large mathematics is yet to provide the essential breakthrough to meet the challenge. The required paradigm shift in our view should be compa- ble to the shift in scienti?c thinking provided by the Newtonian revolution over 300 years ago. Studies of large-scale random graphs and networks are critical for the progress, using methods of discrete mathematics, probabil- tic combinatorics, graph theory, and statistical physics. Recent advances in large scale random network studies are described in this handbook, which provides a signi?cant update and extension - yond the materials presented in the "Handbook of Graphs and Networks" published in 2003 by Wiley. The present volume puts special emphasis on large-scale networks and random processes, which deemed as crucial for - tureprogressinthe?eld. Theissuesrelatedtorandomgraphsandnetworks pose very di?cult mathematical questions.

"This book revives and vastly expands the classical theory of resultants and discriminants. Most of the main new results of the book have been published earlier in more than a dozen joint papers of the authors. The book nicely complements these original papers with many examples illustrating both old and new results of the theory." Mathematical Reviews

This thoroughly revised and updated version of the popular textbook on abstract algebra introduces students to easily understood problems and concepts. John Humphreys and Mike Prest include many examples and exercises throughout the book to make it more appealing to students and instructors. The second edition features new sections on mathematical reasoning and polynomials. In addition, three chapters have been completely rewritten and all others have been updated. First Edition Pb (1990): 0-521-35938-4

The papers in this volume were selected for presentation at the 15th Annual InternationalComputing and CombinatoricsConference (COCOON 2009), held during July 13-15, 2009 in Niagara Falls, New York, USA. Previous meetings of this conference were held in Xian (1995), Hong Kong (1996), Shanghai (1997), Taipei(1998), Tokyo(1999), Sydney(2000), Guilin(2001), Singapore(2002), Big Sky (2003), Jeju Island (2004), Kunming (2005), Taipei (2006), Alberta (2007), and Dalian (2008). In response to the Call for Papers, 125 extended abstracts (not counting withdrawn papers) were submitted from 28 countries and regions, of which 51 were accepted. Authors of the submitted papers were from Cyprus (1), The Netherlands (1), Bulgaria (1), Israel (1), Vietnam (2), Finland (1), Puerto Rico (2), Australia (4), Norway (4), Portugal (1) Spain (2), France (16), Republic of Korea(3), Singapore(2), Italy(6), Iran, (4), Greece(7), Poland(4), Switzerland (8), Hong Kong (10), UK (12), India (7), Taiwan (18), Canada (23), China (19), Japan (39), Germany (44), and the USA (77). The submitted papers were evaluated by an international Technical P- gram Committee (TPC) consisting of Srinivas Aluru (Iowa State University, USA), Lars Arge (University of Aarhus, Denmark), Vikraman Arvind (Ins- tute of Mathematical Sciences, India), James Aspnes (Yale University, USA), Mikhail Atallah (Purdue University, USA), Gill Barequet (Technion - Israel - stitute of Technology, Israel), Michael Brudno (University of Toronto, Canada), Jianer Chen (Texas A&M, USA), Bhaskar DasGupta (University of Illinois at Chicago, USA), Anupam Gupta (Carnegie Mellon University, USA), L

Tolerance graphs can be used to quantify the degree to which there is conflict or accord in a system and can provide solutions to questions in the form of "optimum arrangements." Arising from the authors' teaching graduate students in the U.S. and Israel, this book is intended for use in mathematics and computer science, where the subject can be applied to algorithmics. The inclusion of many exercises with partial solutions will increase the appeal of the book to instructors as well as graduate students.

The study of combinatorial isoperimetric problems exploits similarities between discrete optimization problems and the classical continuous setting. Based on his many years of teaching experience, Larry Harper focuses on global methods of problem solving. His text will enable graduate students and researchers to quickly reach the most current state of research in this topic. Harper includes numerous worked examples, exercises and material about applications to computer science.

Combinatorics, a subject dealing with ways of arranging and distributing objects, involves ideas from geometry, algebra, and analysis. The breadth of the theory is matched by that of its applications, which include topics as diverse as codes, circuit design and algorithm complexity. It has thus become an essential tool in many scientific fields. In this second edition the authors have made the text as comprehensive as possible, dealing in a unified manner with such topics as graph theory, extremal problems, designs, colorings, and codes. The depth and breadth of the coverage make the book a unique guide to the whole of the subject. It is ideal for courses on combinatorical mathematics at the advanced undergraduate or beginning graduate level, and working mathematicians and scientists will also find it a valuable introduction and reference.

A graph complex is a finite family of graphs closed under deletion of edges. Graph complexes show up naturally in many different areas of mathematics. Identifying each graph with its edge set, one may view a graph complex as a simplicial complex and hence interpret it as a geometric object. This volume examines topological properties of graph complexes, focusing on homotopy type and homology. Many of the proofs are based on Robin Forman's discrete version of Morse theory.

The British Combinatorial Conference attracts a large following from the U.K. and international research community. Held at the University of Wales, Bangor, in 2003, the speakers included renowned experts on topics currently attracting significant research interest, as well as less traditional areas such as the combinatorics of protecting digital content. All the contributions are survey papers presenting an overview of the state of the art in a particular area.

Local Newforms for GSp(4) describes a theory of new- and oldforms for representations of GSp(4) over a non-archimedean local field. This theory considers vectors fixed by the paramodular groups, and singles out certain vectors that encode canonical information, such as L-factors and epsilon-factors, through their Hecke and Atkin-Lehner eigenvalues. While there are analogies to the GL(2) case, this theory is novel and unanticipated by the existing framework of conjectures. An appendix includes extensive tables about the results and the representation theory of GSp(4).