journal article Mar 04, 2005

Cores in random hypergraphs and Boolean formulas

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
[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)
[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.
[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.
[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.
[21]
M.Mitzenmacher Tight thresholds for the pure literal rule Technical Note 1997‐011 Digital Systems Research Center Palo Alto CA1997.
[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
Probability Surveys
Metrics
97
Citations
24
References
Details
Published
Mar 04, 2005
Vol/Issue
27(1)
Pages
124-135
License
View
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
Related

You May Also Like

Survey propagation: An algorithm for satisfiability

A. Braunstein, M. Mézard · 2005

260 citations

Regularity Lemma for k‐uniform hypergraphs

Vojtěch Rödl, Jozef Skokan · 2004

151 citations

The transitive closure of a random digraph

Richard M. Karp · 1990

133 citations

Balls and bins: A study in negative dependence

Devdatt Dubhashi, Desh Ranjan · 1998

107 citations

The complexity of counting graph homomorphisms

Martin Dyer, Catherine Greenhill · 2000

93 citations