Mirko Horňák
email: mirko.hornak@upjs.sk.

Mariusz Woźniak
email: mwozniak@uci.agh.edu

On neighbour-distinguishing colourings from lists

Keywords: set of colours, list of colours, neighbour-distinguishing edge colouring, list neighbour-dis-tinguishing index, general list neighbour-distinguishing index

An edge colouring of a graph is said to be neighbour-distinguishing if any two adjacent vertices have distinct sets of colours of their incident edges. In this paper the list version of the problem of determining the minimum number of colours in a neighbour-distinguishing colouring of a given graph is considered.

Introduction

Let G be a finite simple graph, let C be a set of colours (in this paper we shall always suppose C ⊆ N) and let f : E(G) → C be an edge colouring of G. The colour set of a vertex v ∈ V (G) with respect to f is the set S f (v) of colours of edges incident to v. The colouring f is neighbour-distinguishing if it distinguishes any two adjacent vertices by their colour sets, i.e., S f (u) = S f (v) whenever u, v ∈ V (G) and uv ∈ E(G).

As usual, we are interested in the smallest number of colours in a neighbour-distinguishing colouring of G. If the optimisation runs over all proper colourings, that number is called the neighbour-distinguishing index of G, in symbols ndi(G). In the general case (when colourings are not required to be proper) the corresponding invariant is known as the general neighbour-distinguishing index of G and denoted by gndi(G).

The main goal of this paper is to analyse the list versions of the above problems. Denote by P k (X) the set of all k-subsets of a set X and by L k (G) the set of all mappings L : E(G) → P k (N). The set L(e), L ∈ L k (G), e ∈ E(G), is the list of available colours for the edge e. Given L ∈ L k (G), the graph G is Lneighbour-distinguishable provided there is a proper neighbour-distinguishing colouring f : E(G) → N satisfying f (e) ∈ L(e) for every e ∈ E(G). The list neighbour-distinguishing index of G, in symbols lndi(G), is the minimum k such that for every L ∈ L k (G) the graph G is L-neighbour-distinguishable.

This invariant is a generalisation of the "classical" edge-choosability ch (G) of G; for the definition of the edge-choosability as well as that of (vertex-) choosability ch(G) of G see the survey paper [START_REF] Zs | Graph colorings with local constraints-a survey[END_REF] by Tuza. Clearly, we have lndi(G) ≥ max(ndi(G), ch (G)). Recall that according to the List Colouring Conjecture ch (G) should be equal to χ (G), the chromatic index of G.

Remark. In the study of the neighbour-distinguishing index and the list neighbour-distinguishing index it is useful to realise that adjacent vertices of distinct degrees are trivially distinguished by their colour sets.

A graph G is said to be neighbour-irregular if any two of its vertices of the same degree are nonadjacent. The above remark immediately yields

Proposition 1 If G is a neighbour-irregular graph, then ndi(G) = χ (G) and lndi(G) = ch (G). 2
Omitting the requirement that f should be proper we obtain the notions of a generally L-neighbourdistinguishable graph and the general list neighbour-distinguishing index glndi(G) of the graph G.

If G is a disconnected graph with components G 1 , . . . , G q , then evidently lndi(G) = max(lndi(G i ) : i = 1, . . . , q) and glndi(G) = max(glndi(G i ) : i = 1, . . . , q). Therefore, when searching for the neighbour-distinguishing index or general neighbour-distinguishing index, it is sufficient to restrict our attention to connected graphs.

Observe that lndi(K 1 ) = glndi(K 1 ) = 0 and that the graph K 2 does not have any neighbourdistinguishing colouring (either proper or not). So, we shall consider only connected graphs with at least three vertices.

In Section 2 we show that the list neighbour-distinguishing index is equal to the neighbour-distinguishing index for graphs in several classes, namely cycles, trees and unbalanced complete bipartite graphs. This leads us to

Conjecture 2 If G is a connected graph with |V (G)| ≥ 3, then lndi(G) = ndi(G).
Remark. From Proposition 1 it follows that for neighbour-irregular graphs Conjecture 2 and the List Colouring Conjecture are equivalent.

In Section 3 we prove that the general list neighbour-distinguishing index of a tree is at most 3 and we exhibit a tree T with glndi(G) > gndi(G).

Given p, q ∈ Z, let [p, q] := q i=p {i} be the integer interval bounded by p and q. The concatenation of finite sequences A = (a 1 , . . . , a m ) and B = (b 1 , . . . , b n ) is the sequence AB := (a 1 , . . . , a m , b 1 , . . . , b n ). Concatenating finite sequences is clearly associative and we shall use k i=1 A (i) for the result of (successive) concatenation of finite sequences A (1) , . . . , A (k) . So, if

