A basic problem for the interconnection of communications media is to design interconnection networks for specific needs. For example, to minimize delay and to maximize reliability, networks are required that have minimum diameter and maximum connectivity under certain conditions. The book provides a recent solution to this problem. The subject of all five chapters is the interconnection problem. The first two chapters deal with Cayley digraphs which are candidates for networks of maximum connectivity with given degree and number of nodes. Chapter 3 addresses Bruijn digraphs, Kautz digraphs, and their generalizations, which are candidates for networks of minimum diameter and maximum connectivity with given degree and number of nodes. Chapter 4 studies double loop networks, and Chapter 5 considers broadcasting and the Gossiping problem. All the chapters emphasize the combinatorial aspects of network theory.

Developed from the authors’ introductory combinatorics course, this book focuses on a branch of mathematics which plays a crucial role in computer science. Combinatorial methods provide many analytical tools used for determining the expected performance of computer algorithms. Elementary subjects such as combinations and permutations, and mathematical tools such as generating functions and Pólya’s Theory of Counting, are covered, as are analyses of specific problems such as Ramsey Theory, matchings, and Hamiltonian and Eulerian paths.

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

With the advent of digital computers more than half a century ago, - searchers working in a wide range of scienti?c disciplines have obtained an extremely powerful tool to pursue deep understanding of natural processes in physical, chemical, and biological systems. Computers pose a great ch- lenge to mathematical sciences, as the range of phenomena available for rigorous mathematical analysis has been enormously expanded, demanding the development of a new generation of mathematical tools. There is an explosive growth of new mathematical disciplines to satisfy this demand, in particular related to discrete mathematics. However, it can be argued that at large mathematics is yet to provide the essential breakthrough to meet the challenge. The required paradigm shift in our view should be compa- ble to the shift in scienti?c thinking provided by the Newtonian revolution over 300 years ago. Studies of large-scale random graphs and networks are critical for the progress, using methods of discrete mathematics, probabil- tic combinatorics, graph theory, and statistical physics. Recent advances in large scale random network studies are described in this handbook, which provides a signi?cant update and extension - yond the materials presented in the “Handbook of Graphs and Networks” published in 2003 by Wiley. The present volume puts special emphasis on large-scale networks and random processes, which deemed as crucial for - tureprogressinthe?eld. Theissuesrelatedtorandomgraphsandnetworks pose very di?cult mathematical questions.

Developed from the authors’ introductory combinatorics course, this book focuses on a branch of mathematics which plays a crucial role in computer science. Combinatorial methods provide many analytical tools used for determining the expected performance of computer algorithms. Elementary subjects such as combinations and permutations, and mathematical tools such as generating functions and Pólya’s Theory of Counting, are covered, as are analyses of specific problems such as Ramsey Theory, matchings, and Hamiltonian and Eulerian paths.

