随机图

　　The period since the publication of the first edition of this book has seen the theory of random graphs go from strength to strength. Indeed， its appearance happened to coincide with a watershed in the subject; the emergence in the subsequent few years of singnificant new ideas and tools， perhaps most noteably concentration methods， has had a major impact. It could be argued that the subject is now qualitatively different， insofar as results which would previously have been inaccessible are now regarded as routine. Several long standing issues have been resolved， including the value of the chromatic number of a random graph $G-{n，p}$， the existence of Hamilton cycles in random cubic graphs， and precise bounds on certain Ramsey numbers. It remains the case， though， that most of the material in the first edition of the book is vital for gaining an insight into the theory of random graphs.

暂缺《随机图》作者简介

Preface
Notation
1ProbabilityTheoreticPreliminaries
1.1NotationandBasicFacts
1.2SomeBasicDistributions
1.3NormalApproximation
1.4Inequalities
1.5ConvergenceinDistribution
2ModelsofRandomGraphs
2.1TheBasicModels
2.2PropertiesofAlmostAllGraphs
2.3LargeSubsetsofVertices
2.4RandomRegularGraphs
3TheDegreeSequence
3.1TheDistributionofanElementoftheDegreeSequence
3.2AlmostDeterminedDegrees
3.3TheShapeoftheDegreeSequence
3.4JumpsandRepeatedValues
3.5FastAlgorithmsfortheGraphIsomorphismProblem
4SmallSubgraphs
4.1StrictlyBalancedGraphs
4.2ArbitrarySubgraphs
4.3PoissonApproximation
5TheEvolutionofRandomGraphs--SparseComponents
5.1TreesofGivenSizesAsComponents
5.2TheNumberofVerticesonTreeComponents
5.3TheLargestTreeComponents
5.4CompbnentsContainingCycles
6TheEvolutionofRandomGraphs--theGiantComponent
6.1AGapintheSequenceofComponents
6.2TheEmergenceoftheGiantComponent
6.3SmallComponentsafterTimen/2
6.4FurtherResults
6.5TwoApplications
7ConnectivityandMatchings
7.1TheConnectednessofRandomGraphs
7.2Thek-ConnectednessofRandomGraphs
7.3MatchingsinBipartiteGraphs
7.4MatchingsinRandomGraphs
7.5ReliableNetworks
7.6RandomRegularGraphs
8LongPathsandCycles
8.1LongPathsinGe/n--FirstApproach
8.2HamiltonCycles--FirstApproach
8.3HamiltonCycles--SecondApproach
8.4LongPathsinGc/n--SecondApproach
8.5HamiltonCyclesinRegularGraphs--FirstApproach
8.6HamiltonCyclesinRegularGraphs--SecondApproach
9TheAutomorphismGroup
9.1TheNumberofUnlabelledGraphs
9.2TheAsymptoticNumberofUnlabelledRegularGraphs
9.3DistinguishingVerticesbyTheirDistanceSequences
9.4AsymmetricGraphs
9.5GraphswithaGivenAutomorphismGroup
10TheDiameter
10.1LargeGraphsofSmallDiameter
10.2TheDiameterofGp
10.3TheDiameterofRandomRegularGraphs
10.4GraphProcesses
10.5RelatedResults
10.6SmallWorlds
11Cliques,IndependentSetsandColouring
11.1CliquesinGp
11.2PoissonApproximation
11.3GreedyColouringofRandomGraphs
11.4TheChromaticNumberofRandomGraphs
11.5SparseGraphs
12RamseyTheory
12.1BoundsonR(s)
12.2Off-DiagonalRamseyNumbers
12.3Triangle-FreeGraphs
12.4DenseSubgraphs
12.5TheSize-RamseyNumberofaPath
13ExplicitConstructions
13.1CharacterSums
13.2ThePaleyGraphPq
13.3DenseGraphs
13.4SparseGraphs
13.5PseudorandomGraphs
14Sequences,MatricesandPermutations
14.1RandomSubgraphsoftheCube
14.2RandomMatrices
14.3BalancingFamiliesofSets
14.4RandomElementsofFiniteGroups
14.5RandomMappings
15SortingAlgorithms
15.1FindingMostComparisonsinOneRound
15.2SortinginTwoRounds
15.3SortingwithWidthn/2
15.4BinPacking
16RandomGraphsofSmallOrder
16.1Connectivity
16.2IndependentSets
16.3Colouring
16.4RegularGraphs
References
Index