Atnaujinkite slapukų nuostatas

Discrete Mathematical Charms of Paul Erdos: A Simple Introduction [Minkštas viršelis]

(Concordia University, Montréal)
  • Formatas: Paperback / softback, 266 pages, aukštis x plotis x storis: 243x169x10 mm, weight: 540 g, Worked examples or Exercises
  • Išleidimo metai: 26-Aug-2021
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1108927408
  • ISBN-13: 9781108927406
Kitos knygos pagal šią temą:
Discrete Mathematical Charms of Paul Erdos: A Simple IntroductionDidesnis paveikslėlis
  • Formatas: Paperback / softback, 266 pages, aukštis x plotis x storis: 243x169x10 mm, weight: 540 g, Worked examples or Exercises
  • Išleidimo metai: 26-Aug-2021
  • Leidėjas: Cambridge University Press
  • ISBN-10: 1108927408
  • ISBN-13: 9781108927406
Kitos knygos pagal šią temą:
Pastovi nuoroda: https://www.kriso.lt/db/9781108927406.html
Raktažodžiai:
Paul Erds published more papers during his lifetime than any other mathematician, especially in discrete mathematics. He had a nose for beautiful, simply-stated problems with solutions that have far-reaching consequences across mathematics. This captivating book, written for students, provides an easy-to-understand introduction to discrete mathematics by presenting questions that intrigued Erds, along with his brilliant ways of working toward their answers. It includes young Erds's proof of Bertrand's postulate, the Erds-Szekeres Happy End Theorem, De Bruijn-Erds theorem, Erds-Rado delta-systems, Erds-Ko-Rado theorem, Erds-Stone theorem, the Erds-Rényi-Sós Friendship Theorem, Erds-Rényi random graphs, the Chvįtal-Erds theorem on Hamilton cycles, and other results of Erds, as well as results related to his work, such as Ramsey's theorem or Deza's theorem on weak delta-systems. Its appendix covers topics normally missing from introductory courses. Filled with personal anecdotes about Erds, this book offers a behind-the-scenes look at interactions with the legendary collaborator.

Recenzijos

