This book, dedicated to the memory of Gian-Carlo Rota, is the result of a collaborative effort by his friends, students and admirers. Rota was one of the great thinkers of our times, innovator in both mathematics and phenomenology. I feel moved, yet touched by a sense of sadness, in presenting this volume of work, despite the fear that I may be unworthy of the task that befalls me. Rota, both the scientist and the man, was marked by a generosity that knew no bounds. His ideas opened wide the horizons of fields of research, permitting an astonishing number of students from all over the globe to become enthusiastically involved. The contagious energy with which he demonstrated his tremendous mental capacity always proved fresh and inspiring. Beyond his renown as gifted scientist, what was particularly striking in Gian-Carlo Rota was his ability to appreciate the diverse intellectual capacities of those before him and to adapt his communications accordingly. This human sense, complemented by his acute appreciation of the importance of the individual, acted as a catalyst in bringing forth the very best in each one of his students. Whosoever was fortunate enough to enjoy Gian-Carlo Rota's longstanding friendship was most enriched by the experience, both mathematically and philosophically, and had occasion to appreciate son cote de bon vivant. The book opens with a heartfelt piece by Henry Crapo in which he meticulously pieces together what Gian-Carlo Rota's untimely demise has bequeathed to science.

1. Introduction . 1 2. Areas and Angles . . 6 3. Tessellations and Symmetry 14 4. The Postulate of Closest Approach 28 5. The Coexistence of Rotocenters 36 6. A Diophantine Equation and its Solutions 46 7. Enantiomorphy. . . . . . . . 57 8. Symmetry Elements in the Plane 77 9. Pentagonal Tessellations . 89 10. Hexagonal Tessellations 101 11. Dirichlet Domain 106 12. Points and Regions 116 13. A Look at Infinity . 122 14. An Irrational Number 128 15. The Notation of Calculus 137 16. Integrals and Logarithms 142 17. Growth Functions . . . 149 18. Sigmoids and the Seventh-year Trifurcation, a Metaphor 159 19. Dynamic Symmetry and Fibonacci Numbers 167 20. The Golden Triangle 179 21. Quasi Symmetry 193 Appendix I: Exercise in Glide Symmetry . 205 Appendix II: Construction of Logarithmic Spiral . 207 Bibliography . 210 Index . . . . . . . . . . . . . . . . . . . . 225 Concepts and Images is the result of twenty years of teaching at Harvard's Department of Visual and Environmental Studies in the Carpenter Center for the Visual Arts, a department devoted to turning out students articulate in images much as a language department teaches reading and expressing one self in words. It is a response to our students' requests for a "handout" and to l our colleagues' inquiries about the courses: Visual and Environmental Studies 175 (Introduction to Design Science), YES 176 (Synergetics, the Structure of Ordered Space), Studio Arts 125a (Design Science Workshop, Two-Dimension al), Studio Arts 125b (Design Science Workshop, Three-Dimensional),2 as well as my freshman seminars on Structure in Science and Art."

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.

Discrete probability theory and the theory of algorithms have become close partners over the last ten years, though the roots of this partnership go back much longer. The papers in this volume address the latest developments in this active field. They are from the IMA Workshops "Probability and Algorithms" and "The Finite Markov Chain Renaissance." They represent the current thinking of many of the world's leading experts in the field. Researchers and graduate students in probability, computer science, combinatorics, and optimization theory will all be interested in this collection of articles. The techniques developed and surveyed in this volume are still undergoing rapid development, and many of the articles of the collection offer an expositionally pleasant entree into a research area of growing importance.

