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.

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.

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.

This volume provides an up-to-date survey of current research activity in several areas of combinatorics and its applications. These include distance-regular graphs, combinatorial designs, coding theory, spectra of graphs, and randomness and computation. The articles give an overview of combinatorics that will be extremely useful to both mathematicians and computer scientists.

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.

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

Cryptology: Classical and Modern, Second Edition proficiently introduces readers to the fascinating field of cryptology. The book covers classical methods including substitution, transposition, Alberti, Vigenere, and Hill ciphers. It also includes coverage of the Enigma machine, Turing bombe, and Navajo code. Additionally, the book presents modern methods like RSA, ElGamal, and stream ciphers, as well as the Diffie-Hellman key exchange and Advanced Encryption Standard. When possible, the book details methods for breaking both classical and modern methods. The new edition expands upon the material from the first edition which was oriented for students in non-technical fields. At the same time, the second edition supplements this material with new content that serves students in more technical fields as well. Thus, the second edition can be fully utilized by both technical and non-technical students at all levels of study. The authors include a wealth of material for a one-semester cryptology course, and research exercises that can be used for supplemental projects. Hints and answers to selected exercises are found at the end of the book. Features: Requires no prior programming knowledge or background in college-level mathematics Illustrates the importance of cryptology in cultural and historical contexts, including the Enigma machine, Turing bombe, and Navajo code Gives straightforward explanations of the Advanced Encryption Standard, public-key ciphers, and message authentication Describes the implementation and cryptanalysis of classical ciphers, such as substitution, transposition, shift, affine, Alberti, Vigenere, and Hill

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

The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed account of newer topics, including Szemer\'edi's Regularity Lemma and its use, Shelah's extension of the Hales-Jewett Theorem, the precise nature of the phase transition in a random graph process, the connection between electrical networks and random walks on graphs, and the Tutte polynomial and its cousins in knot theory. In no other branch of mathematics is it as vital to tackle and solve challenging exercises in order to master the subject. To this end, the book contains an unusually large number of well thought-out exercises: over 600 in total. Although some are straightforward, most of them are substantial, and others will stretch even the most able reader.

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.

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.

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.

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.

The aim of these notes is to link algorithmic problems arising in knot theory with statistical physics and classical combinatorics. Apart from the theory of computational complexity needed to deal with enumeration problems, introductions are given to several of the topics, such as combinatorial knot theory, randomized approximation models, percolation, and random cluster models.

This volume is comprised of the invited lectures given at the 14th British Combinatorial Conference. The lectures survey many topical areas of current research activity in combinatorics and its applications, and also provide a valuable overview of the subject, for both mathematicians and computer scientists.

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

This book is primarily aimed at graduate students and researchers in graph theory, combinatorics, or discrete mathematics in general. However, all the necessary graph theory is developed from scratch, so the only pre-requisite for reading it is a first course in linear algebra and a small amount of elementary group theory. It should be accessible to motivated upper-level undergraduates.

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.