This book constitutes the refereed proceedings of the Third International Conference on Graph Transformations, ICGT 2006. The book presents 28 revised full papers together with 3 invited lectures. All current aspects in graph drawing are addressed including graph theory and graph algorithms, theoretic and semantic aspects, modeling, tool issues and more. Also includes accounts of a tutorial on foundations and applications of graph transformations, and of ICGT Conference satellite events.

This volume constitutes the refereed proceedings of the 11th International Workshop on Combinatorial Image Analysis, IWCIA 2006, held in Berlin, June 2006. The book presents 34 revised full papers together with two invited papers, covering topics including combinatorial image analysis; grammars and models for analysis and recognition of scenes and images; combinatorial topology and geometry for images; digital geometry of curves and surfaces; algebraic approaches to image processing, and more.

This is the concluding volume of the second edition of the standard text on design theory. Since the first edition there has been extensive development of the theory and this book has been thoroughly rewritten to reflect this. In particular the growing importance of discrete mathematics to many parts of engineering and science have made designs a useful tool for applications, and this fact has been acknowledged here with the inclusion of an additional chapter on applications. It is suitable for advanced courses and as a reference work, not only for researchers in discrete mathematics or finite algebra, but also for those working in computer and communications engineering and other mathematically oriented disciplines. Exercises are included throughout, and the book concludes with an extensive and updated bibliography of well over 1800 items.

Questions of maxima and minima have great practical significance, with applications to physics, engineering, and economics; they have also given rise to theoretical advances, notably in calculus and optimization. Indeed, while most texts view the study of extrema within the context of calculus, this carefully constructed problem book takes a uniquely intuitive approach to the subject: it presents hundreds of extreme value problems, examples, and solutions primarily through Euclidean geometry. Written by a team of established mathematicians and professors, this work draws on the authors' experience in the classroom and as Olympiad coaches. By exposing readers to a wealth of creative problem-solving approaches, the text communicates not only geometry but also algebra, calculus, and topology. Ideal for use at the junior and senior undergraduate level, as well as in enrichment programs and Olympiad training for advanced high school students, this book's breadth and depth will appeal to a wide audience, from secondary school teachers and pupils to graduate students, professional mathematicians, and puzzle enthusiasts.

Combinatorics and Number Theory of Counting Sequences is an introduction to the theory of finite set partitions and to the enumeration of cycle decompositions of permutations. The presentation prioritizes elementary enumerative proofs. Therefore, parts of the book are designed so that even those high school students and teachers who are interested in combinatorics can have the benefit of them. Still, the book collects vast, up-to-date information for many counting sequences (especially, related to set partitions and permutations), so it is a must-have piece for those mathematicians who do research on enumerative combinatorics. In addition, the book contains number theoretical results on counting sequences of set partitions and permutations, so number theorists who would like to see nice applications of their area of interest in combinatorics will enjoy the book, too. Features The Outlook sections at the end of each chapter guide the reader towards topics not covered in the book, and many of the Outlook items point towards new research problems. An extensive bibliography and tables at the end make the book usable as a standard reference. Citations to results which were scattered in the literature now become easy, because huge parts of the book (especially in parts II and III) appear in book form for the first time.

The British Combinatorial Conference is one of the most well-known meetings for combinatorialists. This volume collects the invited talks from the 1999 conference held at the University of Kent, and together these span a broad range of combinatorial topics. The nine talks are from: S. Ball, J. Dinitz, M. Dyer, K. Metsch, J. Pach, R. Thomas, C. Thomassen, N. Wormald, plus a special contribution from W. T. Tutte. All researchers into combinatorics will find that this volume is an outstanding and up-to-date resource.

