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

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
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/9523

Title: Cores in random hypergraphs and Boolean formulas
Authors: Molloy, M.
Keywords: r-uniform hypergraph
random graphs
Issue Date: Aug-2005
Publisher: JOHN WILEY & SONS LTD
Citation: Molloy,M.(2005, Aug). Cores in random hypergraphs and Boolean formulas.Random Structures and Algorithms,27(1), 124-135
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 appearance of a k-core in a random r-uniform hypergraph for all r, k ≥ 2, r + k > 4, and (ii) the threshold for the pure literal rule to find a satisfying assignment for a random instance of r-SAT, r ≥ 3.
Description: “This is a preprint of an article accepted for publication in [Random Structures and Algorithms]  copyright (2005) Wiley Periodicals,Inc.
URI: http://hdl.handle.net/1807/9523
ISSN: 1042-9832
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
cores .pdf227.51 kBAdobe PDF
View/Open

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

uoft