'Vaek Chvįtal was born to write this one-of-a-kind book. Readers cannot help but be captivated by the evident love with which every page has been written. The human side of mathematics is intertwined beautifully with first-rate exposition of first-rate results.' Donald Knuth, Stanford University 'This book is a treasure trove from so many viewpoints. It is a wonderful introduction and an alluring invitation to discrete mathematics - now a central field of mathematics identified mostly with the hero of this book. With lucid, carefully planned chapters on different topics it demonstrates the unique way in which Paul Erds, one of the most prolific and influential mathematicians of the twentieth century, invented and approached problems. Sprinkled with historical and personal anecdotes and pictures, it opens a window to the unique personality of 'Uncle Paul'. And implicitly, it reveals the charming and candid way in which Vaek Chvįtal, an authority in the field and a lifelong friend and collaborator of Erds, likes to combine teaching and story-telling.' Avi Wigderson, IAS, Princeton 'Paul Erds is one of the founding fathers of modern combinatorics, whose ability to pose beautiful problems greatly determined the development of this field and influenced many other areas of mathematics. This book uses some basic questions, which intrigued Paul Erds, to give a nice introduction to many topics in discrete mathematics. It contains a collection of beautiful results, covering such diverse subjects as discrete geometry, Ramsey theory, graph colorings, extremal problems for graphs and set systems and some others. It presents many elegant proofs and exposes the reader to various powerful combinatorial techniques.' Benjamin Sudakov, ETH Zurich 'This is a brilliant book. It manages in one fell swoop to survey and develop a large part of combinatorial mathematics while at the same time chronicling the work of Paul Erds. His contributions to different areas of mathematics are seen here to be part of a coherent whole. Chvįtal's presentation is particularly appealing and accessible. The wonderful personal recollections add to the mathematical content to provide a portrait of Erds' mind recognizable to those who knew him.' Bruce Rothschild, University of California, Los Angeles 'Vaek Chvįtal's book is a gem. Paul Erds' favorite problems and best work are beautifully laid out. Readers unfamiliar with Erds' work cannot fail to appreciate its power and elegance, and those who have seen bits and pieces will have the pleasure of seeing it thoughtfully and lovingly presented by a master. It's hard to imagine now, but there was a time when combinatorics was thought to be a jumble of results without depth or coherence. 'Uncle' Paul understood its heart and soul, and nowhere is this more evident than in Chvįtal's wonderful compendium. This volume belongs on every math-lover's night-table!' Peter Winkler, Dartmouth College 'Beautiful mathematics is presented with great care and clarity in Vaek Chvįtal's book, complemented with well-written anecdotes and personal reminiscences about Paul Erds. This combination makes the book a very enjoyable reading and a lively tribute to the memory of one of the most prolific mathematicians of all time. Studying discrete mathematics from this book is likely to give a great experience to students and established researchers alike.' Gįbor Simonyi, Rényi Institute, Budapest ' Chvįtal (emer., Concordia Univ.) has created a gem in this work and deserves congratulation Highly recommended.' J. Johnson, Choice Magazine 'This wonderfully written book is undoubtedly a significant contribution to the growing body of literature on the various developments in discrete mathematics over the last several decades. Still, to reduce it to only its mathematical dimension would be an act of injustice not only towards the book but also towards its author. The book is a powerful homage to Paul Erdos as one of the leading mathematicians of the twentieth century as well as a person who, with his unprecedented level of academic generosity and overall human kindness, was one of the pillars of the discrete mathematics community during his lifetime.' Veselin Jungic, MathSciNet 'The book is demanding, but a pleasure to work through. I highly recommend it to everyone with a good background in calculus and elementary number theory.' Franz Lemmermeyer, zbMATH 'Chvįtal tells the story of many discrete mathematical ideas, centered around the work of Paul Erds Chvįtal does an exceptional job of putting the mathematical discoveries in their historical context and combining them with photos, personal anecdotes about his time spent with Erds, and letters between the two. This context, along with the topics chosen and the clear writing, make this book exceptional. The book can, of course, be used as a graduate-level textbook. But it is far more than that. [ It] is a phenomenal reference for discrete mathematicians and a 'simple introduction' to discrete mathematics for any mathematician with the desire to learn about the work and life of Paul Erds.' Ranjan Rohatgi, Notices of the American Mathematical Society

Daugiau informacijos