This volume contains the papers presented at the 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2005) and the 9th International Workshop on Randomization and Computation(RANDOM2005), whichtookplaceconcurrentlyattheUniversity of California in Berkeley, on August 22-24, 2005. APPROX focuses on algori- mic and complexity issues surrounding the development of e?cient approximate solutions to computationally hard problems, and APPROX 2005 was the eighth in the series after Aalborg (1998), Berkeley (1999), Saarbru ]cken (2000), Ber- ley (2001), Rome (2002), Princeton(2003), and Cambridge(2004).RANDOM is concerned with applications of randomness to computational and combinatorial problems, and RANDOM 2005 was the ninth workshop in the series foll- ing Bologna (1997), Barcelona (1998), Berkeley(1999), Geneva (2000), Berkeley (2001), Harvard (2002), Princeton (2003), and Cambridge (2004). Topics of interest for APPROX and RANDOM are: design and analysis of approximation algorithms, hardness of approximation, small space and data streaming algorithms, sub-linear time algorithms, embeddings and metric space methods, mathematical programming methods, coloring and partitioning, cuts and connectivity, geometric problems, game theory and applications, network designandrouting, packingand covering, scheduling, designandanalysisofr- domized algorithms, randomized complexity theory, pseudorandomness and - randomization, random combinatorialstructures, randomwalks/Markovchains, expander graphs and randomness extractors, probabilistic proof systems, r- dom projections and embeddings, error-correcting codes, average-case analysis, property testing, computational learning theory, and other applications of - proximation and randomness. The volume contains 20 contributed papers selected by the APPROX P- gram Committee out of 50 submissions, and 21 contributed papers selected by the RANDOM Program Committee out of 51 submis

This book is the first volume in a two-volume set, which will provide the complete proof of classification of two important classes of geometries, closely related to each other: Petersen and tilde geometries. There is an infinite family of tilde geometries associated with nonsplit extensions of symplectic groups over a field of two elements. Besides that there are twelve exceptional Petersen and tilde geometries. These exceptional geometries are related to sporadic simple groups, including the famous Monster group and this volume gives a construction for each of the Petersen and tilde geometries that provides an independent existence proof for the corresponding automorphism group. Important applications of Petersen and tilde geometries are considered, including the so-called Y-presentations for the Monster and related groups, and a complete identification of Y-groups is given. This is an essential purchase for researchers in finite group theory, finite geometries and algebraic combinatorics.

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.

a ~Networka (TM) is a heavily overloaded term, so that a ~network analysisa (TM) means different things to different people. Specific forms of network analysis are used in the study of diverse structures such as the Internet, interlocking directorates, transportation systems, epidemic spreading, metabolic pathways, the Web graph, electrical circuits, project plans, and so on. There is, however, a broad methodological foundation which is quickly becoming a prerequisite for researchers and practitioners working with network models.

From a computer science perspective, network analysis is applied graph theory. Unlike standard graph theory books, the content of this book is organized according to methods for specific levels of analysis (element, group, network) rather than abstract concepts like paths, matchings, or spanning subgraphs. Its topics therefore range from vertex centrality to graph clustering and the evolution of scale-free networks.

In 15 coherent chapters, this monograph-like tutorial book introduces and surveys the concepts and methods that drive network analysis, and is thus the first book to do so from a methodological perspective independent of specific application areas.

