The starting point of this book is Sperner's theorem, which answers the question: What is the maximum possible size of a family of pairwise (with respect to inclusion) subsets of a finite set? This theorem stimulated the development of a fast growing theory dealing with external problems on finite sets and, more generally, on finite partially ordered sets. This book presents Sperner theory from a unified point of view, bringing combinatorial techniques together with methods from programming, linear algebra, Lie-algebra representations and eigenvalue methods, probability theory, and enumerative combinatorics. Researchers and graduate students in discrete mathematics, optimisation, algebra, probability theory, number theory, and geometry will find many powerful new methods arising from Sperner theory.

Current research on the spectral theory of finite graphs may be seen as part of a wider effort to forge closer links between algebra and combinatorics (in particular between linear algebra and graph theory).This book describes how this topic can be strengthened by exploiting properties of the eigenspaces of adjacency matrices associated with a graph. The extension of spectral techniques proceeds at three levels: using eigenvectors associated with an arbitrary labelling of graph vertices, using geometrical invariants of eigenspaces such as graph angles and main angles, and introducing certain kinds of canonical eigenvectors by means of star partitions and star bases. One objective is to describe graphs by algebraic means as far as possible, and the book discusses the Ulam reconstruction conjecture and the graph isomorphism problem in this context. Further problems of graph reconstruction and identification are used to illustrate the importance of graph angles and star partitions in relation to graph structure. Specialists in graph theory will welcome this treatment of important new research.

New and striking results obtained in recent years from an intensive study of asymptotic combinatorics have led to a new, higher level of understanding of related problems: the theory of integrable systems, the Riemann-Hilbert problem, asymptotic representation theory, spectra of random matrices, combinatorics of Young diagrams and permutations, and even some aspects of quantum field theory.

This book constitutes the refereed proceedings of the First International Conference on Graph Transformations, ICGT 2002, held in Barcelona, Spain in October 2002.The 26 revised full papers presented were carefully reviewed and selected by the program committe. Also included are abstracts of 3 invited papers, a tutorial, the extended abstract of a tutorial, and 5 reports of workshops held in conjunction with ICGT. The papers deal with various graphical structures that are useful to describe complex systems and computational structures, like graphs, diagrams, visual sentences, and others. Graph transformations are stongly related to graph theory, graph algorithms, formal language and parsing theory, the theory of concurrent and distributed systems, formal specification and verification, and logic and semantics.

This book constitutes the refereed proceedings of the 8th Annual International Computing and Combinatorics Conference, COCOON 2002, held in Singapore in August 2002.The 60 revised full papers presented together with three invited contributions were carefully reviewed and selected from 106 submissions. The papers are organized in topical sections on complexity theory, discrete algorithms, computational biology and learning theory, radio networks, automata and formal languages, Internet networks, computational geometry, combinatorial optimization, and quantum computing.

This volume contains the proceedings of the NATO Advanced Study Institute "Symmetric Functions 2001: Surveys of Developments and Per- spectives", held at the Isaac Newton Institute for Mathematical Sciences in Cambridge, UK, during the two weeks 25 June - 6 July 2001. The objective of the ASI was to survey recent developments and outline research perspectives in various fields, for which the fundamental questions can be stated in the language of symmetric functions (along the way emphasizing interdisciplinary connections). The instructional goals of the event determined its format: the ASI consisted of about a dozen mini-courses. Seven of them served as a basis for the papers comprising the current volume. The ASI lecturers were: Persi Diaconis, William Fulton, Mark Haiman, Phil Hanlon, Alexander Klyachko, Bernard Leclerc, Ian G. Macdonald, Masatoshi Noumi, Andrei Okounkov, Grigori Olshanski, Eric Opdam, Ana- toly Vershik, and Andrei Zelevinsky. The organizing committee consisted of Phil Hanlon, Ian Macdonald, Andrei 0 kounkov, G rigori 0 lshanski (co-director), and myself ( co-director). The original ASI co-director Sergei Kerov, who was instrumental in determining the format and scope of the event, selection of speakers, and drafting the initial grant proposal, died in July 2000. Kerov's mathemat- ical ideas strongly influenced the field, and were presented at length in a number of ASI lectures. A special afternoon session on Monday, July 2, was dedicated to his memory.

