On smoothed analysis in dense graphs and formulas
On smoothed analysis in dense graphs and formulas
复制标题
关于密集图形和公式的平滑分析
DOI：
10.1002/rsa.20097
复制
发表时间：
2006
影响因子：
1
通讯作者：
P. Tetali
中科院分区：
文献类型：
--
作者：
Michael Krivelevich;B. Sudakov;P. Tetali
我们研究随机图模型，其中通过向给定密度的大图添加随机边来获得随机实例。该模型的研究由 Bohman 及其同事开始（Random Struct Algor 22 (2003), 33‐42；Random Struct Algor 24 (2004), 105‐117）。在这里，我们获得了固定子图的出现和某些拉姆齐属性的尖锐阈值。我们还考虑了随机 k-SAT 公式的相关模型，其中通过将随机 k-子句添加到具有给定子句数量的固定公式中来获得实例，并导出由此获得的随机公式的不可满足性的严格界限。 © 2006 Wiley periodicals, Inc. 随机结构。阿尔格，2006
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