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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom