Coja-Oghlan, Amin, Onsjoe, Mikael and Watanabe, Osamu. (2012) Propagation connectivity of random hypergraphs. Electronic Journal of Combinatorics, Vol.19 . P17. ISSN 1077-8926

Full text not available from this repository.

Abstract

We study the concept of propagation connectivity on random 3-uniform hyper-graphs. This concept is inspired by a simple propagation algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold. Our proof is based on a kind of large deviations analysis of a time-dependent random walk. Based on the analysis, we also give an upper bound on the expected running time of the simple propagation algorithm.

Item Type:	Journal Article
Divisions:	Faculty of Science > Computer Science Faculty of Science > Mathematics
Journal or Publication Title:	Electronic Journal of Combinatorics
Publisher:	Electronic Journal of Combinatorics
ISSN:	1077-8926
Official Date:	16 January 2012
Volume:	Vol.19
Page Range:	P17
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
URI:	http://wrap.warwick.ac.uk/id/eprint/46997

Request changes or add full text files to a record

Actions (login required)

View Item