A (i) = (a (i) 1 , . . . , a (i) m (i) ), then k i=1 A (i) = (a (1) 1 , . . . , a (1)
m (1) , . . . , a (k) 1 , . . . , a (k) m (k) ). For k ∈ Z we denote by (k) 2 the (unique) l ∈ [2, 3] satisfying k ≡ l (mod 2).
Recall that a cycle C of length l ≥ 3 in a graph G can be coded using a sequence

l+1 i=1 (v i ) of its consecutive vertices so that V (C) = {v i : i ∈ [1, l]} and E(C) = {v i v i+1 : i ∈ [1, l]} (with v l+1 = v 1 ).

Proper colourings

The neighbour-distinguishing index of a graph was introduced by Zhang et al. in [START_REF] Zhang | Adjacent strong edge coloring of graphs[END_REF], where the authors found (among other things) the value of this invariant for cycles (C n denotes an n-vertex cycle) and trees:

Proposition 3 Let n be an integer, n ≥ 3. (1) If n = 5, then ndi(C n ) = 5. (2) If n ≡ 0 (mod 3), n = 5, then ndi(C n ) = 4. (3) If n ≡ 0 (mod 3), then ndi(C n ) = 3. 2 Proposition 4 If T is a tree with |V (T )| ≥ 3, then ∆(T ) ≤ ndi(T ) ≤ ∆(T ) + 1.
Moreover, ndi(T ) = ∆(T ) + 1 if and only if T has a pair of adjacent vertices of degree ∆(T ). 2

In the above introductory paper it is conjectured that ndi(G) ≤ ∆(G) + 2 for any connected graph G / ∈ {K 2 , C 5 }. The conjecture was confirmed by Balister et al. in [START_REF] Balister | Adjacent vertex distinguishing edge-colorings[END_REF] for bipartite graphs and for graphs G with ∆(G) = 3. Edwards et al. in [START_REF] Edwards | On the neighbour-distinguishing index of a graph[END_REF] showed even that ndi(G) ≤ ∆(G) + 1 if G is bipartite, planar, and of maximum degree ∆(G) ≥ 12.

In this section we determine the list neighbour-distinguishing index for graphs in some classes with a simple structure.

Cycles

We suppose that

E(C n ) = {e i : i ∈ [1, n]}
and that e i is adjacent to e i+1 for every i ∈ [1, n] with indices taken modulo n (this usual convention will be used throughout the whole paper without explicitly mentioning it in what follows).

Proposition 5 Let n be an integer, n ≥ 3.

(1) If n = 5, then lndi(C n ) = ndi(C n ) = 5. (2) If n ≡ 0 (mod 3), n = 5, then lndi(C n ) = ndi(C n ) = 4. (3) If n ≡ 0 (mod 3), then lndi(C n ) = ndi(C n ) = 3.
Proof: Because of Proposition 3 we shall be done by proving the inequality lndi(C n ) ≤ ndi(C n ) (the reverse inequality being obvious).

(1) The statement is trivial.

(2) It suffices to show that for any L ∈ L 4 (C n ) there is a proper neighbour-distinguishing colouring

f : E(C n ) → N satisfying f (e i ) ∈ L(e i ) for every i ∈ [1, n].
If all lists are the same, the existence of f follows from the fact that ndi(C n ) = 4. Otherwise there are two adjacent edges of C n with distinct lists. Without loss of generality we may suppose that L(e 1 ) = L(e n ), which implies L(e 1 ) \ L(e n ) = ∅. Now determine f (e i ) in the following way: Choose f (e 1 ) ∈ L(e 1 ) \ L(e n ) and f (e

2 ) ∈ L(e 2 ) \ {f (e 1 )}. If j ∈ [3, n -2] and f (e i ) is known for all i ∈ [1, j -1], take f (e j ) ∈ L(e j ) \ {f (e j-2 ), f (e j-1 )}. To finish, let f (e n-1 ) ∈ L(e n-1 )\{f (e n-3 ), f (e n-2 ), f (e 1 )} and f (e n ) ∈ L(e n )\{f (e n-2 ), f (e n-1 ), f (e 1 ), f (e 2 )} (which is possible because f (e 1 ) / ∈ L(e n )).
(3) An edge colouring f :

E(C n ) → N is proper and neighbour-distinguishing if and only if f (e i+1 ) = f (e i ) = f (e i+2 ) for every i ∈ [1, n]. Let F n be the graph with V (F n ) = E(C n ) and E(F n ) = {e i e i+1 : i ∈ [1, n]} ∪ {e i e i+2 : i ∈ [1, n]}.
Thus F n is the square of the line graph of C n and, as the

