Thirty-three Miniatures

Mathematical and Algorithmic Applications of Linear Algebra

Author: Jiří Matoušek

Publisher: American Mathematical Soc.

ISBN: 0821849778

Category: Mathematics

Page: 182

View: 9638

This volume contains a collection of clever mathematical applications of linear algebra, mainly in combinatorics, geometry, and algorithms. Each chapter covers a single main result with motivation and full proof in at most ten pages and can be read independently of all other chapters (with minor exceptions), assuming only a modest background in linear algebra. The topics include a number of well-known mathematical gems, such as Hamming codes, the matrix-tree theorem, the Lovasz bound on the Shannon capacity, and a counterexample to Borsuk's conjecture, as well as other, perhaps less popular but similarly beautiful results, e.g., fast associativity testing, a lemma of Steinitz on ordering vectors, a monotonicity result for integer partitions, or a bound for set pairs via exterior products. The simpler results in the first part of the book provide ample material to liven up an undergraduate course of linear algebra. The more advanced parts can be used for a graduate course of linear-algebraic methods or for seminar presentations. Table of Contents: Fibonacci numbers, quickly; Fibonacci numbers, the formula; The clubs of Oddtown; Same-size intersections; Error-correcting codes; Odd distances; Are these distances Euclidean?; Packing complete bipartite graphs; Equiangular lines; Where is the triangle?; Checking matrix multiplication; Tiling a rectangle by squares; Three Petersens are not enough; Petersen, Hoffman-Singleton, and maybe 57; Only two distances; Covering a cube minus one vertex; Medium-size intersection is hard to avoid; On the difficulty of reducing the diameter; The end of the small coins; Walking in the yard; Counting spanning trees; In how many ways can a man tile a board?; More bricks--more walls?; Perfect matchings and determinants; Turning a ladder over a finite field; Counting compositions; Is it associative?; The secret agent and umbrella; Shannon capacity of the union: a tale of two fields; Equilateral sets; Cutting cheaply using eigenvectors; Rotating the cube; Set pairs and exterior products; Index. (STML/53)


Author: Ida Kantor, Jiří Matoušek,Robert Šámal

Publisher: American Mathematical Soc.

ISBN: 1470422611


Page: 343

View: 2734

Mathematics++ is a concise introduction to six selected areas of 20th century mathematics providing numerous modern mathematical tools used in contemporary research in computer science, engineering, and other fields. The areas are: measure theory, high-dimensional geometry, Fourier analysis, representations of groups, multivariate polynomials, and topology. For each of the areas, the authors introduce basic notions, examples, and results. The presentation is clear and accessible, stressing intuitive understanding, and it includes carefully selected exercises as an integral part. Theory is complemented by applications--some quite surprising--in theoretical computer science and discrete mathematics. The chapters are independent of one another and can be studied in any order. It is assumed that the reader has gone through the basic mathematics courses. Although the book was conceived while the authors were teaching Ph.D. students in theoretical computer science and discrete mathematics, it will be useful for a much wider audience, such as mathematicians specializing in other areas, mathematics students deciding what specialization to pursue, or experts in engineering or other fields.

Understanding and Using Linear Programming

Author: Jiri Matousek,Bernd Gärtner

Publisher: Springer Science & Business Media

ISBN: 3540307176

Category: Mathematics

Page: 226

View: 3661

The book is an introductory textbook mainly for students of computer science and mathematics. Our guiding phrase is "what every theoretical computer scientist should know about linear programming". A major focus is on applications of linear programming, both in practice and in theory. The book is concise, but at the same time, the main results are covered with complete proofs and in sufficient detail, ready for presentation in class. The book does not require more prerequisites than basic linear algebra, which is summarized in an appendix. One of its main goals is to help the reader to see linear programming "behind the scenes".

Approximation Algorithms and Semidefinite Programming

Author: Bernd Gärtner,Jiri Matousek

Publisher: Springer Science & Business Media

ISBN: 3642220150

Category: Mathematics

Page: 251

View: 546

Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material. There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms. This book follows the “semidefinite side” of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms.

Using the Borsuk-Ulam Theorem

Lectures on Topological Methods in Combinatorics and Geometry

Author: Jiri Matousek

Publisher: Springer Science & Business Media

ISBN: 3540766499

Category: Mathematics

Page: 214

View: 7279

To the uninitiated, algebraic topology might seem fiendishly complex, but its utility is beyond doubt. This brilliant exposition goes back to basics to explain how the subject has been used to further our understanding in some key areas. A number of important results in combinatorics, discrete geometry, and theoretical computer science have been proved using algebraic topology. While the results are quite famous, their proofs are not so widely understood. This book is the first textbook treatment of a significant part of these results. It focuses on so-called equivariant methods, based on the Borsuk-Ulam theorem and its generalizations. The topological tools are intentionally kept on a very elementary level. No prior knowledge of algebraic topology is assumed, only a background in undergraduate mathematics, and the required topological notions and results are gradually explained.

An Introduction to Multivariable Mathematics

Author: Leon Simon

