The primary aim of this book is to present a coherent introduction to graph theory, suitable as a textbook for advanced undergraduate and beginning graduate students in mathematics and computer science. It provides a systematic treatment of the theory of graphs without sacrificing its intuitive and aesthetic appeal. Commonly used proof techniques are described and illustrated. The book also serves as an introduction to research in graph theory.

The solutions to each problem are written from a first principles approach, which would further augment the understanding of the important and recurring concepts in each chapter. Moreover, the solutions are written in a relatively self-contained manner, with very little knowledge of undergraduate mathematics assumed. In that regard, the solutions manual appeals to a wide range of readers, from secondary school and junior college students, undergraduates, to teachers and professors.

The interplay between combinatorics and theoretical physics is a recent trend which appears to us as particularly natural, since the unfolding of new ideas in physics is often tied to the development of combinatorial methods, and, conversely, problems in combinatorics have been successfully tackled using methods inspired by theoretical physics. We can thus speak nowadays of an emerging domain of Combinatorial Physics. The interference between these two disciplines is moreover an interference of multiple facets. Its best known manifestation (both to combinatorialists and theoretical physicists) has so far been the one between combinatorics and statistical physics, as statistical physics relies on an accurate counting of the various states or configurations of a physical system. But combinatorics and theoretical physics interact in various other ways. This book is mainly dedicated to the interactions of combinatorics (algebraic, enumerative, analytic) with (commutative and non-commutative) quantum field theory and tensor models, the latter being seen as a quantum field theoretical generalisation of matrix models.

Who first presented Pascal's triangle? (It was not Pascal.) Who first presented Hamiltonian graphs? (It was not Hamilton.) Who first presented Steiner triple systems? (It was not Steiner.) The history of mathematics is a well-studied and vibrant area of research, with books and scholarly articles published on various aspects of the subject. Yet, the history of combinatorics seems to have been largely overlooked. This book goes some way to redress this and serves two main purposes: 1) it constitutes the first book-length survey of the history of combinatorics; and 2) it assembles, for the first time in a single source, researches on the history of combinatorics that would otherwise be inaccessible to the general reader. Individual chapters have been contributed by sixteen experts. The book opens with an introduction by Donald E. Knuth to two thousand years of combinatorics. This is followed by seven chapters on early combinatorics, leading from Indian and Chinese writings on permutations to late-Renaissance publications on the arithmetical triangle. The next seven chapters trace the subsequent story, from Euler's contributions to such wide-ranging topics as partitions, polyhedra, and latin squares to the 20th century advances in combinatorial set theory, enumeration, and graph theory. The book concludes with some combinatorial reflections by the distinguished combinatorialist, Peter J. Cameron. This book is not expected to be read from cover to cover, although it can be. Rather, it aims to serve as a valuable resource to a variety of audiences. Combinatorialists with little or no knowledge about the development of their subject will find the historical treatment stimulating. A historian of mathematics will view its assorted surveys as an encouragement for further research in combinatorics. The more general reader will discover an introduction to a fascinating and too little known subject that continues to stimulate and inspire the work of scholars today.

This is a textbook for an introductory combinatorics course lasting one or two semesters. An extensive list of problems, ranging from routine exercises to research questions, is included. In each section, there are also exercises that contain material not explicitly discussed in the preceding text, so as to provide instructors with extra choices if they want to shift the emphasis of their course.Just as with the first three editions, the new edition walks the reader through the classic parts of combinatorial enumeration and graph theory, while also discussing some recent progress in the area: on the one hand, providing material that will help students learn the basic techniques, and on the other hand, showing that some questions at the forefront of research are comprehensible and accessible to the talented and hardworking undergraduate. The basic topics discussed are: the twelvefold way, cycles in permutations, the formula of inclusion and exclusion, the notion of graphs and trees, matchings, Eulerian and Hamiltonian cycles, and planar graphs.New to this edition are the Quick Check exercises at the end of each section. In all, the new edition contains about 240 new exercises. Extra examples were added to some sections where readers asked for them.The selected advanced topics are: Ramsey theory, pattern avoidance, the probabilistic method, partially ordered sets, the theory of designs, enumeration under group action, generating functions of labeled and unlabeled structures and algorithms and complexity.The book encourages students to learn more combinatorics, provides them with a not only useful but also enjoyable and engaging reading.The Solution Manual is available upon request for all instructors who adopt this book as a course text. Please send your request to [email protected] previous edition of this textbook has been adopted at various schools including UCLA, MIT, University of Michigan, and Swarthmore College. It was also translated into Korean.