line graph of C n is C n itself, F n ∼ = C 2 n (F n is isomorphic to C 2 n ). Therefore, lndi(C n ) = ch(F n ) = ch(C 2 n ).
Since n ≡ 0 (mod 3), say n = 3k, it is clear that the graph F n is an edge-disjoint union of the cycle (e 2 ) k j=1 (e 3j-2 , e 3j , e 3j+2 ) of length 3k and k vertex-disjoint cycles (e 3j-1 , e 3j , e 3j+1 , e 3j-1 ) of length 3 with j ∈ [1, k]. Graphs with such a structure were studied by Fleischner and Stiebitz in [START_REF] Fleischner | A solution to a colouring problem of P. Erdős[END_REF], where it is proved that ch(F n ) = 3. So, by Proposition 3.(3), we have lndi

(C n ) = ch(F n ) = ndi(C n ) = 3. 2

Trees

By Proposition 4, there are two categories of trees: Category k consists of trees T with ndi(T ) = ∆(T ) -1 + k, k = 1, 2. Thus, a tree T is of Category 2 if and only if it has a pair of adjacent vertices of degree ∆(T ).

Theorem 6 If T is a tree with |V (T )| ≥ 3, then lndi(T ) = ndi(T ).

Proof: Consider the following algorithm that enables us to find a neighbour-distinguishing colouring of a given tree T of a given category with colours belonging to lists of an appropriate cardinality.

S(v) ← ∅ for every v ∈ V Pick z, t ∈ V so that zt ∈ E and deg T (z) = 1, then choose f (zt) ∈ L(zt). S(z) ← {f (zt)} S(t) ← {f (zt)} X ← {z} while V \ X = ∅ do Choose y ∈ V \ X so that there is (a unique) x ∈ X with xy ∈ E. if d = deg T (y), N T (y) = {x i : i ∈ [1, d]} and N T (y) ∩ X = {x 1 } then //
) ∈ L(yx i ). S(y) ← S(y) ∪ {f (yx i )} S(x i ) ← S(x i ) ∪ {f (yx i )} if deg T (x i ) = 1 then X ← X ∪ {x i } X ← X ∪ {y} return f (e)
for every e ∈ E // Exhibit a required colouring. // The algorithm builds step by step colour sets S(v) of vertices v ∈ V by assigning colours to all uncoloured edges incident to v. It starts with colouring an arbitrary pendant edge of T so that the (unique) pendant vertex of this edge is the first vertex of the set X of all vertices of T with currently finished colour sets. If X = V , the subgraph of T induced by all currently coloured edges has a leaf out of X (an extension vertex). A successive colouring of all edges (not coloured yet) incident to the extension vertex extends X by all pendant neighbours (out of X) of the extension vertex and, finally, by the extension vertex itself.

To see that the algorithm is correct it is sufficient to use the following two facts: b) If a vertex y is added to X and X ∪ {y} = V , then the subgraph of T induced by all currently coloured edges is a subtree of T , all its non-leaves are in X and at least one of its leaves is not a leaf of the whole T (so that it can be chosen as a new y and guarantees that d ≥ 2 in the corresponding for loop).

Unbalanced complete bipartite graphs

Unbalanced complete bipartite graphs also are in favour of Conjecture 2.

Theorem 7 If m, n are positive integers with m < n, then lndi(K m,n ) = ndi(K m,n ) = n. Proof: It is well known that χ (K m,n ) = n. Since K m,n is neighbour-irregular, by Proposition 1 we have ndi(K m,n ) = χ (K m,n ) = n.
On the other hand, Janssen in [START_REF] Janssen | The Dinitz problem solved for rectangles[END_REF] proved that ch (K m,n ) = n; so, again by Proposition 1, lndi(K m,n ) = ch (K m,n ) = n and we are done. 2

General colourings

The general neighbour-distinguishing index was introduced by Győri et al. in [START_REF] Győri | General neighbour-distinguishing index of a graph[END_REF], where the authors proved that gndi(G) ≤ 2 log 2 χ(G) + 1 for any graph G having no isolated edges. The result was improved by Győri and Palmer who proved in [START_REF] Győri | A new type of edge-derived vertex colorings[END_REF] that χ(G) ≥ 3 implies gndi(G) = log 2 χ(G) + 1 (in the case log 2 χ(G) / ∈ Z the same expression was obtained independently by Horňák and Soták in [START_REF] Horňák | General neighbour-distinguishing index via chromatic number[END_REF]). The analysis of the general list neighbour-distinguishing index seems to be a bit more complicated than that of the list neighbour-distinguishing index. Indeed, we know the exact values just for paths and cycles, for trees we only have an upper bound equal to 3. Also, an analogue of Conjecture 2 fails.

Paths and cycles

We shall see that, as in the case of proper colourings, when passing to the list version the value of the parameter does not change in the classes of paths and cycles.

Proposition 8 Let n be an integer, n ≥ 3.

(1) If n ≡ 1 (mod 2), then glndi(P n ) = gndi(P n ) = 2.

(2) If n ≡ 0 (mod 2), then glndi(P n ) = gndi(P n ) = 3.