Publisher: Morgan & Claypool Publishers

ISBN: 159829802X

Category: Technology & Engineering

Page: 132

View: 8328

The text is designed for use in a forty-lecture introductory course covering linear algebra, multivariable differential calculus, and an introduction to real analysis. The core material of the book is arranged to allow for the main introductory material on linear algebra, including basic vector space theory in Euclidean space and the initial theory of matrices and linear systems, to be covered in the first ten or eleven lectures, followed by a similar number of lectures on basic multivariable analysis, including first theorems on differentiable functions on domains in Euclidean space and a brief introduction to submanifolds. The book then concludes with further essential linear algebra, including the theory of determinants, eigenvalues, and the spectral theorem for real symmetric matrices, and further multivariable analysis, including the contraction mapping principle and the inverse and implicit function theorems. There is also an appendix which provides a nine-lecture introduction to real analysis. There are various ways in which the additional material in the appendix could be integrated into a course--for example in the Stanford Mathematics honors program, run as a four-lecture per week program in the Autumn Quarter each year, the first six lectures of the nine-lecture appendix are presented at the rate of one lecture per week in weeks two through seven of the quarter, with the remaining three lectures per week during those weeks being devoted to the main chapters of the text. It is hoped that the text would be suitable for a quarter or semester course for students who have scored well in the BC Calculus advanced placement examination (or equivalent), particularly those who are considering a possible major in mathematics. The author has attempted to make the presentation rigorous and complete, with the clarity and simplicity needed to make it accessible to an appropriately large group of students. Table of Contents: Linear Algebra / Analysis in R / More Linear Algebra / More Analysis in R / Appendix: Introductory Lectures on Real Analysis

The Art of Mathematics

Coffee Time in Memphis

Author: Béla Bollobás

Publisher: Cambridge University Press

ISBN: 1139936662

Category: Mathematics

Page: N.A

View: 9249

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.

Applied Linear Algebra

The Decoupling Principle

Author: Lorenzo Adlai Sadun

Publisher: American Mathematical Soc.

ISBN: 0821844415

Category: Mathematics

Page: 371

View: 5647

Linear algebra permeates mathematics, as well as physics and engineering. In this text for junior and senior undergraduates, Sadun treats diagonalization as a central tool in solving complicated problems in these subjects by reducing coupled linear evolution problems to a sequence of simpler decoupled problems. This is the Decoupling Principle. Traditionally, difference equations, Markov chains, coupled oscillators, Fourier series, the wave equation, the Schrodinger equation, and Fourier transforms are treated separately, often in different courses. Here, they are treated as particular instances of the decoupling principle, and their solutions are remarkably similar. By understanding this general principle and the many applications given in the book, students will be able to recognize it and to apply it in many other settings. Sadun includes some topics relating to infinite-dimensional spaces. He does not present a general theory, but enough so as to apply the decoupling principle to the wave equation, leading to Fourier series and the Fourier transform. The second edition contains a series of Explorations. Most are numerical labs in which the reader is asked to use standard computer software to look deeper into the subject. Some explorations are theoretical, for instance, relating linear algebra to quantum mechanics. There is also an appendix reviewing basic matrix operations and another with solutions to a third of the exercises.

Mathematical Omnibus

Thirty Lectures on Classic Mathematics

Author: D. B. Fuks,Serge Tabachnikov

Publisher: American Mathematical Soc.

ISBN: 0821843168

Category: Mathematics

Page: 463

View: 8431

The book consists of thirty lectures on diverse topics, covering much of the mathematical landscape rather than focusing on one area. The reader will learn numerous results that often belong to neither the standard undergraduate nor graduate curriculum and will discover connections between classical and contemporary ideas in algebra, combinatorics, geometry, and topology. The reader's effort will be rewarded in seeing the harmony of each subject. The common thread in the selected subjects is their illustration of the unity and beauty of mathematics. Most lectures contain exercises, and solutions or answers are given to selected exercises. A special feature of the book is an abundance of drawings (more than four hundred), artwork by an accomplished artist, and about a hundred portraits of mathematicians. Almost every lecture contains surprises for even the seasoned researcher.

Invitation to Discrete Mathematics

Author: Ji%rí Matousek,Jaroslav Ne%set%ril

Publisher: Oxford University Press

ISBN: 0198570430

Category: Mathematics

Page: 443

View: 2887

Invitation to Discrete Mathematics is an introduction and a thoroughly comprehensive text at the same time. A lively and entertaining style with mathematical precision and maturity uniquely combine into an intellectual happening and should delight the interested reader. A master example of teaching contemporary discrete mathematics, and of teaching science in general.

Linear Programming

Methods and Applications

Author: Saul I. Gass

Publisher: Courier Corporation

ISBN: 048643284X

Category: Mathematics

Page: 532

View: 7206

Comprehensive, well-organized volume, suitable for undergraduates, covers theoretical, computational, and applied areas in linear programming. Expanded, updated edition; useful both as a text and as a reference book. 1995 edition.

Mathematics of Bioinformatics

Theory, Methods and Applications

