test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/9490

Title: The pure literal rule threshold and cores in random hypergraphs
Authors: Molloy, M.
Keywords: r-uniform hypergraph
random structures
Issue Date: Jan-2004
Publisher: SIAM
Citation: Molloy,M.(2004). The pure literal rule threshold and cores in random hypergraphs. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 11-14,(pp.672-681).Philadelphia, PA, USA: Society for Industrial and Applied Mathematics
Abstract: We 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 pure literal rule to find a satisfying assignment for a random instance of r-SAT, r ≥ 3, and (ii) the threshold for the appearance of a k-core in a random r-uniform hypergraph for all r, k ≥ 2, r + k > 4.
Description: pubulished source © SIAM Inc. 2004
URI: http://hdl.handle.net/1807/9490
ISBN: 0-89871-558-X
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
core conference version.pdf233.35 kBAdobe PDF
core conference version.pdf.txt29.8 kBText

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.