Proof: The values of gndi(P n ) come from [START_REF] Győri | General neighbour-distinguishing index of a graph[END_REF] so that we only need to show that glndi(P n ) = gndi(P n ).

An edge colouring f :

E(P n ) → N is neighbour-distinguishing if and only if f (e 1 ) = f (e 2 ), f (e i ) = f (e i+2 ) for every i ∈ [1, n -3] and f (e n-2 ) = f (e n-1 ). Let G n be the graph with V (G n ) = E(P n ) and E(G n ) = {e 1 e 2 } ∪ {e i e i+2 : i ∈ [1, n -3]} ∪ {e n-2 e n-1 }. If n ≥ 4 (n = 2k or n = 2k + 1 with k ∈ Z, k ≥ 2), then G n ∼ = C n-1 . Indeed, the following are cycles in G n : (e 1 ) k-1 i=1 (e 2i )[ k i=1 (e 2k+1-2i )] (if n = 2k) and (e 1 ) k i=1 (e 2i )[ k i=1 (e 2k+1-2i )] (if n = 2k + 1). Therefore, glndi(P n ) = ch(C n-1
) and we are done by using the well-known fact that ch(C l ) = (l) 2 . Finally, G 3 ∼ = P 2 , hence glndi(P 3 ) = ch(P 2 ) = 2 = gndi(P 3 ).

2

Proposition 9 Let n be an integer, n ≥ 3.

(

) If n ≡ 0 (mod 4), then glndi(C n ) = gndi(C n ) = 2. 1
(

) If n ≡ 0 (mod 4), then glndi(C n ) = gndi(C n ) = 3. 2
Proof: Similarly as in the preceding proposition, we only have to prove that glndi

(C n ) = gndi(C n ) (since gndi(C n ) is known from [4]
).

An edge colouring f :

E(C n ) → N is neighbour-distinguishing if and only if f (e i ) = f (e i+2 ) for every i ∈ [1, n]. Let H n be the graph with V (H n ) = E(C n ) and E(H n ) = {e i e i+2 : i ∈ [1, n]}; then glndi(C n ) = ch(H n ). If n is odd, n = 2k + 1, then (e 2k ) k i=0 (e 2i+1 )[ k i=1 (e 2i )] is a cycle in H n , H n ∼ = C n and glndi(C n ) = ch(C n ) = 3. If n is even, n = 2k, k ≥ 3, then (e 2k-2+j ) k-1 i=0 (e j+2i ), j = 1, 2, is a cycle in H n , hence H n ∼ = 2C k and glndi(C n ) = ch(2C k ) = ch(C k ) = (k) 2 .
Finally, H 4 ∼ = 2P 2 , and glndi(H 4 ) = ch(2P 2 ) = ch(P 2 ) = 2. 2

Trees

The following two results are taken from [START_REF] Győri | General neighbour-distinguishing index of a graph[END_REF].

Theorem 10 If G is a connected bipartite graph with |V (G)| ≥ 3, then 2 ≤ gndi(G) ≤ 3. 2
Proposition 11 For any graph G the following statements are equivalent:

(1) gndi(G) = 2.

(2) G is bipartite and there is a bipartition

{X 1 ∪ X 2 , Y } of V (G) such that X 1 ∩ X 2 =
∅ and any vertex of Y has at least one neighbour in both X 1 and X 2 . 2

Proposition 12 If T is a tree with |V (T )| ≥ 3, then gndi(T ) = 2 if and only if the distance between any two leaves of T is even.

Proof: If gndi(T ) = 2, by Proposition 11 we know that there is a bipartition {X 1 ∪ X 2 , Y } of V (T ) such that X 1 ∩ X 2 = ∅ and any vertex of Y has at least one neighbour in both X 1 and X 2 . Thus deg T (y) ≥ 2 for every y ∈ Y , all leaves of T are in X 1 ∪ X 2 and the distance between any two of them is even. Now suppose that the distance between any two leaves of T is even. Let {X, Y } be the bipartition {X, Y } of V (T ) with X containing all leaves of T . Pick x 0 ∈ X and let {X 1 , X 2 } be the decomposition of X determined as follows: x ∈ X i df.

⇔ d T (x 0 , x) ≡ 2i (mod 4), i = 1, 2. Consider a vertex y ∈ Y and its neighbour x lying on the (unique) path joining y to x 0 . Since y is not a leaf, it has a neighbour x = x . Clearly, d T (x 0 , x ) = d T (x 0 , x ) + 2, which means that one of x , x is in X 1 and the other in

: if S f (z) \ S f (y) = {c 1 }, then f (xy) = c 1 ; if S f (y) = {c 2 } (which means that deg T (y) = 1), then f (xy) = c 2 . Since |L(xy)| = 3, f does exist.
Clearly, f is neighbour-distinguishing, the tree T is L-neighbour-distinguishable and glndi(T ) ≤ 3.

