Random Horn Formulas and Propagation Connectivity for Directed Hypergraphs
Robert H. Sloan, Despina Stasi, György Turán
Abstract
We consider the probability that in a random definite Horn formula of size-3 clauses over n variables, where every
such clause is included with probability p, there is a pair of vertices for which forward chaining produces all other
variables. A Ω (1/(n ln n)) lower and a O ((ln ln n)/(n ln n)) upper bound is given for values of p such that the
property holds with high probability. This improves a recent result of Berke and Onsj ̈ (2009) on the propagation
o
connectivity of hypergraphs
Full Text: PDF PostScript