Ramin Kazemi
email: rst.kazemi@gmail.com

Mohammad Q Vahidi-Asl

The Variance of the Profile in Digital Search Trees

Keywords: Digital search trees, tree profiles, Poisson variance, generating functions, saddle point method, singularity analysis, Mellin transform, Poissonization

. The purpose of the present paper is to extend their analysis and to provide a precise analysis of variance of the profile. The main (technical) difference is that we have to deal with an inhomogeneous part in a proper functional-differential equations satisfied by the second moment and Poisson variance. However, we show that the variance is asymptotically of the same order as the expected value which implies concentration. These results are derived by methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization, the saddle point method and singularity analysis.

Introduction

In 1970, Coffman and Eve published a paper that introduced several modification to hashing schemes using trees [START_REF] Coffman | File structures using hashing functions[END_REF]. The paper included three type of trees and some analysis of their basic properties. These trees are known today by different names. Coffman and Eve's sequence trees are what today we call digital search trees. The method is well suited for storing data when the bit composition (or letter composition) of the data is available [START_REF] Mahmoud | Evolution of Random Search Trees[END_REF]. In fact, digital search trees and tries are two classes of so-called log n-trees and their construction is based on digital keys and not on the order structure of the keys as in the case of binary search trees [START_REF] Drmota | Random Trees, An Interplay Between Combinatorics and Probability[END_REF]. They are important in many computer science applications like data compression, pattern matching and hashing. For example, the popular Lempel-Ziv compression scheme is strongly related to digital search trees.

Digital search trees (especially, digital search trees and tries) are fundamental data structures on words [START_REF] Pittel | Asymptotic Growth of a Class of Random Trees[END_REF][START_REF] Prodinger | Digital Search Trees and Basic Hypergeometric Functions[END_REF][START_REF] Sedgewick | Algorithms in C: Fundamental Algorithms, Data Structures, Sorting, Searching[END_REF][START_REF] Szpankowski | A Characterization of Digital Search Trees From the Successful Search Viewpoint[END_REF][START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]. Jacquet and Szpankowski [START_REF] Jacquet | Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees[END_REF] considered the asymptotic behavior of the Lempel-Ziv Fig. 1: A digital search tree built on eight strings s1, ..., s8 (i.e., s1 = 0..., s2 = 1..., s3 = 01..., s4 = 11..., etc.) with internal (ovals) and external (squares) nodes, and its profiles.

parsing scheme and digital search trees by assuming a random model based on independent memoryless input strings. They also analyzed digital tries with Markovian dependency [START_REF] Jacquet | Analysis of Digital Tries with Markovian Dependency[END_REF]. There is a more general random model of dynamical sources but in this case the technicalities are usually more involved [START_REF] Lothaire | Applied Combinatorics on Words[END_REF][START_REF] Szpankowski | Average Case Analysis of Algorithms on Sequences[END_REF]. Furthermore, Louchard and Szpankowski [START_REF] Louchard | Average Profile and Limiting Distribution for a Phrase Size in the Lempel-Ziv Parsing Algorithm[END_REF] studied the average profile and limiting distribution for the phrase size in the Lempel-Ziv parsing algorithm, Jacquet and Régnier [START_REF] Jacquet | Trie Partitioning Process: Limiting Distributions[END_REF] discussed the limiting distribution in a trie partitioning process, and Knessl and Szpankowski [START_REF] Knessl | Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme[END_REF] analyzed the asymptotic behavior of the height in a digital search tree and the longest phrase of the Lempel-Ziv scheme. They also considered the average profile of symmetric digital search trees [START_REF] Knessl | On the Average Profile of Symmetric Digital Search Trees[END_REF] (which means that all letters in the memoryless source appear with the same frequency). Louchard [START_REF] Louchard | Exact and Asymptotic Distributions in Digital and Binary Search Trees[END_REF] provided an exact and asymptotic distribution in digital search trees.

Recently Park et al. [START_REF] Park | Profile of Tries[END_REF][START_REF] Park | Profile of Tries[END_REF] studied the external and internal profiles of tries (with memoryless input strings) and provided a very detailed picture on the asymptotic behaviour of the provile (expected value, variance, limiting distribution). For digital search trees (DST) Drmota and Szpankowski [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] proved asymptotic results on the average profile which are similar to those for tries. The purpose of this paper is to extend their analysis to asymptotics for the variance of the profile.

Before we state our results we recall the construction of a digital search tree (DST) which stores (binary) input strings in its internal nodes. The root contains the first string, and the next string occupies the right or the left child of the root depending on whether its first symbol of the next string is 0 or 1. At each level of the tree a different bit of the key is checked; if the bit is 0, the search continues down the left subtree, if it is 1, the search continues down the right subtree. The remaining strings are stored in available nodes which are directly attached to nodes already existing in the tree, as shown in Figure 1 [START_REF] Knuth | The Art of Computer Programming[END_REF][START_REF] Mahmoud | Evolution of Random Search Trees[END_REF][START_REF] Sedgewick | Algorithms in C: Fundamental Algorithms, Data Structures, Sorting, Searching[END_REF].

Let B n,k be the number of external nodes at level k when n strings are sorted. We study the external profile built over n binary strings generated by a memoryless source, that is, we assume each string is a binary i.i.d. sequence with p being the probability of a "1" (0 < p < 1); we also use q := 1 -p and assume that p < q. We also mention that symmetric DST's, i.e. p = q = 1 2 , are not covered by our analysis because for p < q, g(s, w) is an analytic function for |w| < 1/T (s) where T (s) = p -s + q -s and the saddle point analysis fails for p = q [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF]. In this case we expect a completely different behaviour and also the use of different methods, see also the discussion of the symmetric case in [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF].

In order to state our main result we need the following notations. For a real number α with (log 1 p ) -1 < α < (log 1 q ) -1 , let ρ = ρ(α) be defined by the equation

α = p -ρ + q -ρ p -ρ log 1 p + q -ρ log 1 q .
Explicitly, ρ(α) is given by

ρ = ρ(α) = 1 log(p/q) log 1 -α log(1/p) α log(1/q) -1 .
Furthermore set

β(ρ) = p -ρ q -ρ log(p/q) 2 (p -ρ + q -ρ ) 2 .
Theorem 1 Let Var(B n,k ) denote the variance of the profile in unbalanced digital search trees with underlying probabilities 0 < p < q = 1 -p. Let k and n be positive integers such that k/ log n satisfies (log

1 p ) -1 + ε ≤ k/ log n ≤ (log 1 q ) -1 -ε. Then uniformly Var(B n,k ) = L ρ n,k , log p/q p k n (p -ρ n,k + q -ρ n,k ) k n -ρ n,k 2πβ(ρ n,k )k 1 + O 1 √ k , (1)
where ρ n,k = ρ(k/ log n) and L(ρ, x) is a non-zero periodic function with period 1 in x.

Remark 1 The function L(ρ, x) can be represented as L(ρ, x)

= j∈Z f (ρ + it j )Γ(ρ + it j )e -2jπix
, where f (s) has the form f (s) = g(s -1, 1/T (s))D(s, 1/T (s))

and the functions g(s, w) and D(s, w) are described in [START_REF] Park | Profile of Tries[END_REF] and in Lemma 3, respectively. However, it is not really explicit.

This theorem shows that the variance Var(B n,k ) is of the same order of magnitude as the expected value E(B n,k ). In particular it follows that B n,k is concentrated around its expected value. The function L has small amplitude and their oscillations are consequences of an infinite number of saddle-points appearing in the integrand of the associated Mellin transform. The only difference between two asymptotic formulas is in function L for two different function f . The same phenomenon has been observed for tries [START_REF] Park | Profile of Tries[END_REF][START_REF] Park | Profile of Tries[END_REF] where it was also shown that B n,k satisfies a central limit theorem. It would be natural to expect a corresponding behaviour for DST's, however, the methods of [START_REF] Park | Profile of Tries[END_REF][START_REF] Park | Profile of Tries[END_REF] are not applicable in the present situation.

In order to analyze the variance we use the so-called Poisson variance V k (x) as a (hopefully) good approximation of the variance of the profile Var(B n,k ) [START_REF] Park | Profile of Tries[END_REF] if we set x = n. It is defined by

V k (x) := ∆ k (x, 1) + ∆ k (x, 1) -∆ k (x, 1) 2 , where ∆ k (x, u) = ∞ n=0 E(u B n,k )e -x x n n!
and ∆ k (x, 1) and ∆ k (x, 1) denote the first and the second derivative of ∆ k (x, u) with respect to u at u = 1, respectively. It turs out that the Poisson variance satisfies a recurrence [START_REF] Knessl | Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel-Ziv Scheme[END_REF] that is quite similar to that of the "Poisson expectation" ∆ (1)

k (x) = ∞ n=0 E(B n,k )e -x x n
n! , see [START_REF] Flajolet | Analytic Combinatorics[END_REF], in particular the inhomogeneous part in ( 10) is relatively small. This suggests suggests that the asymptotics of the variance should be of the same order of magnitude as for the expected value. In order to make this heuristics rigorous we have to overcome several technical difficulties. First we have to obtain an explicit solution for F

(3) k (s) of ( 11) which is the most difficult part (Section 2). Then we have to find proper asymptotics for F

(3) k (s) and to invert then Mellin transform of V k (x). This leads us to an infinite number of saddle points (cf. also [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] and [START_REF] Park | Profile of Tries[END_REF]). The final step will be to show that the Poisson variance of V k (n) is asymptotically equal to Var(B n,k ). The reader is referred to [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] and [START_REF] Park | Profile of Tries[END_REF] for a detailed discussion of the above mentioned tools that belong to analytic combinatorics.

Generating Functions

In this section we recall (and extend) the combinatorial analysis of DST's with the help of generating functions.

Basic relations

As already introduced, B n,k denotes the (random) number of external nodes at level k in a digital search tree built over n strings generated by a memoryless source with parameter q > p = 1 -q. We recall the initial conditions

B n,0 = 1 for n = 0, 0 for n ≥ 1.
The probability generating function of the external profile, P n,k (u) = E u B n,k , satisfies the following recurrence relation (cf. [START_REF] Jacquet | Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees[END_REF])

P n+1,k (u) = n j=0 n j p j q n-j P j,k-1 (u)P n-j,k-1 (u). (2)
with initial conditions P 0,k (u) = 1 for k ≥ 1, P 0,0 (u) = u, P n,0 (u) = 1 for n ≥ 1. The corresponding exponential generating function

G k (x, u) = n≥0 P n,k (u) x n n! fulfills the following functional recurrence ∂ ∂x G k (x, u) = G k-1 (px, u)G k-1 (qx, u), k ≥ 1, (3)
with initial conditions G 0 (x, u) = u + e x -1 and G k (0, u) = 1 (k ≥ 1)
. By taking derivatives with respect to u and setting u = 1 we obtain for the exponential generating function

E (1) k (x) = n≥0 E(B n,k )
x n n! the following functional recurrence

E (1) k (x) = e qx E (1)
k-1 (px) + e px E

(1)

k-1 (qx), (4)
with initial conditions E

(1) 0 (x) = 1 and E

(1)

k (0) = 0 (k ≥ 1). The Poisson transform of E (1) k (x), namely ∆ (1) k (x) = e -x n≥0 E(B n,k ) x n n! = e -x E (1)
k (x), k ≥ 0 translates recurrence (4) into ∆ (1) k (x) + ∆ (1) k (x) = ∆ (1) k-1 (px) + ∆ (1) k-1 (qx), k ≥ 1, (5)
with initial conditions ∆

(1) 0 (x) = e -x and ∆

(1)

k (0) = 0 (k ≥ 1)
. Similarly, by taking second derivatives with respect to u and setting u = 1 we obtain for the exponential generating function

E (2) k (x) = n≥0 E(B 2 n,k )
x n n! the following functional recurrence

E (2) k (x) = e qx E (2)
k-1 (px) + e px E (2)
k-1 (qx) + 2E

(1)

