Béla Bollobás

Over the past few decades, graph theory has developed into one of the central areas of modern mathematics, with close (and growing) connections to areas of pure mathematics such as number theory, probability theory, algebra and geometry, as well as to applied areas such as the theory of networks, machine learning, statistical physics, and biology. It is a young and vibrant area, with several major breakthroughs having occurred in just the past few years. This book offers the reader a gentle introduction to the fundamental concepts and techniques of graph theory, covering classical topics such as matchings, colourings and connectivity, alongside the modern and vibrant areas of extremal graph theory, Ramsey theory, and random graphs. The focus throughout is on beautiful questions, ideas and proofs, and on illustrating simple but powerful techniques, such as the probabilistic method, that should be part of every young mathematician's toolkit.

Over the past few decades, graph theory has developed into one of the central areas of modern mathematics, with close (and growing) connections to areas of pure mathematics such as number theory, probability theory, algebra and geometry, as well as to applied areas such as the theory of networks, machine learning, statistical physics, and biology. It is a young and vibrant area, with several major breakthroughs having occurred in just the past few years. This book offers the reader a gentle introduction to the fundamental concepts and techniques of graph theory, covering classical topics such as matchings, colourings and connectivity, alongside the modern and vibrant areas of extremal graph theory, Ramsey theory, and random graphs. The focus throughout is on beautiful questions, ideas and proofs, and on illustrating simple but powerful techniques, such as the probabilistic method, that should be part of every young mathematician's toolkit.

Lovers of mathematics, young and old, professional and amateur, will enjoy this book. It is mathematics with fun: a collection of attractive problems that will delight and test readers. Many of the problems are drawn from the large number that have entertained and challenged students, guests and colleagues over the years during afternoon tea. The problems have their roots in many areas of mathematics. They vary greatly in difficulty: some are very easy, but most are far from trivial, and quite a few rather hard. Many provide substantial and surprising results that form the tip of an iceberg, providing an introduction to an important topic. To enjoy and appreciate the problems, readers should browse the book choosing one that looks particularly enticing, and think about it on and off for a while before resorting to the hint or the solution. Follow threads for an enjoyable and enriching journey through mathematics.

Lovers of mathematics, young and old, professional and amateur, will enjoy this book. It is mathematics with fun: a collection of attractive problems that will delight and test readers. Many of the problems are drawn from the large number that have entertained and challenged students, guests and colleagues over the years during afternoon tea. The problems have their roots in many areas of mathematics. They vary greatly in difficulty: some are very easy, but most are far from trivial, and quite a few rather hard. Many provide substantial and surprising results that form the tip of an iceberg, providing an introduction to an important topic. To enjoy and appreciate the problems, readers should browse the book choosing one that looks particularly enticing, and think about it on and off for a while before resorting to the hint or the solution. Follow threads for an enjoyable and enriching journey through mathematics.

From the reviews: "Béla Bollobás introductory course on graph theory deserves to be considered as a watershed in the development of this theory as a serious academic subject. ... The book has chapters on electrical networks, flows, connectivity and matchings, extremal problems, colouring, Ramsey theory, random graphs, and graphs and groups. Each chapter starts at a measured and gentle pace. Classical results are proved and new insight is provided, with the examples at the end of each chapter fully supplementing the text... Even so this allows an introduction not only to some of the deeper results but, more vitally, provides outlines of, and firm insights into, their proofs. Thus in an elementary text book, we gain an overall understanding of well-known standard results, and yet at the same time constant hints of, and guidelines into, the higher levels of the subject. It is this aspect of the book which should guarantee it a permanent place in the literature." #Bulletin of the London Mathematical Society#1

Percolation theory was initiated some fifty years ago as a mathematical framework for the study of random physical processes such as flow through a disordered porous medium. It has proved to be a remarkably rich theory, with applications beyond natural phenomena to topics such as network modelling. The aims of this book, first published in 2006, are twofold. First to present classical results in a way that is accessible to non-specialists. Second, to describe results of Smirnov in conformal invariance, and outline the proof that the critical probability for random Voronoi percolation in the plane is 1/2. Throughout, the presentation is streamlined, with elegant and straightforward proofs requiring minimal background in probability and graph theory. Numerous examples illustrate the important concepts and enrich the arguments. All-in-all, it will be an essential purchase for mathematicians, physicists, electrical engineers and computer scientists working in this exciting area.

Can a Christian escape from a lion? How quickly can a rumour spread? Can you fool an airline into accepting oversize baggage? Recreational mathematics is full of frivolous questions where the mathematician's art can be brought to bear. But play often has a purpose. In mathematics, it can sharpen skills, provide amusement, or simply surprise, and books of problems have been the stock-in-trade of mathematicians for centuries. This collection is designed to be sipped from, rather than consumed in one sitting. The questions range in difficulty: the most challenging offer a glimpse of deep results that engage mathematicians today; even the easiest prompt readers to think about mathematics. All come with solutions, many with hints, and most with illustrations. Whether you are an expert, or a beginner or an amateur mathematician, this book will delight for a lifetime.

The ever-expanding field of extremal graph theory encompasses an array of problem-solving methods, including applications to economics, computer science, and optimization theory. This volume presents a concise yet comprehensive treatment, featuring complete proofs for almost all of its results and numerous exercises. 1978 edition.

A revised and updated version of the first edition.

In this second edition of the now classic text, the already extensive treatment given in the first edition has been heavily revised by the author. The addition of two new sections, numerous new results and 150 references means that this represents a comprehensive account of random graph theory. The theory (founded by Erdös and Rényi in the late fifties) aims to estimate the number of graphs of a given degree that exhibit certain properties. It not only has numerous combinatorial applications, but also serves as a model for the probabilistic treatment of more complicated random structures. This book, written by an acknowledged expert in the field, can be used by mathematicians, computer scientists and electrical engineers, as well as people working in biomathematics. It is self-contained, and with numerous exercises in each chapter, is ideal for advanced courses or self study.

Now revised and updated, this brisk introduction to functional analysis is intended for advanced undergraduate students, typically final year, who have had some background in real analysis. The author’s aim is not just to cover the standard material in a standard way, but to present results of application in contemporary mathematics and to show the relevance of functional analysis to other areas. Unusual topics covered include the geometry of finite-dimensional spaces, invariant subspaces, fixed-point theorems, and the Bishop-Phelps theorem. An outstanding feature is the large number of exercises, some straightforward, some challenging, none uninteresting.

This text is an in-depth account of graph theory. It reflects the current state of the subject and emphasizes connections with other branches of pure mathematics.

Problems in extremal graph theory have traditionally been tackled by ingenious methods which made use of the structure of extremal graphs. In this book, an update of his 1978 book "Extremal Graph Theory", the author focuses on a trend towards probabilistic methods. He demonstrates both the direct use of probability theory and, more importantly, the fruitful adoption of a probabilistic frame of mind when tackling main line extremal problems. Essentially self-contained, the book does not merely catalog results, but rather includes considerable discussion on a few of the deeper results. The author addresses pure mathematicians, especially combinatorialists and graduate students taking graph theory, as well as theoretical computer scientists. He assumes a mature familiarity with combinatorial methods and an acquaintance with basic graph theory. The book is based on the NSF-CBMS Regional Conference on Graph Theory held at Emory University in June, 1984.