Polynomial Methods in Combinatorics

DOWNLOAD NOW »

Author: Larry Guth

Publisher: American Mathematical Soc.

ISBN: 1470428903

Category: Combinatorial geometry

Page: 273

View: 626

This book explains some recent applications of the theory of polynomials and algebraic geometry to combinatorics and other areas of mathematics. One of the first results in this story is a short elegant solution of the Kakeya problem for finite fields, which was considered a deep and difficult problem in combinatorial geometry. The author also discusses in detail various problems in incidence geometry associated to Paul Erdős's famous distinct distances problem in the plane from the 1940s. The proof techniques are also connected to error-correcting codes, Fourier analysis, number theory, and differential geometry. Although the mathematics discussed in the book is deep and far-reaching, it should be accessible to first- and second-year graduate students and advanced undergraduates. The book contains approximately 100 exercises that further the reader's understanding of the main themes of the book.

A Journey Through Discrete Mathematics

A Tribute to Jiří Matoušek

DOWNLOAD NOW »

Author: Martin Loebl,Jaroslav Nešetřil,Robin Thomas

Publisher: Springer

ISBN: 3319444794

Category: Computers

Page: 810

View: 7669

This collection of high-quality articles in the field of combinatorics, geometry, algebraic topology and theoretical computer science is a tribute to Jiří Matoušek, who passed away prematurely in March 2015. It is a collaborative effort by his colleagues and friends, who have paid particular attention to clarity of exposition – something Jirka would have approved of. The original research articles, surveys and expository articles, written by leading experts in their respective fields, map Jiří Matoušek’s numerous areas of mathematical interest.

Handbook of Discrete and Computational Geometry, Third Edition

DOWNLOAD NOW »

Author: Csaba D. Toth,Joseph O'Rourke,Jacob E. Goodman

Publisher: CRC Press

ISBN: 1351645919

Category: Computers

Page: 1928

View: 1797

The Handbook of Discrete and Computational Geometry is intended as a reference book fully accessible to nonspecialists as well as specialists, covering all major aspects of both fields. The book offers the most important results and methods in discrete and computational geometry to those who use them in their work, both in the academic world—as researchers in mathematics and computer science—and in the professional world—as practitioners in ?elds as diverse as operations research, molecular biology, and robotics. Discrete geometry has contributed signi?cantly to the growth of discrete mathematics in recent years. This has been fueled partly by the advent of powerful computers and by the recent explosion of activity in the relatively young ?eld of computational geometry. This synthesis between discrete and computational geometry lies at the heart of this Handbook. A growing list of application fields includes combinatorial optimization, computer-aided design, computer graphics, crystallography, data analysis, error-correcting codes, geographic information systems, motion planning, operations research, pattern recognition, robotics, solid modeling, and tomography.

Introduction to Random Graphs

DOWNLOAD NOW »

Author: Alan Frieze,Michał Karoński

Publisher: Cambridge University Press

ISBN: 1107118506

Category: Mathematics

Page: 496

View: 3176

The text covers random graphs from the basic to the advanced, including numerous exercises and recommendations for further reading.

Graph Theory As I Have Known It

DOWNLOAD NOW »

Author: W. T. Tutte

Publisher: OUP Oxford

ISBN: 0191637785

Category: Mathematics

Page: 164

View: 7776

