Are people ever rational? Consider this: You auction off a one-dollar bill to the highest bidder, but you set the rules so that the second highest bidder also has to pay the amount of his last bid, even though he gets nothing. Would people ever enter such an auction? Not only do they, but according to Martin Shubik, the game's inventor, the average winning bid (for a dollar, remember) is $3.40. Many winners report that they bid so high only because their opponent "went completely crazy." This game lies at the intersection of three subjects of eternal fascination: human psychology, morality, and John von Neumann's game theory. Hungarian game-theorist Laszlo Mero introduces us to the basics of game theory, including such concepts as zero-sum games, Prisoner's Dilemma and the origins of altruism; shows how game theory is applicable to fields ranging from physics to politics; and explores the role of rational thinking in the context of many different kinds of thinking. This fascinating, urbane book will interest everyone who wonders what mathematics can tell us about the human condition.

Rainbow connections are natural combinatorial measures that are used in applications to secure the transfer of classified information between agencies incommunication networks. "Rainbow Connections of Graphs" covers this new and emerging topicin graph theory and brings together a majority of the results that deal with the concept of rainbow connections, first introduced by Chartrand et al. in 2006.

The authors begin with an introduction to rainbow connectedness, rainbow coloring, and rainbow connection number. The work is organized into the followingcategories, computation of the exact valuesof the rainbow connection numbers for some special graphs, algorithms and complexity analysis, upper bounds in terms of other graph parameters, rainbow connection for dense and sparse graphs, for some graph classes andgraph products, rainbow k-connectivity and k-rainbow index, and, rainbow vertex-connection number.
"Rainbow Connections of Graphs" appeals to researchers and graduate students in the field of graph theory. Conjectures, open problems and questions are given throughout the text with the hope for motivating young graph theorists and graduate students to do further study in this subject.

"