In "The Structure of Affine Buildings," Richard Weiss gives a detailed presentation of the complete proof of the classification of Bruhat-Tits buildings first completed by Jacques Tits in 1986. The book includes numerous results about automorphisms, completions, and residues of these buildings. It also includes tables correlating the results in the locally finite case with the results of Tits's classification of absolutely simple algebraic groups defined over a local field. A companion to Weiss's "The Structure of Spherical Buildings," "The Structure of Affine Buildings" is organized around the classification of spherical buildings and their root data as it is carried out in Tits and Weiss's "Moufang Polygons."

There is a sympathy of ideas among the fields of knot theory, infinite discrete group theory, and the topology of 3-manifolds. This book contains fifteen papers in which new results are proved in all three of these fields. These papers are dedicated to the memory of Ralph H. Fox, one of the world's leading topologists, by colleagues, former students, and friends. In knot theory, papers have been contributed by Goldsmith, Levine, Lomonaco, Perko, Trotter, and Whitten. Of these several are devoted to the study of branched covering spaces over knots and links, while others utilize the braid groups of Artin. Cossey and Smythe, Stallings, and Strasser address themselves to group theory. In his contribution Stallings describes the calculation of the groups In/In+1 where I is the augmentation ideal in a group ring RG. As a consequence, one has for each k an example of a k-generator l-relator group with no free homomorphs. In the third part, papers by Birman, Cappell, Milnor, Montesinos, Papakyriakopoulos, and Shalen comprise the treatment of 3-manifolds. Milnor gives, besides important new results, an exposition of certain aspects of our current knowledge regarding the 3- dimensional Brieskorn manifolds.

In the past three decades, local search has grown from a simple heuristic idea into a mature field of research in combinatorial optimization that is attracting ever-increasing attention. Local search is still the method of choice for NP-hard problems as it provides a robust approach for obtaining high-quality solutions to problems of a realistic size in reasonable time. "Local Search in Combinatorial Optimization" covers local search and its variants from both a theoretical and practical point of view, each topic discussed by a leading authority. This book is an important reference and invaluable source of inspiration for students and researchers in discrete mathematics, computer science, operations research, industrial engineering, and management science.

In addition to the editors, the contributors are Mihalis Yannakakis, Craig A. Tovey, Jan H. M. Korst, Peter J. M. van Laarhoven, Alain Hertz, Eric Taillard, Dominique de Werra, Heinz Muhlenbein, Carsten Peterson, Bo Soderberg, David S. Johnson, Lyle A. McGeoch, Michel Gendreau, Gilbert Laporte, Jean-Yves Potvin, Gerard A. P. Kindervater, Martin W. P. Savelsbergh, Edward J. Anderson, Celia A. Glass, Chris N. Potts, C. L. Liu, Peichen Pan, Iiro Honkala, and Patric R. J. Ostergard."

A variety of different social, natural, and technological systems can be described by the same mathematical framework. This holds from the Internet to food webs and to boards of company directors. In all these situations a graph of the elements of the system and their interconnections displays a universal feature. There are only few elements with many connections, and many elements with few connections. This book presents the experimental evidence of these 'scale-free networks' and provides students and researchers with a corpus of theoretical results and algorithms to analyse and understand these features. The content of this book and the exposition makes it a clear textbook for beginners, and a reference book for the experts.

This clearly written , mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering. "Mathematicians wishing a self-contained introduction need look no further."-American Mathematical Monthly. 1982 ed.

* What is the essence of the similarity between linearly independent sets of columns of a matrix and forests in a graph?
* Why does the greedy algorithm produce a spanning tree of minimum weight in a connected graph?
* Can we test in polynomial time whether a matrix is totally unimodular?
Matroid theory examines and answers questions like these. Seventy-five years of study of matroids has seen the development of a rich theory with links to graphs, lattices, codes, transversals, and projective geometries. Matroids are of fundamental importance in combinatorial optimization and their applications extend into electrical and structural engineering.
This book falls into two parts: the first provides a comprehensive introduction to the basics of matroid theory, while the second treats more advanced topics. The book contains over seven hundred exercises and includes, for the first time in one place, proofs of all of the major theorems in the subject. The last two chapters review current research and list more than eighty unsolved problems along with a description of the progress towards their solutions.
Reviews from previous edition:
"It includes more background, such as finite fields and finite projective and affine geometries, and the level of the exercises is well suited to graduate students. The book is well written and includes a couple of nice touches ... this is a very useful book. I recommend it highly both as an introduction to matroid theory and as a reference work for those already seriously interested in the subject, whether for its own sake or for its applications to other fields." -- AMS Bulletin
"Whoever wants to know what is happening in one of the most exciting chapters of combinatorics has no choice but to buy and peruse Oxley's treatise." -- The Bulletin of Mathematics
"This book is an excellent graduate textbook and reference book on matroid theory. The care that went into the writing of this book is evident by the quality of the exposition." -- Mathematical Reviews