Graph Theory as I Have Known It provides a unique introduction to graph theory by one of the founding fathers, and will appeal to anyone interested in the subject. It is not intended as a comprehensive treatise, but rather as an account of those parts of the theory that have been of special interest to the author. Professor Tutte details his experience in the area, and provides a fascinating insight into how he was led to his theorems and the proofs he used. As well as being of historical interest it provides a useful starting point for research, with references to further suggested books as well as the original papers. The book starts by detailing the first problems worked on by Professor Tutte and his colleagues during his days as an undergraduate member of the Trinity Mathematical Society in Cambridge. It covers subjects such as combinatorial problems in chess, the algebraicization of graph theory, reconstruction of graphs, and the chromatic eigenvalues. In each case fascinating historical and biographical information about the author's research is provided. William Tutte (1917-2002) studied at Cambridge where his fascination for mathematical puzzles brought him into contact with like-minded undergraduates, together becoming known as the 'Trinity four', the founders of modern graph theory. His notable problem-solving skills meant he was brought to Bletchley Park during World War Two. Key in the enemy codebreaking efforts, he cracked the Lorenz cipher for which the Colossus machine was built, making his contribution comparable to Alan Turing's codebreaking for Enigma. Following his incredible war effort Tutte returned to academia and became a fellow of the Royal Society in Britain and Canada, finishing his career as Distinguished Professor Emeritus at the University of Waterloo, Ontario.

Dispersive Partial Differential Equations

Wellposedness and Applications

DOWNLOAD NOW »

Author: M. Burak Erdoğan,Nikolaos Tzirakis

Publisher: Cambridge University Press

ISBN: 1316694585

Category: Mathematics

Page: N.A

View: 4254

The area of nonlinear dispersive partial differential equations (PDEs) is a fast developing field which has become exceedingly technical in recent years. With this book, the authors provide a self-contained and accessible introduction for graduate or advanced undergraduate students in mathematics, engineering, and the physical sciences. Both classical and modern methods used in the field are described in detail, concentrating on the model cases that simplify the presentation without compromising the deep technical aspects of the theory, thus allowing students to learn the material in a short period of time. This book is appropriate both for self-study by students with a background in analysis, and for teaching a semester-long introductory graduate course in nonlinear dispersive PDEs. Copious exercises are included, and applications of the theory are also presented to connect dispersive PDEs with the more general areas of dynamical systems and mathematical physics.

Fourier Analysis and Hausdorff Dimension

DOWNLOAD NOW »

Author: Pertti Mattila

Publisher: Cambridge University Press

ISBN: 1107107350

Category: Mathematics

Page: 452

View: 8864

Modern text examining the interplay between measure theory and Fourier analysis.

Frontiers In Orthogonal Polynomials And Q-series

DOWNLOAD NOW »

Author: Nashed M Zuhair,Li Xin

Publisher: World Scientific

ISBN: 981322889X

Category: Mathematics

Page: 576

View: 974