k-1 (px)E (1)
k-1 (qx), (6)
with initial conditions E

(2)

0 (x) = 1 and E (2)
k (0) = 0 (k ≥ 1). Furthermore, the Poisson transform of E (2) k (x), namely ∆ (2) k (x) = e -x n≥0 E(B 2 n,k ) x n n! = e -x E (2) k (x), k ≥ 0 translates recurrence (6) into ∆ (2) k (x) + ∆ (2) k (x) = ∆ (2) k-1 (px) + ∆ (2) k-1 (qx) + w k (x), k ≥ 1. (7)
where

w k (x) = 2∆ (1)
k-1 (px)∆

(1)

k-1 (qx), ∆ (2)
0 (x) = e -x and ∆

(2)

k (0) = 0 (k ≥ 1)
. By induction it is easy to prove that ∆ (2) k (x) can be represented as finite linear combinations of functions of the form e -p 1 q 2 x with 1 , 2 ≥ 0, and of products of two of these functions. Hence, the Mellin transform of ∆

(2) k (x) (see [START_REF] Flajolet | Analytic Combinatorics[END_REF])

∆ * (2) k (s) = ∞ 0 ∆ (2) k (x)x s-1 dx.
exists for all s with (s) > 0. Since B n,k = 0 for k > n it follows that E

(2)

k (x) = O(x k ) as x → 0 which ensures that ∆ * (2) k
(s) actually exists for s with (s) > -k.

Let us now express ∆ * (2) k (s) as

∆ * (2) k (s) = Γ(s)F (2) k (s)
where Γ(s) is the Euler gamma function. By definition we know that F

k (s) is the finite linear combinations of functions a -s (with certain values of a). Thus, F

k (s) is an entire function. Furthermore [START_REF] Jacquet | Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees[END_REF] translates into F

(2)

k (s) -F (2)
k (s -1) = T (s)F (2)
k-1 (s) + H

(2)

k (s), k ≥ 0, (8)
where

H (2) k (s) = 1 Γ(s) ∞ 0 w k (x)x s-1 dx,

and F

(2) 0 (s) = 1. Note that (8) does not only hold for (s) > -k where the Mellin transform exists. Since F

(2) k (s) continues analytically to an entire function, ( 8) holds for all s, too. The inhomogeneous part in ( 8) is very large compared to the order of magnitude of the homogeneous equation

F (1) k (s) -F (1) k (s -1) = T (s)F (1) k-1 (s), k ≥ 0, (9)
for the first moment (compare with [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF]). Since F

k (s) behaves geometrically as T (s) k it seems that the term F

(1) k+1 (s -1) is negligible compared to the other two terms in (9) [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF]. This phenomenon will also occur for F

k (s) (Section 2.3). We introduce the so-called Poisson variance

V k (x) := ∆ (2) k (x) -∆ (1) k (x) 2
which should be a good approximation for the variance of the profile ( [START_REF] Jacquet | Analytical Depoissonization and Its Applications[END_REF]). By ( 5) and ( 7), V k (x) satisfies

V k (x) + V k (x) = V k-1 (px) + V k-1 (qx) + ∆ (1) k (x) 2 , (10)
with initial condition V 0 (x) = e -x (1 -e -x ) and V k (0) = 0 (k ≥ 1). The Mellin transform of V k (x) is then given as

V * k (s) = ∞ 0 V k (x)x s-1 dx,
and again, we can use a factorization of the form

V * k (s) = Γ(s)F (3) k (s),
where V * k (s) and F

(3)

k (s) can be written in terms of ∆ * (1) k (s), ∆ * (2) k (s), F (1)
k (s), and F

k (s) respectively. In particular, (10) translates into

F (3) k (s) -F (3) k (s -1) = T (s)F (3) k-1 (s) + H (3) k (s), k ≥ 0, (11)
where H

(3)

k (s) = 1 Γ(s) ∞ 0 ∆ (1) k (x) 2 x s-1 dx and also F (3) 0 (s) = 1 -2 -s . We also observe that F (3) k (-r) = 0 for k > r, since Γ(s)F (3)
k (s) is the Mellin transform of V k (x) that exists for (s) > -k. We will use this property several times.

Analysis of F

(1) k (s) Before we will find a solution of ( 8) or [START_REF] Knessl | On the Average Profile of Symmetric Digital Search Trees[END_REF] we recall (and extend) some facts of F (1) k (s) (see [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF]). We define the power series

f (i) (s, w) = k≥0 F (i) k (s)w k , i = 1, 3. (12)
Furthermore we introduce the function operator A as follows

A[f ](s) = j≥0 f (s -j)T (s -j). (13)
We also set

R k (s) = A k [1](s) and g(s, w) = k≥0 R k (s)w k = (I -wA) -1 [1](s). (14)
By the way it is easy to compute R k (s) for a few small values of k. For example,

R 0 (s) = 1, R 1 (s) = p -s 1 -p + q -s 1 -q , R 2 (s) = p -2s (1 -p)(1 -p 2 ) + p -s q -s (1 -p)(1 -pq) + p -s q -s (1 -q)(1 -pq) + q -2s (1 -q)(1 -q 2 )
.

In general we have a representation of the form

R k (s) = k i=0 k i c k,i p i q k-i -s , (15)
where the coefficients c k,i are uniformly bounded by

1 ≤ c k,i ≤ C
for some constant C just depending on p and q.

It is also easy to verify that R k (s) satisfies the recurrence

R k (s) -R k (s -1) = T (s)R k-1 (s) (16)
and satisfies R k (-∞) = 0 (k ≥ 1). From ( 14) and ( 16) we obtain g(s, w) = g(s -1, w)/(1 -wT (s)) and consequently

g(s, w) = j≥0 1 1 -wT (s -j) . ( 17
)
This shows that w = 1/T (s) is the dominanting polar singularity of the mapping w → g(s, w) (if s is sufficiently close to the real axis) and it also follows that

R k (s) ∼ T (s) k j≥1 (1 -T (s -j)/T (s))
as k → ∞. Actually this asymptotics is uniform for real s ≥ 0. By ( 15) it also follows that

|R k (s)| ≤ R k ( (s)) = O T ( (s)) k .
Next we turn to F

k (s) which satisfies the same recurrence ( 16) as R k (s). Hence we expect a similar representation for the generating function f (1) (s, w). However, we have different initial conditions, namely F

(1) k (0) = 0 (k ≥ 1) or f (1) (0, w) = 1. Anyway, it follows (as above) that

f (1) (s, w) = k≥0 F (1) k (s)w k = g(s, w) g(0, w) . ( 18
)
Note that the mapping w → 1/g(0, w) is an entire function. Hence, w = 1/T (s) is again the dominating polar singularity (if s is sufficiently close to the real axis). Consequently

F (1) k (s) ∼ j≥0 (1 -T (-j)/T (s)) ≥1 (1 -T (s -)/T (s)) T (s) k .
This is also one of the main observations of [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF]. It follows from (18) that F

k (s) is a linear combination of R (s), 0 ≤ ≤ k, which also shows that F

(1) k (-∞) exists because R k (0) = 0 for all k (see the proof of Theorem 3 in [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF]). Furthermore, since the ratio f (1) (s, w)/g(s, w) = 1/g(0, w) is independent of s it follows that f (1) (0, w) g(0, w) = f (1) (-∞, w) g(-∞, w) .

However, we have f (1) (0, w) = g(-∞, w) = 1 which implies that

f (1) (-∞, w) = k≥0 F (1) k (-∞)w k = 1 g(0, w) = j≥0 (1 -wT (-j)) .
This also shows that f (1) (s, w) = g(s, w)f (1) (-∞, w) or that we have the explicit representation

F (1) k (s) = k =0 F (1) k-(-∞)R (s). ( 19
)
We also note that

|F (1) k (-∞)| = O(η k ) ( 20
)
for all (fixed) η > 0. This follows from the fact that the mapping w → 1/g(0, w) is an entire function.

Next, we use the estimate |F

(1)

k (s)| ≤ CT ( (s)) k to obtain (with c = (s)/2) G 1, 2 (s) ≤ C 2 2πi|Γ(s)| c+i∞ c-i∞ |Γ(t)||Γ(s -t)| T ( (t) -1) 1 T ( (s -t) -1) 2 dt ≤ C (s) T ( (s)/2 -1) 1+ 2 (25)
Finally by using [START_REF] Prodinger | Digital Search Trees and Basic Hypergeometric Functions[END_REF] and the explicit representation [START_REF] Szpankowski | A Characterization of Digital Search Trees From the Successful Search Viewpoint[END_REF] we also obtain (24). 2

The next lemma is crucial for the solution of our problem.

Lemma 2 There exists a function D 0 (s, w) such that

D 0 (s, w) -D 0 (s -1, w) = 1 g(s -1, w) k≥1 H (3) k (s) w k (26)
and that the mapping w → D 0 (s, w) is analytic for |w| < 1/T ( (s)/2 -1) 2 .

Proof: Let L k (s) be defined by

k≥0 L k (s)w k = 1 g(s -1, w) = j≥1 (1 -wT (s -j)) .
By definition it is clear that L k (s) is a linear combination of terms of the form (p k1 q k2 ) -s , where all coefficients have the same sign. Furthermore, since 1/g(s, w) is an entire function, we have L k (s) = O(η k ) for every (fixed) η > 0.

We will show that for every k ≥ 1 there exists a function D k (s) with

D k (s) -D k (s -1) = k m=1 L k-m (s)H (3) m (s) (27)
= k m=1 L k-m (s) m 1=0 m 2=0 F (1)
m-1 (-∞)F

(1)

m-2 (-∞)G 1, 2 (s)
and with an upper bound of the form

D k (s) = O min{1, |s|} T ( (s)/2 -1) 2k . (28)
By Lemma 1 and by the definition of L k (s) it follows that L k-m (s)G 1, 2 (s) is a linear combination of functions of the form a -s (for certain positive numbers a), where all coefficients have the same sign. Furthermore, there is only a bounded number of real numbers a appearing there with a ≥ 1. Recall that a is of the form p k1 q k2 p i q 1-i + p j q 2-j .

This bound is also independent of k, m, 1 , 2 . Next observe that

a -s = a -s 1 -a - a -(s-1) 1 -a for a = 1 and that a -s = 1 = s -(s -1)
for a = 1. Hence, each term of the form a -s can be written as a difference of the form d(s) -d(s -1).

Of course, this implies the existence of a function D k (s) satisfying (27).

Let us consider one of the terms L k-m (s)G 1, 2 (s). Recall that we already know that L k-m (s)G 1, 2 (s) = O(η k-m T ( (s)/2 -1) 1+ 2 ), where η > 0 is arbitrary. We split it up into a sum

L k-m (s)G 1, 2 (s) = A(s) + B(s),
where A(s) contains all terms of the form a -s with a < 1 and B(s) the remaining ones. Since all coefficients have the same sign, A(s) and B(s) can be bounded from the above as A(s) + B(s). By the above observation we can represent A(s) as A(s) = d 1 (s) -d 1 (s -1), where

d 1 (s) = O(A( (s))) = O(η k-m T ( (s)/2 -1) 1+ 2 ). Similarly we have B(s) = d 2 (s) -d 2 (s -1) with d 2 (s) = O(B( (s))) = O(min{1, |s|} η k-m T ( (s)/2 -1) 1+ 2 ).
Note also that the constants that are implied by the O-notation are uniform, they only depend on p and q. Putting all these estimates together we immediately deduce (28).

Finally, we set

D 0 (s, w) = k≥0 D k (s)w k
which is analytic for |w| < 1/T ( (s)/2 -1) 2 . 2

We are now ready to state and prove a proper representation for f (3) (s, w).

Lemma 3

The function f (3) (s, w) can be represented as f (3) (s, w) = D(s, w)g(s, w), where D(s, w) is analytic for |w| < 1/T ( (s)/2 -1) 2 .

We recall that the dominating singularity of g(s, w) is w = 1/T (s). Since we have the relation

