| We discuss three problems. Although the problems themselves are distinct, two basic themes underly each of them. First, each problem is either directly, or can be viewed as a random graph problem. Second, all the problems can be solved by using elementary techniques from the probabilistic method. We first discuss the Leader Election problem. In the leader election problem, there are n processors, betan of which are bad (or corrupt), and (1 - beta)n of which are good, for some fixed beta. For beta < 1/3, we present an algorithm which elects a leader from the set of all processors such that, with constant probability, this leader is good, and a 1 - o(1) fraction of the good processors know the election result. Further the algorithm only requires each good processor to send and process a number of bits which is polylogarithmic in n.; Next we discuss the chromatic number of a random scaled sector graph. In the random scaled sector graph model, vertices are placed uniformly at random into the [0, 1]2 unit square. Each vertex i is assigned a uniformly at random sector Si, of central angle alphai, in a circle of radius ri (with vertex i as the origin). An arc is present from vertex i to any vertex j, if j falls in Si. We study the value of the chromatic number chi(Gn), for random scaled sector graphs with n vertices, where each vertex spans a sector of alpha degrees with radius rn = lnn n . We prove that for values alpha < pi, as n → infinity w.h.p., chi(Gn) is theta lnn lnlnn . For alpha > pi w.h.p. (with high probability), chi( Gn) is theta(ln n).; Finally, we discuss the probability a sparse random graph or hypergraph is connected. While it is exponentially unlikely that a sparse random graph or hypergraph is connected, with probability 1 - o(1) such a graph has a "giant component" that, given its numbers of edges and vertices, is a uniformly distributed connected graph. This simple observation allows us to estimate the number of connected graphs, and more generally the number of connected d-uniform hypergraphs, on n vertices with ((d - 1)-1 + O(1))n ≤ m = o(n ln n) edges. |