This volume aims to highlight trends and important directions of research in orthogonal polynomials, q-series, and related topics in number theory, combinatorics, approximation theory, mathematical physics, and computational and applied harmonic analysis. This collection is based on the invited lectures by well-known contributors from the International Conference on Orthogonal Polynomials and q-Series, that was held at the University of Central Florida in Orlando, on May 10–12, 2015. The conference was dedicated to Professor Mourad Ismail on his 70th birthday. The editors strived for a volume that would inspire young researchers and provide a wealth of information in an engaging format. Theoretical, combinatorial and computational/algorithmic aspects are considered, and each chapter contains many references on its topic, when appropriate. Contents: Mourad Ismail (Richard Askey)Binomial Andrews–Gordon–Bressoud Identities (Dennis Stanton)Symmetric Expansions of Very Well-Poised Basic Hypergeometric Series (George E Andrews)A Sturm–Liouville Theory for Hahn Difference Operator (M H Annaby, A E Hamza and S D Makharesh)Solvability of the Hankel Determinant Problem for Real Sequences (Andrew Bakan and Christian Berg)Convolution and Product Theorems for the Special Affine Fourier Transform (Ayush Bhandari and Ahmed I Zayed)A Further Look at Time-and-Band Limiting for Matrix Orthogonal Polynomials (M Castro, F A Grünbaum, I Pacharoni and I Zurrián)The Orthogonality of Al–Salam–Carlitz Polynomials for Complex Parameters (Howard S Cohl, Roberto S Costas-Santos and Wenqing Xu)Crouching AGM, Hidden Modularity (Shaun Cooper, Jesús Guillera, Armin Straub and Wadim Zudilin)Asymptotics of Orthogonal Polynomials and the Painlevé Transcendents (Dan Dai)From the Gaussian Circle Problem to Multivariate Shannon Sampling (Willi Freeden and M Zuhair Nashed)Weighted Partition Identities and Divisor Sums (F G Garvan)On the Ismail–Letessier–Askey Monotonicity Conjecture for Zeros of Ultraspherical Polynomials (Walter Gautschi)A Discrete Top-Down Markov Problem in Approximation Theory (Walter Gautschi)Supersymmetry of the Quantum Rotor (Vincent X Genest, Luc Vinet, Guo-Fu Yu and Alexei Zhedanov)The Method of Brackets in Experimental Mathematics (Ivan Gonzalez, Karen Kohl, Lin Jiu and Victor H Moll)Balanced Modular Parameterizations (Tim Huber, Danny Lara and Esteban Melendez)Some Smallest Parts Functions from Variations of Bailey's Lemma (Chris Jennings-Shaffer)Dual Addition Formulas Associated with Dual Product Formulas (Tom H Koornwinder)Holonomic Tools for Basic Hypergeometric Functions (Christoph Koutschan and Peter Paule)A Direct Evaluation of an Integral of Ismail and Valent (Alexey Kuznetsov)Algebraic Generating Functions for Gegenbauer Polynomials (Robert S Maier)q-Analogues of Two Product Formulas of Hypergeometric Functions by Bailey (Michael J Schlosser)Summation Formulae for Noncommutative Hypergeometric Series (Michael J Schlosser)Asymptotics of Generalized Hypergeometric Functions (Y Lin and R Wong)Mock Theta-Functions of the Third Order of Ramanujan in Terms of Appell–Lerch Series (Changgui Zhang)On Certain Positive Semidefinite Matrices of Special Functions (Ruiming Zhang) Readership: Graduate students and researchers interested in orthogonal polynomials and

Gröbner Bases and Convex Polytopes

DOWNLOAD NOW »

Author: Bernd Sturmfels

Publisher: American Mathematical Soc.

ISBN: 0821804871

Category: Mathematics

Page: 162

View: 7239

This book is about the interplay of computational commutative algebra and the theory of convex polytopes. It centers around a special class of ideals in a polynomial ring: the class of toric ideals. They are characterized as those prime ideals that are generated by monomial differences or as the defining ideals of toric varieties (not necessarily normal). The interdisciplinary nature of the study of Grobner bases is reflected by the specific applications appearing in this book. These applications lie in the domains of integer programming and computational statistics. The mathematical tools presented in the volume are drawn from commutative algebra, combinatorics, and polyhedral geometry.

Invitation to Fixed-Parameter Algorithms

DOWNLOAD NOW »

Author: Rolf Niedermeier

Publisher: OUP Oxford

ISBN: 9780198566076

Category: Mathematics

Page: 316

View: 8457

An application-oriented introduction to the highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. Aimed at graduate and research mathematicians, algorithm designers, and computer scientists, it provides a fresh view on this highly innovative field of algorithmic research.

Lectures in Geometric Combinatorics

DOWNLOAD NOW »

Author: Rekha R. Thomas

Publisher: American Mathematical Soc.

ISBN: 9780821841402

Category: Mathematics

Page: 143

View: 9541

This book presents a course in the geometry of convex polytopes in arbitrary dimension, suitable for an advanced undergraduate or beginning graduate student. The book starts with the basics of polytope theory. Schlegel and Gale diagrams are introduced as geometric tools to visualize polytopes in high dimension and to unearth bizarre phenomena in polytopes. The heart of the book is a treatment of the secondary polytope of a point configuration and its connections to the state polytope of the toric ideal defined by the configuration. These polytopes are relatively recent constructs with numerous connections to discrete geometry, classical algebraic geometry, symplectic geometry, and combinatorics.The connections rely on Grobner bases of toric ideals and other methods from commutative algebra. The book is self-contained and does not require any background beyond basic linear algebra. With numerous figures and exercises, it can be used as a textbook for courses on geometric, combinatorial, and computational aspects of the theory of polytopes.