2

The rest of this subsection is devoted to showing that an analogue of Conjecture 2, in which the list neighbour-distinguishing index is replaced by the general list neighbour-distinguishing index, fails.

Let T and L be the tree and the mapping from L 2 (T ), respectively, that are presented in Figure 1. The distance between any two leaves in T is even, hence, by Proposition 12, gndi(T ) = 2. Let us prove that T is not L-neighbour-distinguishable (so that, by Theorem 13, glndi(T ) = 3). Suppose, on the contrary, that f is a neighbour-distinguishing colouring of T with f (e) ∈ L(e) for every e ∈ E(T ).

Algorithm 1 :

 1 ListNeighbourDistinguishing(T, k, L) Input: A tree T = (V, E) with |V | ≥ 3 of Category k and a mapping L : E → N that satisfies |L(e)| = ∆(T ) -1 + k for every e ∈ E. Output: A proper neighbour-distinguishing colouring f : E → N with f (e) ∈ L(e) for every e ∈ E. do

a)

  No list is reduced to the empty set. With k = 1 the worst case (the reduction to a singleton) can apply if either deg T (y) = ∆(T ) or deg T (x) = ∆(T ) -1 = deg T (y). If k = 2, such a situation can appear provided that deg T (x) = ∆(T ) = deg T (y).

2

 2

X 2 . 2 Theorem 13

 2213 By Proposition 11 then gndi(T ) = 2. If T is a tree with |V (T )| ≥ 3, then glndi(T ) ≤ 3.Proof: We proceed by induction on the lexicographical ordering of pairs (diam(T ), |V (T )|), where diam(T ) is the diameter of T . From |V (T )| ≥ 3 we know that diam(T ) ≥ 2. If diam(T ) = 2, then T is a star and glndi(T ) = 2 (it is sufficient to colour the second coloured edge with a colour that is different from the first used colour).So, suppose that diam(T ) ≥ 3 and glndi(T ) ≤ 3 for every tree T with the pair (diam(T ), |V (T )|) lexicographically smaller than the pair (diam(T ), |V (T )|). Let x be an endvertex (a leaf) of a longest path in T and let y be the unique neighbour of x. Further, let z be the unique non-leaf neighbour of y.Consider a mapping L ∈ L 3 (T ), the tree T := T -x and the mapping L := L \ {(xy, L(xy))} ∈ L 3 (T ). By the induction hypothesis there is a neighbour-distinguishing colouring f : E(T ) → N with f (e) ∈ L (e) = L(e) for every e ∈ E(T ). Let f : E(T ) → N be an extension of f with f (xy) ∈ L(xy) that has the following two properties

Fig. 1 :Case 1 :

 11 Fig. 1: A tree T with 2 = gndi(T ) < glndi(T ) = 3.

Acknowledgements

The authors are indebted to an anonymous referee whose well-founded comments helped to improve the presentation of obtained results. They are thankful to Zsolt Tuza for pointing out that Janssen's theorem also yields a support for Conjecture 2.

The work was supported by Science and Technology Assistance Agency under the contract No. APVV-0023-10, by Grant VEGA 1/0652/12 and by the Agency of the Slovak Ministry of Education for the Structural Funds of the EU under the project ITMS:26220120007. .pl. The research was partially supported by the Polish Ministry of Science and Higher Education. 1365-8050


Robert H Sloan

Despina Stasi

György Turán

Random Horn Formulas and Propagation Connectivity for Directed Hypergraphs †

Keywords:

We consider the property 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 variables for which forward chaining produces all other variables. We show that with high probability the property does not hold for p ≤ 1/(11n ln n), and does hold for p ≥ (5 ln ln n)/(n ln n).

Introduction

Horn formulas are a subclass of CNF expressions, where every clause contains at most one unnegated variable. This class is tractable in the sense that many problems that are hard for CNF expressions in general are polynomially solvable for Horn formulas (such as satisfiability and equivalence). It is partly for this reason that Horn formulas are of basic importance in artificial intelligence and other areas. Random Horn formulas have been studied in [START_REF] Dunne | A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses[END_REF][START_REF] Demetrios | The phase transition in the random HornSAT problem[END_REF][START_REF] Istrate | The phase transition in random Horn satisfiability and its algorithmic implications[END_REF][START_REF] Langlois | Combinatorial problems for Horn clauses[END_REF][START_REF] Moore | A continuous-discontinuous second-order transition in the satisfiability of random Horn-SAT formulas[END_REF].

A Horn formula is definite if it consists of clauses containing exactly one unnegated variable. We consider definite Horn formulas with clauses of size 3, i.e., with clauses of the form (ā ∨ b ∨ c), which can also be written as a, b → c. Here a and b form the body of the clause and c is the head of the clause. Implication between a definite Horn formula ϕ and a definite Horn clause C can be decided by forward chaining: mark variables in the body of C and, while there is a clause in ϕ with all its body variables marked, mark its head variable as well. Then C is implied by ϕ iff its head gets marked.