The theory of random graphs is a vital part of the education of any researcher entering the fascinating world of combinatorics. However, due to their diverse nature, the geometric and structural aspects of the theory often remain an obscure part of the formative study of young combinatorialists and probabilists. Moreover, the theory itself, even in its most basic forms, is often considered too advanced to be part of undergraduate curricula, and those who are interested usually learn it mostly through self-study, covering a lot of its fundamentals but little of the more recent developments. This book provides a self-contained and concise introduction to recent developments and techniques for classical problems in the theory of random graphs. Moreover, it covers geometric and topological aspects of the theory and introduces the reader to the diversity and depth of the methods that have been devised in this context.

This book collects some surveys on current trends in discrete mathematics and discrete geometry. The areas covered include: graph representations, structural graphs theory, extremal graph theory, Ramsey theory and constrained satisfaction problems.

The importance of mathematics competitions has been widely recognized for three reasons: they help to develop imaginative capacity and thinking skills whose value far transcends mathematics; they constitute the most effective way of discovering and nurturing mathematical talent; and they provide a means to combat the prevalent false image of mathematics held by high school students, as either a fearsomely difficult or a dull and uncreative subject. This book provides a comprehensive training resource for competitions from local and provincial to national Olympiad level, containing hundreds of diagrams, and graced by many light-hearted cartoons. It features a large collection of what mathematicians call "beautiful" problems - non-routine, provocative, fascinating, and challenging problems, often with elegant solutions. It features careful, systematic exposition of a selection of the most important topics encountered in mathematics competitions, assuming little prior knowledge. Geometry, trigonometry, mathematical induction, inequalities, Diophantine equations, number theory, sequences and series, the binomial theorem, and combinatorics - are all developed in a gentle but lively manner, liberally illustrated with examples, and consistently motivated by attractive "appetiser" problems, whose solution appears after the relevant theory has been expounded.
Each chapter is presented as a "toolchest" of instruments designed for cracking the problems collected at the end of the chapter. Other topics, such as algebra, co-ordinate geometry, functional equations and probability, are introduced and elucidated in the posing and solving of the large collection of miscellaneous problems in thefinal toolchest.
An unusual feature of this book is the attention paid throughout to the history of mathematics - the origins of the ideas, the terminology and some of the problems, and the celebration of mathematics as a multicultural, cooperative human achievement.
As a bonus the aspiring "mathlete" may encounter, in the most enjoyable way possible, many of the topics that form the core of the standard school curriculum.

This book concentrates on the modern theory of dynamical systems and its interactions with number theory and combinatorics. The greater part begins with a course in analytic number theory and focuses on its links with ergodic theory, presenting an exhaustive account of recent research on Sarnak's conjecture on Moebius disjointness. Selected topics involving more traditional connections between number theory and dynamics are also presented, including equidistribution, homogenous dynamics, and Lagrange and Markov spectra. In addition, some dynamical and number theoretical aspects of aperiodic order, some algebraic systems, and a recent development concerning tame systems are described.

Presenting the state of the art, the Handbook of Enumerative Combinatorics brings together the work of today's most prominent researchers. The contributors survey the methods of combinatorial enumeration along with the most frequent applications of these methods. This important new work is edited by Miklos Bona of the University of Florida where he is a member of the Academy of Distinguished Teaching Scholars. He received his Ph.D. in mathematics at Massachusetts Institute of Technology in 1997. Miklos is the author of four books and more than 65 research articles, including the award-winning Combinatorics of Permutations. Miklos Bona is an editor-in-chief for the Electronic Journal of Combinatorics and Series Editor of the Discrete Mathematics and Its Applications Series for CRC Press/Chapman and Hall. The first two chapters provide a comprehensive overview of the most frequently used methods in combinatorial enumeration, including algebraic, geometric, and analytic methods. These chapters survey generating functions, methods from linear algebra, partially ordered sets, polytopes, hyperplane arrangements, and matroids. Subsequent chapters illustrate applications of these methods for counting a wide array of objects. The contributors for this book represent an international spectrum of researchers with strong histories of results. The chapters are organized so readers advance from the more general ones, namely enumeration methods, towards the more specialized ones. Topics include coverage of asymptotic normality in enumeration, planar maps, graph enumeration, Young tableaux, unimodality, log-concavity, real zeros, asymptotic normality, trees, generalized Catalan paths, computerized enumeration schemes, enumeration of various graph classes, words, tilings, pattern avoidance, computer algebra, and parking functions. This book will be beneficial to a wide audience. It will appeal to experts on the topic interested in learning more about the finer points, readers interested in a systematic and organized treatment of the topic, and novices who are new to the field.