T σ 2 -1 2 < T (σ)
the function D(s, w) is analytic in a region containing this singularity. Hence g(s, w) dominates the behaviour of f (3) (s, w) as was the case with f (1) (s, w). Therefore we can expect that F

k (s) behaves similarly as F

(1) k (s) which turns out to be true, see Section 3. Proof: From (11) it follows that f (3) (s, w) satisfies

f (3) (s, w)(1 -wT (s)) = f (3) (s -1, w) + h(s, w),
uniformly for all s with (s) ∈ [a, b], | (s) -2 π log(q/p)| ≤ ε for some integer and k ≥ k 0 , where

f (s) = D(s, 1/T (s))g(s -1, 1/T (s))
is an analytic function that satisfies f (-r) = 0 for r = 1, 2, . . . and is bounded in this region.

Furthermore, if | (s) -2 π log(q/p)| > ε for for all integers then we have for some η > 0 that can be chosen to be uniform for (s) ∈ [a, b]. Furthermore, by the representation [START_REF] Park | Profile of Tries[END_REF] it is clear that w = 1/T (s) is the dominant (and polar) singularity of g(s, w) if s is sufficiently close to the real axis, that is, | (s)| ≤ ε for some ε > 0 that can be be chosen to be uniform for (s) ∈ [a, b]. Since T (s + 2 πi log(q/p)) = e -2πi log(p)/ log(q/p) T (s).

F (3) k (s) = O T ( (s)) k e -γk . (30
this is also true if | (s) -2 π log(q/p)| ≤ ε for some integer .

Next we apply Cauchy's formula for a contour of integration on the circle |w| = e γ /T (s) (for some sufficiently small γ > 0) and the residue theorem it follows that

[w k ]f (3) (s, w) = 1 2πi |w|= e γ /T (s) f (3) (s, w) dw w k+1 = -Res f (3) (s, w)w -k-1 ; w = 1 T (s) + O |T (s)e -γ | k = f (s)T (s) k + O |T (s)e -γ | k , where f (s) = D(s, 1/T (s))g(s -1, 1/T (s))
These estimates are uniform for s contained in a compact interval [a, b]. However, note that f (-r) = 0 for non-negative integer r, since F

k (-r) = 0. Hence, if the interval [a, b] contains a non-positive integer then we multiply by Γ(s) and do completely the same calulations which give (after all) the expansion (29).

Finally, if | (s) -2πi / log(q/p))| > ε for some integer , then there exists γ > 0 such that |T (s)| < e -2γ |T ( (s)|. Hence it follows that f (3) (s, w) is regular for |w| < e 2γ /T ( (s)). Thus, for a contour of integration on the circle |w| = e γ /T ( (s)) in Cauchy's formula we obtain

[w k ]f (3) (s, w) = O T ( (s)) k e -γk .
This completes the proof of Theorem 1. 2

Proof of Theorem 1

In this section, we show that the Poisson variance is asymptotically equal to the variance of the profile. i.e., V k (n) ∼ Var(B n,k ). For this goal, we use the same technique of [START_REF] Park | Profile of Tries[END_REF][START_REF] Park | Profile of Tries[END_REF]. First we prove the following Lemma that is necessary for proving the our main result.

uniformly for |θ| ≤ θ 1 , where θ 1 ≥ n -1/2+ε and δ(n) = o(n -1/2 ), then for any 0 ≥ 2,

a n = 0≤ < 0 f ( ) (n) ! τ (n) + O n 0/2 δ(n) 0 f (n) , (35)
where τ (n) = ![x ](1 + x) n e -nx . In particular

a n = f (n) - n 2 f (n) + O n 2 δ 4 (n) f (n) .
Thus ∆

(2)

k (x) = V k (x) + ∆ (1)
k (x)

2 also satisfies conditions of Lemma 6 and

E(B 2 n,k ) = ∆ (2) k (n) - n 2 ∆ (2) k (n) + O ρ 4 n -2 ∆ (2) k (n) . Also E(B n,k ) 2 = ∆ (1) k (n) - n 2 ∆ (1) k (n) + O ρ 4 n -2 ∆ (1) k (n) 2 = ∆ (1) k (n) 2 -n∆ (1) k
(n)∆

(1)

k (n) + O ρ 4 n -2 (∆ (1)
k (n)) 2 .
Therefore

Var(B n,k ) = E(B 2 n,k ) -E(B n,k ) 2 = V k (n) 1 + O ρ 2 n -1 E(B n,k ) , namely, Var(B n,k ) ∼ V k (n). 2

)

  uniformly for (s) ∈ [a, b]. Proof: Since D(s, w) is analytic for |w| < T ( (s)/2-1) -2 it is also analytic for |w| < T ( (s))-η -1

Lemma 6

 6 Let f (x) := n≥0 a n x n /n! be an entire function, where a n is a given sequence, and f (x) := e -x f (x). If x = re iθ and |f (x)| ≤ c 1 log rf (r)e -rc2θ 2holds uniformly for r ≥ 1, c 1 , c 2 > 0, and |θ| ≤ π, where f (r) ≥ 0, andf ( ) (ne iθ ) = O δ(n) f (n) , = 0, 1, 2, ....,

Proof:n - 2 / 5 e

 25 By the Cauchy formula and upper bound of f (x),a n = n! 2πi |x|=n,| arg(x)|≤n -2/5 x -n-1 e x f (x)dx + O n!n -n log nf (n) ∞ -c2nθ 2 dθ .By Stirling's formula the O-term is equal toO n 1/2 log n f (n)n -1/2 e -c2n 1/5 = O log ne -c2n 1/5 f (n) ,which is negligible in comparison to the main term f (n). The proof is completed similarly to [18, Propo-sition 1].2Proof: (Theorem 1) By[START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] Lemma 6],|e x ∆ (1) k (x)| ≤ c 1 e r ∆(1)k (r) log re -rc2θ 2 for r ≥ 1, c 1 , c 2 > 0,and |θ| ≤ π. We can obtain such upper bound for |e x V k (x)|. By [18, Lemma 4] and Lemma 5 (above) for δ(n) = ρ/n, iθ ) = O ρ n -V k (n) .

Acknowledgements

The first author would like to thank Professor Michael Drmota for suggesting this topic of research. He had the pleasure of meeting him in Vienna. The authors would like to thank the anonymous referees for their valuable comments leading to the improvement of our manuscript.

Remark 2 The analysis of F

(1) k (s) that was given in [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] is not as direct as the approach given here. In [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] it was observed that the recurrence [START_REF] Jacquet | Trie Partitioning Process: Limiting Distributions[END_REF] translates to the relation

which can be translated to the power series representation [START_REF] Park | Profile of Tries[END_REF]. Both approaches use the fact that the limit F [START_REF] Coffman | File structures using hashing functions[END_REF] k (-∞) exists.

Analysis of F

(3)

The main difference between the recurrence [START_REF] Jacquet | Trie Partitioning Process: Limiting Distributions[END_REF] for F [START_REF] Coffman | File structures using hashing functions[END_REF] k (s) and the recurrence [START_REF] Knessl | On the Average Profile of Symmetric Digital Search Trees[END_REF] for

The main problem with this inhomogeneous part is -as we will show in a moment -that the limit H

k (-∞) does not exist. First we derive a proper representation for H

k (s) . Lemma 1 The function H

(3) k (s) can be represented by the sum

where

(with c = (s)/2). Furthermore we have uniformly for

and H

(3)

Proof: The representations ( 22) and ( 23) are immediate from [START_REF] Sedgewick | Algorithms in C: Fundamental Algorithms, Data Structures, Sorting, Searching[END_REF] and from [START_REF] Pittel | Asymptotic Growth of a Class of Random Trees[END_REF]. We also can use the property that (e -ax e -bx ) = -(a + b)e -(a+b)x and that its Mellin transform is given by Γ

Setting D(s, w) = f (3) (s, w)/g(s, w) and by using the relation g(s, w) = g(s -1, w)/(1 -wT (s)) it follows that

Hence, D(s, w) and D 0 (s, w) differ by a function C(s, w) that is periodic in s (with period 1). However, since ∆

k (x) and ∆

k (x) are linear combinations of functions of the form e -(p i q j )x it follows that the Mellin transform of

2 has no periodic parts. Consequently, we have

for some function K(w).

Next we observe that for every non-negative integer m the function f (3) (-m, w) is a polynomial in w. This follows from the fact that

We now choose -m ≤ (s). Then this representation implies that D(s, w) is analytic for |w| < 1/T ( (s)/2 -1) 2 . 2

Asymptotic Analysis

We now prove Theorem 1 by establishing the asymptotic behavior of the variance of the profiles. The plan of the proof is as follows. First we concentrate on the singularity analysis of f (3) (s, w) and obtain an asymptotic expansion for F

k (s). Second we invert the Mellin transform V * k (s) by a proper saddle point method of the dominant part T (s) k x -s = exp k log T (s) -s log x of the integrand in the inverse Mellin integral. Finally we show Var(B n,k ) ∼ V k (n) by standard depoissonization methods [START_REF] Park | Profile of Tries[END_REF].

Singularity Analysis of f (3) (s, w)

In order to obtain asymptotic information for F

(3) k (s) we will analyze the generating function f (3) (s, w) that by Lemma 3 is given by f (3) (s, w) = D(s, w)g(s, w).

Since we will apply the inverse Mellin transform to V * k (s) = Γ(s)F

(29)

Saddle Point Analysis

By the discussion of Lemma 4, we see that F (s). Thus we are in the same situation as in the analysis of the average profile presented in [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF]. Our asymptotic analysis will be therefore similar to that of [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] with a new function A(s) (here called f (s)) that is also equal to zero for -1, -2, -3, ... .

We start with a very short outline of the proof. By applying the inverse Mellin transform in case x = n,

it is natural to choose ρ = ρ n,k as the saddle point of the function

Note also that on the line (s) = ρ there will be infinitely many saddle points

since T (s j ) = e -2πij(log p)/(log p/q) T (ρ), consequently the behaviour of T (s) k z -s around s = s j is almost the same that of T (s) k z -s around s = ρ. This phenomenon gives a periodic leading factor in the asymptotics of V k (x). By Lemma 4, we can safely replace F

k (s) by f (s)T (s) k since the error term is of order O(|T (s)| k e -γk ) and leads to an exponentially small contribution compared to the asymptotic leading term.

We describe the following lemma for the Poisson variance V k (n) and in the next section we will show that Var(B n,k ) ∼ V k (n) in the given range. Lemma 5 Let V k (x) denote the Poisson variance of profile in unbalanced digital search trees with underlying probabilities 0 < p < q. Let k and n be positive integers such that k/ log n satisfies (log 1 p ) -1 + ε < k/ log n < (log 1 q ) -1 -ε. Then uniformly

where the periodic function L(ρ, x) has the following representation L(ρ, x) = j∈Z f (ρ + it j )Γ(ρ + it j )e -2jπix , t j = 2jπ/ log(p/q). (32)

Furthermore, for x = ne iθ , where |θ| ≤ π/2 -ε (for some ε > 0), we still have uniformly

where j 0 abbreviates j 0 = √ log n log(p/q)/(2π).

Proof: The proof is quite identical to that of Lemma 5 in [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] for a new function f (s), see [START_REF] Drmota | The Expected Profile of Digital Search Trees[END_REF] in detail. 2


Andrzej Dudek

David Wajc '

On the complexity of vertex-coloring edge-weightings

Keywords: vertex-coloring, 1-2-3 conjecture, NP-completeness

Given a graph G = (V, E) and a weight function w : E → R, a coloring of vertices of G, induced by w, is defined by χw(v) = e v w(e) for all v ∈ V . In this paper, we show that determining whether a particular graph has a weighting of the edges from {1, 2} that induces a proper vertex coloring is NP-complete.

Introduction

