The Strange Logic of Random Graphs

by Spencer, Joel H.

• ISBN13: 9783540416548
• ISBN10: 3540416544
• Format: Hardcover
• Copyright: 2001-08-01
• Publisher: Springer Verlag

Summary

The study of random graphs was begun by Paul Erdos and Alfred Renyi in the 1960s and now has a comprehensive literature. A compelling element has been the threshold function, a short range in which events rapidly move from almost certainly false to almost certainly true. This book now joins the study of random graphs (and other random discrete objects) with mathematical logic. The possible threshold phenomena are studied for all statements expressible in a given language. Often there is a zero-one law, that every statement holds with probability near zero or near one. The methodologies involve probability, discrete structures and logic, with an emphasis on discrete structures.The book will be of interest to graduate students and researchers in discrete mathematics.

Table of Contents

Part I. Beginnings
Two Starting Examples	3	(10)
A Blend of Probability, Logic and Combinatorics	3	(5)
A Random Unary Predicate	8	(3)
Some Comments on References	11	(2)
Preliminaries	13	(10)
What is the Random Graph G(n,p)?	13	(2)
The Erdos-Renyi Evolution	14	(1)
The Appearance of Small Subgraphs	15	(1)
What is a First Order Theory?	15	(2)
Extension Statements and Rooted Graphs	17	(1)
What is a Zero-One Law?	18	(2)
Almost Sure Theories and Complete Theories	20	(1)
Countable Models	20	(3)
The Ehrenfeucht Game	23	(26)
The Rules of the Game	23	(4)
Equivalence Classes and Ehrenfeucht Value	27	(4)
Connection to First Order Sentences	31	(2)
Inside-Outside Strategies	33	(4)
The Bridge to Zero-One Laws	37	(2)
Other Structures	39	(10)
General First Order Structures	39	(1)
The Simple Case of Total Order	40	(2)
k-Similar Neighborhoods	42	(7)
Part II. Random Graphs
Very Sparse Graphs	49	(20)
The Void	50	(1)
On the k-th Day	50	(1)
On Day w	51	(5)
An Excursion into Rooted Trees	51	(4)
Two Consequences	55	(1)
Past the Double Jump	56	(1)
Beyond Connectivity	57	(1)
Limiting Probabilities	58	(4)
A General Result on Limiting Probabilities	58	(1)
In the Beginning	59	(1)
On the k-th Day	60	(1)
At the Threshold of Connectivity	61	(1)
The Double Jump in the First Order World	62	(7)
Poisson Childbearing	63	(2)
Almost completing the Almost Sure Theory	65	(4)
The Combinatories of Rooted Graphs	69	(10)
Sparse, Dense, Rigid, Safe	69	(4)
The t-Closure	73	(1)
The Finite Closure Theorem	74	(5)
The Janson Inequality	79	(8)
Extension Statements	80	(2)
Counting Extensions	82	(3)
Generic Extension	85	(2)
The Main Theorem	87	(6)
The Look-Ahead Strategy	87	(3)
The Final Move	88	(1)
The Core Argument (Middle Moves)	88	(1)
The First Move	89	(1)
The Original Argument	90	(3)
Countable Models	93	(10)
An Axiomatization for Tα	93	(4)
The Schema	93	(1)
Completeness Proof	93	(2)
The Truth Game	95	(2)
Countable Models	97	(5)
Construction	97	(2)
Uniqueness of the Model	99	(1)
Non Uniqueness of the Model	100	(2)
A Continuum of Complete Theories	102	(1)
Near Rational Powers of n	103	(18)
Infinitely Many Ups and Downs	103	(5)
In the Second Order World	103	(2)
Replacing Second Order by First Order	105	(2)
Are First Order Properties Natural?	107	(1)
Existence of Finite Models	108	(1)
NonSeparability and NonConvergence	109	(6)
Representing All Finite Graphs	110	(1)
NonSeparability	111	(1)
Arithmetization	112	(1)
NonConvergence	113	(2)
The Last Threshold	115	(6)
Just Past n-α: The Theory Tα-	115	(2)
Just Past n-α: A Zero-One Law	117	(4)
Part III. Extras
A Dynamic View	121	(10)
More Zero-One Laws	121	(1)
Near Irrational Powers	121	(1)
Dense Random Graphs	122	(1)
The Limit Function	122	(9)
Definition	122	(1)
Look-Ahead Functions	123	(1)
Well Ordered Discontinuities	124	(1)
Underapproximation sequences	125	(2)
Determination in PH	127	(4)
Strings	131	(14)
Models and Language	131	(1)
Ehrenfeucht Redux	132	(2)
The Rules	132	(1)
The Semigroup	133	(1)
Long Strings	133	(1)
Persistent and Transient	134	(2)
Persistent Strings	136	(1)
Random Strings	137	(1)
Circular Strings	138	(2)
Sparse Unary Predicate	140	(5)
Stronger Logics	145	(8)
Ordered Graphs	145	(4)
Arithmetization	145	(2)
Dance Marathon	147	(1)
Slow Oscillation	148	(1)
Existential Monadic	149	(4)
Three Final Examples	153	(12)
Random Functions	153	(2)
Distance Random G(n,p)	155	(5)
Without Order	155	(2)
With Order	157	(3)
Random Lifts	160	(5)
Bibliography	165	(2)
Index	167