This volume consists of the refereed papers presented at the Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT 2003), held on September 13 16, 2003 at ITB, Bandung, Indonesia. This conf- ence can also be considered as a series of the Japan Conference on Discrete and Computational Geometry (JCDCG), which has been held annually since 1997. The ?rst ?ve conferences of the series were held in Tokyo, Japan, the sixth in Manila, the Philippines, in 2001, and the seventh in Tokyo, Japan in 2002. The proceedings of JCDCG 1998, JCDCG 2000 and JCDCG 2002 were p- lished by Springer as part of the series Lecture Notes in Computer Science: LNCS volumes 1763, 2098 and 2866, respectively. The proceedings of JCDCG 2001 were also published by Springer as a special issue of the journal Graphs and Combinatorics, Vol. 18, No. 4, 2002. TheorganizersaregratefultotheDepartmentofMathematics, InstitutTek- logi Bandung (ITB) and Tokai University for sponsoring the conference. We also thank all program committee members and referees for their excellent work. Our big thanks to the principal speakers: Hajo Broersma, Mikio Kano, Janos Pach andJorgeUrrutia.Finally, ourthanksalsogoestoallourcolleagueswhoworked hard to make the conference enjoyable and successful. August 2004 Jin Akiyama Edy Tri Baskoro Mikio Kano Organization The Indonesia-Japan Joint Conference on Combinatorial Geometry and Graph Theory (IJCCGGT) 2003 was organized by the Department of Mathematics, InstitutTeknologiBandung(ITB)IndonesiaandRIED, TokaiUniversity, Japan

Bipartite graphs are perhaps the most basic of objects in graph theory, both from a theoretical and practical point of view. Until now, they have been considered only as a special class in some wider context. This work deals solely with bipartite graphs, providing traditional material as well as many new and unusual results. The authors illustrate the theory with many applications, especially to problems in timetabling, chemistry, communication networks and computer science. The material is accessible to any reader with a graduate understanding of mathematics and will be of interest to specialists in combinatorics and graph theory.

This volume presents the proceedings of the 10th International Workshop on Combinatorial Image Analysis, held December 1 3, 2004, in Auckland, New Zealand. Prior meetings took place in Paris (France, 1991), Ube (Japan, 1992), Washington DC (USA, 1994), Lyon (France, 1995), Hiroshima (Japan, 1997), Madras (India, 1999), Caen (France, 2000), Philadelphia (USA, 2001), and - lermo (Italy, 2003). For this workshop we received 86 submitted papers from 23 countries. Each paper was evaluated by at least two independent referees. We selected 55 papers for the conference. Three invited lectures by Vladimir Kovalevsky (Berlin), Akira Nakamura (Hiroshima), and Maurice Nivat (Paris) completed the program. Conference papers are presented in this volume under the following topical part titles: discrete tomography (3 papers), combinatorics and computational models (6), combinatorial algorithms (6), combinatorial mathematics (4), d- ital topology (7), digital geometry (7), approximation of digital sets by curves and surfaces (5), algebraic approaches (5), fuzzy image analysis (2), image s- mentation (6), and matching and recognition (7). These subjects are dealt with in the context of digital image analysis or computer vision."

ICGT 2004 was the 2nd International Conference on Graph Transformation, following the ?rst one in Barcelona (2002), and a series of six international workshops on graph grammars with applications in computer science between 1978 and 1998. ICGT 2004 was held in Rome (Italy), Sept. 29 Oct. 1, 2004 under the auspices of the European Association for Theoretical Computer S- ence (EATCS), the European Association of Software Science and Technology (EASST), and the IFIP WG 1.3, Foundations of Systems Speci?cation. The scope of the conference concerned graphical structures of various kinds (like graphs, diagrams, visual sentences and others) that are useful when - scribing complex structures and systems in a direct and intuitive way. These structures are often augmented with formalisms that add to the static descr- tion a further dimension, allowing for the modelling of the evolution of systems via all kinds of transformations of such graphical structures. The ?eld of graph transformation is concerned with the theory, applications, and implementation issues of such formalisms. The theory is strongly related to areas such as graph theory and graph - gorithms, formal language and parsing theory, the theory of concurrent and distributed systems, formal speci?cation and veri?cation, logic, and semantics. The application areas include all those ?elds of computer science, information processing, engineering, andthe naturalsciences wherestatic anddynamicm- elling using graphical structures and graph transformations, respectively, play important roles. In many of these areas tools based on graph transformation technology have been implemented and used."