For a given graph G = (V, E), let w : E → R be a weight function. We say that w is proper if the coloring of the vertices χ w (v) = e v w(e), v ∈ V , is proper. In 2004, [START_REF] Karoński | Edge weights and vertex colours[END_REF] showed that any graph with no components isomorphic to K 2 has a proper weighting from a finite set of reals. Furthermore, they conjectured that every graph with no components isomorphic to K 2 has a proper weighting from W = {1, 2, 3}. Addario-Berry, [START_REF] Addario-Berry | Vertex-colouring edgeweightings[END_REF] showed that the above holds if W = {1, . . . , 30}. This result was improved by [START_REF] Addario-Berry | Degree constrained subgraphs[END_REF], who showed that one can take W = {1, . . . , 16}. Subsequently, [START_REF] Wang | On vertex-coloring 13-edge-weighting[END_REF] proved that W = {1, . . . , 13} suffices. A recent breakthrough by [START_REF] Kalkowski | Vertex-coloring edge-weightings: Towards the 1-2-3conjecture[END_REF] showed that the set of weights can be as small as W = {1, 2, 3, 4, 5}.

On the other hand, [START_REF] Addario-Berry | Degree constrained subgraphs[END_REF] showed that almost all graphs have a proper weighting from {1, 2}. In this paper, we show that determining whether a particular graph has a proper weighting of the edges from {1, 2} is NP-complete. Consequently, there is no simple characterization of graphs with proper weightings from {1, 2}, unless P=NP. Formally, let 1-2WEIGHT = {G : G is a graph having a proper weighting from {1, 2}} . † Email: andrzej.dudek@wmich.edu. ‡ Email: sdavidwa@cs.technion.ac.il This work was performed while the author was visiting Carnegie Mellon University. Theorem 1.1 1-2WEIGHT is NP-complete.

Before we prove this statement, we consider a similar theorem with a somewhat simpler proof, which we use as a template to prove Theorem 1.1. By analogy to 1-2WEIGHT we denote by 0-1WEIGHT the family of graphs with a proper weighting from {0, 1} and show the following:

Theorem 1.2 0-1WEIGHT is NP-complete.
2 0-1WEIGHT is NP-complete

Here we prove Theorem 1.2. First note that 0-1WEIGHT is clearly in NP, since one can verify in polynomial time for a given graph whether a weighting of its edges from {0, 1} is proper.

Next we consider the well-known NP-hard problem 3-COLOR = {G : G is a graph having a proper 3-vertex-coloring} .

In order to prove that 0-1WEIGHT is NP-hard (and hence NP-complete), we show a reduction from 3-COLOR to 0-1WEIGHT. To this end, we define a polynomial time reduction h, such that G ∈ 3-COLOR if and only if h(G) ∈ 0-1WEIGHT. To achieve this, we need two auxiliary gadgets. We refer to the first gadget as a triangle gadget. This consists of a triangle xab, with x referred to as the top and with a and b each having no other coinciding edges. Note that any proper weighting w from {0, 1} of a graph with such a triangle must hold w(xa) = w(xb); otherwise χ w (a) = w(ab) + w(ax) = w(ba) + w(bx) = χ w (b). Hence, {w(xa), w(xb)} = {0, 1} and so every such triangle gadget contributes exactly 1 to χ w (x).

The second gadget, called a k-disallowing gadget, consists of a main triangle vxy with v referred to as the root and with x and y each constituting the top of k -1 distinct triangle gadgets (see Figure 1(a)). Note that in any proper weighting w from {0, 1}, w(vx) = w(vy); otherwise, as both χ w (x) and χ w (y) have k -1 contributed by x and y's triangles,

χ w (x) = w(xv) + w(xy) + k -1 = w(yv) + w(yx) + k -1 = χ w (y). Therefore, if w(xy) = 0 then {χ w (x), χ w (y)} = {k -1, k} and, if w(xy) = 1 then {χ w (x), χ w (y)} = {k, k + 1}.
In either case, v has one neighbor z ∈ {x, y} with χ w (z) = k, and consequently, χ w (v) = k in any proper weighting from {0, 1}. Also {w(vx), w(vy)} = {0, 1} and hence this gadget contributes exactly 1 to χ w (v). Now we are ready to show a reduction from 3-COLOR to 0-1WEIGHT, h, such that G ∈ 3-COLOR if and only if h(G) ∈ 0-1WEIGHT. Let G = (V, E) be a graph of order n. We may assume that n ≥ 3. Otherwise, n ≤ 2 and G is in 3-COLOR and so it suffices to take as h(G) an empty graph which is trivially in 0-1WEIGHT. For n ≥ 3 we construct the graph h(G) = (W, F ) as follows (see Figure 1(c)). We start with G = (V, E). For each v ∈ V :

(i) connect v to two new vertices, s and t (distinct for each v);

(ii) add n -1 new k-disallowing gadgets for all k ∈ {n + 2, n + 3, . . . , 2n} with v as their root.

Clearly, h(G) can be calculated in time polynomial in the size of G.

Fact 2.1 In h(G) the following holds: any proper weighting w from {0, 1} satisfies χ w (v) ∈ {n -1, n, n + 1} for every v ∈ V .

Proof: Fix v ∈ V . Since w(vs) + w(vt) ∈ {0, 1, 2}, v is the endpoint of deg(v) ≤ n -1 edges in V ,
and v is the root of (n -1) k-disallowing gadgets (each contributing 1 to χ w (v)), we have:

χ w (v) ∈ {0, 1, 2} + {0, 1, . . . , deg(v)} + {n -1} ⊆ {n -1, n, . . . , 2n},
where by A + B we mean the set of all sums of an element from A with an element from B. Observing the above and the fact that v is the root of k-disallowing gadgets for all k ∈ {n + 2, . . . , 2n}, we find that any proper weighting w from {0, 1} satisfies χ w (v) ∈ {n -1, n, n + 1}, as claimed.

2

It remains to show that G ∈ 3-COLOR if and only if h(G) ∈ 0-1WEIGHT. First let us assume that G ∈ 3-COLOR. That means there exists a proper 3-coloring of G, say χ : V → {n -1, n, n + 1}. We define a weighting of the edges of h(G), w : F → {0, 1} as follows. For all e ∈ E let w(e) = 0. For all v ∈ V , if χ(v) = n -1 then w(vs) = w(vt) = 0; otherwise, if χ(v) = n then w(vs) = 1 and w(vt) = 0; and finally, if χ(v) = n+1 then w(vs) = w(vt) = 1. All other edges (parts of gadgets) are weighted as follows: For a triangle gadget xab with root x, w(xa) = 1, w(xb) = w(ab) = 0. For a k-disallowing gadget with root v, and main triangle vxy, w(vx) = w(xy) = 1, w(vy) = 0, and the weighting of all other triangle gadgets as described above. Note that w is a proper weighting of h(G) (satisfying χ w (v) = χ(v) for all v ∈ V ), as required. Now let us assume that G / ∈ 3-COLOR. Therefore, for all χ : V → {n -1, n, n + 1}, χ is not proper. But, from Fact 2.1, any proper weighting from {0, 1} of h(G) satisfies χ w (v) ∈ {n -1, n, n + 1} for all v ∈ V . Thus, there is no such proper weighting and hence h(G) / ∈ 0-1WEIGHT. This completes the proof of Theorem 1.2.

1-2WEIGHT is NP-complete

The proof of Theorem 1.1 extends the ideas introduced in the proof of Theorem 1.2. Since clearly 1-2WEIGHT is in NP, it remains to show that 1-2WEIGHT is NP-hard. As before, we show a reduction from 3-COLOR to 1-2WEIGHT. To this end, we define a polynomial time reduction f , such that G ∈ 3-COLOR if and only if f (G) ∈ 1-2WEIGHT. Below we define auxiliary gadgets.

As in Section 2, we will use a triangle gadget. Now note that every triangle xab, with only x having other adjacent edges (x is referred to as the top), contributes exactly 3 to χ w (x) in any proper weighting w from {1, 2}. Now we define a 2-edge gadget consisting of the set of vertices {x, c, d, e, f } with x and c adjacent and {c, d, e, f } spanning a complete graph K 4 . One can check that every proper weighting w from {1, 2} of a graph adjacent to such a gadget only at x requires w(xc) = 2. We refer to x as the endpoint.

We use the above gadgets to construct another gadget, called a k-disallowing gadget. As we will see, this gadget has similar properties as its namesake in Section 2. We therefore allow ourselves the re-use of the name for this new, slightly different, gadget. We assume that k ≥ 8. The k-disallowing gadget contains a main triangle vxy with v referred to as the root. Moreover, if k is even, x and y each form the endpoint of (k -6)/2 edge disjoint 2-edge gadgets and x and y are each tops of distinct triangle gadgets (see Figure 2(a)). If k is odd, x and y each form the endpoint of (k -3)/2 edge disjoint 2-edge gadgets (see Figure 2(b)). Note that in any proper weighting w from {1, 2}, w(vx) = w(vy); otherwise, since the weight contributed by gadgets to χ w (x) and χ w (y) is k -3, then χ w (x) = w(xv) + w(xy) + k -3 = w(yv) + w(yx) + k -3 = χ w (y). Therefore, for any k, if w(xy) = 1 then {χ w (x), χ w (y)} = {k -1, k} and, if w(xy) = 2 then {χ w (x), χ w (y)} = {k, k + 1}. In either case, v has one neighbor z ∈ {x, y} with χ w (z) = k, and consequently, χ w (v) = k in any proper weighting from {1, 2}. Also {w(vx), w(vy)} = {1, 2}, and hence this gadget contributes exactly 3 to χ w (v).

Now we are ready to show a polynomial time reduction from 3-COLOR to 1-2WEIGHT, f , such that G ∈ 3-COLOR if and only if f (G) ∈ 1-2WEIGHT. Let G = (V, E) be a graph of order n. As in Section 2, we may assume that n ≥ 3. We construct the graph f (G) = (W, F ) as follows (see Figure 2(d)). We start with G = (V, E). For each v ∈ V :

(i) connect v to two new vertices s and t (distinct for each v);

Fig. 1 :

 1 Fig. 1: A k-disallowing gadget (a) and its symbolic representation (b); a construction of h(G) (c).

Fig. 2 :

 2 Fig. 2: A k-disallowing gadget (a) for even k, (b) for odd k and their symbolic representation (c); a construction of f (G), (d).

(

  ii) connect v to all vertices from a new set U v (distinct for each v) with |U v | = n -1 -deg(v);

Acknowledgements

We would like to thank Michał Karoński, who introduced us to the 1-2-3 conjecture. We are also very grateful to the referees for their detailed comments on an earlier version of this paper.

(iii) add n -1 new k-disallowing gadgets for all k ∈ {4n + 1, 4n + 2, . . . , 5n -1} with v as their root.

Clearly, f (G) can be calculated in time polynomial in the size of G.

Fact 3.1 In f (G) the following holds: any proper weighting w from {1, 2} satisfies χ w (v) ∈ {4n -2, 4n -1, 4n} for every v ∈ V .

Proof: Fix v ∈ V . Since w(vs) + w(vt) ∈ {2, 3, 4}, v is the endpoint of n -1 edges with endpoints in V ∪ U v and v is the root of (n -1) k-disallowing gadgets (each contributing 3 to χ w (v)), we have:

Observing the above and the fact that v is the root of k-disallowing gadgets for all k ∈ {4n + 1, 4n + 2, . . . , 5n -1}, we find that any proper weighting w from {1, 2} satisfies χ w (v) ∈ {4n -2, 4n -1, 4n}, as claimed.

2

First let us assume that G ∈ 3-COLOR. That means there exists a proper 3-coloring of G, say χ : V → {4n -2, 4n -1, 4n}. We define a weighting of the edges of f (G), w : F → {1, 2} as follows.