Originally published in 1996, this is a presentation of some complex problems of discrete mathematics in a simple and unified form using an original, general combinatorial scheme. The author's aim is not always to present the most general results, but rather to focus attention on ones that illustrate the methods described. A distinctive aspect of the book is the large number of asymptotic formulae derived. Professor Sachkov begins with a discussion of block designs and Latin squares before proceeding to treat transversals, devoting much attention to enumerative problems. The main role in these problems is played by generating functions, which are considered in Chapter 3. The general combinatorial scheme is then introduced and in the last chapter Polya's enumerative theory is discussed. This is an important book, describing many ideas not previously available in English; the author has taken the chance to update the text and references where appropriate.

In recent years, algorithmic graph theory has become increasingly important as a link between discrete mathematics and theoretical computer science. This textbook introduces students of mathematics and computer science to the interrelated fields of graphs theory, algorithms and complexity.

Simply put, quantum calculus is ordinary calculus without taking limits. This undergraduate text develops two types of quantum calculi, the q-calculus and the h-calculus. As this book develops quantum calculus along the lines of traditional calculus, the reader discovers, with a remarkable inevitability, many important notions and results of classical mathematics. This book is written at the level of a first course in calculus and linear algebra and is aimed at undergraduate and beginning graduate students in mathematics, computer science, and physics. It is based on lectures and seminars given by Professor Kac over the last few years at MIT.

Applications of Davenport-Schinzel sequences arise in areas as diverse as robot motion planning, computer graphics and vision, and pattern matching. These sequences exhibit some surprising properties that make them a fascinating subject for research in combinatorial analysis. This book provides a comprehensive study of the combinatorial properties of Davenport-Schinzel sequences and their numerous geometric applications. These sequences are sophisticated tools for solving problems in computational and combinatorial geometry. This first book on the subject by two of its leading researchers will be an important resource for students and professionals in combinatorics, computational geometry, and related fields.

This book constitutes the refereed proceedings of the 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, held in Guilin, China, in August 2001.The 50 revised full papers and 16 short papers presented were carefully reviewed and selected from 97 submissions. The papers are organized in topical sections on complexity theory, computational biology, computational geometry, data structures and algorithms, games and combinatorics, graph algorithms and complexity, graph drawing, graph theory, online algorithms, randomized and average-case algorithms, Steiner trees, systems algorithms and modeling, and computability.

This book constitutes the joint refereed proceedings of the 4th International Workshop on Approximation Algorithms for Optimization Problems, APPROX 2001 and of the 5th International Workshop on Ranomization and Approximation Techniques in Computer Science, RANDOM 2001, held in Berkeley, California, USA in August 2001. The 26 revised full papers presented were carefully reviewed and selected from a total of 54 submissions. Among the issues addressed are design and analysis of approximation algorithms, inapproximability results, on-line problems, randomization, de-randomization, average-case analysis, approximation classes, randomized complexity theory, scheduling, routing, coloring, partitioning, packing, covering, computational geometry, network design, and applications in various fields.

Discrete Mathematics is one of the fastest growing areas in mathematics today with an ever-increasing number of courses in schools and universities. Graphs and Applications is based on a highly successful Open University course and the authors have paid particular attention to the presentation, clarity and arrangement of the material, making it ideally suited for independent study and classroom use. An important part of learning graph theory is problem solving; for this reason large numbers of examples, problems (with full solutions) and exercises (without solutions) are included.Accompanying the book is a CD-ROM comprising a Graphs Database, containing all the simple unlabelled graphs with up to seven vertices, and a Graphs Editor that enables students to construct and manipulate graphs. Both the Database and Editor are simple to use and allow students to investigate graphs with ease. Computing Notes and suggested activities are provided.