How do you convey to your students, colleagues and friends some of the beauty of the kind of mathematics you are obsessed with? If you are a mathematician interested in finite or topological geometry and combinatorial designs, you could start by showing them some of the (400+) pictures in the "picture book". Pictures are what this book is all about; original pictures of everybody's favorite geometries such as configurations, projective planes and spaces, circle planes, generalized polygons, mathematical biplanes and other designs which capture much of the beauty, construction principles, particularities, substructures and interconnections of these geometries. The level of the text is suitable for advanced undergraduates and graduate students. Even if you are a mathematician who just wants some interesting reading you will enjoy the author's very original and comprehensive guided tour of small finite geometries and geometries on surfaces This guided tour includes lots of sterograms of the spatial models, games and puzzles and instructions on how to construct your own pictures and build some of the spatial models yourself.

Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts 1 to create a coherent mathematical view of these foundations. The result of this collaborative work is presented here in the hope that it does justice to the individual contributor and that the reader has a chance of judging the work as a whole. E. Engeler ETH Zurich, April 1994 lCollected in Chapter III, An Algebraization of Algorithmics, in Algorithmic Properties of Structures, Selected Papers of Erwin Engeler, World Scientific PubJ. Co., Singapore, 1993, pp. 183-257. I Historical and Philosophical Background Erwin Engeler In the fall of 1928 a young American turned up at the Mathematical Institute of Gottingen, a mecca of mathematicians at the time; he was a young man with a dream and his name was H. B. Curry. He felt that he had the tools in hand with which to solve the problem of foundations of mathematics mice and for all. His was an approach that came to be called "formalist" and embodied that later became known as Combinatory Logic."

This fascinating look at combinatorial games, that is, games not involving chance or hidden information, offers updates on standard games such as Go and Hex, on impartial games such as Chomp and Wythoff's Nim, and on aspects of games with infinitesimal values, plus analyses of the complexity of some games and puzzles and surveys on algorithmic game theory, on playing to lose, and on coping with cycles. The volume is rounded out with an up-to-date bibliography by Fraenkel and, for readers eager to get their hands dirty, a list of unsolved problems by Guy and Nowakowski. Highlights include some of Siegel's groundbreaking work on loopy games, the unveiling by Friedman and Landsberg of the use of renormalization to give very intriguing results about Chomp, and Nakamura's 'Counting Liberties in Capturing Races of Go'. Like its predecessors, this book should be on the shelf of all serious games enthusiasts.

The main purpose of these lectures is first to briefly survey the fundamental con nection between the representation theory of the symmetric group Sn and the theory of symmetric functions and second to show how combinatorial methods that arise naturally in the theory of symmetric functions lead to efficient algorithms to express various prod ucts of representations of Sn in terms of sums of irreducible representations. That is, there is a basic isometry which maps the center of the group algebra of Sn, Z(Sn), to the space of homogeneous symmetric functions of degree n, An. This basic isometry is known as the Frobenius map, F. The Frobenius map allows us to reduce calculations involving characters of the symmetric group to calculations involving Schur functions. Now there is a very rich and beautiful theory of the combinatorics of symmetric functions that has been developed in recent years. The combinatorics of symmetric functions, then leads to a number of very efficient algorithms for expanding various products of Schur functions into a sum of Schur functions. Such expansions of products of Schur functions correspond via the Frobenius map to decomposing various products of irreducible representations of Sn into their irreducible components. In addition, the Schur functions are also the characters of the irreducible polynomial representations of the general linear group over the complex numbers GLn(C).

This book is written by a mathematician and a theoretical biologist who have arrived at a good mutual understanding and a well worked-out common notation. The reader need hardly be convinced of the necessity of such a mutual understanding, not only for the two investigators, but also for the sciences they represent. Like Moliere's hero, geneticists are gradually beginning to understand that, unknowingly, they have been speaking in the language of cybernetics. Mathematicians are unexpec tedly discovering that many past and present problems and methods of genetics can be naturally formulated in the language of graph theory. In this way a powerful abstract mathematical theory suddenly finds a productive application. Moreover, in its turn, such an application be gins to "feed" the mathematical theory by presenting it with a number of new problems. The reader may judge for himself the fruitfulness of such mutual interaction. At the same time several important circumstances need to be men tioned. The formalization and rigorous formulation given here embraces not only the older problems, known by geneticists for many decades (the construction of genetic maps, the analysis of complementation, etc. ), but also comparatively new problems: the construction of partial com plementation maps, phylogenetic trees of proteins, etc."

