TITLE: Satisfiability and the Giant Component in Online Variants of the Classical Random Models
SPEAKER: David Kravitz
WHEN: April 17, 1:30pm
WHERE: DH 4303
ABSTRACT:
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 $(e_1,f_1)$, $(e_2,f_2)$, …, $(e_{cn},f_{cn})$ 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 $G_A(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 $c_A$ for the emergence of a giant component in $G_A( cn )$ (i.e. if $c < c_A$ then with high probability the largest component in $G_A(cn)$ has $o(n)$ vertices and if $c > c_A$ then with high probability there is a component of size $\Omega(n)$ in $G_A(cn)$). We show that a particular algorithm in this class with high probability produces a giant component before $0.385 n$ 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 $x_1,…,x_n$, 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 \emph{Online-Lazy} accepts an expected $(1-\frac{1}{2^k})cn+z_kn$ clauses for some constant $z_k$. If these clauses are given offline, it is possible to do much better, $(1-\frac{1}{2^k})cn+\Omega(\sqrt c)n$ can be accepted \whp. The question of closing the gap between $(1-\frac{1}{2^k})cn+z_kn$ and $(1-\frac{1}{2^k})cn+\Omega(\sqrt c)n$ for the online version was posed by Coppersmith, Gamarnik, Hajiaghayi, and Sorkin. We show that for any $k \geq 1$, any online algorithm will accept less than $(1-\frac{1}{2^k})cn+(\ln 2)n$ $k$-clauses \whp, furthermore we show that this bound is asymptotically tight as $k \to \infty$.
We also introduce a new random model for random $2-SAT$. It is well-known that inn 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.
