Jaroslav Nesetril - Böcker

This is a book about graph homomorphisms. Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. The subject gives a useful perspective in areas such as graph reconstruction, products, fractional and circular colourings, and has applications in complexity theory, artificial intelligence, telecommunication, and, most recently, statistical physics.Based on the authors' lecture notes for graduate courses, this book can be used as a textbook for a second course in graph theory at 4th year or master's level and has been used for courses at Simon Fraser University (Vancouver), Charles University (Prague), ETH (Zurich), and UFRJ (Rio de Janeiro). The exercises vary in difficulty. The first few are usually intended to give the reader an opportunity to practice the concepts introduced in the chapter; the later ones explore related concepts, or even introduce new ones. For the harder exercises hints and references are provided.The authors are well known for their research in this area and the book will be invaluable to graduate students and researchers alike.

This second edition of Invitation to Discrete Mathematics is a clear and self-contained introduction to discrete mathematics. Aimed mainly at undergraduate and early graduate students of mathematics and computer science, it is written with the goal of stimulating interest in mathematics and an active, problem-solving approach to the presented material. The reader is led to an understanding of the basic principles and methods of actually doing mathematics (and having fun at that). By focussing on a more selective range of topics than many discrete mathematics textbooks, allowing greater depth of treatment using a number of different approaches, the book reflects the conviction of the authors, active and internationally renowned mathematicians, that the most important gain from studying mathematics is the cultivation of clear and logical thinking and habits useful for attacking new problems. More than 400 enclosed exercises with a wide range of difficulty, many of them accompanied by hints for solution, support this approach to teaching. The readers will appreciate the lively and informal style of the text accompanied by more than 200 drawings and diagrams. Specialists in various parts of science with a basic mathematical education wishing to apply discrete mathematics in their field can use the book as a useful source, and even experts in combinatorics may occasionally learn from pointers to research literature or from presentations of recent results. Invitation to Discrete Mathematics should make delightful reading both for beginners and for mathematical professionals.The main topics include: elementary counting problems, asymptotic estimates, partially ordered sets, basic graph theory and graph algorithms, finite projective planes, elementary probability and the probabilistic method, generating functions, Ramsey's theorem, and combinatorial applications of linear algebra. General mathematical notions going beyond the high-school level are thoroughly explained in the introductory chapter. An appendix summarizes the undergraduate algebra needed in some of the more advanced sections of the book.

Here is a comprehensive overview of the mathematical life of Paul Erdos (1913-1996), a versatile and prolific mathematician. This second volume covers graph theory and combinatorics, extremal and Ramsey theory, and Erdos's research on set theory.

Here is a comprehensive overview of the mathematical life of the legendary Paul Erdos (1913-1996), one of the most versatile and prolific mathematicians of our time. This first volume features personal memories of Paul Erdos by a number of his colleagues.

This is the most comprehensive survey of the mathematical life of the legendary Paul Erdős (1913-1996), one of the most versatile and prolific mathematicians of our time. For the first time, all the main areas of Erdős' research are covered in a single project. Because of overwhelming response from the mathematical community, the project now occupies over 1000 pages, arranged into two volumes. These volumes contain both high level research articles as well as key articles that survey some of the cornerstones of Erdős' work, each written by a leading world specialist in the field. A special chapter "Early Days", rare photographs, and art related to Erdős complement this striking collection. A unique contribution is the bibliography on Erdős' publications: the most comprehensive ever published. This new edition, dedicated to the 100th anniversary of Paul Erdős' birth, contains updates on many of the articles from the two volumes of the first edition, several new articles from prominent mathematicians, a new introduction, and more biographical information about Paul Erdős with an updated list of publications.The second volume contains chapters on graph theory and combinatorics, extremal and Ramsey theory, and a section on infinity that covers Erdős' research on set theory. All of these chapters are essentially updated, particularly the extremal theory chapter that contains a survey of flag algebras, a new technique for solving extremal problems.