For all e ∈ E let w(e) = 1. For all edges e = vu with v ∈ V and u ∈ U v we set w(e) = 1. For all v ∈ V , if χ(v) = 4n -2 then w(vs) = w(vt) = 1; otherwise, if χ(v) = 4n -1 then w(vs) = 1 and w(vt) = 2; finally, if χ(v) = 4n then w(vs) = w(vt) = 2. All other edges (parts of gadgets) are weighted as follows: For a triangle gadget xab with root x, w(xa) = 2, w(xb) = w(ab) = 1. For a 2-gadget defined by {x, c, d, e, f } with x adjacent to c, we have w(xc) = w(cd) = w(ce) = w(de) = w(df ) = 2 and w(cf ) = w(ef ) = 1. For a k-disallowing gadget with root v and main triangle vxy, w(vx) = w(xy) = 2, w(vy) = 1, and the weighting of all other gadgets as described above. Note that w is a proper weighting of f (G) (satisfying χ w (v) = χ(v) for all v ∈ V ), as required.

Next let us assume that G / ∈ 3-COLOR. Therefore, for all χ : V → {4n -2, 4n -1, 4n}, χ is not a proper vertex coloring. But, from Fact 3.1, any proper weighting from {1, 2} of f (G) satisfies χ w (v) ∈ {4n -2, 4n -1, 4n} for all v ∈ V . Thus, there is no such proper weighting and hence f (G) / ∈ 1-2WEIGHT. This concludes the proof of Theorem 1.1.

Concluding remarks

In this paper we showed that determining whether a graph has a proper weighting from either {0, 1} or {1, 2} is NP-complete. As a matter of fact, these two problems are not the same, in the sense that the corresponding families of graphs 0-1WEIGHT and 1-2WEIGHT are not equal. For example, the graph consisting only of one 2-edge gadget is in 1-2WEIGHT, as seen before, but it is easy to check that it is not in 0-1WEIGHT. Furthermore, we believe that our approach can be generalized to show that determining whether a graph has a proper weighting from {a, b} is NP-complete for any different rational numbers a and b. It is not clear if the same would hold for any two distinct irrational numbers.


Yury Person
email: person@math.fu-berlin.de.

Mathias Schacht
email: schacht@math.uni-hamburg.de

An expected polynomial time algorithm for coloring 2-colorable 3-graphs †

Keywords: coloring, hypergraphs, average case analysis

We present an algorithm that for 2-colorable 3-uniform hypergraphs, finds a 2-coloring in average running time O(n 5 log 2 n).

Introduction

One of the classical problems in complexity theory is to decide whether a given k-uniform hypergraph is 2-colorable (or bipartite). Here a hypergraph is said to be -colorable, if there is a coloring of its vertices with colors, such that no hyperedge is monochromatic. We call such coloring proper. The chromatic number of the hypergraph is defined to be the minimal number of colors needed to color a hypergraph properly.

While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovász [START_REF] Lovász | Coverings and coloring of hypergraphs[END_REF] that the problem becomes N P -complete for k-uniform hypergraphs and k ≥ 3. Moreover, Guruswami et al. [START_REF] Guruswami | Hardness of approximate hypergraph coloring[END_REF] proved that it is N P -hard to color bipartite, k-uniform hypergraphs with a constant number of colors for k ≥ 4. It was also shown by Dinur et al. [START_REF] Dinur | The hardness of 3-uniform hypergraph coloring[END_REF] that this problem remains inapproximable by a constant for 3-uniform hypergraphs. On the other hand, recently, Krivelevich et al. [START_REF] Krivelevich | Approximating coloring and maximum independent sets in 3-uniform hypergraphs[END_REF] found a polynomial time algorithm which colors 3-uniform bipartite hypergraphs using O(n 1/5 log c n) colors. Another positive result is due to Chen and Frieze [START_REF] Chen | Coloring bipartite hypergraphs, Integer programming and combinatorial optimization[END_REF]. Those authors studied colorings of so-called α-dense bipartite 3uniform hypergraphs, where a 3-uniform hypergraph is α-dense if the joint degree of any two vertices is at least αn. A randomized algorithm that can color H in n O(1/α) time was found [START_REF] Chen | Coloring bipartite hypergraphs, Integer programming and combinatorial optimization[END_REF].

The purpose of this paper is to present an algorithm that colors a hypergraph chosen uniformly at random from the family of all labelled, 3-uniform, bipartite hypergraphs on n vertices in O(n 5 log 2 n) expected time. Indeed, we prove a slightly more general result for the class of Fano-free hypergraphs, see Theorem 1. Before we state it precisely we review related results for graphs.

In 1984 Wilf [START_REF] Wilf | Backtrack: an O(1) expected time algorithm for the graph coloring problem[END_REF] noted, using a simple counting argument, that one can decide in constant expected time, whether a graph is -colorable. Few years later Turner [START_REF] Turner | Almost all k-colorable graphs are easy to color[END_REF] gave an O(|V | + |E| log ) algorithm for optimally coloring almost all -colorable graphs. This result was further expanded by Dyer and Frieze [START_REF] Dyer | The solution of some random NP-hard problems in polynomial expected time[END_REF] who developed an algorithm which colored every -colorable graph on n vertices properly (with colors) in O(n 2 ) expected time.

Another line of research concerns the study of monotone properties of the type Forb(n, L) for a fixed graph L, i.e., the family of all labeled graphs on n vertices, which contain no copy of L as a (not necessarily induced) subgraph. Prömel and Steger [START_REF] Prömel | Coloring clique-free graphs in linear expected time[END_REF] gave an algorithm that colors properly (regardless of the value of its chromatic number χ(G)) a randomly chosen member G from Forb(n, K +1 ), i.e., the class of all labeled K +1 -free graphs, in O(n 2 ) expected time. This is clearly a generalization of the result of Dyer and Frieze in the light of the well known result of Kolaitis et al. [START_REF] Ph | K l+1 -free graphs: asymptotic structure and a 0-1 law[END_REF] that almost all K +1 -free graphs are -colorable.

In [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF] we studied Forb(n, F ), where F is the 3-uniform hypergraph of the Fano plane, which is the unique triple system with 7 hyperedges on 7 vertices where every pair of vertices is contained in precisely one hyperedge. It was shown independently by Füredi and Simonovits [START_REF] Füredi | Triple systems not containing a Fano configuration[END_REF] and Keevash and Sudakov [START_REF] Keevash | The Turán number of the Fano plane[END_REF], that for large n the unique extremal Fano-free hypergraph is the balanced, complete, bipartite hypergraph B n = (U ∪W, E Bn ), where |U | = n/2 , |W | = n/2 and E Bn consists of all hyperedges with at least one vertex in U and one vertex in W . The hypergraph of the Fano plane F is not bipartite, i.e., for every vertex partition X ∪Y = V (F ) into two classes there exists an edge of F which is either contained in X or in Y . Consequently, Forb(n, F ) contains any bipartite 3-uniform hypergraph on n vertices. However, deleting any hyperedge from F results in a bipartite hypergraph.

Let B n be the class of all labeled bipartite hypergraphs on n vertices. It was shown in [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF] that

|Forb(n, F )| ≤ (1 + 2 -Ω(n 2 ) )|B n | . (1)
Our main result here states that one can color a 3-uniform hypergraph chosen uniformly at random from Forb(n, F ) in polynomial expected time.

Theorem 1 There is an algorithm with average running time O(n 5 log 2 n) which colors every member from Forb(n, F ) properly.

Together with (1) we immediately derive in a similar manner to Steger and Prömel [START_REF] Prömel | Coloring clique-free graphs in linear expected time[END_REF] that one can color a 3-uniform hypergraph chosen uniformly at random from B n in polynomial expected time.

Corollary 2 There is an algorithm with average running time O(n 5 log 2 n) which finds a bipartition of every member from B n .

Algorithmic version of the weak hypergraph regularity lemma

In [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF] we used the so-called weak hypergraph regularity lemma in conjuction with the recently discovered counting lemma for linear hypergraphs from [START_REF] Kohayakawa | Weak hypergraph regularity and linear hypergraphs[END_REF]. A hypergraph is linear if any pair of hyperedges shares at most one vertex. Since the Fano plane is linear, this counting lemma is applicable.

Throughout this paper we will consider only 3-uniform hypergraphs and by a hypergraph we will always mean a 3-uniform hypergraph. For the sake of a simpler notation we set

F n = Forb(n, F ) ,
where by F we will always denote the hypergraph of the Fano plane. We will refer to hypergraphs not containing a copy of F , as Fano-free hypergraphs.

For a hypergraph H = (V, E) and a set U ⊆ V we denote by H[U ] the 3-uniform subhypergraph of H induced on U . We write E H (U ) or simply E(U ) for the edges completely contained in U , i.e.,

E H (U ) = E ∩ U 3 .
We let e H (U ) (resp. e(U )) denote the cardinality of E H (U ). Similarly, for two disjoint subsets U and W we write

E(U, W ) = E(U ∪ W ) \ (E(U ) ∪ E(W )) = {e ∈ E : e ⊂ U ∪W, |e ∩ U ||e ∩ W | ≥ 1} and e(U, W ) = |E(U, W )|. For pairwise disjoint sets V 1 , V 2 , and V 3 denote by E H (V 1 , V 2 , V 3 ) the set of all hyperedges from H that intersect all three sets, further set e H (V 1 , V 2 , V 3 ) = |E H (V 1 , V 2 , V 3 )|
The weak hypergraph regularity lemma is a straightforward extension of Szemerédi's regularity lemma [START_REF] Szemerédi | Regular partitions of graphs, Problèmes combinatoires et théorie des graphes[END_REF] for graphs. Here we introduce it only for 3-uniform hypergraphs, but a similar lemma holds for general k. Let H = (V, E) be a hypergraph and let W 1 , W 2 , W 3 be pairwise disjoint non-empty subsets of V . We denote by d

H (W 1 , W 2 , W 3 ) = d(W 1 , W 2 , W 3 ) the density of the 3-partite induced subhypergraph H[W 1 , W 2 , W 3 ] of H, defined by d H (W 1 , W 2 , W 3 ) = e H (W 1 , W 2 , W 3 ) |W 1 ||W 2 ||W 3 | .
We say the triple

(V 1 , V 2 , V 3 ) of pairwise disjoint subsets V 1 , V 2 , V 3 ⊆ V is (ε, d)-regular, for ε > 0 and d ≥ 0, if |d H (W 1 , W 2 , W 3 ) -d| ≤ ε for all triples of subsets W 1 ⊆ V 1 , W 2 ⊆ V 2 , W 3 ⊆ V 3 satisfying |W i | ≥ ε|V i |, i = 1, 2, 3. We say the triple (V 1 , V 2 , V 3 ) is ε-regular if it is (ε, d)
-regular for some d ≥ 0. An ε-regular partition of a set V (H) has the following properties:

(i ) V = V 1 ∪ . . . ∪V t (ii ) ||V i | -|V j || ≤ 1 for all 1 ≤ i, j ≤ t, (iii ) for all but at most ε t 3 sets {i 1 , i 2 , i 3 } ⊆ [t], the triple (V i1 , V i2 , V i3 ) is ε-regular.
We will apply an algorithmic version of the weak hypergraph regularity lemma which was established by Czygrinow and Rödl [START_REF] Czygrinow | An algorithmic regularity lemma for hypergraphs[END_REF] and in a slightly adjusted form for our needs, it will be used here to analyze our coloring algorithm Color(H), that will be introduced in the next section:

Theorem 3 (Algorithmic weak regularity lemma) For every integer t 0 ≥ 1 and every ε > 0, there exist T 0 = T 0 (t 0 , ε), n 0 = n 0 (t 0 , ε) and an algorithm Regularize, which for every hypergraph

H = (V, E) on n ≥ n 0 vertices finds in O(n 5 log 2 n) time an ε-regular partition V = V 1 ∪ . . . ∪V t with t 0 ≤ t ≤ T 0 .
Typically, when studying the regular partition of a hypergraph, one defines a new hypergraph of bounded size with the vertex set being the partition classes and the edge set being ε-regular triples with sufficient density. Our algorithm will also work with such cluster-hypergraphs. The following definition makes this precise.

Definition 4 For a hypergraph H = (V, E) with an ε-regular partition V (H) = V 1 ∪ . . . ∪V t of its vertex set and an η > 0 let H(η) = (V * , E * ) be the cluster-hypergraph with vertex set V * = {1, . . . , t} and edge set E * , where for 1 ≤ i < j < k ≤ t it is {i, j, k} ∈ E * if and only if the triple