This textbook provides an accessible introduction to the rich and beautiful area of hyperplane arrangement theory, where discrete mathematics, in the form of combinatorics and arithmetic, meets continuous mathematics, in the form of the topology and Hodge theory of complex algebraic varieties. The topics discussed in this book range from elementary combinatorics and discrete geometry to more advanced material on mixed Hodge structures, logarithmic connections and Milnor fibrations. The author covers a lot of ground in a relatively short amount of space, with a focus on defining concepts carefully and giving proofs of theorems in detail where needed. Including a number of surprising results and tantalizing open problems, this timely book also serves to acquaint the reader with the rapidly expanding literature on the subject. Hyperplane Arrangements will be particularly useful to graduate students and researchers who are interested in algebraic geometry or algebraic topology. The book contains numerous exercises at the end of each chapter, making it suitable for courses as well as self-study.

This new edition to the classic book by ggplot2 creator Hadley Wickham highlights compatibility with knitr and RStudio. ggplot2 is a data visualization package for R that helps users create data graphics, including those that are multi-layered, with ease. With ggplot2, it's easy to: produce handsome, publication-quality plots with automatic legends created from the plot specification superimpose multiple layers (points, lines, maps, tiles, box plots) from different data sources with automatically adjusted common scales add customizable smoothers that use powerful modeling capabilities of R, such as loess, linear models, generalized additive models, and robust regression save any ggplot2 plot (or part thereof) for later modification or reuse create custom themes that capture in-house or journal style requirements and that can easily be applied to multiple plots approach a graph from a visual perspective, thinking about how each component of the data is represented on the final plot This book will be useful to everyone who has struggled with displaying data in an informative and attractive way. Some basic knowledge of R is necessary (e.g., importing data into R). ggplot2 is a mini-language specifically tailored for producing graphics, and you'll learn everything you need in the book. After reading this book you'll be able to produce graphics customized precisely for your problems, and you'll find it easy to get graphics out of your head and on to the screen or page.

Graphentheorie: eine Theorie, oder einfach eine Methode, um Sachverhalte an- schaulich darzustellen, die auch in anderer Weise erfassbar waren? Beides trifft zu: Tatsachlich ist die Graphentheorie heute bereits ein recht weit entwickelter Zweig der diskreten Mathematik, mit dem sich Spezialisten befassen. Auf der anderen Seite bietet die Abstraktion von Problemstellungen aus der "rea- len" Welt auf die beiden urspriinglich der Geometrie entliehenen Elemente "Punkt" und "Kante" eine reizvolle Gelegenheit, auch fUr die Losung von Aufgaben eher kombinatorischer Natur an die bildliche Vorstellung zu appellieren. Dieses Buch ist aus dem Manuskript einer einsemestrigen Vorlesung entstan- den, die ich mehrere Male an der Eidgenossischen Technischen Hochschule Ziirich (ETH) fUr Studenten der Informatik und der Mathematik in mittleren Semestern gehalten habe. Der Text richtet sich - ausser an dies en Kreis - durchaus auch an Studenten von Hoheren Technischen Lehranstalten (bzw. Fachhochschulen), sowie an Gymnasiallehrer. Die letzteren werden zwar den Stoff kaum als geschlos- senen Lehrgang beniitzen, konnen jedoch eventuell einzelne herausgegriffene Teile im Unterricht der oberen Klassen einbringen. Das Buch solI zunachst eine erste EinfUhrung in die Graphentheorie vermitteln - wer nur diese sucht, kann im Extremfall die Kapitel 3 und 4, sowie in den folgenden Kapiteln alles, was sich auf Algorithmen bezieht, weglassen.

