On smoothed analysis in dense graphs and formulas

Abstract We study a model of random graphs, where a random instance is obtained by adding random edges to a large graph of a given density. The research on this model has been started by Bohman and colleagues (Random Struct Algor 22 (2003), 33‐42 ; Random Struct Algor 24 (2004), 105‐117 ). Here we obtain a sharp threshold for the appearance of a fixed subgraph and for certain Ramsey properties. We also consider a related model of randomk‐SAT formulas, where an instance is obtained by adding randomk‐clauses to a fixed formula with a given number of clauses, and derive tight bounds for the non‐satisfiability of the thus‐obtained random formula. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006