| We introduce and study online versions of two classical random structures. The first is a variation on the classical random graph model, the second is the satisfiability model.;We begin with the random graph. Let c be a constant and (e1, f1), ( e2, f2), ... , (e cn, fcn), be a sequence of ordered pairs of edges on vertex set [n] chosen uniformly and independently at random. Let A be an algorithm for the online choice of one edge from each presented pair, and for i = 1, ... , cn let GA(i) be the graph on vertex set [n] consisting of the first i edges chosen by A. We prove that all algorithms in a certain class have a critical value cA for the emergence of a giant component in GA(cn) (i.e. if c cA then with high probability there is a component of size O(n ) in GA(cn)). We show that a particular algorithm in this class with high probability produces a giant component before 0.385n steps in the process (i.e. we exhibit an algorithm that creates a giant component relatively quickly). The fact that another specific algorithm that is in this class has a critical value resolves a conjecture of Spencer. In addition, we establish a lower bound on the time of emergence of a giant component in any process produced by an online algorithm and show that there is a phase transition for the offline version of the problem of creating a giant component.;Now we consider satisfiability. Given n Boolean variables x1, ... , xn, a k -clause is a disjunction of k literals, where a literal is a variable or its negation. Suppose random k-clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated k-clauses as possible with the condition that it must be possible to satisfy every clause which is accepted. When cn random k-clauses on n variables are given, a natural online algorithm known as Online-Lazy accepts an expected (1 - 12k )cn + zkn clauses for some constant zk. If these clauses are given offline, it is possible to do much better, an expected (1 - 12k )cn + O( c )n can be accepted. The question of closing the gap between (1- 12k )cn + zkn and (1- 12k )cn + O( c )n for the online version was posed by Coppersmith, Gamarnik, Hajiaghayi, and Sorkin. We show that for any k ≥ 1, any online algorithm will accept less than (1 - 12k )cn + (ln 2)n k-clauses whp , furthermore we show that this bound is asymptotically tight as k → infinity.;We also introduce a new random model for random 2--SAT. It is well-known that in the standard model there is a sharp phase transition, the probability of satisfiability quickly drops as the number of clauses exceeds the number of variables. The location of this phase transition suggests that there is a direct connection between the appearance of a giant in the corresponding 2n-vertex graph and satisfiability. Here we show that the giant has nothing to do with satisfiability, and in fact the expected degree of a randomly chosen vertex is the important parameter. |