Graph Searching Games and Probabilistic Methods is the first book that focuses on the intersection of graph searching games and probabilistic methods. The book explores various applications of these powerful mathematical tools to games and processes such as Cops and Robbers, Zombie and Survivors, and Firefighting. Written in an engaging style, the book is accessible to a wide audience including mathematicians and computer scientists. Readers will find that the book provides state-of-the-art results, techniques, and directions in graph searching games, especially from the point of view of probabilistic methods. The authors describe three directions while providing numerous examples, which include: * Playing a deterministic game on a random board. * Players making random moves. * Probabilistic methods used to analyze a deterministic game.

50 Years of Combinatorics, Graph Theory, and Computing advances research in discrete mathematics by providing current research surveys, each written by experts in their subjects. The book also celebrates outstanding mathematics from 50 years at the Southeastern International Conference on Combinatorics, Graph Theory & Computing (SEICCGTC). The conference is noted for the dissemination and stimulation of research, while fostering collaborations among mathematical scientists at all stages of their careers. The authors of the chapters highlight open questions. The sections of the book include: Combinatorics; Graph Theory; Combinatorial Matrix Theory; Designs, Geometry, Packing and Covering. Readers will discover the breadth and depth of the presentations at the SEICCGTC, as well as current research in combinatorics, graph theory and computer science. Features: Commemorates 50 years of the Southeastern International Conference on Combinatorics, Graph Theory & Computing with research surveys Surveys highlight open questions to inspire further research Chapters are written by experts in their fields Extensive bibliographies are provided at the end of each chapter

This volume contains the papers presented at the Third Discrete Mathematics and Theoretical Computer Science Conference (DMTCS1), which was held at 'Ovidius'University Constantza, Romania in July 2001.The conference was open to all areas of discrete mathematics and theoretical computer science, and the papers contained within this volume cover topics such as: abstract data types and specifications; algorithms and data structures; automata and formal languages; computability, complexity and constructive mathematics; discrete mathematics, combinatorial computing and category theory; logic, nonmonotonic logic and hybrid systems; molecular computing.

This book constitutes the thoroughly refereed post-proceedings of the 10th International Symposium on Graph Drawing, GD 2002, held in Irvine, CA, USA, in August 2002.The 24 revised full papers, 9 short papers, and 7 software demonstrations presented together with a report on the GD 2002 graph drawing contest were carefully reviewed and selected from a total of 48 regular paper submissions. All current aspects of graph drawing are addressed.

Eschewing the often standard dry and static writing style of traditional textbooks, Discrete Encounters provides a refreshing approach to discrete mathematics. The author blends traditional course topics and applications with historical context, pop culture references, and open problems. This book focuses on the historical development of the subject and provides fascinating details of the people behind the mathematics, along with their motivations, deepening readers' appreciation of mathematics. This unique book covers many of the same topics found in traditional textbooks, but does so in an alternative, entertaining style that better captures readers' attention. In addition to standard discrete mathematics material, the author shows the interplay between the discrete and the continuous and includes high-interest topics such as fractals, chaos theory, cellular automata, money-saving financial mathematics, and much more. Not only will readers gain a greater understanding of mathematics and its culture, they will also be encouraged to further explore the subject. Long lists of references at the end of each chapter make this easy. Highlights: Features fascinating historical context to motivate readers Text includes numerous pop culture references throughout to provide a more engaging reading experience Its unique topic structure presents a fresh approach The text's narrative style is that of a popular book, not a dry textbook Includes the work of many living mathematicians Its multidisciplinary approach makes it ideal for liberal arts mathematics classes, leisure reading, or as a reference for professors looking to supplement traditional courses Contains many open problems Profusely illustrated