This is the most comprehensive survey of the mathematical life of the legendary Paul Erdős (1913-1996), one of the most versatile and prolific mathematicians of our time. For the first time, all the main areas of Erdős' research are covered in a single project. Because of overwhelming response from the mathematical community, the project now occupies over 1000 pages, arranged into two volumes. These volumes contain both high level research articles as well as key articles that survey some of the cornerstones of Erdős' work, each written by a leading world specialist in the field. A special chapter "Early Days", rare photographs, and art related to Erdős complement this striking collection. A unique contribution is the bibliography on Erdős' publications: the most comprehensive ever published. This new edition, dedicated to the 100th anniversary of Paul Erdős' birth, contains updates on many of the articles from the two volumes of the first edition, several new articles from prominent mathematicians, a new introduction, more biographical information about Paul Erdős, and an updated list of publications.The first volume contains the unique chapter "Early Days", which features personal memories of Paul Erdős by a number of his colleagues. The other three chapters cover number theory, random methods, and geometry. All of these chapters are essentially updated, most notably the geometry chapter that covers the recent solution of the problem on the number of distinct distances in finite planar sets, which was the most popular of Erdős' favorite geometry problems.

This book collects the extended abstracts of the accepted contributions to EuroComb21. A similar book is published at every edition of EuroComb (every two years since 2001) collecting the most recent advances in combinatorics, graph theory, and related areas.

This carefully edited volume contains selected refereed papers based on lectures presented by many distinguished speakers at the "Integers Conference 2005", an international conference in combinatorial number theory. The conference was held in celebration of the 70th birthday of Ronald Graham, a leader in several fields of mathematics.

This volume contains selected refereed papers based on lectures presented at the ‘Integers Conference 2007’, an international conference in combinatorial number theory that was held in Carrollton, Georgia in October 2007.The proceedings include contributions from many distinguished speakers, including George Andrews, Neil Hindman, Florian Luca, Carl Pomerance, Ken Ono and Igor E. Shparlinski. Among the topics considered in these papers are additive number theory, multiplicative number theory, sequences, elementary number theory, theory of partitions, and Ramsey theory.

Over a career that spanned 60 years, Ronald L. Graham (known to all as Ron) made significant contributions to the fields of discrete mathematics, number theory, Ramsey theory, computational geometry, juggling and magical mathematics, and many more. Ron also was a mentor to generations of mathematicians, he gave countless talks and helped bring mathematics to a wider audience, and he held signifi cant leadership roles in the mathematical community. This volume is dedicated to the life and memory of Ron Graham, and includes 20-articles by leading scientists across a broad range of subjects that refl ect some of the many areas in which Ron worked.

Elwyn Berlekamp, John Conway, and Richard Guy wrote ‘Winning Ways for your Mathematical Plays’ and turned a recreational mathematics topic into a full mathematical fi eld. They combined set theory, combinatorics, codes, algorithms, and a smattering of other fi elds, leavened with a liberal dose of humor and wit. Their legacy is a lively fi eld of study that still produces many surprises. Despite being experts in other areas of mathematics, in the 50 years since its publication, they also mentored, talked, and played games, giving their time, expertise, and guidance to several generations of mathematicians. This volume is dedicated to Elwyn Berlekamp, John Conway, and Richard Guy. It includes 20 contributions from colleagues that refl ect on their work in combinatorial game theory.

This volume consists of twenty articles stemming from presentations given at the 2023 Integers Conference. They represent a variety of active areas of research in combinatorial number theory, including additive number theory, multiplicative number theory, elementary number theory, the theory of partitions, Ramsey theory, sequences, algebraic combinatorics, enumerative combinatorics, and Diophantine equations.

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.