This book contains 33 papers from among the 41 papers presented at the Eighth International Conference on Fibonacci Numbers and Their Applications which was held at the Rochester Institute of Technology, Rochester, New York, from June 22 to June 26, 1998. These papers have been selected after a careful review by well known referees in the field, and they range from elementary number theory to probability and statistics. The Fibonacci numbers and recurrence relations are their unifying bond. It is anticipated that this book, like its seven predecessors, will be useful to research workers and graduate students interested in the Fibonacci numbers and their applications. June 1, 1999 The Editor F. T. Howard Mathematics and Computer Science Wake Forest University Box 7388 Reynolda Station Winston-Salem, NC USA xvii THE ORGANIZING COMMITTEES LOCAL COMMITTEE INTERNATIONAL COMMITTEE Anderson, Peter G. , Chairman Horadam, A. F. (Australia), Co-Chair Arpaya, Pasqual Philippou, A. N. (Cyprus), Co-Chair Biles, John Bergum, G. E. (U. S. A. ) Orr, Richard Filipponi, P. (Italy) Radziszowski, Stanislaw Harborth, H. (Germany) Rich, Nelson Horibe, Y. (Japan) Howard, F. (U. S. A. ) Johnson, M. (U. S. A. ) Kiss, P. (Hungary) Phillips, G. M. (Scotland) Turner, J. (New Zealand) Waddill, M. E. (U. S. A. ) xix LIST OF CONTRIBUTORS TO THE CONFERENCE AGRATINI, OCTAVIAN, "Unusual Equations in Study. " *ANDO, SHIRO, (coauthor Daihachiro Sato), "On the Generalized Binomial Coefficients Defined by Strong Divisibility Sequences. " *ANATASSOVA, VASSIA K. , (coauthor J. C.

This is a collection of surveys and research papers on topics of interest in combinatorics, given at a conference in Matrahaza, Hungary. Originally published in journal form, it is here reissued as a book due to its special interest. It is dedicated to Paul Erdoes, 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. Erdoes was one of the greatest mathematicians of his century and often the subject of anecdotes about his somewhat unusual lifestyle. A preface, written by friends and colleagues, gives a flavour of his life, including many such stories, and also describes the broad outline and importance of his work in combinatorics and other related fields. Here is a succinct introduction to important ideas in combinatorics for researchers and graduate students.

This volume, the third in a sequence that began with The Theory of Matroids and Combinatorial Geometries, concentrates on the applications of matroid theory to a variety of topics from engineering (rigidity and scene analysis), combinatorics (graphs, lattices, codes and designs), topology and operations research (the greedy algorithm). As with its predecessors, the contributors to this volume have written their articles to form a cohesive account so that the result is a volume which will be a valuable reference for research workers.

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.

This work presents a data visualization technique that combines graph-based topology representation and dimensionality reduction methods to visualize the intrinsic data structure in a low-dimensional vector space. The application of graphs in clustering and visualization has several advantages. A graph of important edges (where edges characterize relations and weights represent similarities or distances) provides a compact representation of the entire complex data set. This text describes clustering and visualization methods that are able to utilize information hidden in these graphs, based on the synergistic combination of clustering, graph-theory, neural networks, data visualization, dimensionality reduction, fuzzy methods, and topology learning. The work contains numerous examples to aid in the understanding and implementation of the proposed algorithms, supported by a MATLAB toolbox available at an associated website.

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.

Combinatorial Algorithms on Words refers to the collection of manipulations of strings of symbols (words) - not necessarily from a finite alphabet - that exploit the combinatorial properties of the logical/physical input arrangement to achieve efficient computational performances. The model of computation may be any of the established serial paradigms (e.g. RAM's, Turing Machines), or one of the emerging parallel models (e.g. PRAM, WRAM, Systolic Arrays, CCC). This book focuses on some of the accomplishments of recent years in such disparate areas as pattern matching, data compression, free groups, coding theory, parallel and VLSI computation, and symbolic dynamics; these share a common flavor, yet ltave not been examined together in the past. In addition to being theoretically interest ing, these studies have had significant applications. It happens that these works have all too frequently been carried out in isolation, with contributions addressing similar issues scattered throughout a rather diverse body of literature. We felt that it would be advantageous to both current and future researchers to collect this work in a sin gle reference. It should be clear that the book's emphasis is on aspects of combinatorics and com plexity rather than logic, foundations, and decidability. In view of the large body of research and the degree of unity already achieved by studies in the theory of auto mata and formal languages, we have allocated very little space to them."

It has long been recognized that there are fascinating connections between cod ing theory, cryptology, and combinatorics. Therefore it seemed desirable to us to organize a conference that brings together experts from these three areas for a fruitful exchange of ideas. We decided on a venue in the Huang Shan (Yellow Mountain) region, one of the most scenic areas of China, so as to provide the additional inducement of an attractive location. The conference was planned for June 2003 with the official title Workshop on Coding, Cryptography and Combi natorics (CCC 2003). Those who are familiar with events in East Asia in the first half of 2003 can guess what happened in the end, namely the conference had to be cancelled in the interest of the health of the participants. The SARS epidemic posed too serious a threat. At the time of the cancellation, the organization of the conference was at an advanced stage: all invited speakers had been selected and all abstracts of contributed talks had been screened by the program committee. Thus, it was de cided to call on all invited speakers and presenters of accepted contributed talks to submit their manuscripts for publication in the present volume. Altogether, 39 submissions were received and subjected to another round of refereeing. After care ful scrutiny, 28 papers were accepted for publication."

First published in 1993, this thesis is concerned with the design of efficient algorithms for listing combinatorial structures. The research described here gives some answers to the following questions: which families of combinatorial structures have fast computer algorithms for listing their members? What general methods are useful for listing combinatorial structures? How can these be applied to those families which are of interest to theoretical computer scientists and combinatorialists? Amongst those families considered are unlabelled graphs, first order one properties, Hamiltonian graphs, graphs with cliques of specified order, and k-colourable graphs. Some related work is also included, which compares the listing problem with the difficulty of solving the existence problem, the construction problem, the random sampling problem, and the counting problem. In particular, the difficulty of evaluating Polya's cycle polynomial is demonstrated.

This IMA Volume in Mathematics and its Applications ALGORITHMS FOR PARALLEL PROCESSING is based on the proceedings of a workshop that was an integral part of the 1996-97 IMA program on "MATHEMATICS IN HIGH-PERFORMANCE COMPUTING. " The workshop brought together algorithm developers from theory, combinatorics, and scientific computing. The topics ranged over models, linear algebra, sorting, randomization, and graph algorithms and their analysis. We thank Michael T. Heath of University of lllinois at Urbana (Com puter Science), Abhiram Ranade of the Indian Institute of Technology (Computer Science and Engineering), and Robert S. Schreiber of Hewlett Packard Laboratories for their excellent work in organizing the workshop and editing the proceedings. We also take this opportunity to thank the National Science Founda tion (NSF) and the Army Research Office (ARO), whose financial support made the workshop possible. A vner Friedman Robert Gulliver v PREFACE The Workshop on Algorithms for Parallel Processing was held at the IMA September 16 - 20, 1996; it was the first workshop of the IMA year dedicated to the mathematics of high performance computing. The work shop organizers were Abhiram Ranade of The Indian Institute of Tech nology, Bombay, Michael Heath of the University of Illinois, and Robert Schreiber of Hewlett Packard Laboratories. Our idea was to bring together researchers who do innovative, exciting, parallel algorithms research on a wide range of topics, and by sharing insights, problems, tools, and methods to learn something of value from one another."

Quantum field theory is one of most central constructions in 20th century th- retical physics, and it continues to develop rapidly in many different directions. The aim of the workshop "New Developments in Quantum Field Theory," which was held in Zakopane, Poland, June 14-20, 1997, was to capture a broad selection of the most recent advances in this field. The conference was sponsored by the Scientific and - vironmental Affairs Division of NATO, as part of the Advanced Research Workshop series. This book contains the proceedings of that meeting. Major topics covered at the workshop include quantized theories of gravity, string theory, conformal field theory, cosmology, field theory approaches to critical phenomena and the renormalization group, matrix models, and field theory techniques applied to the theory of turbulence. One common theme at the conference was the use of large-Nmatrix models to obtain exact results in a variety of different disciplines. For example, it has been known for several years that by taking a suitable double-scaling limit, certain string theories (or two-dimensional quantum gravity coupled to matter) can be re-obtained from the large-Nexpansion of matrix models. There continues to be a large activity in this area of research, which was well reflected by talks given at our workshop. Remarkably, large- Nmatrix models have very recently - just a few months before our meeting - been shown to have yet another deep relation to string theory.

The need for a comprehensive survey-type exposition on formal languages and related mainstream areas of computer science has been evident for some years. In the early 1970s, when . the book Formal Languages by the second mentioned editor appeared, it was still quite feasible to write a comprehensive book with that title and include also topics of current research interest. This would not be possible anymore. A standard-sized book on formal languages would either have to stay on a fairly low level or else be specialized and restricted to some narrow sector of the field. The setup becomes drastically different in a collection of contributions, where the best authorities in the world join forces, each of them concentrat ing on their own areas of specialization. The present three-volume Handbook constitutes such a unique collection. In these three volumes we present the current state of the art in formal language theory. We were most satisfied with the enthusiastic response given to our request for contributions by specialists representing various subfields. The need for a Handbook of Formal Languages was in many answers expressed in different ways: as an easily accessible his torical reference, a general source of information, an overall course-aid, and a compact collection of material for self-study. We are convinced that the final result will satisfy such various needs. The theory of formal languages constitutes the stem or backbone of the field of science now generally known as theoretical computer science.

There have been significant developments in the theory and practice of combinatorial optimization in the last 15 years. This progress has been evidenced by a continuously increasing number of international and local conferences, books and papers in this area. This book is also another contribution to this burgeoning area of operations research and optimization. This volume contains the contributions of the participants of the recent NATO Ad vanced Study Institute, New Frontiers in the Theory and Practice of Combinatorial Op timization, which was held at the campus of Bilkent University, in Ankara, Turkey, July 16-29, 1990. In this conference, we brought many prominent researchers and young and promising scientists together to discuss current and future trends in the theory and prac tice of combinatorial optimization. The Bilkent campus was an excellent environment for such an undertaking. Being outside of Ankara, the capital of Turkey, Bilkent University gave the participants a great opportunity for exchanging ideas and discussing new theories and applications without much distraction. One of the primary goals of NATO ASIs is to bring together a group of scientists and research scientists primarily from the NATO countries for the dissemination of ad vanced scientific knowledge and the promotion of international contacts among scientists. We believe that we accomplished this mission very successfully by bringing together 15 prominent lecturers and 45 promising young scientists from 12 countries, in a university environment for 14 days of intense lectures, presentations and discussions.

Since its very existence as a separate field within computer science, computer graphics had to make extensive use of non-trivial mathematics, for example, projective geometry, solid modelling, and approximation theory. This interplay of mathematics and computer science is exciting, but also makes it difficult for students and researchers to assimilate or maintain a view of the necessary mathematics. The possibilities offered by an interdisciplinary approach are still not fully utilized. This book gives a selection of contributions to a workshop held near Genoa, Italy, in October 1991, where a group of mathematicians and computer scientists gathered to explore ways of extending the cooperation between mathematics and computer graphics.

The mathematical theory of computation has given rise to two important ap proaches to the informal notion of "complexity" Kolmogorov complexity, usu ally a complexity measure for a single object such as a string, a sequence etc., measures the amount of information necessary to describe the object. Compu tational complexity, usually a complexity measure for a set of objects, measures the compuational resources necessary to recognize or produce elements of the set. The relation between these two complexity measures has been considered for more than two decades, and may interesting and deep observations have been obtained. In March 1990, the Symposium on Theory and Application of Minimal Length Encoding was held at Stanford University as a part of the AAAI 1990 Spring Symposium Series. Some sessions of the symposium were dedicated to Kolmogorov complexity and its relations to the computational complexity the ory, and excellent expository talks were given there. Feeling that, due to the importance of the material, some way should be found to share these talks with researchers in the computer science community, I asked the speakers of those sessions to write survey papers based on their talks in the symposium. In response, five speakers from the sessions contributed the papers which appear in this book."

A gentle introduction to the highly sophisticated world of discrete mathematics, Mathematical Problems and Proofs presents topics ranging from elementary definitions and theorems to advanced topics -- such as cardinal numbers, generating functions, properties of Fibonacci numbers, and Euclidean algorithm. This excellent primer illustrates more than 150 solutions and proofs, thoroughly explained in clear language. The generous historical references and anecdotes interspersed throughout the text create interesting intermissions that will fuel readers' eagerness to inquire further about the topics and some of our greatest mathematicians. The author guides readers through the process of solving enigmatic proofs and problems, and assists them in making the transition from problem solving to theorem proving. At once a requisite text and an enjoyable read, Mathematical Problems and Proofs is an excellent entree to discrete mathematics for advanced students interested in mathematics, engineering, and science.

This volume contains survey articles based on the invited lectures given at the Twenty-second British Combinatorial Conference, held in July 2009 at the University of St Andrews. This biennial conference is a well-established international event, with speakers from all over the world. By its nature this volume provides an up-to-date overview of current research activity in several areas of combinatorics, including graph theory, design theory and packing problems. Each article is clearly written and assumes little prior knowledge on the part of the reader. The authors are some of the world s foremost researchers in their fields, and here they summarize existing results, and give a unique preview of the most recent developments. The book provides a valuable survey of the present state of knowledge in combinatorics. It will be useful to research workers and advanced graduate students, primarily in mathematics but also in computer science, statistics and engineering.

The use of topological ideas to explore various aspects of graph theory, and vice versa, is a fruitful area of research. There are links with other areas of mathematics, such as design theory and geometry, and increasingly with such areas as computer networks where symmetry is an important feature. Other books cover portions of the material here, but there are no other books with such a wide scope. This book contains fifteen expository chapters written by acknowledged international experts in the field. Their well-written contributions have been carefully edited to enhance readability and to standardize the chapter structure, terminology and notation throughout the book. To help the reader, there is an extensive introductory chapter that covers the basic background material in graph theory and the topology of surfaces. Each chapter concludes with an extensive list of references.

The theory of Petri nets is a part of computer science whose importance is increasingly acknowledged. Many papers and anthologies, whose subject matter is net theory and its applications, have appeared to date. There exist at least seven introductory textbooks on the theory. The present monograph augments this literature by offering a mathematical treatment of one of the central aspects of net theory: the modelling of concur rency by partially ordered sets. Occurrence nets - which are special nets as well as special partial orders - are proposed by net theory for this purpose. We study both the general properties of occurrence nets and their use in describing the concurrent behaviour of systems. Occurrence nets may be contrasted with a more language-oriented approach to the modelling of concurrency known as arbitrary interleaving. We will dis cuss some connections between these' two approaches. Other approaches based on partially ordered sets - such as the theory of traces, the theory of event structures and the theory of semi words - are not considered in this book, in spite of the strong links between them and net theory."

Food webs hold a central place in ecology. They describe which organisms feed on which others in natural habitats. This book describes recently discovered empirical regularities in real food webs: it proposes a novel theory unifying many of these regularities, as well as extensive empirical data. After a general introduction, reviewing the empirical and theoretical discoveries about food webs, the second portion of the book shows that community food webs obey several striking phenomenological regularities. Some of these unify, regardless of habitat. Others differentiate, showing that habitat significantly influences structure. The third portion of the book presents a theoretical analysis of some of the unifying empirical regularities. The fourth portion of the book presents 13 community food webs. Collected from scattered sources and carefully edited, they are the empirical basis for the results in the volume. The largest available set of data on community food webs provides a valuable foundation for future studies of community food webs. The book is intended for graduate students, teachers and researchers primarily in ecology. The theoretical portions of the book provide materials useful to teachers of applied combinatorics, in particular, random graphs. Researchers in random graphs will find here unsolved mathematical problems.

Ever since the discovery of the five platonic solids in ancient times, the study of symmetry and regularity has been one of the most fascinating aspects of mathematics. Quite often the arithmetical regularity properties of an object imply its uniqueness and the existence of many symmetries. This interplay between regularity and symmetry properties of graphs is the theme of this book. Starting from very elementary regularity properties, the concept of a distance-regular graph arises naturally as a common setting for regular graphs which are extremal in one sense or another. Several other important regular combinatorial structures are then shown to be equivalent to special families of distance-regular graphs. Other subjects of more general interest, such as regularity and extremal properties in graphs, association schemes, representations of graphs in euclidean space, groups and geometries of Lie type, groups acting on graphs, and codes are covered independently. Many new results and proofs and more than 750 references increase the encyclopaedic value of this book.

In the late forties, Mathematical Programming became a scientific discipline in its own right. Since then it has experienced a tremendous growth. Beginning with economic and military applications, it is now among the most important fields of applied mathematics with extensive use in engineering, natural sciences, economics, and biological sciences. The lively activity in this area is demonstrated by the fact that as early as 1949 the first "Symposium on Mathe- matical Programming" took place in Chicago. Since then mathematical programmers from all over the world have gath- ered at the intfrnational symposia of the Mathematical Programming Society roughly every three years to present their recent research, to exchange ideas with their colleagues and to learn about the latest developments in their own and related fields. In 1982, the XI. International Symposium on Mathematical Programming was held at the University of Bonn, W. Germany, from August 23 to 27. It was organized by the Institut fUr Okonometrie und Operations Re- search of the University of Bonn in collaboration with the Sonderforschungs- bereich 21 of the Deutsche Forschungsgemeinschaft. This volume constitutes part of the outgrowth of this symposium and docu- ments its scientific activities. Part I of the book contains information about the symposium, welcoming addresses, lists of committees and sponsors and a brief review about the Ful- kerson Prize and the Dantzig Prize which were awarded during the opening ceremony.