(V i , V j , V k ) is ε-regular and the density satisfies d H (V i , V j , V k ) ≥ η.
In [START_REF] Kohayakawa | Weak hypergraph regularity and linear hypergraphs[END_REF] a counting lemma for linear hypergraphs in the context of the weak regularity lemma was proved. In [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF] we noted that the same proof also holds for the lower bound and for a slightly relaxed definition of an ε-regular triple. More precisely, we say a triple

(V 1 , V 2 , V 3 ) of pairwise disjoint subsets V 1 , V 2 , V 3 ⊆ V is one-sided (ε, d)-regular for ε > 0 and d ≥ 0 if d H (W 1 , W 2 , W 3 ) ≥ d for all triples of subsets W 1 ⊆ V 1 , W 2 ⊆ V 2 , W 3 ⊆ V 3 satisfying |W i | ≥ ε|V i |, i = 1, 2, 3. Note also, that an (ε, d)-regular triple is one-sided (ε, d -ε)-regular.
Theorem 5 (Key-Lemma (Theorem 3.3 in [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF])) For every ∈ N and d > 0 there exist ε = ε( , d) > 0 and a positive integer m 0 = m 0 ( , d) with the following property.

If H is an -partite 3-uniform hypergraph with vertex classes V 1 , . . . , V , such that |V 1 | = . . . = |V | ≥ m 0 , and L is a linear hypergraph on vertices such that for every e ∈ E(L) the triple (V i ) i∈e is one-sided (ε, d)-regular. Then H contains a copy of L.

2

The proof of Theorem 5 is given in [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF]Theorem 3.3] and, in fact, it follows along the lines of the proof of the counting lemma for linear hypergraphs in [START_REF] Kohayakawa | Weak hypergraph regularity and linear hypergraphs[END_REF].

Algorithm for coloring Fano-free hypergraphs

Below we first present the simple algorithm Color(H) which is based on the subroutine Partition(H, α). Obviously, Color(H) finds a proper coloring of H. We will show that Step 2 has a running time of O(n 5 log 2 n) for all H. Hence for proving Theorem 1 it suffices to show that there exists an α > 0 such that Step 5 of the algorithm will be executed for at most 2 -n log 2 n |Forb(n, F )| 3-uniform hypergraphs from Forb(n, F ).

The subroutine Partition(H, α) finds a locally minimal partition X H ∪Y H = V (H), i.e., a partition for which e(X H ) + e(Y H ) cannot be decreased by moving a single vertex from one class to another. Moreover, we will show later that for "most" 3-uniform hypergraphs H from Forb(n, F ) the algorithm Partition(H, α) outputs a partition with the additional property e(X H ) + e(Y H ) < αn 3 .

Algorithm 2: Partition (H, α) Input: H ∈ Forb(n, F ), α > 0 Output: Locally minimal vertex partition of H: V = X H ∪Y H Choose ε := ε(α) and η := η(α) appropriately (see Lemma 8); 1 Apply Regularize(H, ε, 1/ε ) and obtain an ε-regular partition V 1 , . . . , V t ; 2
Define cluster hypergraph H(η) with densities at least η;

3 Find partition A ∪B of V (H(η)) which minimizes e H(η) (A) + e H(η) (B); 4 Set W 1 := ∪ a∈A V a and W 2 := ∪ b∈B V b ; 5 while ∃w ∈ W i such that deg Wi (w) > deg W [2]\{i} (w) do 6 move w to W [2]\{i} ; 7 Output (W 1 , W 2 ); 8
In Step 2 the algorithm Regularize(H, ε, t) will be used as a subroutine. This algorithm, due to Czygrinow and Rödl [START_REF] Czygrinow | An algorithmic regularity lemma for hypergraphs[END_REF], finds an ε-regular partition of a 3-uniform hypergraph H on n vertices and at least t 0 many clusters in time O(n 5 log 2 n). Step 4 requires only constant time, that depends on ε only. The "while"-loop also requires at most O(n 5 ) steps, as the update step requires at most O(n 2 ) operations and the "while"-loop terminates after at most n 3 executions. Indeed, in every loop we increase the cut and there are at most n 3 hyperedges in H.

Further tools

In the following we will introduce more notations and basic facts before we start with the analysis of the algorithm Color(H). We recall the result of Füredi and Simonovits [START_REF] Füredi | Triple systems not containing a Fano configuration[END_REF] and Keevash and Sudakov [START_REF] Keevash | The Turán number of the Fano plane[END_REF] on the extremal number for the hypergraph of the Fano plane F asserts for sufficiently large n:

ex(n, F ) = e(B n ) = |E Bn | = n 3 - n/2 3 - n/2 3 = n 3 8 - n 2 4 -O(n) ≤ n 3 8 .
The following simple bounds on |B n | will be used:

2 e(Bn) ≤ |B n | ≤ 2 n • 2 e(Bn) . (2)
Indeed there are at most 2 n partitions of [n] in two disjoint sets and there are at most e(B n ) hyperedges running between those two sets.

The following holds for the Fano-extremal hypergraph B n :

δ 1 (B n ) = n 2 -1 n 2 + n/2 2 ≥ 3 8 n 2 -n , (3)
where for a hypergraph H = (V, E) we denote by δ 1 (H) the minimum vertex degree, i.e.,

δ 1 (H) = min u∈V {v, w} : {u, v, w} ∈ E , while setting ∆(H) = max u∈V {v, w} : {u, v, w} ∈ E
to be the maximum degree of H. Furthermore, we have

e(B n ) = e(B n-3 ) + δ 1 (B n ) + δ 1 (B n-1 ) + δ 1 (B n-2 ).
For a given hypergraph H = (V, E) and a vertex v ∈ V we define its link L H (v) = (V \ {v}, E v ) to be the graph whose edges together with v form hyperedges of H, namely

E v = {{u, w} : {v, u, w} ∈ E} .
We define the degree of v ∈ V to be deg

(v) = deg H (v) = |E(L H (v))|
, and sometimes we omit H when it is clear from the context. For A ⊆ V (H) and v ∈ V (H) denote by

L A (v) = L H (v)[A] = (A \ {v}, E v ∩ A 2 )
the link of v induced on A.

The following stability result for Fano-free hypergraphs was proved by Keevash and Sudakov [START_REF] Keevash | The Turán number of the Fano plane[END_REF] and Füredi and Simonovits [START_REF] Füredi | Triple systems not containing a Fano configuration[END_REF], in order to determine the extremal hypergraph for the Fano plane: Theorem 6 (Stability theorem for Fano-free hypergraphs) For every α > 0 there exists λ > 0 and n 0 such that for every Fano-free hypergraph H on n ≥ n 0 vertices with at least ( 1 8 -λ)n 3 hyperedges there exists a partition V (H) = X ∪Y so that e(X) + e(Y ) < αn 3 .

It follows from the work in [START_REF] Füredi | Triple systems not containing a Fano configuration[END_REF][START_REF] Keevash | The Turán number of the Fano plane[END_REF] that λ = λ(α) is indeed a computable function.

By h(x) = -x log x -(1 -x) log(1 -x) we denote the entropy function, and by log we always mean log 2 . Note further, h(x) → 0 as x tends to 0, and h(x) ≥ x for x ≤ 1 2 . We will use the entropy function h(x) together with the well-known inequality

n xn ≤ 2 h(x)n ,
which holds for 0 < x < 1. Furthermore, we will use that for n > 3k we have j<k n j < n k . Often we will omit floors and ceilings, as they will have no effect on our asymptotic arguments.

Proof of main result

Overview of the proof

So far we have presented our coloring algorithm Color(H) and it is left to show that there exist appropriate choices for α and for ε and η inside the subroutine Partition(H, α) which yield the claimed running time. More precisely, we will show that for sufficiently small α, ε and η the proportion of hypergraphs H in Forb(n, F ) for which Step 6 in Color(H) is required, is "negligible".

In the main part of the proof we show that there are at most 2 -Ω(n 2 ) |Forb(n, F )| such hypergraphs in Forb(n, F ). To prove this, we study structural properties of a typical H from Forb(n, F ). Our analysis uses ideas from [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF]. We will introduce a chain of subsets of Forb(n, F ) such that all members of them possess certain "typical" properties. More precisely, we study the following chains of subsets of F n :

F n ⊇ F n (α) ⊇ F n (α, β) ⊇ F n (α, β),
and

F n ⊇ B n ⊇ F n (α, β).
The first subset F n (α) consists of those members, that admit at least one locally minimal partition (X H , Y H ) with the properties e(X H ) + e(Y H ) < αn 3 and |X H | ≈ |Y H |. Using the weak hypergraph regularity lemma and Theorem 6, we will show that for most of the members from F n (α) the algorithm Partition(H, α) finds a locally minimal partition for given α. Therefore, additionally, we obtain that most of the hypergraphs from Forb(n, F ) lie in F n (α).

The further analysis proceeds as follows. We introduce two more proper subsets of Forb(n, F ): F n (α, β) and F n (α, β) which describe two further "useful" properties of almost all Fano-free hypergraphs on n vertices. The family F n (α, β) contains those members from F n (α) which are "dense everywhere" in the sense that whenever we take three disjoint subsets of vertices, say W 1 , W 2 , W 3 , not all of them contained in X H or Y H (for any locally minimal partition satisfying properties from F n (α)), the number of hyperedges that run between them will be at least d|W 1 ||W 2 ||W 3 | for some positive constant d > 0. Moreover, every vertex will have small degree in its own partition class (i.e. X H or Y H ). Thus, essentially, there exists "only one" locally minimal partition. For members of the last class F n (α, β) we demand that the joint link of every set of 3 vertices of any of the two partition classes X H and Y H must contain a K 4 . We then deduce that the last property implies in fact bipartiteness. As a seemingly surprising fact, we obtain, that for almost all members from Forb(n, F ) any locally minimal partition for some appropriate α already satisfies e(X H ) + e(Y H ) = 0.

Proof of Theorem 1

Below we give proper definitions of the classes described above and we state the lemmas that relate the sizes of these hypergraph classes. The proofs of the corresponding statements are given in the next section, Section 6. First we recall the definition of a locally minimal partition. A vertex partition

X H ∪Y H of V (H) is locally minimal if e(X , Y ) ≥ e(X H , Y H ) for all partitions X ∪Y of V (H) with |X ∆X H | ≤ 1. Furthermore, we say a partition is α-good, if e(X H )+e(Y H ) < αn 3 and |X H |, |Y H | < n/2+2 h(6α)n.
The first class F n (α) of Fano-free hypergraphs is defined as follows.

Definition 7 Let α > 0 and n ∈ N. We set

F n (α) = H ∈ F n : ∃ a locally minimal α-good partition V = X H ∪Y H .
Lemma 8 For every α ∈ (0, 1 12 ) there exist (computable) constants c , ε, η > 0 and an integer n 0 such that for all n ≥ n 0 the algorithm Partition(H, α) finds for all but at most 2 e(Bn)-c n 3 hypergraphs H ∈ F n a locally minimal partition X H ∪Y H of its vertex set with the following two properties:

• e(X H ) + e(Y H ) < αn 3 , • |X H |, |Y H | < n/2 + 2 h(6α)n.
In particular, we have:

|F n \ F n (α)| < 2 e(Bn)-c n 3 .
Next we define the subfamily of "everywhere dense" hypergraphs from F n (α).

Definition 9 For α, β > 0 and n ∈ N let F n (α, β) denote the family of those hypergraphs H ∈ F n (α), such that for any locally minimal α-good partition X H ∪Y H of V (H) the following condition holds.

For any pairwise disjoint sets