This volume is dedicated to the memory of Rudolf Ahlswede, who passed away in December 2010. The Festschrift contains 36 thoroughly refereed research papers from a memorial symposium, which took place in July 2011.

Thefour macro-topics of this workshop: theory of games and strategic planning; combinatorial group testing and database mining; computational biology and string matching; information coding and spreading and patrolling on networks; provide a comprehensive picture of the vision Rudolf Ahlswede put forward of a broad and systematic theory of search.

In January 1989 a Workshop on Algorithms, Word Problems and Classi- fication in Combinatorial Group Theory was held at MSRl. This was part of a year-long program on Geometry and Combinatorial Group Theory or- ganised by Adyan, Brown, Gersten and Stallings. The organisers of the workshop were G. Baumslag, F.B. Cannonito and C.F. Miller III. The pa- pers in this volume are an outgrowth of lectures at this conference. The first three papers are concerned with decision problems and the next two with finitely presented simple groups. These are followed by two papers dealing with combinatorial geometry and homology. The remaining papers are about automatic groups and related topics. Some of these papers are, in essence, announcements of new results. The complexity of some of them are such that neither the Editors nor the Reviewers feel that they can take responsibility for vouching for the completeness of the proofs involved. We wish to thank the staff at MSRl for their help in organising the workshop and this volume.

This IMA Volume in Mathematics and its Appllcations GRAPH THEORY AND SPARSE MATRIX COMPUTATION is based on the proceedings of a workshop that was an integraI part of the 1991- 92 IMA program on "Applied Linear AIgebra." The purpose of the workshop was to bring together people who work in sparse matrix computation with those who conduct research in applied graph theory and grl: l, ph algorithms, in order to foster active cross-fertilization. We are grateful to Richard Brualdi, George Cybenko, Alan Geo ge, Gene Golub, Mitchell Luskin, and Paul Van Dooren for planning and implementing the year-Iong program. We espeeially thank Alan George, John R. Gilbert, and Joseph W.H. Liu for organizing this workshop and editing the proceedings. The finaneial support of the National Science Foundation made the workshop possible. A vner Friedman Willard Miller. Jr. PREFACE When reality is modeled by computation, linear algebra is often the con nec tiori between the continuous physical world and the finite algorithmic one. Usually, the more detailed the model, the bigger the matrix, the better the answer. Efficiency demands that every possible advantage be exploited: sparse structure, advanced com puter architectures, efficient algorithms. Therefore sparse matrix computation knits together threads from linear algebra, parallei computing, data struetures, geometry, and both numerieal and discrete algorithms."