Surveys in Combinatorics, 1991

DOWNLOAD NOW »

Author: A. D. Keedwell

Publisher: Cambridge University Press

ISBN: 9780521407663

Category: Mathematics

Page: 300

View: 6022

This volume contains the invited papers presented at the British Combinatorial Conference, held at the University of Surrey in July 1991.

Combinatorial Commutative Algebra

DOWNLOAD NOW »

Author: Ezra Miller,Bernd Sturmfels

Publisher: Springer Science & Business Media

ISBN: 0387271031

Category: Mathematics

Page: 420

View: 4054

Recent developments are covered Contains over 100 figures and 250 exercises Includes complete proofs

Recent Trends in Combinatorics

DOWNLOAD NOW »

Author: Andrew Beveridge,Jerrold R. Griggs,Leslie Hogben,Gregg Musiker,Prasad Tetali

Publisher: Springer

ISBN: 3319242989

Category: Mathematics

Page: 778

View: 463

This volume presents some of the research topics discussed at the 2014-2015 Annual Thematic Program Discrete Structures: Analysis and Applications at the Institute for Mathematics and its Applications during Fall 2014, when combinatorics was the focus. Leading experts have written surveys of research problems, making state of the art results more conveniently and widely available. The three-part structure of the volume reflects the three workshops held during Fall 2014. In the first part, topics on extremal and probabilistic combinatorics are presented; part two focuses on additive and analytic combinatorics; and part three presents topics in geometric and enumerative combinatorics. This book will be of use to those who research combinatorics directly or apply combinatorial methods to other fields.

Thirty-three Miniatures

Mathematical and Algorithmic Applications of Linear Algebra

DOWNLOAD NOW »

Author: Jiří Matoušek

Publisher: American Mathematical Soc.

ISBN: 0821849778

Category: Mathematics

Page: 182

View: 8807

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)

Two-Dimensional Homotopy and Combinatorial Group Theory

DOWNLOAD NOW »

Author: Cynthia Hog-Angeloni,Wolfgang Metzler,Allan J. Sieradski

Publisher: Cambridge University Press

ISBN: 9780521447003

Category: Mathematics

Page: 412

View: 2883

Basic work on two-dimensional homotopy theory dates back to K. Reidemeister and J. H. C. Whitehead. Much work in this area has been done since then, and this book considers the current state of knowledge in all the aspects of the subject. The editors start with introductory chapters on low-dimensional topology, covering both the geometric and algebraic sides of the subject, the latter including crossed modules, Reidemeister-Peiffer identities, and a concrete and modern discussion of Whitehead's algebraic classification of 2-dimensional homotopy types. Further chapters have been skilfully selected and woven together to form a coherent picture. The latest algebraic results and their applications to 3- and 4-dimensional manifolds are dealt with. The geometric nature of the subject is illustrated to the full by over 100 diagrams. Final chapters summarize and contribute to the present status of the conjectures of Zeeman, Whitehead, and Andrews-Curtis. No other book covers all these topics. Some of the material here has been used in courses, making this book valuable for anyone with an interest in two-dimensional homotopy theory, from graduate students to research workers.

Graphs for Pattern Recognition

Infeasible Systems of Linear Inequalities

DOWNLOAD NOW »

Author: Damir Gainanov

Publisher: Walter de Gruyter GmbH & Co KG

ISBN: 3110481065

Category: Mathematics

Page: 158

View: 2508

Data mining and pattern recognition are areas based on the mathematical constructions discussed in this monograph. By using combinatorial and graph theoretical techniques, it is shown how to tackle infeasible systems of linear inequalities. These are, in turn, building blocks of geometric decision rules for pattern recognition.

