Series: Mathematical Association of America Textbooks
Hardback (ISBN-13: 9780883857533)
Combining the features of a textbook with those of a problem workbook, this text for mathematics, computer science and engineering students presents a natural, friendly way to learn some of the essential ideas of graph theory. The material is explained using 360 strategically placed problems with connecting text, which is then supplemented by 280 additional homework problems. This problem-oriented format encourages active involvement by the reader while always giving clear direction. This approach is especially valuable with the presentation of proofs, which become more frequent and elaborate as the book progresses. Arguments are arranged in digestible chunks and always appear together with concrete examples to help remind the reader of the bigger picture. Topics include spanning tree algorithms, Euler paths, Hamilton paths and cycles, independence and covering, connections and obstructions, and vertex and edge colourings.
* Introduces graph theory using 360 explanatory exercises, with a further
280 homework problems to help students master the concepts * Topics include
Hall’s Theorem, the Konig-Egervary Theorem, matrices and Latin squares
* Ideal for undergraduates in mathematics, computer science and engineering
Preface; A. Basic Concepts; B. Isomorphic graphs; C. Bipartite graphs; D. Trees and forests; E. Spanning tree algorithms; F. Euler paths; G. Hamilton paths and cycles; H. Planar graphs; I. Independence and covering; J. Connections and obstructions; K. Vertex coloring; L. Edge coloring; M. Matching theory for bipartite graphs; N. Applications of matching theory; O. Cycle-Free digraphs; Answers to selected problems.
Quick search
Hardback (ISBN-13: 9780521515924)
This simple, compact toolkit for designing and analyzing stochastic approximation algorithms requires only basic literacy in probability and differential equations. Yet these algorithms have powerful applications in control and communications engineering, artificial intelligence and economic modelling. The dynamical systems viewpoint treats an algorithm as a noisy discretization of a limiting differential equation and argues that, under reasonable hypotheses, it tracks the asymptotic behaviour of the differential equation with probability one. The differential equation, which can usually be obtained by inspection, is easier to analyze. Novel topics include finite-time behaviour, multiple timescales and asynchronous implementation. There is a useful taxonomy of applications, with concrete examples from engineering and economics. Notably it covers variants of stochastic gradient-based optimization schemes, fixed-point solvers, which are commonplace in learning algorithms for approximate dynamic programming, and some models of collective behaviour. Three appendices give background on differential equations and probability.
* Simple, compact, cohesive * Motivated by modern applications and implementation
* Discussion of current topics: finite-time behaviour, multiple timescales,
asynchronous implementation
Preface; 1. Introduction; 2. Basic convergence analysis; 3. Stability criteria; 4. Lock-in probability; 5. Stochastic recursive inclusions; 6. Multiple timescales; 7. Asynchronous schemes; 8. A limit theorem for fluctuations; 9. Constant stepsize algorithms; 10. Applications; 11. Appendices; References; Index.
Paperback (ISBN-13: 9780521067331)
This volume is dedicated to Paul Erdos, who profoundly influenced mathematics in the twentieth century, with over 1200 papers in number theory, complex analysis, probability theory, geometry, interpretation theory, algebra set theory and combinatorics. One of Erdos’ hallmarks was the host of stimulating problems and conjectures, to many of which he attached monetary prices, in accordance with their notoriety. A feature of this volume is a collection of some 50 outstanding unsolved problems, together with their ‘value’! Eminent mathematicians from around the world have contributed articles to this volume that reflect the diversity of Erdos’ interests, and it will be a fund of insight for number theorists, combinatorialists, set theorists and analysts.
Contents
Frontispiece; List of contributors; Preface; 1. Generating expanders from
two permutations M. Ajtai, J. Komols and E. Szemeredi; 2. Sum-free subsets
N. Alon and D. J. Kleitman; 3. Is there a different proof of the Erdos-Rado
theorem* J. E. Baumgartner; 4. Almost collinear triples among N points
on the plane J. Beck; 5. Hamilton cycles in random graphs of minimal degree
at least |k| B. Bollobas, T. I. Fenner and A. M. Frieze; 6. The circumference
of a graph with a given minimal degree B. Bollobas and R. Haggkvist; 7.
On arithmetic progressions in sums of sets of integers J. Bourgain; 8.
Partitions sans petits sommants J. Dixmier and J. L. Nicolas; 9. A compact
sequential space A. Dow; 10. The critical parameter for connectedness of
some random graphs R. Durret and H. Kesten; 11. Multiplicative functions
on arithmetic progressions: the large moduli P. D. T. A. Elliott; 12. Locally
finite groups of permutations of N acting on loo M. Foreman; 13. Hypergraphs
games and the chromatic number F. Galvin; 14. On arithmetic graphs associated
with integral domains K. Gyory; 15. On the number of certain subgraphs
of graphs without large cliques and independent subsets A. Hajnal, Z. Nagy
and L. Soukup; 16. Sets of multiples and Behrend sequences R. R. Hall;
17. A functional equation arising from the mortality tables W. K. Hayman;
18. The differences between consecutives primes, IV R. Heath-Brown; 19.
On the cofinality of countable products of cardinal numbers T. Jech; On
a-centered posets I. Juhasz and K. Kunen; 20. A Galvin-Hajnal conjecture
on uncountably chromatic graphs P. Komjath; 21. Necessary conditions for
mean convergence of Hermite-Fejer interpolation A. Mate and P. Nevai; 22.
Graphs with no unfriendly partitions E. C. Milner and S. Shelah; 23. On
the Erdos-Fuchs theorem H. L. Montgomery and R. C. Vaughan; 24. A tournament
which is not finitely representable Z. Nagy and Z. Szentmiklossy; 25. On
the volume of spheres covered by a random walk P. Revesz; 26. Special Lucas
sequences, including the Fibonacci sequence, modulo a prime A. Schinzel;
27. A remark on heights of subspaces W. Schmidt and S. Shelah; 28. On the
greatest prime factor of an arithmetical progression T. N. Shorey and R.
Tijdeman; 29. The probabilistic lens: Sperner, Turan and Bergman revisited
J. Spencer; 30. On the mean convergence of derivatives of Lagrange interpolation
J. Szabodos and A. K. Varma; 31. Sur une question d’Erdos et Schinzel
G. Tenenbaum; 32. Some recent results on interpolation P. Vertesi; 33.
Partitioning the quadruples of topological spaces W. Weiss; Selected problems.
Paperback (ISBN-13: 9780521064477)
Markov chains are an important idea, related to random walks, which crops up widely in applied stochastic analysis. They are used, for example, in performance modelling and evaluation of computer networks, queuing networks, and telecommunication systems. The main point of the present book is to provide methods, based on the construction of Lyapunov functions, of determining when a Markov chain is ergodic, null recurrent, or transient. These methods can also be extended to the study of questions of stability. Of particular concern are reflected random walks and reflected Brownian motion. The authors provide not only a self-contained introduction to the theory but also details of how the required Lyapunov functions are constructed in various situations.
* Original research, first time of publication * Lots of interest in subject
matter * Of interest to researchers in applied mathematics, statistics,
probability
Introduction and history; 1. Preliminaries; 2. General criteria; 3. Explicit construction of Lyapunov functions; 4. Ideology of induced chains; 5. Random walks in two dimensional complexes; 6. Stability; 7. Exponential convergence and analyticity for ergodic Markov chains; Bibliography.
From the hardback review: ‘The monograph is an excellent piece of work that gives an original and alternative view on countable Markov chains.’ Mededelingen van het Wiskundig Genootschap
Paperback (ISBN-13: 9780521065085)
This book provides a solid foundation and an extensive study for an important class of constrained optimization problems known as Mathematical Programs with Equilibrium Constraints (MPEC), which are extensions of bilevel optimization problems. The book begins with the description of many source problems arising from engineering and economics that are amenable to treatment by the MPEC methodology. Error bounds and parametric analysis are the main tools to establish a theory of exact penalisation, a set of MPEC constraint qualifications and the first-order and second-order optimality conditions. The book also describes several iterative algorithms such as a penalty-based interior point algorithm, an implicit programming algorithm and a piecewise sequential quadratic programming algorithm for MPECs. Results in the book are expected to have significant impacts in such disciplines as engineering design, economics and game equilibria, and transportation planning, within all of which MPEC has a central role to play in the modelling of many practical problems.
* Broad appeal and coverage of topic * Diversity of approaches * Many illustrative
source problems and examples
1. Introduction; 2. Exact penalisation of MPEC; 3. First-order optimality conditions; 4. Verification of MPEC hypotheses; 5. Second-order optimality conditions; 6. Algorithms for MPEC.