This book offers a comprehensive treatment of the exercises and case studies as well as summaries of the chapters of the book "Linear Optimization and Extensions" by Manfred Padberg. It covers the areas of linear programming and the optimization of linear functions over polyhedra in finite dimensional Euclidean vector spaces.Here are the main topics treated in the book: Simplex algorithms and their derivatives including the duality theory of linear programming. Polyhedral theory, pointwise and linear descriptions of polyhedra, double description algorithms, Gaussian elimination with and without division, the complexity of simplex steps. Projective algorithms, the geometry of projective algorithms, Newtonian barrier methods. Ellipsoids algorithms in perfect and in finite precision arithmetic, the equivalence of linear optimization and polyhedral separation. The foundations of mixed-integer programming and combinatorial optimization.

Graph drawing comprises all aspects of visualizing structural relations between objects. The range of topics dealt with extends from graph theory, graph algorithms, geometry, and topology to visual languages, visual perception, and information visualization, and to computer-human interaction and graphics design. This monograph gives a systematic overview of graph drawing and introduces the reader gently to the state of the art in the area. The presentation concentrates on algorithmic aspects, with an emphasis on interesting visualization problems with elegant solutions. Much attention is paid to a uniform style of writing and presentation, consistent terminology, and complementary coverage of the relevant issues throughout the 10 chapters.This tutorial is ideally suited as an introduction for newcomers to graph drawing. Ambitioned practitioners and researchers active in the area will find it a valuable source of reference and information.

This book contains seventeen contributions made to George Andrews on the occasion of his sixtieth birthday, ranging from classical number theory (the theory of partitions) to classical and algebraic combinatorics. Most of the papers were read at the 42nd session of the Séminaire Lotharingien de Combinatoire that took place at Maratea, Basilicata, in August 1998.This volume contains a long memoir on Ramanujan's Unpublished Manuscript and the Tau functions studied with a contemporary eye, together with several papers dealing with the theory of partitions. There is also a description of a maple package to deal with general q-calculus. More subjects on algebraic combinatorics are developed, especially the theory of Kostka polynomials, the ice square model, the combinatorial theory of classical numbers, a new approach to determinant calculus.

This book constitutes the refereed proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching, CPM 2002, held in Fukuoka, Japan, in July 2002.The 21 revised full papers presented together with two invited contributions were carefully reviewed and selected from 37 submissions. The papers are devoted to current theoretical and computational aspects of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. Among the application fields are the World Wide Web, computational biology, computer vision, multimedia, information retrieval, data compression, and pattern recognition.

From the reviews:"This book (...) defines the boundaries of the subject now called combinatorial group theory. (...)it is a considerable achievement to have concentrated a survey of the subject into 339 pages. This includes a substantial and useful bibliography; (over 1100 (items)). ...the book is a valuable and welcome addition to the literature, containing many results not previously available in a book. It will undoubtedly become a standard reference." Mathematical Reviews, AMS, 1979

Algebraic coding theory has in recent years been increasingly applied to the study of combinatorial designs. This book gives an account of many of those applications together with a thorough general introduction to both design theory and coding theory - developing the relationship between the two areas. The first half of the book contains background material in design theory, including symmetric designs and designs from affine and projective geometry, and in coding theory, coverage of most of the important classes of linear codes. In particular, the authors provide a new treatment of the Reed-Muller and generalized Reed-Muller codes. The last three chapters treat the applications of coding theory to some important classes of designs, namely finite planes, Hadamard designs and Steiner systems, in particular the Witt systems. The book is aimed at mathematicians working in either coding theory or combinatorics - or related areas of algebra. The book is, however, designed to be used by non-specialists and can be used by those graduate students or computer scientists who may be working in these areas.

Finite geometry and combinatorics is the art of counting any phenomena that can be described by a diagram. Everyday life is full of applications; from telephones to compact disc players, from the transmission of confidential information to the codes on any item on supermarket shelves. This is a collection of thirty-five articles on covering topics such as finite projective spaces, generalized polygons, strongly regular graphs, diagram geometries and polar spaces. Included here are articles from many of the leading practitioners in the field including, for the first time, several distinguished Russian mathematicians. Many of the papers contain important new results and the growing use of computer algebra packages in this area is also demonstrated.