Cores in random hypergraphs and Boolean formulas

Michael Molloy

doi:10.1002/rsa.20061

journal article Mar 04, 2005

Cores in random hypergraphs and Boolean formulas

Michael Molloy

Random Structures & Algorithms Vol. 27 No. 1 pp. 124-135 · Wiley

View at Publisher Save 10.1002/rsa.20061

Abstract

AbstractWe describe a technique for determining the thresholds for the appearance of cores in random structures. We use it to determine (i) the threshold for the appearance of ak‐core in a randomr‐uniform hypergraph for allr, k≥ 2,r+k> 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance ofr‐SAT,r≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005

Topics

No keywords indexed for this article. Browse by subject →

References

24

[1]

10.1016/s0304-3975(01)00159-1

[2]

D.Achlioptas P.Beame andM.Molloy A sharp threshold in proof complexity Proc 33rdSymp Theory Comput (STOC) 2001 pp.337–346. 10.1145/380752.380820

[3]

D.AchlioptasandM.Molloy Analysis of a list‐colouring algorithm on a random graph Proc 38th Annu Symp Foundations of Computer Science (FOCS) 1997 pp.204–212. 10.1109/sfcs.1997.646109

[4]

K. Azuma "Weighted sums of certain dependent random variables" Tokuku Math J (1967)

[5]

10.1016/0097-3165(78)90059-6

[6]

Bollobás B. (1984)

[7]

Bollobás B. "Martingales, isoperimetric inequalities and random graphs" Colloq Math Soc Janós Bolyai (1987)

[8]

Bollobás B. "The width of random graph orders" Math Sci (1995)

[9]

A.Broder A.Frieze andE.Upfal On the satisfiability and maximum satisfiability of random 3‐CNF formulasProc 4th Annu ACM‐SIAM Symp Discrete Algorithms (SODA) (1993) pp.322–330.

[10]

10.1002/rsa.3240020103

[11]

10.1145/48014.48016

[12]

10.1017/s0963548300001796

[13]

Erdös P. "On the evolution of random graphs" Magayr Tud Akad Mat Kutato Int Kozl (1960)

[14]

D.FernholzandV.Ramachandran Cores and connectivity in sparse random graphs Technical Report TR‐04‐13 The University of Texas at Austin Department of Computer Sciences 2004.

[15]

10.1016/s0304-3975(02)00640-0

[16]

10.1093/comjnl/39.6.547

[17]

S. Janson (2000) 10.1002/9781118032718

[18]

J.Kim Poisson cloning model for random graphs in preparation.

[19]

M.Luby M.Mitzenmacher andA.Shokrollahi Analysis of random processes via and‐or tree evaluation Proc 9th Symp Discrete Algorithms (SODA) 1998 pp.364–373.

[20]

10.1016/0012-365x(91)90162-u

[21]

M.Mitzenmacher Tight thresholds for the pure literal rule Technical Note 1997‐011 Digital Systems Research Center Palo Alto CA1997.

[22]

10.1002/(sici)1098-2418(199603)8:2<159::aid-rsa6>3.0.co;2-x

[23]

10.1006/jctb.1996.0036

[24]

N. C.Wormald Some problems in the enumeration of labelled graphs Doctoral thesis Newcastle University 1978.

Cited By

97

Modern Minimal Perfect Hashing: A Survey

Hans-Peter Lehmann, Thomas Mueller · 2026

ACM Computing Surveys

Differential equation approximations for Markov chains

R.W.R. Darling, J.R. Norris · 2008

Probability Surveys

Metrics

97

Citations

24

References

Details

Published: Mar 04, 2005
Vol/Issue: 27(1)
Pages: 124-135
License: View

Authors

M

Michael Molloy

Cite This Article

Michael Molloy (2005). Cores in random hypergraphs and Boolean formulas. Random Structures & Algorithms, 27(1), 124-135. https://doi.org/10.1002/rsa.20061

Cores in random hypergraphs and Boolean formulas

You May Also Like