A Type of Connectivity in Random Directed Hypergraphs and Its Connection to Horn Formulas

Description

-uniform directed hypergraph, then the procedure of forward chaining in Horn formulas gives rise to a type of connected component in the underlying directed hypergraph.

Let H be a random 3-uniform directed hypergraph selected by including each possible edge independently with probability p(n). We consider the property that almost every H is connected in this sense, and give upper and lower bounds for a threshold function.