Combinatorial Methods in Density Estimation

DOWNLOAD NOW »

Author: Luc Devroye,Gabor Lugosi

Publisher: Springer Science & Business Media

ISBN: 9780387951171

Category: Mathematics

Page: 208

View: 1241

Density estimation has evolved enormously since the days of bar plots and histograms, but researchers and users are still struggling with the problem of the selection of the bin widths. This text explores a new paradigm for the data-based or automatic selection of the free parameters of density estimates in general so that the expected error is within a given constant multiple of the best possible error. The paradigm can be used in nearly all density estimates and for most model selection problems, both parametric and nonparametric. It is the first book on this topic. The text is intended for first-year graduate students in statistics and learning theory, and offers a host of opportunities for further research and thesis topics. Each chapter corresponds roughly to one lecture, and is supplemented with many classroom exercises. A one year course in probability theory at the level of Feller's Volume 1 should be more than adequate preparation. Gabor Lugosi is Professor at Universitat Pompeu Fabra in Barcelona, and Luc Debroye is Professor at McGill University in Montreal. In 1996, the authors, together with Lászlo Györfi, published the successful text, A Probabilistic Theory of Pattern Recognition with Springer-Verlag. Both authors have made many contributions in the area of nonparametric estimation.

Solving Systems of Polynomial Equations

DOWNLOAD NOW »

Author: Bernd Sturmfels

Publisher: American Mathematical Soc.

ISBN: 0821832514

Category: Mathematics

Page: 152

View: 3048

A classic problem in mathematics is solving systems of polynomial equations in several unknowns. Today, polynomial models are ubiquitous and widely used across the sciences. They arise in robotics, coding theory, optimization, mathematical biology, computer vision, game theory, statistics, and numerous other areas. This book furnishes a bridge across mathematical disciplines and exposes many facets of systems of polynomial equations. It covers a wide spectrum of mathematical techniques and algorithms, both symbolic and numerical.The set of solutions to a system of polynomial equations is an algebraic variety - the basic object of algebraic geometry. The algorithmic study of algebraic varieties is the central theme of computational algebraic geometry. Exciting recent developments in computer software for geometric calculations have revolutionized the field. Formerly inaccessible problems are now tractable, providing fertile ground for experimentation and conjecture. The first half of the book gives a snapshot of the state of the art of the topic. Familiar themes are covered in the first five chapters, including polynomials in one variable, Grobner bases of zero-dimensional ideals, Newton polytopes and Bernstein's Theorem, multidimensional resultants, and primary decomposition.The second half of the book explores polynomial equations from a variety of novel and unexpected angles. It introduces interdisciplinary connections, discusses highlights of current research, and outlines possible future algorithms. Topics include computation of Nash equilibria in game theory, semidefinite programming and the real Nullstellensatz, the algebraic geometry of statistical models, the piecewise-linear geometry of valuations and amoebas, and the Ehrenpreis-Palamodov theorem on linear partial differential equations with constant coefficients.Throughout the text, there are many hands-on examples and exercises, including short but complete sessions in MapleR, MATLABR, Macaulay 2, Singular, PHCpack, CoCoA, and SOSTools software. These examples will be particularly useful for readers with no background in algebraic geometry or commutative algebra. Within minutes, readers can learn how to type in polynomial equations and actually see some meaningful results on their computer screens. Prerequisites include basic abstract and computational algebra. The book is designed as a text for a graduate course in computational algebra.

Combinatorial Optimization

Algorithms and Complexity

DOWNLOAD NOW »

Author: Christos H. Papadimitriou,Kenneth Steiglitz

Publisher: Courier Corporation

ISBN: 0486320138

Category: Mathematics

Page: 528

View: 3812

This graduate-level text considers the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; local search heuristics for NP-complete problems, more. 1982 edition.