Author: Matthew He,Sergey Petoukhov

Publisher: John Wiley & Sons

ISBN: 9781118099520

Category: Computers

Page: 298

View: 6167

Mathematics of Bioinformatics: Theory, Methods, and Applications provides a comprehensive format for connecting and integrating information derived from mathematical methods and applying it to the understanding of biological sequences, structures, and networks. Each chapter is divided into a number of sections based on the bioinformatics topics and related mathematical theory and methods. Each topic of the section is comprised of the following three parts: an introduction to the biological problems in bioinformatics; a presentation of relevant topics of mathematical theory and methods to the bioinformatics problems introduced in the first part; an integrative overview that draws the connections and interfaces between bioinformatics problems/issues and mathematical theory/methods/applications.

Combinatorial Problems and Exercises

Author: L. Lovász

Publisher: Elsevier

ISBN: 0080933092

Category: Mathematics

Page: 636

View: 3344

The aim of this book is to introduce a range of combinatorial methods for those who want to apply these methods in the solution of practical and theoretical problems. Various tricks and techniques are taught by means of exercises. Hints are given in a separate section and a third section contains all solutions in detail. A dictionary section gives definitions of the combinatorial notions occurring in the book. Combinatorial Problems and Exercises was first published in 1979. This revised edition has the same basic structure but has been brought up to date with a series of exercises on random walks on graphs and their relations to eigenvalues, expansion properties and electrical resistance. In various chapters the author found lines of thought that have been extended in a natural and significant way in recent years. About 60 new exercises (more counting sub-problems) have been added and several solutions have been simplified.

A Primer on the Calculus of Variations and Optimal Control Theory

Author: Mike Mesterton-Gibbons

Publisher: American Mathematical Soc.

ISBN: 0821847724

Category: Mathematics

Page: 252

View: 1653

The calculus of variations is used to find functions that optimize quantities expressed in terms of integrals. Optimal control theory seeks to find functions that minimize cost integrals for systems described by differential equations. This book is an introduction to both the classical theory of the calculus of variations and the more modern developments of optimal control theory from the perspective of an applied mathematician. It focuses on understanding concepts and how to apply them. The range of potential applications is broad: the calculus of variations and optimal control theory have been widely used in numerous ways in biology, criminology, economics, engineering, finance, management science, and physics. Applications described in this book include cancer chemotherapy, navigational control, and renewable resource harvesting. The prerequisites for the book are modest: the standard calculus sequence, a first course on ordinary differential equations, and some facility with the use of mathematical software. It is suitable for an undergraduate or beginning graduate course, or for self study. It provides excellent preparation for more advanced books and courses on the calculus of variations and optimal control theory.

Linear Programming

Author: Vasek Chvatal

Publisher: Macmillan

ISBN: 9780716715870

Category: Mathematics

Page: 478

View: 4205

For upper-division/graduate courses in operations research/management science, mathematics, and computer science, this text covers basic theory, selected applications, network flow problems, and advanced techniques.

Linear Programming: An Introduction to Finite Improvement Algorithms

Second Edition

Author: Daniel Solow

Publisher: Courier Corporation

ISBN: 0486493768

Category: Mathematics

Page: 432

View: 6645

This text covers the basic theory and computation for a first course in linear programming, including substantial material on mathematical proof techniques and sophisticated computation methods. Includes Appendix on using Excel. 1984 edition.


Author: Joel Spencer

Publisher: American Mathematical Soc.

ISBN: 1470409046

Category: Mathematics

Page: 189

View: 7129

Asymptotics in one form or another are part of the landscape for every mathematician. The objective of this book is to present the ideas of how to approach asymptotic problems that arise in discrete mathematics, analysis of algorithms, and number theory. A broad range of topics is covered, including distribution of prime integers, Erdős Magic, random graphs, Ramsey numbers, and asymptotic geometry. The author is a disciple of Paul Erdős, who taught him about Asymptopia. Primes less than , graphs with vertices, random walks of steps--Erdős was fascinated by the limiting behavior as the variables approached, but never reached, infinity. Asymptotics is very much an art. The various functions , , , , all have distinct personalities. Erdős knew these functions as personal friends. It is the author's hope that these insights may be passed on, that the reader may similarly feel which function has the right temperament for a given task. This book is aimed at strong undergraduates, though it is also suitable for particularly good high school students or for graduates wanting to learn some basic techniques. Asymptopia is a beautiful world. Enjoy!

Mathematical Time Capsules

Historical Modules for the Mathematics Classroom

Author: Dick Jardine

Publisher: MAA

ISBN: 088385984X


Page: 204

View: 5125

Mathematical Time Capsules offers teachers historical modules for immediate use in the mathematics classroom. Readers will find articles and activities from mathematics history that enhance the learning of topics covered in the undergraduate or secondary mathematics curricula. Each capsule presents at least one topic or a historical thread that can be used throughout a course. The capsules were written by experienced practitioners to provide teachers with historical background and classroom activities designed for immediate use in the classroom, along with further references and resources on the chapter subject. --Publisher description.