Premium
On smoothed analysis in dense graphs and formulas
Author(s) -
Krivelevich Michael,
Sudakov Benny,
Tetali Prasad
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20097
Subject(s) - struct , random graph , mathematics , discrete mathematics , random regular graph , combinatorics , graph , satisfiability , computer science , chordal graph , 1 planar graph , programming language
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 random k ‐SAT formulas, where an instance is obtained by adding random k ‐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