**University Lecture Series**

Volume: 49;
2009;
250 pp;
Softcover

MSC: Primary 60; 05; 91;
Secondary 11

Print ISBN: 978-0-8218-4756-5

Product Code: ULECT/49

List Price: $62.00

AMS Member Price: $49.60

MAA member Price: $55.80

**Electronic ISBN: 978-1-4704-1644-7
Product Code: ULECT/49.E**

List Price: $62.00

AMS Member Price: $49.60

MAA member Price: $55.80

#### You may also like

#### Supplemental Materials

# Inevitable Randomness in Discrete Mathematics

Share this page
*József Beck*

Mathematics has been called the science of order. The subject is
remarkably good for generalizing specific cases to create abstract
theories. However, mathematics has little to say when faced with
highly complex systems, where disorder reigns. This disorder can be
found in pure mathematical arenas, such as the distribution of primes,
the \(3n+1\) conjecture, and class field theory.

The purpose of this book is to provide examples—and rigorous
proofs—of the complexity law:

(1) discrete systems are either simple or they exhibit advanced
pseudorandomness;

(2) a priori probabilities often exist even when there is no
intrinsic symmetry.

Part of the difficulty in achieving this purpose is in trying to
clarify these vague statements. The examples turn out to be
fascinating instances of deep or mysterious results in number theory
and combinatorics.

This book considers randomness and complexity. The traditional
approach to complexity—computational complexity theory—is
to study very general complexity classes, such as P, NP and PSPACE.
What Beck does is very different: he studies interesting concrete
systems, which can give new insights into the mystery of complexity.

The book is divided into three parts. Part A is mostly an essay on
the big picture. Part B is partly new results and partly a survey of
real game theory. Part C contains new results about graph games,
supporting the main conjecture. To make it accessible to a wide
audience, the book is mostly self-contained.

#### Readership

Graduate students and research mathematicians interested in discrete mathematics, combinatorics, and number theory.

#### Reviews & Endorsements

[T]he book gives a particular reading to a large portion of modern mathematics. ...[and] offers an interesting unifying approach and, in doing so, gives the reader a broad review of a number of combinatorial problems. These are accompanied by a very good choice of bibliographic references.

-- Michele Zito, Mathematical Reviews

#### Table of Contents

# Table of Contents

## Inevitable Randomness in Discrete Mathematics

- Cover Cover11 free
- Title page iii5 free
- Contents v7 free
- Preface ix11 free
- Part I. Reading the shadows on the wall and formulating a vague conjecture 115 free
- Complex systems 317
- Collecting data: Apparent randomness of digit sequences 1327
- Collecting data: More randomness in number theory 2135
- Laplace and the principle of insufficient reason 3751
- Collecting proofs for the SLG conjecture 4963
- Part II. More evidence for the SLG conjecture: Exact solutions in real game theory 6781
- Ramsey theory and games 6983
- Pratice session (I): More on Ramsey games and strategies 89103
- Practice session (II): Connectivity games and more strategies 99113
- What kind of games? 111125
- Exact solutions of games: Understanding via the equiprobability postulate 123137
- Equiprobability postulate with constraints (endgame policy) 135149
- Constraints and threshold clustering 147161
- Threshold clustering and a few bold conjectures 155169
- Part III. New evidence: Games and graphs, the surplus, and the square root law 163177
- Yet another simplification: Sparse hypergraphs and the surplus 165179
- Is surplus the right concept? (I) 177191
- Is surplus the right concept? (II) 185199
- Working with a game-theoretic partition function 193207
- An attempt to save the variance 203217
- Proof of theorem 1: Combining the variance with an exponential sum 209223
- Proof of theoem 2: The upper bound 219233
- Conclusion (I): More on theorem 1 227241
- Conclusion (II): Beyond the SLG conjecture 237251
- Dictionary of phrases and concepts 245259
- References 247261
- Back Cover Back Cover1267