The combinatorial theory of species, introduced by Joyal in 1980, provides a unified understanding of the use of generating functions for both labeled and unlabeled structures as well as a tool for the specification and analysis of these structures. This key reference presents the basic elements of the theory and gives a unified account of its developments and applications. The authors offer a modern introduction to the use of various generating functions, with applications to graphical enumeration, Polya Theory and analysis of data structures in computer science, and to other areas such as special functions, functional equations, asymptotic analysis, and differential equations.

Thisvolumeconsistsofpapersselectedfromthe presentationsgivenatthe Int- national Workshop and Symposium on "Applications of Graph Transformation with Industrial Relevance" (AGTIVE 2003). The papers underwent up to two additional reviews. This volume contains the revised versions of these papers. AGTIVE2003wasthesecondeventoftheGraphTransformationcommunity. The aim of AGTIVE is to unite people from research and industry interested in the application of Graph Transformation to practical problems. The ?rst wo- shoptookplaceatKerkrade,TheNetherlands.Theproceedingsappearedasvol. 1779ofSpringer-Verlags'sLectureNotesinComputerScienceseries.Thissecond workshop, AGTIVE 2003, was held in historic Charlottesville, Virginia, USA. Graphs constitute well-known, well-understood, and frequently used means to depict networks of related items in di?erent application domains. Various typesofgraphtransformationapproaches- alsocalledgraphgrammarsorgraph rewriting systems - have been proposed to specify, recognize, inspect, modify, anddisplaycertainclassesofgraphsrepresentingstructuresofdi?erentdomains. Research activities based on Graph Transformations (GT for short) cons- tute a well-established scienti?c discipline within Computer Science. The int- national GT research community is quite active and has organized international workshops and the conference ICGT 2002. The proceedings of these events, a three volume handbook on GT, and books on speci?c approaches as well as big application projects give a good documentation about research in the GT ?eld (see the list at the end of the proceedings). The intention of all these activities has been (1) to bring together the - ternational community in a viable scienti?c discussion, (2) to integrate di?erent approaches, and (3) to build a bridge between theory and practice.

This self-contained book examines results on transfinite graphs and networks achieved through a continuing research effort during the past several years. These new results, covering the mathematical theory of electrical circuits, are different from those presented in two previously published books by the author, Transfiniteness for Graphs, Electrical Networks, and Random Walks and Pristine Transfinite Graphs and Permissive Electrical Networks.

Two initial chapters present the preliminary theory summarizing all essential ideas needed for the book and will relieve the reader from any need to consult those prior books. Subsequent chapters are devoted entirely to novel results and cover:

* Connectedness ideas---considerably more complicated for transfinite graphs as compared to those of finite or conventionally infinite graphs----and their relationship to hypergraphs

* Distance ideas---which play an important role in the theory of finite graphs---and their extension to transfinite graphs with more complications, such as the replacement of natural-number distances by ordinal-number distances

* Nontransitivity of path-based connectedness alleviated by replacing paths with walks, leading to a more powerful theory for transfinite graphs and networks

Additional features include:

* The use of nonstandard analysis in novel ways that leads to several entirely new results concerning hyperreal operating points for transfinite networks and hyperreal transients on transfinite transmission lines; this use of hyperreals encompasses for the first time transfinite networks and transmission lines containing inductances and capacitances, in addition to resistances

* A useful appendix with concepts from nonstandard analysis used in the book

* May serve as a reference text or as a graduate-level textbook in courses or seminars

Graphs and Networks: Transfinite and Nonstandard will appeal to a diverse readership, including graduate students, electrical engineers, mathematicians, and physicists working on infinite electrical networks. Moreover, the growing and presently substantial number of mathematicians working in nonstandard analysis may well be attracted by the novel application of the analysis employed in the work.

ISBN 0-8176-4292-7

