Index Ackermann function, 175 adversary strategy, 146 algorithm, 80, 137 approximation via trapezoids, 50 arithmetic progression, 175 asymptotic calculus, 128 asymptotic geometry, 125 asymptotic to g(n), 28 automorphism group of the k-cycle, 89 bell shaped curve, 6, 10, 37, 40 big oh, 28 bijection between Pr¨ ufer sequences and rooted forests, 88 and rooted trees, 82 and spanning trees, 79 binary tree, 171 binomial coefficient, 57, 64, 67, 117, 161 binomial distribution, 23, 64, 68, 108, 109, 111 binomial tail, 68, 151, 155 Bonferroni inequalities, 161, 163 Borel–Cantelli lemma, 152, 153, 158, 159 Cayley’s formula, 169 rooted forests, 83 rooted trees, 73 Central Limit Theorem, 69, 106, 107, 109, 151, 154, 155 Chebyshev’s inequality, 68, 69 Chernoff bound, 69, 104, 105, 107, 110, 151, 153, 156, 158 child of a node, 72 coloring, 93 complete graph, 93 conditional probability, 25 convergent sum, 3 convex hull, 129 countable sequence of events, 152 Coupon Collector, 165, 167 cycle of the permutation, 55 dependency graph, 95, 96 diagonalization, 175 edge effects, 127 entropy function, 64 Erd˝ os–R´ enyi random graph, 167 Erd˝ os Magic, 94, 99, 100, 127 Erd˝ os theorem, 98 Euler’s constant, 53, 165 expectation, 104 expected number of tree components, 63 expected number of trees of size k in the random graph G(n, p), 62 181
Previous Page Next Page