We consider random definite Horn formulas with clauses of size 3 over n variables, where every clause is included with probability p. It follows directly from the results of [LMST09] that p = (2 ln n)/n is a threshold probability for the following property: every pair of variables implies every other variable (see also [START_REF] Dunne | A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses[END_REF] for a related result).

In this paper we consider the property that some pair of variables implies every other variable. This property is closely related to the property of propagation connectivity for 3-uniform undirected hypergraphs, introduced recently by Berke and Onsjö [START_REF] Berke | Propagation connectivity of random hypergraphs[END_REF]. They consider a marking process like forward Robert H. Sloan Despina Stasi, György Turán chaining, except that now a vertex can be marked if it is contained in an edge whose other two vertices are already marked. A 3-uniform undirected hypergraph is propagation connected if there is a pair of vertices such that the marking process, starting from that pair, marks every vertex. Berke and Onsjö showed that for p < 1/(n(log n) 2 ) random hypergraphs are a.a.s. not propagation connected [START_REF] Berke | Propagation connectivity of random hypergraphs[END_REF] and for p > 1/(n(log n) 0.4 ) random hypergraphs are a.a.s. propagation connected [START_REF] Berke | Propagation connectivity of random hypergraphs[END_REF]. The first result proves a lower bound for the transition from random hypergraphs being a.a.s. not propagation connected to random hypergraphs being a.a.s. propagation connected, and the second result proves an upper bound for the transition. We use the terms lower and upper bound in a similar sense throughout the paper.

The Horn formula property mentioned above is equivalent to propagation connectivity for directed 3uniform hypergraphs, where by a directed hypergraph we mean a hypergraph with each edge having a distinguished vertex called its head, and the other vertices called its body. (This is one of the possible definitions of a directed hypergraph. There are several other variants.) In the rest of the paper we use the terminology of propagation connectivity for directed hypergraphs instead of Horn formulas. We show that random directed 3-uniform hypergraphs for p ≤ 1/(11n ln n) are a.a.s. not propagation connected and for p ≥ (5 ln ln n)/(n ln n) are a.a.s. propagation connected. The proofs are based on two versions of the "fanning-out process" (see, e.g., [START_REF] Karp | The transitive closure of a random digraph[END_REF][START_REF] Janson | Random Graphs[END_REF]). For the upper bound we start the process by exploring a subset of the vertices and finding a maximal degree pair within that subset.

For the undirected hypergraph version of the problem, Coja-Oghlan, Onsjö and Watanabe concurrently and independently proved lower and upper bounds, both of the order 1/(n ln n) [START_REF] Coja-Oghlan | Propagation connectivity of random hypergraphs[END_REF]. It appears that their argument can be adapted to yield order 1/(n ln n) lower and upper bounds in the directed case as well. The proofs we present here are simpler.

The lower and upper bounds are presented in Section 3 and 4. In the closing section we mention a few open problems.

Preliminaries

We consider 3-uniform directed hypergraphs H with directed edges of the form u, v → w. The pair (u, v) is the body of the edge and w is the head of the edge. Note that the body is an unordered pair. The degree of a pair (u, v) is the number of vertices w that form an edge u, v → w with the pair. We refer to vertex w as a successor of (u, v). The (u, v)-propagation connected component (or simply (u, v)-component) of H is the set of vertices marked by the marking process starting with (u, v).

The probability model where a random directed hypergraph is formed over the vertex set [n] = {1, . . . , n} by including each edge u, v → w independently with probability p is denoted by DH(n, p). For any monotone increasing property of directed hypergraphs the probability that the property holds for a random directed hypergraph drawn from DH(n, p) is a monotone non-decreasing function of p (see [Bol01, Th.2.1]).

We use the following versions of the Chernoff bounds [START_REF] Janson | Random Graphs[END_REF].

Proposition 2.1 If X ∈ BIN(n, p) and t ≥ 0 then (a) Pr[X ≥ E[X] + t] ≤ exp - t 2 2(E[X]+ t 3 ) , (b) Pr[X ≤ E[X] -t] ≤ exp -t 2 2E[X] .

A lower bound

We first give a lower bound for probabilities p such that a random directed hypergraph from DH(n, p) is a.a.s. propagation connected.

Theorem 3.1 Let p ≤ 1/(11n ln n). In a random directed hypergraph from DH(n, p) a.a.s. every propagation connected component has size at most 11 ln n.