This volume presents up-to-date research on finite geometries and designs, a key area in modern applicable mathematics. An introductory chapter discusses topics presented in each of the main chapters, and is followed by articles from leading international figures in this field. These include a discussion of the current state of finite geometry from a group-theoretical viewpoint, and surveys of difference sets and of small embeddings of partial cycle systems into Steiner triple systems. Also presented are successful searches for spreads and packing of designs, rank three geometries with simplicial residues and generalized quadrangles satisfying Veblen's Axiom. In addition, there are articles on new 7-designs, biplanes, various aspects of triple systems, and many other topics. This book will be a useful reference for researchers working in finite geometries, design theory or combinatorics in general.

This volume consists of the papers presented by the invited lecturers at the 16th British Combinatorial Conference. This biennial meeting is one of the most important for combinatorialists, attracting leading figures in the field. This overview of up-to-date research will be a valuable resource for researchers and graduate students.

The first of two companion volumes on anabelian algebraic geometry, this book contains the famous, but hitherto unpublished manuscript 'Esquisse d'un Programme' (Sketch of a Program) by Alexander Grothendieck. This work, written in 1984, fourteen years after his retirement from public life in mathematics, together with the closely connected letter to Gerd Faltings, dating from 1983 and also published for the first time in this volume, describe a powerful program of future mathematics, unifying aspects of geometry and arithmetic via the central point of moduli spaces of curves; it is written in an artistic and informal style. The book also contains several articles on subjects directly related to the ideas explored in the manuscripts; these are surveys of mathematics due to Grothendieck, explanations of points raised in the Esquisse, and surveys on progress in the domains described there.

Combinatorics on words, or finite sequences, is a field that grew from the disparate mathematics branches of group theory and probability. In recent times, it has gained recognition as an independent theory and has found substantial applications in computer science automata theory and linguistics. This volume is the first to present a thorough treatment of this theory and includes discussions of Thue's square free words, Van der Waerden's theorem, and Ramsey's theorem. This volume is an accessible text for undergraduate and graduate level students in mathematics and computer science as well as specialists in all branches of applied mathematics.

This 1997 work explores the role of probabilistic methods for solving combinatorial problems. These methods not only provide the means of efficiently using such notions as characteristic and generating functions, the moment method and so on but also let us use the powerful technique of limit theorems. The basic objects under investigation are nonnegative matrices, partitions and mappings of finite sets, with special emphasis on permutations and graphs, and equivalence classes specified on sequences of finite length consisting of elements of partially ordered sets; these specify the probabilistic setting of Sachkov's general combinatorial scheme. The author pays special attention to using probabilistic methods to obtain asymptotic formulae that are difficult to derive using combinatorial methods. This was an important book, describing many ideas not previously available in English; the author has taken the chance to rewrite parts of the text and refresh the references where appropriate.

Paul Erdoes was one of the greatest mathematicians of this century, known the world over for his brilliant ideas and stimulating questions. On the date of his 80th birthday a conference was held in his honour at Trinity College, Cambridge. Many leading combinatorialists attended. Their subsequent contributions are collected here. The areas represented range from set theory and geometry, through graph theory, group theory and combinatorial probability, to randomised algorithms and statistical physics. Erdoes himself was able to give a survey of recent progress made on his favourite problems. Consequently this volume, consisting of in-depth studies at the frontier of research, provides a valuable panorama across the breadth of combinatorics as it is today.

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.

This book develops the combinatorics of Young tableaux and shows them in action in the algebra of symmetric functions, representations of the symmetric and general linear groups, and the geometry of flag varieties. The first part of the book is a self-contained presentation of the basic combinatorics of Young tableaux, including the remarkable constructions of "bumping" and "sliding", and several interesting correspondences. In Part II the author uses these results to study representations with geometry on Grassmannians and flag manifolds, including their Schubert subvarieties, and the related Schubert polynomials. Much of this material has never before appeared in book form. There are numerous exercises throughout, with hints and answers provided. Researchers in representation theory and algebraic geometry as well as in combinatorics will find this book interesting and useful, while students will find the intuitive presentation easy to follow.