Discrete Mathematics & Theoretical Computer Science, Vol 14, No 2 (2012)

Font Size:  Small  Medium  Large

Random Horn Formulas and Propagation Connectivity for Directed Hypergraphs

Robert H. Sloan, Despina Stasi, György Turán


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