W 1 ⊂ X H , W 2 ⊂ Y H and W 3 ⊂ Z H , where Z H ∈ {X H , Y H }, with |W i | ≥ βn for i = 1, 2, 3 we have e H (W 1 , W 2 , W 3 ) ≥ 1 4 |W 1 ||W 2 ||W 3 |.
The proof of the following lemma is similar to the proofs of Lemmas 4.2 and 4.3 in [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF], for completeness we include the proof of Lemma 10 in Section 6.

Lemma 10 For every γ > 0 there exist (computable) constants α, β, c > 0 and an integer n 0 such that for every n ≥ n 0 and H ∈ F n (α, β), we have:

1. |F n (α) \ F n (α, β)| < 2 e(Bn)-c n 3 .

max{∆(H[X H ]), ∆(H[Y H ]

)} < γn 2 for any locally minimal α-good partition X H ∪Y H ,

We finally define the last subclass of Fano-free hypergraphs.

Definition 11 For α, β > 0 and n ∈ N, let F n (α, β) denote the family of those hypergraphs H ∈ F n (α, β), such that for any locally minimal α-good partition X H ∪Y H of V (H) the following holds. For all triples z 1 , z 2 , z 3 ∈ Z of vertices with

Z ∈ {X H , Y H } we have L Q (z 1 )∩L Q (z 2 )∩L Q (z 3 ) ⊇ K 4 , where {Q, Z} = {X H , Y H }.
In other words, we require that the common link of any triple from X H or Y H contains a copy of K 4 in the other vertex class.

It follows directly from the definition, that every H ∈ F n (α, β) is bipartite, i.e., F n (α, β) ⊆ B n . Otherwise, any hyperedge e, say in X H , together with the K 4 in Y H , which lies in the common link of the vertices of e would span a copy of the hypergraph of the Fano plane.

To obtain a bound on |F n (α, β) \ F n (α, β)| we estimate in at most how many ways one can construct a Fano-free hypergraph from F n (α, β) \ F n (α, β), i.e. a Fano-free hypergraph with a locally minimal partition and a hyperedge inside it.

Lemma 12 There exist (computable) constants α, β, c > 0 and an integer n 0 , such that for every n ≥ n 0 we have

|F n (α) \ F n (α, β)| ≤ 2 e(Bn)-cn 2 .
We remark that the bound in Lemma 12 is considerably weaker than those in Lemma 10 and Lemma 8 having only -cn 2 in the exponent instead of -cn 3 . The reason for that is that the number of Fanofree hypergraphs which are not bipartite is 2 e(Bn)-Θ(n 2 ) . The corresponding argument can be found in Section 7.

Proof of Theorem 1: We first apply Lemma 12 and obtain constants α, β and c. Then Lemma 8 applied with α returns ε, η and c . Below we show that these constants α, ε and η are suitable choices in the algorithms Color and Partition. Indeed for these choices of α, ε and η, Lemma 8 asserts that the partition X H ∪Y H provided by Partition(H, α) is locally minimal and α-good for all but 2 e(Bn)-c n 3 hypergraphs H ∈ F n . Moreover, due to Lemma 12 this partition satisfies e(X H ) + e(Y H ) = 0 for all H ∈ F n (α, β), i.e. this partition is a correct 2-coloring of H. Finally, it follows from Lemma 8 and Lemma 12 that Step 6 of the algorithm Color is only considered for at most 2 e(Bn)-c n 3

+ 2 e(Bn)-cn 2

Fano-free hypergraphs. 2

Proofs of Lemmas

Proof of Lemma 8: The proof of Lemma 8 combines the weak hypergraph regularity lemma with the stability theorem for Fano-free hypergraphs applied to the cluster-hypergraph. Let λ = λ(α/2) and n 0 (α/2) be given by the stability theorem, Theorem 6. We may assume λ < 16h(6α). We set

c = λ 17 ,
and we choose η such that λ > (16/3)h(6η) and η ≤ α/2. Later we will apply the Key-lemma, Theorem 5, with = 7 and L being the hypergraph of the Fano plane to the cluster-hypergraph of an ε-regular partition. For that we set ε = min{ε(7, η/2), η/2}, where ε(7, η/2) is as asserted by Theorem 5.

We also choose a lower bound on the number of clusters in an ε-regular partition to be

t 0 = max{1/ε, n 0 (α/2)},
where n 0 (α/2) is the bound given by Theorem 6, so that we can later apply Theorem 6 (stability theorem) to the cluster-hypergraph. Finally set n be sufficiently large, in particular, set n 0 max{T 0 , n 0 }, where T 0 and n 0 are given by the weak regularity lemma, Theorem 3, which in turn will deliver an ε-regular partition later.

For the main steps of the proof it is sufficient to keep in mind that

0 < 1/t 0 ≤ ε ≤ η λ α.
We may assume in the following that t divides n, and thus |V i | = n/t for all i = 1, . . . , t.

We will upper bound the number of hypergraphs for which Partition(H, α) fails to produce a locally minimal α-good partition in two steps. More formally, we consider the subset F n (α) which consists of those hypergraphs H from F n , for which Partition(H, α) returns a locally minimal α-good partition. Thus, our aim is to show that |F n \ F n (α)| is at most 2 e(Bn)-c n 3 . Our proof has two steps. In the first step we bound the number of hypergraphs H that have e(X H ) + e(Y H ) ≥ αn 3 for every locally minimal partition (X H , Y H ). In the second step we show that most of the hypergraphs H every locally minimal partition X H ∪Y H with e(X H ) + e(Y H ) < αn 3 will also satisfy:

max{|X H |, |Y H |} < n 2 + 2 h(6α)n .
Here and in the following (X H , Y H ) will stand for a locally minimal partition, and unless it is specified otherwise, it will stand for an arbitrary locally minimal partition.

Step

for every locally minimal partition X H ∪Y H . We apply the weak regularity lemma, Theorem 3, with parameters ε and t 0 . Firstly, we estimate the number of hyperedges, which are contained in the "uncontrolled" part of the regular partition:

• the number of hyperedges intersecting at most two of the clusters is at most

t n/t 2 n < 1 2t n 3 ,
• the number of hyperedges contained in irregular triples is at most

ε t 3 n t 3 < ε 6 n 3 ,
• the number of hyperedges that are contained in ε-regular triples of density less than η is at most

η n t 3 t 3 < η 6 n 3 .
Thus, the number of discarded edges is less than ηn 3 . Secondly, consider the resulting cluster-hypergraph H(η). It must be Fano-free as otherwise Theorem 5 would imply that H also contains a copy of the hypergraph of the Fano plane.

Recall that by assumption (4) we have for every locally minimal partition e(X H ) + e(Y H ) ≥ αn 3 . Below we will show that this assumption implies that e(H(η)) ≤ (1 -λ)t 3 /8. In fact, assuming the contrary, Theorem 6 applied to H(η) would yield the existence of a bipartition of {1, . . . , t} into disjoint sets A and B with e H(η) (A) + e H(η) (B) < αt 3 /2. We define the following bipartition of V (H)

X = i∈A V i and Y = j∈B V j .
Clearly, we then have

e H (X) + e H (Y ) < ηn 3 + α 2 t 3 n t 3 < αn 3 .
Note that if shifting vertices between X and Y until a locally minimal partition is reached, only decreases the number of edges within classes. Thus, we would arrive at a locally minimal bipartition (X , Y ) with e H (X ) + e H (Y ) < αn 3 , which yields a contradiction to (4). Now we are able to bound the number of hypergraphs H ∈ F n with e(X H ) + e(Y H ) ≥ αn 3 for every locally minimal partition X H ∪Y H from above by calculating the total possible number of ε-regular partitions together with all possible cluster-hypergraphs associated with them and all possible hypergraphs that could give rise to such a particular cluster-hypergraph. This way we get, for sufficiently large n, due to the choice of η, at most

T0 t=t0 t n • 2 ( t 3 ) • 2 (1-λ) t 3 8 ( n t ) 3 •   ηn 3 -1 j=0 n 3 j   ≤ T n+1 0 • 2 ( T 0 3 ) • 2 (1-λ)n 3 /8 • n 3 ηn 3 ≤ 2 (n+1) log T0+( T 0
3 )+n 3 /8-λn 3 /8+h(6η)n 3 /6 < 2 n 3 /8-λn 3 /16 , hypergraphs whose every locally minimal partition (X H , Y H ) satisfies (4).

Step 2. We now estimate the number of those hypergraphs H which have a locally minimal partition

(X H , Y H ) with e(X H ) + e(Y H ) < αn 3 , but max{|X H |, |Y H |} ≥ n/2 + 2 h(6α)n. (5)
First we upper bound e(X H , Y H ) for such a hypergraph H by

e(X H , Y H ) ≤ |X H | |Y H | 2 + |Y H | |X H | 2 < n 2 |X H ||Y H | < n 3 8 -2h(6α)n 3 .
Note that there are at most 2 n possible partitions of V (H), and since less than αn 3 hyperedges are completely contained in X H and Y H , those hyperedges can be chosen in at most

αn 3 -1 i=0 n 3 i ≤ n 3 αn 3
ways. Finally, as we assumed that the partitions satisfy (5), we estimate the number of possible choices of hyperedges between X H and Y H by 2 n 3 /8-2h(6α)n 3 . Altogether we get, that there are at most

2 n • n 3 αn 3 • 2 n 3 /8-2h(6α)n 3 ≤ 2 n+h(6α)n 3 /6+n 3 /8-2h(6α)n 3 ≤ 2 n 3 /8-h(6α)n 3
hypergraphs H with e(X H ) + e(Y H ) < αn 3 and

max{|X H |, |Y H |} ≥ n 2 + 2 h(6α)n.
Combining Steps 1 and 2 we obtain:

|F n \ F n (α)| ≤ |F n \ F n (α)| ≤ 2 n 3 /8-λn 3 /16 + 2 n 3 /8-h(6α)n 3 < 2 n 3 /8-λn 3 /16+1 , since h(6α) > λ/16. Due to n 3 /8 -e(B n ) ≤ n 2 /4 + O(n)
and the choice of c = λ/17, the lemma follows for sufficiently large n. 2

To prove Lemma 10, we will use a special form of the regularity lemma for graphs. Before we state it, we briefly introduce the concept of ε-regularity for graphs.

For a bipartite graph

G = (V 1 , V 2 , E) we define the density of G as d(V 1 , V 2 ) := |E| |V1||V2| . The density of a subpair (U 1 , U 2 ), where U i ⊆ V i for i = 1, 2 is defined as d(U 1 , U 2 ) := e(U1,U2)
|U1||U2| . Here, as in the hypergraph case, e(U 1 , U 2 ) denotes the number of edges with one end in U 1 and the other in U 2 . We say, G, or simply

(V 1 , V 2 ), is ε-regular if for all U i ⊆ V i , |U i | ≥ |V i |, i = 1, 2 the following holds: |d(V 1 , V 2 ) -d(U 1 , U 2 )| < ε.
Now we can state the theorem, which is a straightforward consequence of the regularity lemma [START_REF] Szemerédi | Regular partitions of graphs, Problèmes combinatoires et théorie des graphes[END_REF]:

Theorem 13 Let η > 0, then for every ε ∈ (0, η/3) there exist T 0 , N 0 such that the following holds. For all vertex disjoint graphs G X and G Y on n ≥ N 0 vertices with e(G X ), e(G Y ) ≥ ηn 2 there exist t ≤ T 0 and pairwise disjoint sets

X 1 , X 2 , Y 1 , Y 2 , Y 3 , Y 4 , each of size n/t, and X 1 , X 2 ⊂ V (G X ) and Y i ⊂ V (G Y ), i ∈ [4], so that G X [X 1 , X 2 ], G Y [Y 1 , Y 2 ] and G Y [Y 3 , Y 4 ] are ε-regular with density at least η/3. 2
Proof of Lemma 10: For the second part of the proof, we let ε = min{ 1 2 ε(γ/6), γ/6}, where ε(γ/6) is as asserted by Theorem 5. We choose β = ε/T 0 , where T 0 is as asserted by Theorem 13 when applied with η = γ and ε. Furthermore we choose n 0 to be sufficiently large, in particular larger than N 0 .