This volume represents the refereed proceedings of the "Sixth International Conference on Finite Fields and Applications (Fq6)" held in the city of Oaxaca, Mexico, between 22-26 May 200l. The conference was hosted by the Departmento do Matermiticas of the U niversidad Aut6noma Metropolitana- Iztapalapa, Nlexico. This event continued a series of biennial international conferences on Finite Fields and Applications, following earlier meetings at the University of Nevada at Las Vegas (USA) in August 1991 and August 1993, the University of Glasgow (Scotland) in July 1995, the University of Waterloo (Canada) in August 1997, and at the University of Augsburg (Ger- many) in August 1999. The Organizing Committee of Fq6 consisted of Dieter Jungnickel (University of Augsburg, Germany), Neal Koblitz (University of Washington, USA), Alfred }. lenezes (University of Waterloo, Canada), Gary Mullen (The Pennsylvania State University, USA), Harald Niederreiter (Na- tional University of Singapore, Singapore), Vera Pless (University of Illinois, USA), Carlos Renteria (lPN, Mexico). Henning Stichtenoth (Essen Univer- sity, Germany). and Horacia Tapia-Recillas, Chair (Universidad Aut6noma l'vIetropolitan-Iztapalapa. Mexico). The program of the conference consisted of four full days and one half day of sessions, with 7 invited plenary talks, close to 60 contributed talks, basic courses in finite fields. cryptography and coding theory and a series of lectures at local educational institutions. Finite fields have an inherently fascinating structure and they are im- portant tools in discrete mathematics.

The Probability Theory of Patterns and Runs has had a long and distinguished history, starting with the work of de Moivre in the 18th century and that of von Mises in the early 1920's, and continuing with the renewal-theoretic results in Feller's classic text An Introduction to Probability Theory and its Applications, Volume 1. It is worthwhile to note, in particular, that de Moivre, in the third edition of The Doctrine of Chances (1756, reprinted by Chelsea in 1967, pp. 254-259), provides the generating function for the waiting time for the appearance of k consecutive successes. During the 1940's, statisticians such as Mood, Wolfowitz, David and Mosteller studied the distribution theory, both exact and asymptotic, of run-related statistics, thereby laying the foundation for several exact run tests. In the last two decades or so, the theory has seen an impressive re-emergence, primarily due to important developments in Molecular Biology, but also due to related research thrusts in Reliability Theory, Distribution Theory, Combinatorics, and Statistics.

One service mathematics has rendered the 'Et moi, ..., si j'avait su comment en revenir, It has put common sense back je n'y serais point al e.' human race. Jules Verne where it belongs, on the topmost shelf next to the dusty canister labelled 'discarded n- sense'. The series is divergent; therefore we may be able to do something with it. Eric T. Bell o. Heaviside Mathematics is a tool for thought. A highly necessary tool in a world where both feedback and non linearities abound. Similarly, all kinds of parts of mathematics serve as tools for other parts and for other sciences. Applying a simple rewriting rule to the quote on the right above one finds such statements as: 'One service topology has rendered mathematical physics .. .'; 'One service logic has rendered com puterscience .. .'; 'One service category theory has rendered mathematics .. .'. All arguably true. And all statements obtainable this way form part of the raison d'etre of this series."

Sri Gopal Mohanty has made pioneering contributions to lattice path counting and its applications to probability and statistics. This is clearly evident from his lifetime publications list and the numerous citations his publications have received over the past three decades. My association with him began in 1982 when I came to McMaster Univer sity. Since then, I have been associated with him on many different issues at professional as well as cultural levels; I have benefited greatly from him on both these grounds. I have enjoyed very much being his colleague in the statistics group here at McMaster University and also as his friend. While I admire him for his honesty, sincerity and dedication, I appreciate very much his kindness, modesty and broad-mindedness. Aside from our common interest in mathematics and statistics, we both have great love for Indian classical music and dance. We have spent numerous many different subjects associated with the Indian music and hours discussing dance. I still remember fondly the long drive (to Amherst, Massachusetts) I had a few years ago with him and his wife, Shantimayee, and all the hearty discussions we had during that journey. Combinatorics and applications of combinatorial methods in probability and statistics has become a very active and fertile area of research in the recent past."

"La narraci6n literaria es la evocaci6n de las nostalgias. " ("Literary narration is the evocation of nostalgia. ") G. G. Marquez, interview in Puerta del Sol, VII, 4, 1996. A Personal Prehistory In 1972 I started cooperating with members of the Biodynamics Research Unit at the Mayo Clinic in Rochester, Minnesota, which was under the direction of Earl H. Wood. At that time, their ambitious (and eventually realized) dream was to build the Dynamic Spatial Reconstructor (DSR), a device capable of collecting data regarding the attenuation of X-rays through the human body fast enough for stop-action imaging the full extent of the beating heart inside the thorax. Such a device can be applied to study the dynamic processes of cardiopulmonary physiology, in a manner similar to the application of an ordinary cr (computerized tomography) scanner to observing stationary anatomy. The standard method of displaying the information produced by a cr scanner consists of showing two-dimensional images, corresponding to maps of the X-ray attenuation coefficient in slices through the body. (Since different tissue types attenuate X-rays differently, such maps provide a good visualization of what is in the body in those slices; bone - which attenuates X-rays a lot - appears white, air appears black, tumors typically appear less dark than the surrounding healthy tissue, etc. ) However, it seemed to me that this display mode would not be appropriate for the DSR.

This IMA Volume in Mathematics and its Applications Coding Theory and Design Theory Part I: Coding Theory is based on the proceedings of a workshop which was an integral part of the 1987-88 IMA program on APPLIED COMBINATORICS. We are grateful to the Scientific Committee: Victor Klee (Chairman), Daniel Kleitman, Dijen Ray-Chaudhuri and Dennis Stanton for planning and implementing an exciting and stimulating year long program. We especially thank the Workshop Organizer, Dijen Ray-Chaudhuri, for organizing a workshop which brought together many of the major figures in a variety of research fields in which coding theory and design theory are used. A vner Friedman Willard Miller, Jr. PREFACE Coding Theory and Design Theory are areas of Combinatorics which found rich applications of algebraic structures. Combinatorial designs are generalizations of finite geometries. Probably, the history of Design Theory begins with the 1847 pa per of Reverand T. P. Kirkman "On a problem of Combinatorics," Cambridge and Dublin Math. Journal. The great Statistician R. A. Fisher reinvented the concept of combinatorial 2-design in the twentieth century. Extensive application of alge braic structures for construction of 2-designs (balanced incomplete block designs) can be found in R. C. Bose's 1939 Annals of Eugenics paper, "On the construction of balanced incomplete block designs." Coding Theory and Design Theory are closely interconnected. Hamming codes can be found (in disguise) in R. C. Bose's 1947 Sankhya paper "Mathematical theory of the symmetrical factorial designs.""

In April of 1996 an array of mathematicians converged on Cambridge, Massachusetts, for the Rotafest and Umbral Calculus Workshop, two con ferences celebrating Gian-Carlo Rota's 64th birthday. It seemed appropriate when feting one of the world's great combinatorialists to have the anniversary be a power of 2 rather than the more mundane 65. The over seventy-five par ticipants included Rota's doctoral students, coauthors, and other colleagues from more than a dozen countries. As a further testament to the breadth and depth of his influence, the lectures ranged over a wide variety of topics from invariant theory to algebraic topology. This volume is a collection of articles written in Rota's honor. Some of them were presented at the Rotafest and Umbral Workshop while others were written especially for this Festschrift. We will say a little about each paper and point out how they are connected with the mathematical contributions of Rota himself."

This present volume is the Proceedings of the 14th International Conference on Near rings and Nearfields held in Hamburg at the Universitiit der Bundeswehr Hamburg, from July 30 to August 06, 1995. This Conference was attended by 70 mathematicians and many accompanying persons who represented 22 different countries from all five continents. Thus it was the largest conference devoted entirely to nearrings and nearfields. The first of these conferences took place in 1968 at the Mathematische For schungsinstitut Oberwolfach, Germany. This was also the site of the conferences in 1972, 1976, 1980 and 1989. The other eight conferences held before the Hamburg Conference took place in eight different countries. For details about this and, more over, for a general historical overview of the development of the subject, we refer to the article "On the beginnings and development of near-ring theory" by G. Betsch [3]. During the last forty years the theory of nearrings and related algebraic struc tures like nearfields, nearmodules, nearalgebras and seminearrings has developed into an extensive branch of algebra with its own features. In its position between group theory and ring theory, this relatively young branch of algebra has not only a close relationship to these two more well-known areas of algebra, but it also has, just as these two theories, very intensive connections to many further branches of mathematics.

This volume presents a collection of papers on game theory dedicated to Michael Maschler. Through his dedication and contributions to game theory, Maschler has become an important figure particularly in the area of cooperative games. Game theory has since become an important subject in operations research, economics and management science. As befits such a volume, the main themes covered are cooperative games, coalitions, repeated games, and a cost allocation games. All the contributions are authoritative surveys of a particular topic, so together they will present an invaluable overview of the field to all those working on game theory problems.

These are the proceedings of the conference "Symbolic Computation, Number Theory, Special Functions, Physics and Combinatorics" held at the Department of Mathematics, University of Florida, Gainesville, from November 11 to 13, 1999. The main emphasis of the conference was Com puter Algebra (i. e. symbolic computation) and how it related to the fields of Number Theory, Special Functions, Physics and Combinatorics. A subject that is common to all of these fields is q-series. We brought together those who do symbolic computation with q-series and those who need q-series in cluding workers in Physics and Combinatorics. The goal of the conference was to inform mathematicians and physicists who use q-series of the latest developments in the field of q-series and especially how symbolic computa tion has aided these developments. Over 60 people were invited to participate in the conference. We ended up having 45 participants at the conference, including six one hour plenary speakers and 28 half hour speakers. There were talks in all the areas we were hoping for. There were three software demonstrations."

This book presents a collection of papers from the Spring 1995 Work shop on Computational Approaches to Processing the Prosody of Spon taneous Speech, hosted by the ATR Interpreting Telecommunications Re search Laboratories in Kyoto, Japan. The workshop brought together lead ing researchers in the fields of speech and signal processing, electrical en gineering, psychology, and linguistics, to discuss aspects of spontaneous speech prosody and to suggest approaches to its computational analysis and modelling. The book is divided into four sections. Part I gives an overview and theoretical background to the nature of spontaneous speech, differentiating it from the lab-speech that has been the focus of so many earlier analyses. Part II focuses on the prosodic features of discourse and the structure of the spoken message, Part ilIon the generation and modelling of prosody for computer speech synthesis. Part IV discusses how prosodic information can be used in the context of automatic speech recognition. Each section of the book starts with an invited overview paper to situate the chapters in the context of current research. We feel that this collection of papers offers interesting insights into the scope and nature of the problems concerned with the computational analysis and modelling of real spontaneous speech, and expect that these works will not only form the basis of further developments in each field but also merge to form an integrated computational model of prosody for a better understanding of human processing of the complex interactions of the speech chain."

The title of this book, Learning Discrete Mathematics with ISETL raises two issues. We have chosen the word "Learning" rather than "Teaching" because we think that what the student does in order to learn is much more important than what the professor does in order to teach. Academia is filled with outstanding mathematics teachers: excellent expositors, good organizers, hard workers, men and women who have a deep understanding of Mathematics and its applications. Yet, when it comes to ideas in Mathe matics, our students do not seem to be learning. It may be that something more is needed and we have tried to construct a book that might provide a different kind of help to the student in acquiring some of the fundamental concepts of Mathematics. In a number of ways we have made choices that seem to us to be the best for learning, even if they don't always completely agree with standard teaching practice. A second issue concerns students' writing programs. ISETL is a pro gramming language and by the phrase "with ISETL" in the title, we mean that our intention is for students to write code, think about what they have written, predict its results, and run their programs to check their predic tions. There is a trade-off here. On the one hand, it can be argued that students' active involvement with constructing Mathematics for themselves and solving problems is essential to understanding concepts."

Mathematical Foundations of Computer Science, Volume I is the first of two volumes presenting topics from mathematics (mostly discrete mathematics) which have proven relevant and useful to computer science. This volume treats basic topics, mostly of a set-theoretical nature (sets, functions and relations, partially ordered sets, induction, enumerability, and diagonalization) and illustrates the usefulness of mathematical ideas by presenting applications to computer science. Readers will find useful applications in algorithms, databases, semantics of programming languages, formal languages, theory of computation, and program verification. The material is treated in a straightforward, systematic, and rigorous manner. The volume is organized by mathematical area, making the material easily accessible to the upper-undergraduate students in mathematics as well as in computer science and each chapter contains a large number of exercises. The volume can be used as a textbook, but it will also be useful to researchers and professionals who want a thorough presentation of the mathematical tools they need in a single source. In addition, the book can be used effectively as supplementary reading material in computer science courses, particularly those courses which involve the semantics of programming languages, formal languages and automata, and logic programming.