Proof: By monotonicity we may assume p = 1/(11n ln n). The following process is used to explore H ∈ DH(n, p). Start with two sets A 0 = {u, v} and B 0 = ∅. The sets A i and B i represent the sets of discovered vertices and saturated pairs at iteration i respectively, and put m i = |A i |. At iteration i of the process consider vertices u i and v i such that u i , v i ∈ A i-1 and (u i , v i ) ∈ B i-1 . Find every edge u i , v i → w where w ∈ A i-1 . Construct the set A i so that it contains all vertices in set A i-1 plus all vertices w, where w is the head of an edge that was found in step i. Construct the set B i by

B i = B i-1 ∪ {(u i , v i )}.
When every pair in A i is saturated, we have discovered all the vertices in the component, and from then on we put A j = A i , B j = B i for every j > i.

We need to show that this process stabilizes after a small number of steps with high probability. Define X i to be the number of successors, in V A i-1 , of the pair (u i , v i ) to be saturated. Each edge with body (u i , v i ) and head in V A i-1 is in the hypergraph with probability p, independently of the presence or absence of any other edge. Furthermore each such edge is considered at most once in the process. Thus

X i ∈ BIN(n -m i-1 , p).
Let k = 11 ln n . If the process generates at least k vertices then this must happen in the first k-1 2 iterations. Thus the probability of generating at least k vertices is at most

Pr    ( k-1 2 ) i=1 X i ≥ k -2    . (1)
Let X + i ∈ BIN(n, p) and replace the upper limit in the summation (1) by k 2 for convenience. Then, noting that ( k 2 ) i=1 X + i ∈ BIN k 2 n, p and as such has mean k 2 np, the probability (1) can be upper bounded by

Pr    ( k 2 ) i=1 X + i ≥ k -2    = Pr    ( k 2 ) i=1 X + i ≥ k 2 np + k -2 - k 2 np    .
Using the values of p and k we note that np

∼ 1/k, giving k 2 np ∼ k -2 -k 2 np ∼ k/2. Then the Chernoff bound (Proposition 2.1(a)) with t = k -2 -k 2 np gives the upper bound exp {-(3k)/16} ∼ exp {-(33 ln n)/16} = o(n -2
), which implies the theorem by the union bound. 2

An upper bound

In this section we give a sufficient condition for probabilities p such that a random directed hypergraph from DH(n, p) is a.a.s. propagation connected.

Theorem 4.1 For p ≥ (5 ln ln n)/(n ln n) a random directed hypergraph from DH(n, p) is a.a.s. propagation connected.

Proof: By monotonicity we may assume p = (5 ln ln n)/(n ln n). We use a modification of the process described above. First we consider all edges over the first n/4 vertices and find a highest-degree pair (u, v) in that subset. Starting from the successors of that pair we find a sufficiently large part of the rest of the component using a variant of the original process organized into phases as follows.

Let m = (ln n)/(ln ln n) and assume that we found a pair (u, v) with m successors w 1 , . . . , w m among the first n/4 vertices. Let A 0 = {w 1 , . . . , w m } be the initial set of discovered vertices and let C 0 be the (3/4)n vertices not considered so far, forming the initial set of available vertices. In iteration i of the new process we pick an arbitrary set D i-1 ⊆ C i-1 of n/2 available vertices, and we find all edges u, v → w, where u, v ∈ A i-1 and w ∈ D i-1 . If there are at least m distinct successors in D i-1 then let A i be any m of these and put C i = C i-1 \ A i . Otherwise let A j = A i-1 for every j ≥ i. We run this process for ln n ln ln n iterations.

The following lemma, analogous to bounds for graphs (see [Bol01, Ch.3]), gives a bound for the maximal degree of a pair in H ∈ DH(n, p). This lemma is stated for the smaller and simpler probability 1/(n ln n), but applies also to larger p by monotonicity. Lemma 4.2 If p = 1/(n ln n), then the maximum degree of H ∈ DH(n, p) is a.a.s. at least (ln 4n)/(ln ln 4n).

Proof: Let d = (ln 4n)/(ln ln 4n) and let the random variable Y ij be the number of successors of pair (i, j) in H. Then Y ij ∈ BIN (n -2, p) and since we are dealing with directed edges, the variables Y ij are independent. Thus the probability that every degree is smaller than d is

(1 -Pr [Y ij ≥ d]) ( n 2 ) ≤ 1 - n -2 d p d (1 -p) n-2-d ( n 2 ) < 1 - 1 2 n -2 d p d ( n 2 ) ,
if n is sufficiently large. For the last inequality we used the fact that (1 -p) n-2-d = 1 -o(1). Using 1 -x < e -x , we need to show that

pn d d n 2 → ∞.
This follows by taking logarithms and using the definitions of p and d. The expression on the right tends to infinity, since the first term tends to infinity, the second term is positive and the third term has a constant limit.

2