Diskrete und kontinuierliche Methoden der mathematischen Optimierung werden in diesem Lehrbuch integriert behandelt. Nach einer Einfuhrung werden konvexe Mengen (mit einer Anwendung auf notwendige Optimalitatsbedingungen bei Ungleichungsrestriktionen) behandelt, gefolgt von einer genaueren Betrachtung des Spezialfalls von Polyedern und dessen Zusammenhang zum Linearen Programmieren. Eine ausfuhrliche Darstellung des Simplexverfahrens schliesst diesen Teil ab. Danach wird die Konvexitat von Funktionen (inklusive einiger Abschwachungen) untersucht und fur ein grundliches Studium von Optimalitatskriterien sowie der Lagrange-Dualitat verwendet. Schliesslich folgen noch ein Ausblick auf allgemeine Algorithmen sowie ein kurzer Anhang zur affinen Geometrie. In der Neuauflage ist Anordnung und Darstellung des behandelten Stoffs nochmals grundlich im Sinne der aktuellen BA-Studiengange Mathematik, Wirtschaftswissenschaften und Informatik uberarbeitet worden.

Introducing the reader to the mathematics beyond complex networked systems, these lecture notes investigate graph theory, graphical models, and methods from statistical physics. Complex networked systems play a fundamental role in our society, both in everyday life and in scientific research, with applications ranging from physics and biology to economics and finance. The book is self-contained, and requires only an undergraduate mathematical background.

The study of network theory is a highly interdisciplinary field, which has emerged as a major topic of interest in various disciplines ranging from physics and mathematics, to biology and sociology. This book promotes the diverse nature of the study of complex networks by balancing the needs of students from very different backgrounds. It references the most commonly used concepts in network theory, provides examples of their applications in solving practical problems, and clear indications on how to analyse their results. In the first part of the book, students and researchers will discover the quantitative and analytical tools necessary to work with complex networks, including the most basic concepts in network and graph theory, linear and matrix algebra, as well as the physical concepts most frequently used for studying networks. They will also find instruction on some key skills such as how to proof analytic results and how to manipulate empirical network data. The bulk of the text is focused on instructing readers on the most useful tools for modern practitioners of network theory. These include degree distributions, random networks, network fragments, centrality measures, clusters and communities, communicability, and local and global properties of networks. The combination of theory, example and method that are presented in this text, should ready the student to conduct their own analysis of networks with confidence and allow teachers to select appropriate examples and problems to teach this subject in the classroom.

The theory of lattices, initiated by Dedekind in the past centu- ry, and revived in the thirties by Garrett Birkhoff, F. Klein-Barmen, ore, and von Neumann, is only in our time coming into its own. The fledgling theory was handicapped by a contingent historical circumstance. The peculiarities of mathematical personality of the founders made lattice theory less welcome to the mathematical public of the time than it otherwise might have been. Thus Dedekind was wi- dely thought in his time to be far too abstract for his own good, and some of his peers, notably Kronecker, did not hesitate to state their loud and clear disapproval. Later on, the tempers of Garrett Birkhoff and John von Neumann clashed with those of some of the "mainstream"' mathematicians of their time. Norman Levinson once related to me the following anecdote about von Neumann. Invited to deliver the weekly mathematics colloquium at Harvard sometime in the thirties, he chose the subject of his current interest, namely, continuous geometries. At the end of the lecture, as the public was streaming out, G. H. Hardy, who was at the time visiting Cambridge, was overheard whispering to G. D. Birkhoff (Gar- rett's father): "He is quite clearly a very brilliant man, but why does he waste his time on this stuff?" I myself, when still an assistant professor, was once stopped in the hall of M. I. T.

This is the first book to focus on the topological index, the Harary index, of a graph, including its mathematical properties, chemical applications and some related and attractive open problems. This book is dedicated to Professor Frank Harary (1921-2005), the grandmaster of graph theory and its applications. It has be written by experts in the field of graph theory and its applications. For a connected graph G, as an important distance-based topological index, the Harary index H(G) is defined as the sum of the reciprocals of the distance between any two unordered vertices of the graph G. In this book, the authors report on the newest results on the Harary index of a graph. These results mainly concern external graphs with respect to the Harary index; the relations to other topological indices; its properties and applications to pure graph theory and chemical graph theory; and two significant variants, i.e., additively and multiplicatively weighted Harary indices. In the last chapter, we present a number of open problems related to the Harary index. As such, the book will not only be of interest to graph researchers, but to mathematical chemists as well.