Dieses Buch ist [...] eine hervorragende Einführung in Kombinatorik und Graphentheorie für Studienanfänger in Mathematik (und Informatik). [...] das Buch ist wegen des ungewöhnlichen und sehr attraktiven Stiles der Darstellung bemerkenswert. [...] Die Sprachform ist vorwiegend die eines Gespräches mit dem Leser, der dadurch in die Gedankengänge und Überlegungen des Autors hineingeführt und hineingezogen wird. Zum Beispiel werden bei einem Beweis zuerst die Grundidee oder die Zielsetzung genannt und erläutert, und auch im weiteren Verlauf wird immer wieder durch alternative Formulierungen das Verständnis vertieft oder ermöglicht. Dadurch werden im Leser adäquate Vorstellungen zu den formalen Schritten erzeugt, die dann wieder eigenständiges und kreatives Denken ermöglichen. Die Lektüre ist also anregend und sehr motivierend! Die Aufgaben sind dagegen ziemlich anspruchsvoll, werden aber ausführlich erläutert. [..]W. Dörfler (Klagenfurt), Internationale Mathematische Nachrichten, 2003, Vol 57, Issue 192, S. 46-47[Die Bereiche Kombinatorik und Graphentehorie] werden in all ihren Ausprägungen, reizvollen Einzelergebnissen und vielfältigen Anwendungen [...] ausführlich dargestellt. In gemächlicher Breite behandeln die Autoren ihre Themen, beweisen Kernsätze mehrfach auf unterschiedliche Weise und motivieren wichtige Theorien sehr anregend. Ihr selbstgestelltes Ziel, Freude und Genuss an mathematischem Denken zu vermitteln, dürften sie erreicht haben. Eine Vielzahl inhaltlich sehr reizvoller Aufgaben bereichern den Text; für die schwierigeren findet man in einem Schlusskapitel Lösungshilfen. In weiten Teilen reichen Schulkenntnisse für ein Verständnis aus. Der sehr gehaltvolle Band kann neben Studierenden daher auch bereits Schülern empfohlen werden.Wolfgang Grölz, ekz-Informationsdienst, ID 44/2002 - BA 12/2002

This book constitutes the refereed proceedings of the 7th Annual European Symposium on Algorithms, ESA '99, held in Prague, Czech Republic, in July 1999.The 44 revised papers presented were carefully reviewed and selected from a total of 122 submissions. All areas of algorithmic research are covered, in particular approximation algorithms, combinatorial optimization, computational mathematics, computational science, databases and information retrieval, graph computations, network algorithms, online algorithms, pattern matching, data compression, parallel algorithms, distributed algorithms, and sequential algorithms.

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants.This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms. Jaroslav Nešetřil is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris.This book is related to the material presented by the first author at ICM 2010.

This volume contains the post-proceedings of the 8th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2012, held in Znojmo, Czech Republic, in October, 2012.The 13 thoroughly revised papers were carefully selected out of 31 submissions and are presented together with 6 invited papers. The topics covered by the papers include: computer-aided analysis and verification, applications of game theory in computer science, networks and security, modern trends of graph theory in computer science, electronic systems design and testing, and quantum information processing.

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants.This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms. Jaroslav Nešetřil is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris.This book is related to the material presented by the first author at ICM 2010.

One of the important areas of contemporary combinatorics is Ramsey theory. Ramsey theory is basically the study of structure preserved under partitions. The general philosophy is reflected by its interdisciplinary character. The ideas of Ramsey theory are shared by logicians, set theorists and combinatorists, and have been successfully applied in other branches of mathematics. The whole subject is quickly developing and has some new and unexpected applications in areas as remote as functional analysis and theoretical computer science. This book is a homogeneous collection of research and survey articles by leading specialists. It surveys recent activity in this diverse subject and brings the reader up to the boundary of present knowledge. It covers virtually all main approaches to the subject and suggests various problems for individual research.

In the tradition of EuroComb'01 (Barcelona), Eurocomb'03 (Prague), EuroComb'05 (Berlin), Eurocomb'07 (Seville), Eurocomb'09 (Bordeaux), and Eurocomb'11 (Budapest), this volume covers recent advances in combinatorics and graph theory including applications in other areas of mathematics, computer science and engineering. Topics include, but are not limited to: Algebraic combinatorics, combinatorial geometry, combinatorial number theory, combinatorial optimization, designs and configurations, enumerative combinatorics, extremal combinatorics, ordered sets, random methods, topological combinatorics.