We also use a version of a lemma of [START_REF] Berke | Propagation connectivity of random hypergraphs[END_REF] showing that a.a.s. every component is either small or contains every vertex. Such a statement holds for several probabilities p, but we state it here for p = (5 ln ln n)/(n ln n), as this property is not monotone. This lemma is similar to the gap theorem in [START_REF] Karp | The transitive closure of a random digraph[END_REF] and its proof is included for completeness. Proof: If a set of vertices is a propagation connected component then there can be no edges with body in the component and head outside. Thus the probability that there is a component of size k is at most

n k • (1 -p) ( k 2 )(n-k) .
We show that for

(ln n) 2 ≤ k ≤ n -1 this quantity is o(1/n). If n/2 ≤ k ≤ n -1 then replacing n k with n n-k gives the upper bound ne n -k n-k exp -p k 2 (n -k) = exp -(n -k) p k 2 -ln ne n -k .
As p k 2 = Ω (n ln ln n/ ln n), the probability is upper bounded by exp{-Ω (n ln ln n/ ln n)}. Else (ln n) 2 ≤ k < n/2 and the analogous calculation gives the upper bound

exp -k ln k + p(k -1)(n -k) 2 -(ln n + 1) .
Here n -k can be replaced by n/2 and then substituting the values of p and k we can lower bound ln k + p(k -1)(n -k)/2 -(ln n + 1) by Ω (ln n). Since k ≥ (ln n) 2 we get an upper bound of the form exp{-Ω (ln n) 3 }.

2

Returning to the proof of Theorem 4.1, let us say that we are successful if we find a pair of degree m among the first n/4 vertices, we can run the iterative process for ln n ln ln n iterations, always finding m new vertices, and the event described in Lemma 4.3 occurs. In this case, after the last iteration we found a component of size (ln n) 2 , and by Lemma 4.3 the hypergraph is propagation connected.

The number Z i of edges added in the ith iteration has distribution BIN m Since we saturate more than one pair in an iteration it is possible that the same vertex is discovered by more than one edge. The probability of such a conflict is at most

m 2 2 • n 2 • p 2 = O (ln n) 2 n(ln ln n) 2 .
(3)

  Lemma 4.3 ([BO09b]) If p = (5 ln ln n)/(n ln n) then a.a.s. every propagation connected component has either size n or size less than (ln n) 2 .

2 n2

 2 , p . Using the Chernoff bound (Proposition 2.1(b)) for the probability that there are fewer than m such edges we getPr [Z i < m] ≤ exp -(E[Z i ] -m) 2 2E[Z i ] < exp -ln n 41 ln ln n .(2)The last bound is due toE[Z i ] ∼ m 2 np/4 ∼ (5 ln n)/(4 ln ln n) and E[Z i ] -m ∼ (ln n)/(4 ln ln n) which gives (E[Z i ] -m) 2 2E[Z i ] ∼ln n 40 ln ln n .

† This material is based upon work supported by the National Science Foundation under Grant No. CCF-0916708. 1365-8050

If Z i ≥ m and there are no conflicts in iteration i then we found at least m new vertices in that iteration. Hence, using Lemmas 4.2, 4.3 and the bounds (2) and (3), the probability of failure is

2

The approach used in this paper seems to require edge probabilities of the order of magnitude given in Theorem 4.1, as the probability should be large enough to produce a sufficient number of newly discovered vertices, starting from an initial set of size determined by the maximum degree calculation of Lemma 4.2.

Open Problems

It follows from the result of [START_REF] Langlois | Combinatorial problems for Horn clauses[END_REF] mentioned in the introduction and Theorem 3.1 that the fraction of pairs (u, v) such that the (u, v)-component has size n grows from 0 to 1 over the interval between p = Ω (1/(n ln n)) and O (ln n/n). It would be interesting to have more detailed information about growth over this interval.

Forward chaining can be studied for different ranges of the parameters. For example, [START_REF] Moore | A continuous-discontinuous second-order transition in the satisfiability of random Horn-SAT formulas[END_REF] gives phase transition results on forward chaining where the marking process is started from a positive fraction of the vertices and p is of the form c/n 2 . Forward chaining could be studied beyond just determining the size of the component produced. The process producing a propagation connected component can also be viewed, using the terminology of propositional logic, as a resolution derivation of consequences, or using the terminology of directed graphs, as a hyperpath [AIL + 10]. Considering combinatorial parameters of the structure of a propagation connected component, such as its depth, could also be of interest from the point of view of knowledge base applications.

The Internet and other large networks motivated the study of random graphs in models different from the standard models of fixed edge probabilities or fixed number of edges. For evolving knowledge bases, modeled by random Horn formulas, we are not aware of any such work. A possible choice would be to consider random subformulas of a given formula (corresponding to 'true' knowledge). For random graphs such a model has been studied, e.g., in [START_REF] Fan | The spectral gap of a random subgraph of a graph[END_REF].

Acknowledgements

The authors would like to thank the referee for a careful reading of this paper and useful suggestions.