This book contains two sets of notes prepared for the Advanced Course on R- sey Methods in Analysis given at the Centre de Recerca Matem` atica in January 2004, as part of its year-long research programme on Set Theory and its Appli- tions. The common goal of the two sets of notes is to help young mathematicians enter a very active area of research lying on the borderline between analysis and combinatorics. The solution of the distortion problem for the Hilbert space, the unconditional basic sequence problem for Banach spaces, and the Banach ho- geneous space problem are samples of the most important recent advances in this area, and our two sets of notes will give some account of this. But our main goal was to try to expose the general principles and methods that lie hidden behind and are most likely useful for further developments. The goal of the ?rst set of notes is to describe a general method of building norms with desired properties, a method that is clearly relevant when testing any sort of intuition about the in?nite-dimensional geometry of Banach spaces. The goal of the second set of notes is to expose Ramsey-theoretic methods relevant for describing the rough structure present in this sort of geometry. We would like to thank the coordinator of the Advanced Course, Joan Ba- ria, and the director of the CRM, Manuel Castellet, for giving us this challenging but rewarding opportunity. Part A SaturatedandConditional StructuresinBanachSpaces SpirosA.

Notwithstanding its title, the reader will not find in this book a systematic account of this huge subject. Certain classical aspects have been passed by, and the true title ought to be "Various questions of elementary combina­ torial analysis". For instance, we only touch upon the subject of graphs and configurations, but there exists a very extensive and good literature on this subject. For this we refer the reader to the bibliography at the end of the volume. The true beginnings of combinatorial analysis (also called combina­ tory analysis) coincide with the beginnings of probability theory in the 17th century. For about two centuries it vanished as an autonomous sub­ ject. But the advance of statistics, with an ever-increasing demand for configurations as well as the advent and development of computers, have, beyond doubt, contributed to reinstating this subject after such a long period of negligence. For a long time the aim of combinatorial analysis was to count the different ways of arranging objects under given circumstances. Hence, many of the traditional problems of analysis or geometry which are con­ cerned at a certain moment with finite structures, have a combinatorial character. Today, combinatorial analysis is also relevant to problems of existence, estimation and structuration, like all other parts of mathema­ tics, but exclusively forjinite sets.

Combinatorics and Algebraic Geometry have enjoyed a fruitful interplay since the nineteenth century. Classical interactions include invariant theory, theta functions and enumerative geometry. The aim of this volume is to introduce recent developments in combinatorial algebraic geometry and to approach algebraic geometry with a view towards applications, such as tensor calculus and algebraic statistics. A common theme is the study of algebraic varieties endowed with a rich combinatorial structure. Relevant techniques include polyhedral geometry, free resolutions, multilinear algebra, projective duality and compactifications.

Probabilistic and combinatorial techniques are often used for solving advanced problems. This book describes different probabilistic modeling methods and their applications in various areas, such as artificial intelligence, offshore platforms, social networks, and others. It aims to educate how modern probabilistic and combinatorial models may be created to formalize uncertainties; to train how new probabilistic models can be generated for the systems of complex structures; to describe the correct use of the presented models for rational control in systems creation and operation; and to demonstrate analytical possibilities and practical effects for solving different system problems on each life cycle stage.

Graph algorithms are easy to visualize and indeed there already exists a variety of packages to animate the dynamics when solving problems from graph theory. Still it can be difficult to understand the ideas behind the algorithm from the dynamic display alone.

by Gian-Carlo Rota The subjects of mathematics, like the subjects of mankind, have finite lifespans, which the historian will record as he freezes history at one instant of time. There are the old subjects, loaded with distinctions and honors. As their problems are solved away and the applications reaped by engineers and other moneymen, ponderous treatises gather dust in library basements, awaiting the day when a generation as yet unborn will rediscover the lost paradise in awe. Then there are the middle-aged subjects. You can tell which they are by roaming the halls of Ivy League universities or the Institute for Advanced Studies. Their high priests haughtily refuse fabulous offers from eager provin­ cial universities while receiving special permission from the President of France to lecture in English at the College de France. Little do they know that the load of technicalities is already critical, about to crack and submerge their theorems in the dust of oblivion that once enveloped the dinosaurs. Finally, there are the young subjects-combinatorics, for instance. Wild­ eyed individuals gingerly pick from a mountain of intractable problems, chil­ dishly babbling the first words of what will soon be a new language. Child­ hood will end with the first Seminaire Bourbaki. It could be impossible to find a more fitting example than matroid theory of a subject now in its infancy. The telltale signs, for an unfailing diagnosis, are the abundance of deep theorems, going together with a paucity of theories.

This book can be seen as a continuation of Equations and Inequalities: El­ ementary Problems and Theorems in Algebra and Number Theory by the same authors, and published as the first volume in this book series. How­ ever, it can be independently read or used as a textbook in its own right. This book is intended as a text for a problem-solving course at the first­ or second-year university level, as a text for enrichment classes for talented high-school students, or for mathematics competition training. It can also be used as a source of supplementary material for any course dealing with combinatorics, graph theory, number theory, or geometry, or for any of the discrete mathematics courses that are offered at most American and Canadian universities. The underlying "philosophy" of this book is the same as that of Equations and Inequalities. The following paragraphs are therefore taken from the preface of that book.

[UPDATED 6/6/2000] Group actions on trees furnish a unified geometric way of recasting the chapter of combinatorial group theory dealing with free groups, amalgams, and HNN extensions. Some of the principal examples arise from rank one simple Lie groups over a non-archimedean local field acting on their Bruhat–Tits trees. In particular this leads to a powerful method for studying lattices in such Lie groups. This monograph extends this approach to the more general investigation of $X$-lattices $\Gamma$, where $X$ is a locally finite tree and $\Gamma$ is a discrete group of automorphisms of $X$ of finite covolume. These "tree lattices" are the main object of study. Special attention is given to both parallels and contrasts with the case of Lie groups. Beyond the Lie group connection, the theory has applications to combinatorics and number theory. The authors present a coherent survey of the results on uniform tree lattices, and a (previously unpublished) development of the theory of non-uniform tree lattices, including some fundamental and recently proved existence theorems. Non-uniform tree lattices are much more complicated than unifrom ones; thus a good deal of attention is given to the construction and study of diverse examples. Some interesting new phenomena are observed here which cannot occur in the case of Lie groups. The fundamental technique is the encoding of tree actions in terms of the corresponding quotient "graph of groups." {\it Tree Lattices} should be a helpful resource to researchers in the field, and may also be used for a graduate course in geometric group theory.