### 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