A captivating introduction to key results of discrete mathematics through the work of Paul Erds, blended with first-hand reminiscences.
Foreword xiii
Preface xvii
Acknowledgments xix
Introduction 1(2)
1 A Glorious Beginning: Bertrand's Postulate
3(15)
1.1 Binomial Coefficients
3(2)
1.2 A Lemma
5(1)
1.3 The Unique Factorization Theorem
6(1)
1.4 Legendre's Formula
6(1)
1.5 Erdos's Proof of Bertrand's Postulate
7(3)
1.5.1 The Plan
7(1)
1.5.2 A Formula for e(p, N)
8(1)
1.5.3 An Upper Bound on pe(P,N)
8(1)
1.5.4 Splitting the Left-Hand Side of (1.9)
8(1)
1.5.5 Putting the Pieces Together
9(1)
1.6 Proof of Bertrand's Original Conjecture
10(1)
1.7 Earlier Proofs of Bertrand's Postulate
11(2)
1.7.1 Chebyshev
11(1)
1.7.2 Landau
12(1)
1.7.3 Ramanujan
12(1)
1.8 Further Results and Problems Concerning Primes
13(5)
1.8.1 Landau's Problems
13(1)
1.8.2 Small Gaps between Consecutive Primes
13(1)
1.8.3 Large Gaps between Consecutive Primes
14(1)
1.8.4 Primes in Arithmetic Progressions
15(1)
1.8.5 On revient toujours a ses premieres amours
15(3)
2 Discrete Geometry And Spinoffs
18(18)
2.1 The Happy Ending Theorem
18(4)
2.2 The Sylvester--Gallai Theorem
22(2)
2.3 A De Bruijn--Erdos Theorem
24(3)
2.4 Other Proofs of the De Bruijn--Erdos Theorem
27(9)
2.4.1 Hanani
27(2)
2.4.2 Motzkin
29(1)
2.4.3 Ryser
30(1)
2.4.4 Basterfield, Kelly, Conway
31(5)
3 Ramsey's Theorem
36(15)
3.1 Ramsey's Theorem for Graphs
36(2)
3.2 Ramsey Numbers
38(5)
3.3 A More General Version of Ramsey's Theorem
43(1)
3.4 Applications to the Happy Ending Theorem
44(2)
3.5 Ramsey's Theorem in Its Full Generality
46(1)
3.6 A Self-Centered Supplement: Self-Complementary Graphs
47(4)
4 Delta-Systems
51(8)
4.1 A-Systems of Erdos and Rado
51(2)
4.2 Ramsey's Theorem and Weak A-Systems
53(2)
4.3 Deza's Theorem
55(4)
5 Extremal Set Theory
59(23)
5.1 Sperner's Theorem
59(4)
5.1.1 A Simple Proof of Sperner's Theorem
60(2)
5.1.2 The Bollobas Set Pairs Inequality
62(1)
5.2 The Erdos--Ko--Rado theorem
63(6)
5.2.1 A Simple Proof of the Erdos--Ko--Rado Theorem
65(1)
5.2.2 Extremal Families in the Erdos--Ko--Rado Theorem
66(3)
5.3 Turan Numbers
69(6)
5.3.1 A Lower Bound on T(n, k)
70(2)
5.3.2 Turan Numbers and Steiner Systems
72(2)
5.3.3 An Upper Bound on T(n, k)
74(1)
5.4 Turan Functions
75(2)
5.5 Chromatic Number of Hypergraphs
77(5)
6 Van Der Waerden's Theorem
82(15)
6.1 The Theorem
82(5)
6.1.1 Van der Waerden's proof of W(3, 2) ≥ 325
83(1)
6.1.2 Van der Waerden's proof of W(3, 3)≥ MN with M = 7(2 · 37 + 1) and N = M(2 · 3M + 1)
84(2)
6.1.3 Van der Waerden's proof of W(4,2) ≥ MN with M = 3/2W(3, 2) and N = 3/2W(3, 2W)
86(1)
6.2 A Proof
87(4)
6.2.1 A Warm-up Example
87(1)
6.2.2 An Overview of the Proof
88(1)
6.2.3 C(1, d) Holds for All d
89(1)
6.2.4 C(k, d) with All d Implies C(k + 1, 1)
90(1)
6.2.5 C(k, d) Implies C(k, d + 1)
90(1)
6.3 Van der Waerden Numbers
91(2)
6.3.1 Exact Values
91(1)
6.3.2 Upper Bounds
92(1)
6.3.3 Lower Bounds
92(1)
6.4 Szemeredi's Theorem
93(1)
6.5 Ramsey Theory
94(3)
7 Extremal Graph Theory
97(17)
7.1 Turan's Theorem
97(4)
7.1.1 Two Theorems
97(1)
7.1.2 A Greedy Heuristic
98(1)
7.1.3 Proof of Theorem 7.2
99(2)
7.1.4 Turan's Theorem and Turan Numbers
101(1)
7.2 The Erdos--Stone Theorem
101(4)
7.3 The Erdos--Stone--Simonovits Formula
105(1)
7.4 When F Is Bipartite
106(5)
7.4.1 An Erdos--Simonovits conjecture
106(1)
7.4.2 When F Is a Complete Bipartite Graph
107(2)
7.4.3 When Every Subgraph of F Has a Vertex of Degree at Most r
109(1)
7.4.4 When F Is a Cycle
110(1)
7.5 Prehistory
111(1)
7.6 Beyond Turan Functions
112(2)
8 The Friendship Theorem
114(11)
8.1 The Friendship Theorem
114(4)
8.2 Strongly Regular Graphs
118(7)
9 Chromatic Number
125(26)
9.1 The Chromatic Number
125(1)
9.2 The Unbearable Weakness of the Bound Χ ≤ ω
126(2)
9.3 The End of Hajos's Conjecture
128(4)
9.4 Graphs with a Large Chromatic Number and No Triangles
132(4)
9.4.1 Zykov
132(1)
9.4.2 Tutte
133(1)
9.4.3 Mycielski
133(1)
9.4.4 Erdos and Hajnal
134(1)
9.4.5 Lovasz
135(1)
9.5 Graphs with a Large Chromatic Number and No Short Cycles
136(6)
9.6 An Upper Bound on the Chromatic Number
142(3)
9.7 Small Subgraphs Do Not Determine Chromatic Number
145(6)
10 Thresholds Of Graph Properties
151(24)
10.1 Connectivity
152(10)
10.1.1 The Inclusion-Exclusion Principle and Bonferroni Inequalities
153(2)
10.1.2 Lemma on Isolated Vertices
155(2)
10.1.3 Lemma on a Single Nontrivial Component
157(5)
10.1.4 Proof of Theorem 10.1
162(1)
10.2 Subgraphs
162(5)
10.2.1 A Lemma
163(1)
10.2.2 Proof of Theorem 10.7
164(3)
10.3 Evolution of Random Graphs and the Double Jump
167(3)
10.4 Finite Probability Theory
170(5)
11 Hamilton Cycles
175(17)
11.1 A Theorem That Involves Degrees of Vertices
175(7)
11.1.1 An Algorithmic Proof of Theorem 11.4
179(2)
11.1.2 A Digression: Testing the Hypothesis of Theorem 11.2
181(1)
11.2 A Theorem That Involves Connectivity and Stability
182(5)
11.3 Hamilton Cycles in Random Graphs
187(5)
Appendix A A FEW TRICKS OF THE TRADE
192(23)
A.1 Inequalities
192(2)
A.1.1 Two workhorses
192(1)
A.1.2 Cauchy--Bunyakovsky--Schwarz Inequality
192(1)
A.1.3 Jensen's Inequality
193(1)
A.2 Factorials and Stirling's Formula
194(2)
A.3 Asymptotic Expressions for Binomial Coefficients
196(2)
A.4 The Binomial Distribution
198(3)
A.5 Tail of the Binomial Distribution
201(4)
A.6 Tail of the Hypergeometric Distribution
205(4)
A.7 Two Models of Random Graphs
209(6)
Appendix B DEFINITIONS, TERMINOLOGY, NOTATION
215(3)
B.1 Graphs
215(1)
B.2 Hypergraphs
216(1)
B.3 Asymptotic Notation
217(1)
B.4 Sundry Notation
217(1)
Appendix C MORE ON ERDOS
218(8)
C.1 Selected Articles
218(1)
C.2 Selected Books
219(1)
C.3 Films
220(1)
C.4 Websites
220(1)
C.5 An FBI File
220(2)
C.6 A Photo Album
222(4)
Bibliography 226(18)
Index 244
Vaek Chvįtal is Professor Emeritus of Concordia University, where he served as Canada Research Chair in Combinatorial Optimization (20042011) and Canada Research Chair in Discrete Mathematics from 2011 to his retirement in 2014. He is the author of Linear Programming (1983) and co-author of The Traveling Salesman Problem: A Computational Study (2007). In the 1970s, he wrote three joint papers with Paul Erds. He is a recipient of the CSGSS Award for Excellence in Teaching, Rutgers University (1992, 1993, 2001) and co-recipient of the Beale-Orchard-Hays Prize (2000), Frederick W. Lanchester Prize (2007), and John von Neumann Theory Prize (2015).