For the first part, we choose α > 0 such that

β 3 1 -h 1 4 ≥ h(6α) 3
and set c = h(6α)/12.

It is sufficient to keep in mind: 0 α β ε γ.

(1) We estimate |F n (α) \ F n (α, β)| as follows. There are at most 2 n partitions X H ∪Y H = [n] of the vertex set and we can choose the edges lying completely within X H and Y H in at most possible ways. Moreover, there are at most

2 n 2 + 2 h(6α)n βn 3 • 1 4 β 3 n 3 -1 i=0 β 3 n 3 i < 2 3n+1 β 3 n 3 1 4 β 3 n 3
ways to select W 1 , W 2 , W 3 and the hyperedges in e H (W 1 , W 2 , W 3 ). Finally, there are at most 2 e(Bn)-β 3 n 3 ways for choosing the remaining edges. Multiplying everything together, we obtain

|F n (α) \ F n (α, β)| ≤ 2 4n+1 n 3 αn 3 β 3 n 3 1 4 β 3 n 3 2 e(Bn)-β 3 n 3 ≤ 2 4n+1+h(6α) n 3 6 +h(1/4)β 3 n 3 +e(Bn)-β 3 n 3 ≤ 2 e(Bn)-2c n 3 ,
for sufficiently large n.

(2) We prove the second part by contradiction. More precisely, we will assume that there exists 2 , and we will show that H contains a Fano plane.

H ∈ F n (α, β) with max{∆(H[X H ]), ∆(H[Y H ])} ≥ γn
Without loss of generality we may assume that there exists

H ∈ F n (α, β) and a vertex x ∈ X H with deg H[X] (x) ≥ γn 2 . Thus, |L Y (x)| ≥ |L X (x)| ≥ γn 2 ,
as otherwise this violates the minimality condition of the partition

X H ∪Y H = V (H). Define graphs G X = (X H \ {x}, L X (x)) and G Y = (Y H , L Y (x)).
We apply Theorem 13 to G X ∪G Y and obtain ε-regular pairs

(X 1 , X 2 ) ⊂ G X and (Y 1 , Y 2 ), (Y 3 , Y 4 ) ⊂ G Y , with |X i | = |Y j | ≥ (n -1)/T 0 and i ∈ [2], j ∈ [4]
, each of density at least γ/3.

Consider the following 7-partite subhypergraph L with vertex classes {x}, X 1 , X 2 , Y 1 , Y 2 , Y 3 and Y 4 . Denote L x to be the hypergraph obtained from L by blowing up its first vertex class {x} to the size of X 1 (all other partition classes are equal), and denote this blown-up class by X. More precisely,

L x = (W x , E x ), where W x = X ∪X 1 ∪X 2 ∪Y 1 ∪Y 2 ∪Y 3 ∪Y 4 and {a, b, c} ∈ E x ⇔ {a, b, c} ∈ E(L) , if {a, b, c} ∩ X = ∅ , {x, b, c} ∈ E(L) , if a ∈ X and b, c ∈ X .
Note, that L contains a Fano plane if, and only if L x contains one. Now we apply Theorem 5 to L x , as L x contains now 7 one-sided (ε, γ/6)-regular triples and these triples form a Fano plane. This is true since the triples ( X, X 1 , X 2 ), ( X, Y 1 , Y 2 ) and ( X, Y 3 , Y 4 ) inherit the ε-regularity from the ε-regular pairs of (X 1 , X 2 ), (Y 1 , Y 2 ), and (Y 3 , Y 4 ), while the other triples are one-sided (ε, γ/6)-regular due to the choice of β and the properties shown in (1). This yields a contradiction and, hence, Lemma 10 follows.

2

For the proof of Lemma 12 we will use the following lemma shown in [START_REF] Person | Almost all hypergraphs without Fano planes are bipartite[END_REF], which is a straightforward consequence of Janson's inequality [START_REF] Janson | Poisson approximation for large deviations[END_REF].

Lemma 14

The probability that the binomial random graph G(m, 1 8 ) with m ≥ 253 vertices and edge probability 1/8 does not contain a copy of K 4 is bounded from above by exp(-2 -11 m 2 ).

2

Proof of Lemma 12: We set ϑ = 2 -17 and c = ϑ 4

and choose γ > 0 such that 3h(2γ) < ϑ .

Let α, β and c be given by Lemma 10. We may also assume that

3 h(6α) + 6h(6α) < ϑ/2 , (8)
as choosing α smaller we will only have to eventually increase n 0 . Again, it is sufficient to keep in mind that 0 < α, β γ ϑ = 2 -17 .

Due to Lemma 10 we have 3 . Deleting S from V (H), we obtain a Fano-free hypergraph H on n -3 vertices, where V (H ) = [n] \ S. Note that for every H ∈ F n (α, β) \ F n (α, β) there exists a hypergraph H ∈ F n-3 such that H can be obtained from H in the following way. For H ∈ F n-3 we choose a set S of 3 vertices, which we connect in an appropriate manner, so that the resulting hypergraph is in

|F n (α) \ F n (α, β)| ≤ 2 e(Bn)-c n 3 , (9)
F n (α, β) \ F n (α, β).
We can choose the set S, the partition of H and the set which contains S in at most

n 3 2 n-3
ways. Note that the implicit partition of H chosen that way is not necessarily locally minimal. Only after we add S back, we obtain a locally minimal α-good partition (X H , Y H ). Since H ∈ F n (α, β) we infer from Lemma 10 that every vertex in S has at most γn 2 neighbors in its own partition class. This again bounds the number of ways for choosing these hyperedges by

  γn 2 -1 j=0 n 2 j   3 ≤ n 2 γn 2 3 .
For every vertex in S we have at most 2 n 2 /4 possibilities for choosing edges with one more end in the same partition as S and the other end in the other partition class, this gives us at most

2 3n 2 /4
ways to choose that type of hyperedges. The last estimate concerns the number of ways we can connect our triple S to the other partition class, say Y , without creating any single copy of K 4 , which is contained in the joint link of the vertices from S. Here we use Lemma 14. For every vertex v in S we can choose its link graph L Y (v) in at most 2 ( |Y | 2 ) ways. However, since the joint link of three vertices in S contains no K 4 , we infer from Lemma 14, that there are at most

2 3( |Y | 2 ) exp(-2 -11 |Y | 2 ) < 2 3( |Y | 2 )-|Y | 2 /2 11
ways.

Combining the above estimates and

n/4 ≤ |Y | ≤ n/2 + 2 h(6α)n , we obtain |F n (α, β) \ F n (α, β)| ≤ n 3 2 n-3 • n 2 γn 2 3 2 3n 2 /4 2 3( |Y | 2 )-|Y | 2 /2 11 |F n-3 | (8) ≤ 2 3 log n+n+3h(2γ)n 2 /2+9n 2 /8+ϑn 2 /2-n 2 /2 15 |F n-3 | (7) ≤ 2 δ1(Bn-2)+δ1(Bn-1)+δ1(Bn)+ϑn 2 -n 2 /2 16 |F n-3 | (6) = 2 δ1(Bn-2)+δ1(Bn-1)+δ1(Bn)-ϑn 2 |F n-3 | (1) ≤ 2 -ϑn 2 • 2 n-2 • |B n |.
Since

|F n | (1)
≤ 2|B n | ≤ 2 e(Bn)+n+1 , it follows from [START_REF] Guruswami | Hardness of approximate hypergraph coloring[END_REF], that |F n (α) \ F n (α, β)| ≤ 2 e(Bn)-cn 2 due to the choice of c. 2

A construction

Note that the error terms obtained in Lemmas 8 and 10 are of the order 2 -Ω(n 3 ) , while Lemma 12 only yields 2 -Ω(n 2 ) . The construction below indicates that Lemma 12 cannot be improved to obtain a similar bound. More precisely, we show that the number of the nonbipartite Fano-free hypergraphs is

|Forb(n, F )| -|B n | = 2 -Θ(n 2 ) |B n |. (10)
Thus, for that many hypergraphs the algorithm Color(H) will perform the brute force search for an optimal coloring of the vertices. Indeed, ( . The rough idea is to take a random balanced bipartite hypergraph on n -9 vertices, and then add some additional hyperedges incident to some of the remaining 9 vertices, such that almost surely the resulting hypergraph is not bipartite. A routine application of Chernoff's inequality gives then [START_REF] Janson | Poisson approximation for large deviations[END_REF].

Let H be a random balanced bipartite 3-uniform hypergraph with classes A, B such that |A| + |B| = n -9. Let v 1 , . . . , v 9 be new vertices, let G 1 , . . . , G 6 ∈ G(A, 1/2), i.e. G i 's are random graphs on the vertex set A. We define the hypergraph H to have A ∪B ∪{v 1 , . . . , v 9 } as a vertex set, and we define the hyperedge set of H to be: Note that H -v 7 v 8 v 9 is bipartite, and moreover, since the hyperedges incident with v 7 , v 8 and v 9 are disjoint, H must be Fano-free. It is easy to show that with high probability, H is not bipartite. In fact, w.h.p. a proper coloring of H -v 7 v 8 v 9 is unique (up to permutation of the two colors).

Concluding Remarks

We presented a deterministic algorithm that colors in O(n 5 log 2 n) average running time every Fano-free hypergraph properly, which together with (1) implies also the class of bipartite 3-uniform hypergraphs. Instead of asking for a deterministic algorithm, we could use results of Frieze and Kannan [START_REF] Frieze | The regularity lemma and approximation schemes for dense problems[END_REF][START_REF]Quick approximation to matrices and applications[END_REF], or a more recent one by Fischer, Matsliah and Shapira [START_REF] Fischer | Approximate hypergraph partitioning and applications[END_REF] to design randomized algorithms with better running time that color the same classes of hypergraphs properly with high probability. Note that the bottleneck in our algorithm was Step 2 of the algorithm Partition(H, α), which employed an application of the algorithmic version of the weak hypergraph regularity lemma due to Czygrinow and Rödl [START_REF] Czygrinow | An algorithmic regularity lemma for hypergraphs[END_REF], that required O(n 5 log 2 n) time. However, note that the while-loop of the same algorithm Partition(H, α) has (naively implemented) a running time of O(n 5 ).

It would be interesting to find faster randomized and deterministic algorithms for Corollary 2. Another interesting question, which might improve the running time is to find better deterministic algorithms for the weak hypergraph regularity lemma. In fact, in the case of graph regularity lemma an optimal algorithm was found in [START_REF] Kohayakawa | An optimal algorithm for checking regularity[END_REF].

Algorithm 1 : 1 ( 3 output 2 - 4 else 5 try all n n = 2 n

 1132452 Color (H) Input: H from Forb(n, F ) Output: Proper coloring of H Choose α > 0 appropriately (see Lemma 12); X, Y ) ← Partition (H, α); 2 if e(X) + e(Y ) = 0 then coloring corresponding to (X, Y ); log 2 n possible colorings and output the one that minimizes the number of colors 6 used;

  implies |Forb(n, F )| -|B n | |B n | ≤ 2 -Ω(n 2 ) , while the construction below shows |Forb(n, F )| -|B n | ≥ |B n |2 -O(n 2 )

E

  (H) := E(H ) ∪{e ∪ {v i } : e ∈ E(G i ), i ∈ [6]} ∪ {{v 1 , v 2 , v 7 }, {v 3 , v 4 , v 8 }, {v 5 , v 6 , v 9 }, {v 7 , v 8 , v 9 }}.

  1. Consider a hypergraph H ∈ F n satisfying e(X H ) + e(Y H ) ≥ αn 3

  and we estimate |F n (α, β) \ F n (α, β)| as follows.Let H ∈ F n (α, β)\F n (α, β) and X H ∪Y H be an arbitrary locally minimal α-good partition. Consider a subset S ∈ X H

	3	∪ Y H

Acknowledgements

We would like to thank Asaf Shapira, Anusch Taraz and anonymous referees for useful suggestions.

Coloring 2-colorable 3-graphs

Supported by GIF grant no. I-