Jean-Claude Bermond

Alain Jean-Marie

Dorian Mazauric

Joseph Yu

Well Balanced Designs for Data Placement *

Keywords: data placement, balanced designs, Steiner systems placement de données, configurations équilibrées, systèmes de Steiner

The problem we consider in this article is motivated by data placement, in particular data replication in distributed storage and retrieval systems. We are given a set V of v servers along with b files (data, documents). Each file is replicated on exactly k servers. A placement consists in finding a family of b subsets of V (representing the files) called blocks, each of size k. Each server has some probability to fail and we want to find a placement which minimizes the variance of the number of available files. It was conjectured that there always exists an optimal placement (with variance better than that of any other placement for any value of the probability of failure). We show that the conjecture is true, if there exists a well balanced design, that is a family of blocks, each of size k, such that each j-element subset of V , 1 ≤ j ≤ k, belongs to the same or almost the same number of blocks (difference at most one). The existence of well balanced designs is a difficult problem as it contains as a subproblem the existence of Steiner systems. We completely solve the case k = 2 and give bounds and constructions for k = 3 and some values of v and b.

Introduction

The problem we consider in this article is motivated by data placement in particular data replication in distributed storage and retrieval systems (see [1][START_REF] Baert | Minimization of download time variance in a distributed vod system[END_REF][START_REF] Baert | Performance analysis of dat replication in grid delivery networks[END_REF][START_REF] Jean-Marie | Combinatorial designs and availability[END_REF]). We use here the terminology of design and graph theory (so the notations are somewhat different from the papers mentioned above). We are given a set V of v servers along with b files (data, documents). Each file is replicated (placed) on exactly k servers. The set of servers containing file i is therefore a subset of size k, which will be called a block and denoted B i . A placement consists of giving a family F of blocks B i ,

1 ≤ i ≤ b.
A server is available (on-line) with some probability δ and so unavailable (offline, failed) with the probability 1-δ. The file i is said to be available if one of the servers containing it is available or equivalently the file is unavailable if all the servers containing it are unavailable. In [START_REF] Baert | Minimization of download time variance in a distributed vod system[END_REF][START_REF] Baert | Performance analysis of dat replication in grid delivery networks[END_REF][START_REF] Jean-Marie | Combinatorial designs and availability[END_REF] the authors studied the random variable Λ, the number of available files and they proved that the mean is E(Λ) = b(1 -(1 -δ) k ); so this mean is independent of the placement. However they proved that the variance of Λ depends on the placement and showed (see [START_REF] Jean-Marie | Combinatorial designs and availability[END_REF]) that minimizing the variance corresponds to minimizing the polynomial P (F, x) = k j=0 v j x j where x = 1 1-δ (so x ≥ 1) and v j denotes the number of ordered pairs of blocks intersecting in exactly j elements. So we can summarize our problem as follows:

Problem: 1 Let v, k, b be given positive integers and x be a real number, x ≥ 1; find a placement that is a family F of b blocks, each of size k, on a set of v elements, which minimizes the polynomial P (F, x) = k j=0 v j x j , where v j denotes the number of ordered pairs of blocks intersecting in exactly j elements. Such a placement will be called optimal for the value x.

In [START_REF] Jean-Marie | Combinatorial designs and availability[END_REF] the following conjecture is proposed: Conjecture 1 For any v, k, b there exists a family F * which is optimal for all the values of x ≥ 1 (that is P (F * , x) ≤ P (F, x) for any F and any x ≥ 1).

Note that for x = 1, we have P (F, 1) = b(b -1) as the value is the number of ordered pairs of blocks. So we can restrict to the case x > 1. Note also that all the coefficients are even; indeed if B and B ′ intersect in j elements, then so do B ′ and B. So, we could have considered only (non ordered) pairs of blocks, in which case the polynomial will have been one half of that for ordered pairs. Before stating our results let us give some examples. Let v = 4, b = 4, k = 2. We can consider different placements:

• Family F 1 : B 1 = B 2 = B 3 = B 4 = {1, 2}; then P (F 1 , x) = 12x 2 • Family F 2 : B 1 = B 2 = {1, 2}, B 3 = B 4 = {3, 4}; then P (F 2 , x) = 4x 2 + 8 • Family F 3 : B 1 = {1, 2}, B 2 = {1, 3}, B 3 = {1, 4}, B 4 = {2, 3}; then P (F 3 , x) = 10x + 2 • Family F 4 : B 1 = {1, 2}, B 2 = {2, 3}, B 3 = {3, 4}, B 4 = {1, 4}; then P (F 4 , x) = 8x + 4.
For any x ≥ 1, P (F 4 , x) ≤ P (F i , x) and it can be proven that indeed F 4 is an optimal family for any x ≥ 1. Note that according to the values of x, F 2 can be better (or worse) than F 3 . For x ≤ 3 2 , P (F 2 , x) ≤ P (F 3 , x) (for example for x = 5 4 , P (F 2 , 5 4 ) = 14 + 1 4 and P (F 3 , 5 4 ) = 14 + 1 2 ). But for x ≥ 3 2 , P (F 2 , x) ≥ P (F 3 , x) (for example for x = 2, P (F 2 , 2) = 24 and P (F 3 , 2) = 22). Let now v = 5, b = 3, k = 3. We claim that the family F * consisting of the three blocks {1, 2, 3}, {1, 2, 4}, {3, 4, 5} is optimal for all x ≥ 1. We have P (F * , x) = 2x 2 + 4x. Let F be any

RR n°7725

other family with a polynomial P (F, x) = a 3 x 3 + a 2 x 2 + a 1 x + a 0 . As v = 5, there can never be two disjoint blocks; so a 0 = 0. Furthermore we always have a 3 + a 2 + a 1 = b(b -1) = 6. So P (F, x) -P (F * , x) = (x -1)(a 3 x 2 + (a 3 + a 2 -2)x). If a 3 ≥ 2 (that is at least one block repeated), then P (F, x) -P (F * , x) > 0 for any x > 1. If a 3 = 0, among 3 blocks necessarily two of them have a pair in common and so a 2 ≥ 2 and P (F, x) -P (F * , x) ≥ 0 for all x ≥ 1.

Our results

For a family F let λ F x1,...,xj (or shortly λ x1,...,xj ) denote the number of blocks of the family containing the j-element subset {x 1 , . . . , x j }. A family F is j-balanced if the λ x1,...,xj are all equal or almost equal, that is, if for any two j-element subsets {x 1 , . . . , x j } and {y 1 , . . . , y j }, |λ x1,...,xj -λ y1,...,yj | ≤ 1. Furthermore, a family F is well balanced if it is j-balanced for 1 ≤ j ≤ k, where k is the size of the blocks.

We first show in Section 3 that

P (F, x) = Σ k j=1 Σ x1,...,xj λ 2 x1,...,xj (x -1) j -bx k + b 2 .
The form of the above polynomial enables us to prove in Section 3 that a well balanced family is also optimal and therefore Conjecture 1 is proven for the values of b, for which there exists a well balanced family.

The rest of the paper is devoted to the construction of well balanced families and so optimal ones. We consider first the case k = 2 (Section 4) where such families are easy to construct for any b. The cases k > 2, are much more complicated. Starting with k = 3, there are values of v and b for which there do not exist well balanced families (Section 5). In Section 6, we deal with the case k = 3 using results of design theory. Indeed the problem of constructing well balanced families contains as a subproblem the question of the existence of Steiner systems. Recall that a t-Steiner system (or (v, k, λ) t-design) is a family of blocks such that each t-element subset appears in exactly λ blocks (see [START_REF]The CRC Handbook of Combinatorial Designs[END_REF][START_REF] Colbourn | Steiner systems[END_REF]). In that case it is well-known that also, for 1 ≤ j ≤ t each j-element subset appears in exactly λ j blocks, where

λ j = λ ( v-j t-j ) ( k-j t-j )
. So a t-design is j-balanced for all j, 1 ≤ j ≤ t. In particular, if t = k -1 and the blocks are repeated the same or almost the same number of times, then a k-Steiner System is also well balanced. As an example, a Steiner Triple System (STS) consists of a family of triples, such that each pair of elements appears in exactly one triple. In that case each element appears in v-1 2 triples and no triple is repeated. Therefore, an STS is a well balanced family. It is well-known that an STS exists if and only if v ≡ 1 or 3 (mod 6) and then b = v(v-1)

6

. That gives some sporadic values for which there exist well balanced families. In Section 6, we construct many other families; for example we show that such families exist for any b for the values of v ≡ 3 (mod 6) for which there exist a large number of disjoint Kirkman triple systems (see [START_REF] Lu | On large sets of disjoint Steiner triple systems I, II, III[END_REF]15]). We also develop various tools and use them to solve many cases when v = 6t + 4 and to verify the conjecture for small values of v. Finally, in Section 7, we present some results for values of k > 3.

Properties of P (F, x) and well balanced families

Recall that λ x1,...,xj denotes the number of blocks of the family containing the j-element subset {x 1 , . . . , x j }. By convention λ ∅ = b. In this section, we express the polynomial P (F, x) in function of λ x1,...,xj and deduce the optimality of well balanced families.

Proposition 1 P (F, x) = k j=0 x1,...,xj λ x1,...,xj (λ x1,...,xj -1)(x -1) j . RR n°7725 Proof P (F, x) = k h=0 v h x h . Let us write P (F, x) = k j=0 µ j (x-1) j . Using x h = (x-1+1) h = h j=0 h j (x -1) j , we get µ j = k h=j h j v h .
We claim that µ j = x1,...,xj λ x1,...,xj (λ x1,...,xj -1). Indeed λ x1,...,xj (λ x1,...,xj -1) counts the number of ordered pairs of blocks which contain x 1 , . . . , x j . This number is the sum of the ordered pairs of blocks which intersect in exactly the j elements x 1 , . . . , x j , plus those intersecting in exactly j + 1 elements containing x 1 , . . . , x j , plus more generally those intersecting in exactly in h elements containing x 1 , . . . , x j , where, j ≤ h ≤ k. When we sum on all the possible j-element subsets to obtain x1,...,xj λ x1,...,xj (λ x1,...,xj -1) , we therefore get:

• the number of ordered pairs of blocks intersecting in exactly j elements, that is v j

• plus the number of ordered pairs of blocks intersecting in exactly j + 1 elements, which are counted j+1 j times. Indeed, if the intersection of two blocks is {x 1 , . . . , x j+1 } they are counted for all the j-element subsets included in {x 1 , . . . , x j+1 } which are in number j+1 j . Therefore we have j+1 j v j+1 such ordered pairs of blocks.

• plus more generally, for h, j ≤ h ≤ k we count h j v h ordered pairs of blocks intersecting in exactly h elements; indeed if the intersection of two blocks is {x 1 , . . . , x h } they are counted for all the j-element subsets included in {x 1 , . . . , x h }, that is h j times. Therefore we get exactly µ j which is the left-hand side of the equation of the claim.

We will use the following equality intensively

It follows from the fact that a given block B is counted once in all the λ x1,...,xj such that {x 1 , . . . , x j } ⊂ B and we have k j such j-element subsets.

Theorem 1 P (F, x) = k j=1 x1,...,xj λ 2 x1,...,xj (x -1) j -bx k + b 2 .
Proof Using Equation 1, we get

k j=0 x1,...,xj λ x1,...,xj (x -1) j = k j=0 b k j (x -1) j = b(x - 1 + 1) k = bx k .
Replacing in the expression of P (F, x) given in Proposition 1 and using the fact that λ 2 ∅ = b 2 we obtain the theorem.

So, we can state our main theorem

Theorem 2 If F * is well balanced, then F * is optimal, that is, P (F * , x) ≤ P (F, x) for any F and any x ≥ 1.

Proof If F * is well balanced, then all the coefficients of the polynomial as expressed in the Theorem 1 are minimized and so F * is optimal.

Note that for a j-balanced family, the coefficient of (x -1) j in the polynomial P (F, x) is easy to compute. Let b k j = q v j + r, with r < v j . Then we have r values of the λ x1,...,xj equal to q + 1 and v j -r equal to q. So, x1,...,xj λ 2 x1,...,xj = v j q 2 + 2qr + r. When b = v k , the family consisting of all the possible k-element subsets is well balanced and will be called a complete family. Furthermore, for any j, the values of the λ x1,...,xj are all equal to λ j = v-j k-j . By taking h copies we get also a well balanced family for b = h v k .

Proposition 3 Let v and k be given and let b

′ = h v k + b with b < v k .
Then, there exists a well balanced family F ′ for b ′ if and only if there exists a well balanced family F for b.

Proof If we have a well balanced family F for some b ≤ v k we can construct a well balanced family F ′ for b ′ = h v k + b by adding h complete families to F. Conversely if we have a well balanced family F ′ for b ′ = h v k + b, each k-element subset is repeated h or h + 1 times and so by deleting h copies of each block, we can deduce a well balanced family for b.

The next proposition generalizes this idea to optimal families.

Proposition 4 Let v and k be given and let b

′ = h v k +b with b ≤ v k .
If there exists an optimal family for b ′ , then there exists an optimal family for b and furthermore the optimal family for b ′ consists of the optimal family for b plus h complete families.

Proof Suppose there exists an optimal family F ′ for b ′ . This family is necessarily k-balanced. Indeed suppose it is not the case and let F ′′ be a k-balanced family (such a family can be easily constructed by taking among the v k subsets of size k, b of them repeated h + 1 times and the other v k -b repeated h times). But, the coefficient of x k in P (F ′′ , x) will be strictly less than that of P (F ′ , x) and so for x large enough P (F ′′ , x) < P (F ′ , x) contradicting the optimality of F ′ . So each k-element subset appears exactly h or h + 1 times.

P (G ′ , x) -P (F ′ , x) = P (G, x) -P (F, x)
. Therefore if F is not optimal there exists a family G and a value x for which P (G, x) < P (F, x) and for this value of x we have P (G ′ , x) < P (F ′ , x) and F ′ is not optimal, a contradiction.

We conjecture that the converse is true: that is starting from an optimal family F for some b ≤ v k , the family F ′ obtained by adding h complete families is also optimal. This is true, if Conjecture 1 on the existence of an optimal family for any v, b, k is true, as in that case any optimal family is k-balanced.

In what follows we will restrict ourselves to the case b ≤ v k . In fact the following proposition shows that we only need to consider the values of b ≤ 1 2 v k .

RR n°7725

Proposition 5 Let v and k be given. An optimal family F for b = v k -b can be obtained from an optimal family F for b ≤ v k by taking as blocks the k-element subsets which are not blocks of F.

Proof Let F be an optimal family with b blocks and let F be the family obtained from F by taking as blocks the k-element subsets which are not blocks of F. F has b = v k -b blocks. Furthermore, if λx1,...,xj denotes the number of blocks of the family F containing {x 1 , . . . , x j }, we have λx1,...,xj = v-j k-j -λ x1,...,xj . Consider another family Ḡ with b blocks and let G be the complementary family obtained from Ḡ by taking as blocks the k-element subsets which are not blocks of Ḡ; G has b blocks. We also have: μx1,...,xj = v-j k-j -µ x1,...,xj and so we get P ( Ḡ, x) -P ( F, x) = P (G, x) -P (F, x). Therefore if F is an optimal family, then F is also an optimal family.

Case k = 2

Theorem 3 Let k = 2. Then for any v and b there exists a well balanced family.

Proof In view of Proposition 4, we only need to consider the case b ≤ v 2 . In the case k = 2 the blocks are pairs of elements and so the problem consists of designing a simple graph with v vertices and b edges that is almost regular (the degree of a vertex

x being d(x) = ⌊ 2b v ⌋ or ⌈ 2b v ⌉). We distinguish two cases. • Case v even. Let b = q v 2 + r for 0 ≤ r < v 2 .
It is well-known that, for v even, the edges of the complete graph K v can be partitioned into v -1 perfect matchings (set of v 2 disjoint edges covering the vertices). In that case the family consisting of q perfect matchings plus r edges of the (q + 1)th perfect matching forms the required family with b = q v 2 + r edges, none of them repeated and with the degree of a vertex equal to q or q + 1.

• Case v odd. Let b = qv + r for 0 ≤ r < v. It is also well-known that for v odd, the edges of the complete graph K v can be partitioned into v-1 2 hamiltonian cycles (cycles containing each vertex exactly once). In that case consider the family consisting of q hamiltonian cycles plus the following r edges of the (q + 1)th hamiltonian cycle: if the cycle is x 0 , x 1 , . . . , x i , . . . , x v-1 we take the r edges {x 2j , x 2j+1 } for 0 ≤ j ≤ r -1 (indices being taken modulo v). Then it consists of b = qv + r edges none of them being repeated; furthermore the degree of a vertex is 2q or 2q + 1 if r ≤ v-1 2 and 2q + 1 or 2q + 2 otherwise and so in both cases

d(x) = ⌊ 2b v ⌋ or ⌈ 2b v ⌉.
An algorithm to construct a well balanced family starting from any family.

In some cases related to practical applications, files and servers may be appearing or disappearing over time, leaving the storage system in an unbalanced situation. Instead of starting over, it might be helpful to design an algorithm which, starting from some family, constructs an optimal well balanced family. That is in general a difficult problem; but for k = 2, we can easily design such a procedure.

Let v and b be given and k = 2 and consider any family F; we will transform it into a well balanced family with the same parameters. First let us construct a 2-balanced family. Suppose, F is not 2-balanced; so there exist two edges (blocks) {x, y} and {z, t} with λ x,y ≥ λ z,t + 2. Then, delete from F one edge {x, y} and add one edge {z, t}. Repeating this procedure we end after a finite number of steps with a family such that for any pair of edges {x, y} and {z, t} |λ x,y -λ z,t | ≤ 1, that is a 2-balanced family. Now let us show how to construct a well balanced family from a 2-balanced one. Let F be a 2-balanced family with λ x,y = λ or λ -1; suppose it is not 1-balanced; then there exist two vertices x and z with d(x) ≥ d(z)+2. So there exists a vertex y = x, z with λ x,y ≥ λ z,y + 1; otherwise d(x) = y =x,z λ x,y + λ x,z ≤ y =x,z λ z,y + λ x,z = d(z) a contradiction. Thus, λ x,y = λ and λ z,y = λ -1. Deleting from F one edge {x, y} and adding one edge {z, y}, we still get a 2-balanced family F ′ (λ ′

x,y = λ -1 and λ ′ z,y = λ); but we have reduced the gap between the degrees of x and z, as d ′ (x) = d(x) -1 and d ′ (z) = d(z) + 1, while the other degrees remain unchanged. Repeating this procedure we end after a finite number of steps with a 1-balanced and 2-balanced, so a well balanced family.

Case k = 3: Impossible configurations

For k = 3, there are values of v and b for which there do not exist well balanced families. In this section, we identify several such sets of parameters. Then, in Section 6, we proceed towards the construction of well balanced families for some other cases.

Consider for instance v = 4 and b = 2. There are 6 possible different pairs {x, y} and 6 pairs in the two blocks, so if there exists a 2-balanced family, then λ x,y = 1 for all {x, y}. But this is impossible as v -1 = 3 and there cannot exist a partition of the edges of K 4 into triples (non existence of a (4, 3, 1)-design). The argument is generalized in the following proposition:

Proposition 6 Let k = 3, v be even and λ be odd. If λ v(v-1) 2 -v 2 < 3b < λ v(v-1)

2

+ v 2 , then there does not exist a 2-balanced family.

Proof Note that the number of possible pairs is v(v-1)

2

. By Equation 1, x,y λ x,y = 3b. We distinguish three cases:

• 3b = λ v(v-1)

2

. In that case a 2-balanced family will verify λ x,y = λ for all pairs {x, y} and then we should have λ x = λ v-1 2 which is impossible as λ is odd and v is even (non existence of a (v, 3, λ)-design for v even and λ odd).

• 3b < λ v(v-1)

2

. In that case we cannot have all the λ x,y ≥ λ. So we have one of the λ x,y ≤ λ -1 and if the family is 2-balanced all the λ x,y ≤ λ. But, then λ x ≤ λ v-1 2 and as

λ(v -1) is odd, λ x ≤ λ v-1 2 -1 2 . Using Equation 1, 3b = x λ x ≤ λ v(v-1) 2 -v 2 . Therefore, there does not exist a 2-balanced family if λ v(v-1) 2 -v 2 < 3b < λ v(v-1) 2 . • 3b > λ v(v-1)

2

. In that case we cannot have all the λ x,y ≤ λ. So we have one of the λ x,y ≥ λ + 1 and if the family is 2-balanced all the λ x,y ≥ λ. But, then λ x ≥ λ v-1 2 and as

λ(v -1) is odd, λ x ≥ λ v-1 2 + 1 2 . Using Equation 1, 3b = x λ x ≥ λ v(v-1) 2 + v 2 . Therefore there does not exist a 2-balanced family if λ v(v-1) 2 < 3b < λ v(v-1)
Proposition 7 Let k = 3. If λ v(v-1)

6

is not an integer, then there does not exist a well balanced family for b = ⌊λ v(v-1)

6 ⌋ and b ′ = ⌈λ v(v-1) 6 ⌉. Proof Let b = ⌊λ v(v-1) 6 ⌋. If λ v(v-1) 6 is not an integer, then 3b = λ v(v-1) 2 -ǫ where ǫ = 1 or 2. By Equation 1, 3b = x λ x and so if F is 1-balanced λ x = λ(v-1) 2 except for ǫ vertices for RR n°7725
which the value is one less. Similarly by Equation 1, 3b = x,y λ x,y and so if F is 2-balanced λ x,y = λ except for ǫ pairs appearing λ -1 times. But for an x 0 with λ x0 = λ(v-1)

2

-1, we have λ(v -1) -2 pairs containing it (2 pairs per block containing it) and so two pairs appear λ -1 times. If ǫ = 2 we have another vertex

x ′ 0 with λ x ′ 0 = λ(v-1)

2

-1 and altogether at least 3 pairs appear λ -1 times (only the pair {x 0 , x ′ 0 } can be counted twice). So, we have, in all cases, at least ǫ + 1 pairs appearing λ -1 times, contradicting the fact that if F is 2-balanced only ǫ pairs appear λ -1 times.

The proof for b

′ = ⌈λ v(v-1) 6 ⌉ is similar. In that case 3b ′ = λ v(v-1) 2 + ǫ where ǫ = 1 or 2. If F is 1-balanced λ x = λ(v-1)
2 except for ǫ vertices for which the value is one more. If F is 2-balanced λ x,y = λ except for ǫ pairs appearing λ + 1 times. The argument applied for the vertex x 0 (or both x 0 and x ′ 0 ), with λ x0 = λ(v-1)

2

+ 1 gives at least ǫ + 1 pairs appearing λ + 1 times, a contradiction. Proposition 7 applies for v ≡ 5 (mod 6) and λ ≡ 0 (mod 3); for example there do not exist well balanced families for {v = 5; b ≡ 3, 4, 6, 7 (mod 10)} or {v = 11; b ≡ 18, 19, 36, 37 (mod 55)}. It applies also for v ≡ 2 (mod 6) and λ ≡ 0 (mod 3); for λ odd it is included in Proposition 6, but for λ even we get new values of non existence of well balanced families for {v = 8; b ≡ 18, 19, 37, 38 (mod 56)}.

6 Case k = 3: Construction of well balanced families

Summary of the results

Our current results are summarized in Table 1. In addition to well balanced families, we provide solutions to the optimization problem stated in introduction for the "small" values of v and any value of b. To construct some well balanced families we will use some results obtained in design theory in particular on Steiner Triple Systems (see the handbook [START_REF]The CRC Handbook of Combinatorial Designs[END_REF] for details).

The results obtained lead us to conjecture that the values excluded by Propositions 6 and 7 are the only ones for which there do not exist well balanced families. In what follows we will construct well balanced families for b ≤ v 3 ; indeed due to Proposition 3, it gives all the values of the form b + h v 3 .

STS and KTS (Steiner Triple Systems and Kirkman Triple Systems)

Recall that a (v, 3, 1) Steiner Triple System (STS(v) shortly) is defined as a family of triples (blocks of size 3), such that every pair of elements belongs to exactly one block (λ x,y = 1). So it is 2-balanced (and also 3-balanced); it is well-known that every vertex belongs to exactly v-1 2 blocks and therefore it is well balanced. Such a design exists if and only if v ≡ 1 or 3 (mod 6).

In that case b = v(v-1)

6

. For example, for v = 7, the blocks of a (7, 3, 1)-design are B i = {i, i + 1, i + 3}, 0 ≤ i ≤ 6, the numbers being taken modulo 7. For v = 9, we provide below two STS (9)

v = 9: {0, ∞, ∞ ′ } {0, 2, 5} {0, 3, 4} {0, 1, 6} {1, 2, 4} {1, 3, ∞ ′ } {1, 5, ∞} {2, 3, ∞} {3, 5, 6} {4, 6, ∞} {2, 6, ∞ ′ } {4, 5, ∞ ′ } Example 1 (a): a Kirkman triple System K A for v = 9 {1, ∞, ∞ ′ } {1, 3, 6} {1, 4, 5} {1, 2, 0} {2, 3, 5} {2, 4, ∞ ′ } {2, 6, ∞} {3, 4, ∞} {4, 6, 0} {5, 0, ∞} {3, 0, ∞ ′ } {5, 6, ∞ ′ } Example 1 (b): another Kirkman Triple System K B for v = 9
Using directly Steiner Triple Systems provides some sporadic values of v and b for which there exist well balanced families. We can get more values of b by considering more than one STS(v); but we have to ensure that the family is 3-balanced (that is no block is repeated). Fortunately the answer can be obtained due to the existence of families of disjoint STS(v) (see Theorem 4 below). Two STS(v) are said to be disjoint if they have no triple in common. A set of v -2 disjoint STS(v) is called a large set of disjoint STS(v) and briefly denoted by LSTS(v). An LSTS(v) can be viewed as a partition of the complete family of v 3 triples into STS(v). In 1850, Cayley showed that there are only two disjoint STS [START_REF] Colbourn | Steiner systems[END_REF] and so there is no LSTS [START_REF] Colbourn | Steiner systems[END_REF]. The same year Kirkman showed that there exists an LSTS (9). Such an LSTS( 9) is given by taking as first STS(9) that of Example 1 (a); the 6 other STS(9) are obtained from the first one by developing modulo 7 (that is applying the automorphism fixing ∞ and ∞ ′ and mapping i to i + 1). For example, the second STS( 9) is obtained by adding 1 to each number (∞ and ∞ ′ are invariant and 6 + 1 = 0 (mod 7)) and given in Example 1 (b).

RR n°7725

Due to the efforts of many authors the following theorem completely settles the existence of LSTS(v).

Theorem 4 ( [START_REF] Lu | On large sets of disjoint Steiner triple systems I, II, III[END_REF]15,[START_REF] Teirlinck | A completion of Lu's determination of the spectrum of large sets of disjoint Steiner triple systems[END_REF] (see [START_REF] Ji | A new existence proof for large sets of disjoint Steiner triple systems[END_REF] for a simple proof )) For v ≡ 1 or 3 (mod 6), v > 7, there exists an LSTS(v).

Proposition 8 Let k = 3, and v ≡ 1 or 3 (mod 6), v > 7, then there exists a well balanced family for any b multiple of v(v-1)

6

.

Proof Let b = h v(v-1) 6 ; b ≤ v 3 or equivalently, h ≤ v -2.
According to Theorem 4, there exists an LSTS(v), formed of v -2 disjoint STS(v). Then, the family consisting of any h disjoint STS(v), extracted from the LSTS(v), is well balanced (with λ x,y = h and λ x = h v-1

2 ). For b ≥ v 3 the result follows by using Proposition 3.

We will see in Proposition 20 that the existence of two disjoint STS [START_REF] Colbourn | Steiner systems[END_REF] suffices to construct a well balanced family for v = 7 and any b.

When v = 6t + 3, there exist STS(v) which have a stronger property. The triples of the STS(v) can themselves be partitioned into 3t + 1 classes, called parallel classes, where a parallel class consists of 2t + 1 blocks forming a partition of the v elements. Such an STS(v) is called resolvable or a Kirkman Triple System (briefly KTS(v)). Examples 1 (a) and (b) are KTS (9) where the 4 parallel classes correspond to the 4 columns. It is well-known that a KTS(v) exists for any v ≡ 3 (mod 6) [START_REF] Ray-Chauduri | Solution of Kirkman's schoolgirl problem[END_REF].

In our next constructions, we will need families of disjoint STS(v) containing a KTS(v). The existence of mixed STS/KTS structures has not been specifically studied in the literature and we propose some conjectures about them (Conjectures 3, 4 and 5). However we can use results on families of disjoint KTS, which have indeed been studied for a long time. A set of v -2 disjoint KTS(v) is called a large set of disjoint KTS(v) and briefly denoted by LKTS(v). As mentioned previously, Kirkman showed in 1850 that an LKTS(9) exists and in 1974, Denniston found an LKTS (15). For v = 9, the LSTS(9) described above, is in fact an LKTS(9) as the resolvabilty is conserved by automorphisms. An example of a KTS(15) denoted K A is given in Example 2 below. Developing modulo 13, that is, applying the automorphism fixing ∞ and ∞ ′ and mapping i to i + 1, we get 13 disjoint KTS (15) and so an LKTS (15)

∞ ′ } {1, 10, ∞ ′ } {4, 9, ∞ ′ } {5, 7, ∞ ′ } {11, 12, ∞ ′ } {2, 8, ∞ ′ } {0, ∞, ∞ ′ } Example 2 (a): a Kirkman Triple System K A for v = 15 {1, 2, 10} {1, 3, 8} {1
∞ ′ } {2, 11, ∞ ′ } {5, 10, ∞ ′ } {6, 8, ∞ ′ } {12, 0, ∞ ′ } {3, 9, ∞ ′ } {1, ∞, ∞ ′ } Example 2 (b): another Kirkman Triple System K B for v = 15 RR n°7725
Since then, many people have done some research on their existence. The more recent paper is [START_REF] Zhou | New results on large sets of Kirkman triple systems[END_REF] where the reader can find other references. The results to date are summarized in the following theorem:

Theorem 5 [18, Theorems 1.1 and 3.3] (a) For any integer r ∈ {1, 7, 11, 13, 17, 35, 53, 67, 91, 123} ∪ {2 2p+1 25 q : p, q ≥ 1}, there exists an LKTS(v) for v = 3 a 5 b r s i=1 (2.13 ni + 1)

t j=1 (2.7 mj + 1), a, n i , m j ≥ 1 (1 ≤ i ≤ s, 1 ≤ j ≤ t), b, s, t ≥ 0 and further a + s + t ≥ 2 if b ≥ 1 and r = 1. (b) There exists an LKTS(3v) for v = s i=1 (2q ni i +1) t j=1 (4 mj -1)
where s+t ≥ 1, n i , m j ≥ 1, q i ≡ 7 (mod 12) and q i is a prime power.

Case v = 6t + 3

We first propose a simple construction which gives the answer for v = 6t + 3, when there exist families of disjoint STS(v), at least one of them being a KTS(v).

Proposition 9 Let k = 3 and v = 6t + 3. If there exists a family of 3t + 1 disjoint STS(v), one of them being a KTS(v), then there exists a well balanced family for any b.

Proof By Propositions 3 and 5, we can suppose b ≤

1 2 v 3 = (2t + 1)(3t + 1) 6t+1 2 .
Let the number of blocks be b = q(2t + 1)(3t + 1) + r(2t + 1) + s with 0 ≤ q ≤ 3t; 0 ≤ r < 3t + 1; 0 ≤ s < 2t + 1. Then a well balanced family for b consists of q disjoint STS(v) taken from the family avoiding the singled-out KTS(v), plus r parallel classes of the KTS(v) and s triples of the (r + 1)th parallel class of this KTS(v). Indeed, by assumption on the family, all the triples are disjoint and so λ x,y,z = 0 or 1. In each STS(v) a pair of elements appears exactly once; so λ x,y = q or q + 1 (exactly q if r = 0, s = 0). In each parallel class of the KTS(v), each vertex appears exactly once; so λ x = (3t + 1)q + r or (3t + 1)q + r + 1 (exactly (3t + 1)q + r if s = 0). Proposition 9 can be applied when there exists an LKTS(v). There is no need to have a structure as strong as this, but only 3t + 1 disjoint STS, with one of them being a KTS. We conjecture that such a structure always exists for v = 6t + 3; this conjecture will imply Conjecture 2 for v ≡ 3 (mod 6).

Conjecture 3 For v = 6t + 3, there exist 3t + 1 disjoint STS(v) one of them being a KTS(v).

The following stronger conjecture is also interesting.

Conjecture 4

For v = 6t + 3, there exist an LSTS(v) such that one of its STS(v) is a KTS(v).

Constructions for v = 6t + 4

In this section we present various construction techniques for the case v = 6t + 4. We will need the existence of two disjoint KTS(6t + 3) denoted K A and K B . We illustrate them for v = 10 (Proposition 16) and v = 16 (Proposition 17) verifying Conjecture 2 for these values. For v = 10 we will use the two disjoint KTS(9) of Example 1 (a) and Example 1 (b). To ease the reading, we substitute ∞ with 7 and ∞ ′ with 8.

K A : {0, 7, 8} {0, 2, 5} {0, 3, 4} {0, 1, 6} K B : {1, 7, 8} {1, 3, 6} {1, 4, 5} {0, 1, 2} {1, 2, 4} {1, 3, 8} {1, 5, 7} {2, 3, 7} {2, 3, 5} {2, 4, 8} {2, 6, 7} {3, 4, 7} {3, 5, 6} {4, 6, 7} {2, 6, 8} {4, 5, 8}
{0, 4, 6} {0, 5, 7} {0, 3, 8} {5, 6, 8} RR n°7725

Splitting Process: Construction A

The following central construction applies to a family containing a KTS(6t+3) and adds 2(2t+1) blocks to it. It consists in "splitting" triples using an extra element. Construction A. Consider a parallel class of a KTS(6t + 3) and a new element α (= 6t + 4) and replace each of the 2t + 1 triples {x j , y j , u j } of this class (1 ≤ j ≤ 2t + 1) by the 3 triples {x j , y j , α}, {x j , u j , α}, and {y j , u j , α}.

For example take the KTS(9) K A . We replace the first class consisting of the 3 blocks {0, 7, 8}, {1, 2, 4}, {3, 5, 6} by the 9 blocks {0, 7, α}, {0, 8, α}, {7, 8, α}, {1, 2, α}, {1, 4, α}, {2, 4, α}, {3, 5, α}, {3, 6, α}, {5, 6, α}.

Proposition 10 Let k = 3 and v = 6t + 4. If there exist, for p ≤ 3t + 1, min(2p, 6t) disjoint STS(6t + 3) one of them being a KTS(6t + 3), then there exists a well balanced family for b 2p = 2p(3t + 2)(2t + 1).

Proof We apply Construction A for p classes of the KTS K A by adding a new element α. As the classes are taken in the same KTS, α appears in 3p(2t + 1) disjoint triples; so λ α = 3p(2t + 1). Furthermore each pair {α, x} appears exactly 2p times; so λ α,x = 2p. Then, for 1 ≤ p ≤ 3t, we add to this modified K A , (2p-1) STS(6t+3), that exist by hypothesis. Any x = α appears 3t+1 times in each of these STS and 3t + 1 + p times in the modified K A ; so, λ x = 2p(3t + 1) + p = 3p(2t + 1). Each pair {x, y} (x = α, y = α) appears exactly once in the modified K A and in each of the other 2p -1 STS; so, λ x,y = 2p. Therefore the family constructed is well balanced. For p = 3t + 1, the result was already known, as the family obtained is a complete family with b 6t+2 = (6t + 2)(3t + 2)(2t + 1) = 6t+4 3 . So only 2p = 6t disjoint STS(6t + 3) are needed.

We can extend Proposition 10 to get well balanced families for more values of b either by deleting or adding blocks. However, we need the existence of a second disjoint KTS(6t + 3) K B and of other disjoint STS. We conjecture that such a structure always exists.

Conjecture 5 For v = 6t + 3, there exists an LSTS(v) such that two of its STS(v) are KTS(v).

We will present now a deletion process (Deletion A-B), an addition process (Construction B), and then a construction (Construction C) useful for small values of b, not covered by the previous constructions.

Deletion Process: Deletion A-B

We start with the well balanced family obtained in Proposition 10 for b 2p with a KTS(6t + 3) K A . We also suppose that there exists a second KTS(6t + 3), denoted K B , and we choose it as one of the other 2p -1 STS(6t + 3) used in the proof of the proposition. We now present a deletion process.

Deletion A-B. This construction consists in deleting a block {x, y, α} appearing in a class of K A modified by Construction A, and some blocks of the class of K B which contains the pair {x, y}, except precisely the block {x, y, z} of this class. Doing so some pairs appear one less and if we delete all the blocks of the class of K B , different from {x, y, z}, all elements appear one less except z. We can also delete a whole class of K B , in which case all elements appear one less except α.

We illustrate this process with an example, which will also serve for other constructions. Otherwise we can conclude only if p ≥ 2. Indeed, either the block {z 1 , z 2 , z 3 } is in a K C = K A and we choose K C as one of the 2p STS(6t + 3) used in the proof of Proposition 10. Otherwise, Using Proposition 5 we get also:

if {z 1 , z 2 , z 3 } is in K A ,
Proposition 13 Let k = 3, v = 6t + 4, 1 ≤ p ≤ 3t + 1 and b 2p = 2p(3t + 2)(2t + 1)
. If there exist min(2p + 1, 6t + 1) disjoint STS(6t + 3), two of them being a KTS(6t + 3), then there exists a well balanced family for b 2p ≤ b ≤ b 2p + 6t + 3 and when t ≥ 2 and p = 3t -

1 for b 2p ≤ b ≤ b 2p + (12t + 7).
Note that, for p = 3t + 1, we do not need the hypothesis on the existence of disjoint STS. Indeed, we can use the complete family on 6t + 4 elements where the modified K A consists of all the blocks containing α and K B is a KTS(6t + 3) (which always exists).

Addition Process: Construction B

In what follows we suppose again that k = 3 and v = 6t + 4 and that there exist 2p + 1 (p ≤ 3t) disjoint STS(6t + 3), two of them denoted K A and K B being KTS(6t + 3). We start with the well balanced family obtained for b 2p by using K A and by choosing the other 2p -1 STS(6t + 3) to be different from K B . We now present an addition process called Construction B.

Construction B. Choose a class C of K B , replace a block {x, y, z} by the block {x, y, α} and add some of the other 2t blocks of this class. This construction can be combined with Construction A as long as {x, y} is not a pair appearing in a modified block of K A (otherwise the block {x, y, α} will be repeated).

Doing Construction B for one class C 1 of K B is always possible as we have the freedom to choose the classes to modify in K A . For example, we choose a triple {x 1 , y 1 , z 1 } in K B to be modified and fix the class C A of K A containing {x 1 , y 1 } as one of the non modified class in Construction A. Applying Construction B for C 1 , we get a well balanced family for b

2p ≤ b ≤ b 2p + 2t + 1.
We can do Construction B a second time with another block {x 2 , y 2 , z 2 } chosen in another class of K B replacing it by the block {x 2 , y 2 , α}. We can choose this block in such a way that the pair {x 2 , y 2 } also appears in the class C A of K A containing {x 1 , y 1 }. For that, let C A be the class of K A containing {x 1 , y 1 } and let {z 1 , x 2 , a 2 } be the triple of this class containing z 1 . Note that this triple is different from that containing {x 1 , y 1 } as no block is repeated and the block {x 1 , y 1 , z 1 } is already in K B . We choose as the second class C 2 of K B that containing the pair {z 1 , x 2 }. Let {z 1 , x 2 , z 2 } be the triple containing the pair {z 1 , x 2 }; we apply Construction B by replacing it with {z 1 , x 2 , α}. So, adding {z If t = 1 (v = 10), we cannot go further as we have used the 4 classes of K B , but we know by proposition 6 that there does not exist a family for b 2p + 14. Now, we suppose t ≥ 2 and continue the process by applying Construction B for other classes of K B . We have only to make sure that the pairs {x, y} of the modified block {x, y, α} are not appearing in a modified block of K A and are pairwise disjoint, otherwise we will have created two pairs {x, α}. So, we can do Construction B with a block {x 4 , y 4 , z 4 } as long as x 4 and y 4 are different from the 6 elements x 1 , y 1 , z 1 , x 2 , z 2 , x 3 . Note that these 6 elements can appear in a pair in at most 3 blocks of a class. So an admissible pair {x 4 , y 4 } always exists. This pair can be in a class of K A different from C A and C ′ A and the construction works only for p ≤ 3t -2. If t ≥ 3, a simple counting argument shows that we can find two blocks {x 4 , y 4 , z 4 } and {z 4 , y 5 , z 5 } with x 4 , y 4 , z 4 , y 5 , different from the 6 elements x 1 , y 1 , z 1 , x 2 , z 2 , x 3 . Note that the pair {z 4 , y 5 } can appear in a class of K A different from C A , C ′ A and the class containing {x 4 , y 4 }; so in general the construction works only for p ≤ 3t -3. For t = 2, that is v = 16, we will see in Appendix 1 that it also true. We summarize our results in the following proposition.

Construction C

We take the blocks of an STS(v), v ≡ 1 or 3 (mod 6). We choose v+1 2 pairs {x i , y i } (0

≤ i ≤ v-1
2 ) covering all the elements. So, as v is odd, each element is covered once, except one x 0 which is covered twice. Then, we add the v+1 2 blocks {x i , y i , α}. Doing so we get a well balanced family for v + 1 and b = v(v-1) 6 + v+1 2 ; indeed λ x = v+1 2 except λ x0 = v+1 2 + 1 and λ x,y = 1 except for the v+1 2 chosen pairs and {x 0 , α} for which the value is 2. Then we can continue adding h disjoint blocks (1 ≤ h ≤ v 3 ) as long as they are not in the STS(v), do not contain x 0 and do not contain one of the pairs for which the value λ x,y = 2. We can continue the process as long as we keep the balance.

More generally, when v + 1 = 6t + 4, we apply Construction C starting with some STS(v) and choosing the v+1 2 = 3t + 2 covering pairs in a small number of classes (only 2 if possible) of another KTS(6t + 3). Then we can add the h blocks of a non used class replacing the block {x 0 , y 0 , z 0 } containing the x 0 which is repeated twice by the block {α, y 0 , z 0 }. We get all the values of b such that (3t + 1)(2t + 1) + 3t + 2 ≤ b ≤ (3t + 1)(2t + 1) + 5t + 3 = (6t + 4)(t + 1). Note that we have, for b = (6t + 4)(t + 1): λ x = 3(t + 1) and λ x,y = 1 or 2. We can also mix Construction C with Construction A as long as the pairs containing α are not in a modified class of K A . We can then continue adding a new class with a block modified and so on like we did in Construction B.

Let us now show how Construction C gives the missing values, for v = 10. We will use Construction C by choosing as first STS(9) K A and by picking the pairs in the KTS K B given at the beginning of this subsection. We add the triples {1, 8, α}, {3, 5, α}, {0, 6, α}, obtained with pairs appearing in the first class of K B . We also add {2, 4, α}, {0, 7, α} using pairs appearing in the second class of K B . We get a well balanced family for b = 12 + 5 = 17. Here λ x = 5 except λ 0 = 6, as 0 appears in two added blocks; λ x,y = 1 except for the 6 pairs {1, 8}, {3, 5}, {0, 6}, {2, 4}, {0, 7}, and {0, α}. Then, we can add the 2 blocks of the 3rd class {1, 4, 5} and {2, 6, 7} and the block {3, 8, α}. Therefore we get the missing values 17 ≤ b ≤ 20. Note that for b = 20, λ x = 6 and λ x,y = 1 or 2, as a pair appears exactly in one block of K B .

So, we have completely solved the case v = 10, as summarized in the following proposition:

Proposition 16 For v = 10 conjecture 2 is verified; that is there exists a well balanced family for all b, except b ≡ 14, 15, 16 (mod 30) for which such a family cannot exist.

We also are able to completely solve the case v = 16. The proof of Proposition 17 is given in Appendix 1.

Proposition 17 For v = 16, Conjecture 2 is verified; that is there exists a well balanced family for all b except b ≡ 38, 39, 40, 41, 42 (mod 80) for which such a family cannot exist.

Other tools

We can also obtain results for other congruences of v.

Proposition 18 Let k = 3 and v = 6t > 6 (resp. v = 6t + 2). There exists a well balanced family for b = ht(6t -2) (resp. b = ht(6t + 2)).

Proof Take, as v + 1 ≡ 1 or 3 (mod 6), the blocks of a set of h disjoint STS(v + 1) and delete all the h v 2 blocks containing the element v + 1.

We can extend this construction to other values. As an example, consider v = 8 and b = 12. We start with the solution obtained before for b = 8 by deleting the blocks containing ∞ ′ in the Example 1 (a) of a KTS (9). Note that λ x,y = 1 except for the 4 pairs {0, ∞}, {1, 3}, {2, 6}, {4, 5} which are missing. We can add now 4 blocks taken from another KTS(9), for example that of Example 1 (b), containing these pairs; namely the blocks {5, 0, ∞}, {1, 3, 6}, {2, 6, ∞}, {1, 4, 5}.

We can also use, instead of triple systems, packing or covering with triples. For example, it is known (see [START_REF] Colbourn | Quadratic leaves of maximal partial triple systems[END_REF]), that when v ≡ 5 (mod 6), K v -H, where H is a 2-regular graph can be decomposed into triples when the number of edges is a multiple of 3. In particular, if we take a cycle H = C 3h+1 , 3h + 1 ≤ v, we get a well balanced family for b = v(v-1)-6h-2

6

. We get more values by taking decompositions of λK V -H, where H is a 2-regular graph (see [START_REF] Chaffee | Group divisible designs with two associate classes and quadratic leaves of triple systems[END_REF][START_REF] Chaffee | Neighborhoods in maximum packings of 2k n and quadratic leaves of triple systems[END_REF], but one needs to check that there are no repeated triples). Similarly (see [9]), for v ≡ 5 (mod 6), K v + H, where H is a 2-regular graph can be decomposed into triples if the number of edges is a multiple of 3. In particular if we take H = C 3h ′ +2 , 3h ′ + 2 ≤ v we get a well balanced family for b = v(v-1)+6h ′ +4

= v(v-1)-6h-2 6 with 3h + 1 ≤ v and b = v(v-1)+6h ′ +4 6 with 3h ′ + 2 ≤ v.
Similarly, when v ≡ 0, 2 (mod 6), K v minus a perfect matching can be decomposed into triples and so we get a well balanced family for b = v(v-2) 6 and when v ≡ 0 (mod 6), K v plus a perfect matching can be decomposed into triples and so we get a well balanced family for b = v 2 6 .

• The case λ

3 v(v -1)(v -2) < k(k -1)(k -2)b < λ 3 v(v -1)(v -2) + (k -2 -r)v(v -1
) can be handled exactly as the preceding one.

We could also get a similar result by using for a 3-balanced family the values of λ x but the result is in fact a consequence of Propositions 21 and 22. On the constructive side we have seen in Section 3 that a (v, k, λ)(k -1)-design is a well balanced family. Recall that a (v, k, λ) t-design is a family of blocks of size k such that each t-element subset appears in exactly λ blocks. When t = k -1 and λ = 1 a (v, k, 1)(k -1)-design is also called a Steiner System S(k -1, k, n). For k = 3 we have the classical STS(v).

For k = 4 it has been proved that a (v, 4, 1) 3-design also called a quadruple system SQS(v) exists if and only if v ≡ 2 or 4 (mod 6) [11]. For larger values of λ see for example Table 4.37 on page 82 of [START_REF]The CRC Handbook of Combinatorial Designs[END_REF]. For k ≥ 5 only few Steiner systems are known (see chapter II.5 of [START_REF]The CRC Handbook of Combinatorial Designs[END_REF]), such as the (12, 6, 1)5-design and the (11, 5, 1)4-design obtained by deleting an element or the (24, 6, 1)5-design and the (23, 5, 1)4-design.

Similar techniques as those used for k = 3 can be used for small values of v to obtain well balanced families for k = 4. We can also use resolvable designs. For k = 4 and v ≡ 4 or 8 (mod 12), there exist resolvable Kirkman Quadruple Systems, that is (v, 4, 1)(3)-design such that the quadruples can themselves be partitioned into (v-1)(v-2) 6 parallel classes, each consisting of v 4 blocks forming a partition of the v elements. We can also use disjoint SQS(v). Two SQS(v) are said to be disjoint if they have no quadruple in common. Similarly to STS(v), a set of v -3 disjoint SQS(v) is called a large set of disjoint SQS(v) and briefly denoted by LSQS(v). Unfortunately no such system has been shown to exist. However in [START_REF] Etzion | Towards a large set of Steiner quadruple systems[END_REF] v -5 disjoint quadruple systems have been exhibited when v = 5.2 p .

Conclusion

In this article we attack a conjecture (Conjecture 1) coming from a data placement problem. In this process, we introduce a new class of combinatorial objects, called well balanced families, which generalize classical designs. We give various constructions of well balanced families of triples; but we are far from getting a complete answer (see Conjecture 2). In some cases the answer will follow from some conjectures on disjoint Steiner Triple Systems which are of interest in themselves (Conjectures 3, 4, 5) and we hope that this paper will motivate new researches in design theory.

At that point we use a variant of Construction B; indeed instead of choosing the pair {x 4 , y 4 } in a class of K B different from one already used, we can choose it in a modified class add the remaining blocks of this class and all the blocks of another class to keep the balance. For example we replace {3, 10, 11} of the 4th class by {3, 10, α} (z 4 = 11), and {6, 11, 12} of the first class by {6, 11, α} (z 5 = 12). The advantage is that the pairs {3, 10}, {6, 11} are still in the 7th class of K A . Adding the blocks of 2 other classes we get a well balanced family for all 80p ≤ b ≤ 80p + 31 (we have to choose in K A not to modify the 7th class in Construction A). We can then replace the block {3, 7, 12} of the 7th class of K B by {7, 12, α} (z 6 = 3) and add all the other blocks of the 7th class of K B . We should not modify in K A the class containing {7, 12} namely the 3rd one. That is possible; indeed, as p ≤ 5, we can leave 2 classes unmodified in K A (the 3rd and 7th). Then we can add the block {z 4 , z 5 , z 6 } = {3, 11, 12} which appears in K A + 8 as translated from the block {8, 3, 4} and finally blocks of the last class not used of K B .

In summary we get a well balanced family for 80p ≤ b ≤ 80p + 37 for 0 ≤ p ≤ 5 and for p = 6, only 480 ≤ b ≤ 495. Using Proposition 5 and the fact that 16 3 = 560 we get also the values 65 ≤ b ≤ 80 and for p ′ ≥ 2, 80p ′ -37 ≤ b ≤ 80p ′ . So, we get all the values except b ≡ 38, 39, 40, 41, 42 (mod 80), for which we know by Proposition 6 that no well balanced family can exist, and 43 ≤ b ≤ 64 (and 496 ≤ b ≤ 517) for which we will use Construction C. For 49 ≤ b ≤ 64 (and 496 ≤ b ≤ 511), it follows also from the process of deletion.

Construction C. We use the Construction C by choosing the STS(15) K A and by picking the pairs in the KTS K B . We add the triples {0, 5, α}, {11, 12, α}, {8, 9, α} and {4, 7, α} obtained with pairs appearing in the first class of K B . We also add {1, 3, α}, {0, 6, α}, {10, 13, α} and {2, 14, α} with pairs appearing in the second class of K B . We get a well balanced family for b = 35 + 8 = 43. Here λ x = 8 except λ 0 = 9, as 0 appears in two pairs. Then, we can add the blocks of the 4th class replacing {0, 4, 13} by {4, 13, α} and so we get the missing values 43 ≤ b ≤ 48. That is enough to conclude.

Remark : However if we do not want to use DeletionA-B , but use only the addition process, we can get the missing values 49 ≤ b ≤ 64 by pursuing construction C. Note that for b = 48, λ x = 9 and λ x,y = 1 or 2 as a pair appears exactly in one block of K B . We then add the blocks of the 3rd (resp. 5th and 6th) classes of K B , replacing {7, 9, 11} by {7, 11, α}, (resp. {2, 3, 4} by {2, 3, α} and {5, 8, 12} by {8, 12, α}). Finally, we can add the block {4, 5, 9} which appears in the second class of K B and has not been modified. Note that λ x = 12 and no pairs appears 3 times as each element appears with α one or twice (case of 0, 2, [START_REF] Baert | Performance analysis of dat replication in grid delivery networks[END_REF][START_REF] Chaffee | Group divisible designs with two associate classes and quadratic leaves of triple systems[END_REF][START_REF] Colbourn | Steiner systems[END_REF][START_REF] Colbourn | Quadratic leaves of maximal partial triple systems[END_REF]11,[START_REF] Jean-Marie | Combinatorial designs and availability[END_REF][START_REF] Ji | A new existence proof for large sets of disjoint Steiner triple systems[END_REF]. Therefore, we get all the values 43 ≤ b ≤ 64. So we have completely solved the case v = 16.

  x1,...,xj λ x1,...,xj = b k j .

2 + v 2 .

 22 For example, there do not exist well balanced families for k = 3 and {v = 6; b ≡ 5 (mod 10)}; {v = 8; b ≡ 9, 10, 27, 28, 29, 46, 47 (mod 56)}; {v = 10; b ≡ 14, 15, 16 (mod 30)}; {v = 12; b ≡ 21, 22, 23 (mod 44)}; {v = 16; b ≡ 38, 39, 40, 41, 42 (mod 80)}.

Conjecture 2

 2 Let k = 3, there exists a well balanced family for the values of v and b different from that excluded by Propositions 6 and 7. In particular we conjecture that, if v ≡ 1 or 3 (mod 6), then there exists a well balanced family for any b.

Example 3 (v = 10 )

 310 Consider the case v = 10. We will use the Deletion A-B procedure to obtain well balanced families for b 2p -12 = 30p -12 ≤ b ≤ 30p = b 2p for any p, and RR n°7725

instead of using {x 3 , y 3 , u 3 }

 333 we use another block {x 4 , y 4 , u 4 } in the class modified of K A and select among a 4 , b 4 , c 4 a value distinct from z 1 and z 2 . The block {z 1 , z 2 , z 4 } cannot be in K A as the pair {z 1 , z 2 } appears once (already in {z 1 , z 2 , z 3 }). For p ≥ 2, we can apply other deletions. We have to choose if possible blocks in K B in classes not containing one of the pairs {z 1 , z 2 }, {z 1 , z 3 }, {z 2 , z 3 }. It is possible to do 3 more deletions for t > 2 (the case t = 1, v = 10 being already handled in Example 3 and t = 2, v = 16 is solved in Appendix 1) as we have at least 10 classes. Doing so we get the values b 2p -(12t + 7) ≤ b ≤ b 2p . We summarize the results obtained in the following proposition. Proposition 12 Let k = 3 and v = 6t + 4 ≥ 16, 2 ≤ p ≤ 3t + 1 and b 2p = 2p(3t + 2)(2t + 1). If there exist min(2p + 1, 6t + 1) disjoint STS(6t + 3), two of them being a KTS(6t + 3), then there exists a well balanced family for b 2p -(12t + 7) ≤ b ≤ b 2p .

  1 , x 2 , α} we get a well balanced family for b 2p + 2t + 2 and by adding some of the other blocks of C 2 , we get a well balanced family for b 2p + 2t + 2 ≤ b ≤ b 2p + 4t + 2. We can then add all the blocks of a third class of K B getting the following proposition: Proposition 14 Let k = 3, v = 6t + 4, 0 ≤ p ≤ 3t and b 2p = 2p(3t + 2)(2t + 1). If there exist 2p + 1 disjoint STS(6t + 3), two of them being KTS(6t + 3), then there exists a well balanced family for b 2p ≤ b ≤ b 2p + 6t + 3.

Proposition 15

 15 Let k = 3, v = 6t + 4 ≥ 22, 0 ≤ p ≤ 3t -3 and b 2p = 2p(3t + 2)(2t + 1). If there exist 2p + 1 disjoint STS(6t + 3) two of them being KTS(6t + 3), then there exists a well balanced family for b 2p ≤ b ≤ b 2p + 12t + 7.

Example 3 (

 3 end) In the case v = 10, Construction C allows to cover values of b ∈ {17, 18, 19, 20}, and so by Proposition 5, b ∈ {100, 101, 102, 103}.

6 .

 6 For example, for v = 11 we get a well balanced family for b = 15, 16, 17 and b = 20, 21, 22. Proposition 19 Let k = 3 and v = 6t + 5. Then there exists a well balanced family for b

  Consider for example k = 4 and v = 9. By Proposition 21, with λ = 1 there does no exist a 2-balanced family for b = 5, 6 and with λ = 2 for b = 12, 13; and more generally for b ≡ 5, 6, 12, 13 (mod 18). By Proposition 22, with λ 3 = 1 there does no exist a 3-balanced family for b = 19, 20, 21, 22, 23 and with λ 3 = 3 for b = 61, 62, 63, 64, 65 and more generally for b ≡ 19, 20, 21, 22, 23 (mod 42).

on b blocks and let G ′ be the family on b ′ blocks obtained by adding h complete families to

  G. Let µ x1,...,xj (resp. µ ′ x1,...,xj ) denote the number of blocks of the family G (resp. G ′ ) containing {x 1 , . . . , x j }. Then we have: µ ′ x1,...,xj = µ x1,...,xj + h v-j k-j . So, by Equation 1, x1,...,xj λ x1,...,xj = x1,...,xj µ x1,...,xj and x1,...,xj λ ′

	Now, deleting h copies of each block we get a family F with b = b ′ -h v k blocks (none of them being repeated). Note that if λ x1,...,xj (resp. λ ′ x1,...,xj ) denotes the number of blocks
	of the family F (resp. F ′ ) containing {x 1 , . . . , x j } we have: λ ′ x1,...,xj = λ x1,...,xj + h v-j k-j .
	Consider another family G x1,...,xj = x1,...,xj µ ′ x1,...,xj ,
	then	x1,...,xj λ 2 x1,...,xj -x1,...,xj µ 2 x1,...,xj =	x1,...,xj λ ′2 x1,...,xj -x1,...,xj µ ′2 x1,...,xj and thus

Table 1 :

 1 . Those are actually disjoint Kirkman triple systems (see the definition below).

	v	b	Result
	6t	ht(6t -2)	Proposition 18
	6t + 1	ht(6t + 1)	Proposition 8
	6t + 2	ht(6t + 2)	Proposition 18
	6t + 3, *	any	Proposition 9
	6t + 4, * *	b 2p -(6t + 3) ≤ b ≤ b 2p + 6t + 3	Propositions 11 and 14
	6t + 4 ≥ 16, **, 2 ≤ p ≤ 3t -1, b 2p -(12t + 7) ≤ b ≤ b 2p + 12t + 7 Propositions 12 and 13 6t + 5 6t 2 + 9t -h + 3, h ≤ 2t + 1 Proposition 19
	6t + 5	6t 2 + 9t + h ′ + 4, h ′ ≤ 2t + 2	Proposition 19
	5	b ≡ 3, 4, 6, 7 (mod 10)	Proposition 20
	6	b ≡ 5 (mod 10)	Proposition 20
	7	any	Proposition 20
	8	b ≡ 9, 10, 18, 19, 27, 28,
		29, 37, 38, 46, 47 (mod 56)	Proposition 20
	9	any	Proposition 9
	10	b ≡ 14, 15, 16 (mod 30)	Proposition 16
	11	b ≡ 18, 19, 36, 37 (mod 55)	Proposition 20
	15	any	Proposition 9
	16	b ≡ 38, 39, 40, 41, 42 (mod 80)	Proposition 17

Well balanced families constructed for k = 3; t ≥ 1; b 2p := 2p(3t + 2)(2t + 1), p ≥ 1. Condition * (resp. **) = There exist 3t + 1 disjoint STS(v) one (resp. two) of them being a KTS(v). For v ≤ 11 and v = 16, the conditions are all also necessary by Propositions 6 and 7. Example 1 Two disjoint Kirkman Triple Systems for

  . Example 2 (b) shows K B = K A + 1.

	Example 2 Two disjoint Kirkman Triple Systems for v = 15:
	{0, 1, 9}	{0, 2, 7}	{0, 3, 11}	{0, 4, 6}	{0, 5, 8}	{0, 10, 12}	{1, 4, 5}
	{2, 4, 12}	{3, 4, 8}	{1, 7, 12} {1, 8, 11}	{1, 2, 3}	{3, 5, 9}	{2, 6, 11}
	{5, 10, 11} {5, 6, 12}	{6, 8, 10} {2, 9, 10}	{6, 7, 9}	{4, 7, 11}	{3, 7, 10}
	{7, 8, ∞} {9, 11, ∞} {2, 5, ∞} {3, 12, ∞} {4, 10, ∞}	{1, 6, ∞}	{8, 9, 12}
	{3, 6,

RR n°7725

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

b = 30p -13 for p ≥ 2. Using Proposition 5 and the fact that 10 3 = 120, we will also get the values 30p ≤ b ≤ 30p + 12 and for p ′ ≤ 2, b ′ = 30p ′ + 13.

We will use the two disjoint KTS(9) K A and K B given at the beginning of this subsection. We start with the solution obtained for b = 30p in the proof of Proposition 10, where the first class of K A is one of the modified classes in Construction A. We can apply Deletion A-B, by deleting {x 1 , y 1 , α} = {7, 8, α} and some blocks of the first class of K B (which contains the pair {7, 8}) such as {2, 3, 5} and {0, 4, 6}, but not {x 1 , y 1 , z 1 } = {1, 7, 8}. Therefore, we get a solution for 30p -3 ≤ b ≤ 30p. Note that for b = 30p -3, we have λ x = 9p -1, except for z 1 = 1 (λ 1 = 9p). We can repeat the Deletion A-B by deleting {x 2 , y 2 , α} = {1, 4, α} and some blocks of the third class of K B except {x 2 , y 2 , z 2 } = {1, 4, 5}. Then we repeat Deletin A-B a third time by deleting {x 3 , y 3 , α} = {5, 6, α} and some blocks of the 4th class of K B except {x 3 , y 3 , z 3 } = {5, 6, 8}. So we get a well balanced family for 30p -9 ≤ b ≤ 30p; but, if p = 1 we cannot go further. However, if p ≥ 2, having done 3 times the Deletion A-B, we can delete the block {z 1 , z 2 , z 3 } = {1, 5, 8} which appears in K C = K A -1 as translated from the block {2, 6, 8} (recall that 8 is invariant). This K C has to be chosen as one of the 2p STS(6t + 3) in the proof of Proposition 10 and therefore, we get a solution, when p ≥ 2 for b = 30p -10, where λ x = 9p -3 and λ x,y = 2p or 2p -1. Deleting the blocks of the 2nd class, we finally get a well balanced family for 30p -13 ≤ b ≤ 30p for p ≥ 2.

However, we could have done the deletion in a different way; indeed we can delete the 3 blocks appearing in the first modified class in Construction A: {0, 8, α}, {1, 4, α}, {3, 5, α}. To avoid deleting twice some pairs we should keep the blocks of K B : {0, 3, 8} and {1, 4, 5}, both of which appear in the third class of K B and {2, 3, 5} appearing in the first class. Now, if we delete the block {2, 6, 7} in the third class and all the blocks of the 2nd and 4th class we get a solution for b = 30p -10 and deleting the two blocks of the first class different from {2, 3, 5} we get finally a solution for 30p -12 ≤ b ≤ 30p for any p. Using Proposition 5 and the fact that 10 3 = 120, we get also the values 30p ′ ≤ b ≤ 30p ′ + 12 and for p ′ ≤ 2, b = 30p ′ + 13.

In summary, we get, for v = 10, all the values of b, except b ≡ 14, 15, 16 (mod 30), which we already know, by Proposition 6, no well balanced family can exist and b = 17 (and 103), for which we will prove the existence of a well balanced family later (Construction C).

In general we can do Deletion A-B h times, h ≤ 3t + 1 (number of classes of K B ), if the two following conditions hold: (i) all the pairs {x, y} of the deleted blocks {x, y, α} are disjoint (in order to avoid to delete twice a pair {x, α}) and (ii) for any two deleted blocks {x, y, α} and {x ′ , y ′ , α} in K A the two corresponding blocks, that we keep in K B {x, y, z} and {x ′ , y ′ , z ′ } should satisfy z = z ′ .

We can fulfill these conditions for h ≤ 3. Indeed, let the original blocks in the class we have modified in K A be {x 1 , y 1 , u 1 }, {x 2 , y 2 , u 2 } and {x 3 , y 3 , u 3 }. For each i = 1, 2, 3, we can delete one of the 3 modified blocks {x i , y i , α} or {x i , u i , α} or {y i , u i , α}. Let in K B the blocks containing the pair {x i , y i } (resp. {x i , u i } or {y i , u i }) be {x i , y i , a i } (resp. {x i , u i , b i } or {y i , u i , c i }). Note that as each pair appears exactly once in K B , for a given i: a i , b i , c i are distinct. We can choose for z 1 for example a 1 ; for z 2 one among a 2 , b 2 , c 2 distinct from z 1 (there are at least two choices) and for z 3 one among a 3 , b 3 , c 3 distinct from z 1 and z 2 (there is at least one choice). Doing so we get a well balanced family for b 2p - At this point we have to be careful as λ z1 , λ z2 , λ α are one less than the other λ x and we cannot add a block {z 1 , z 2 , α} as the pair {z 1 , α} will appear twice more than the other pairs. Therefore we have to use a different idea. But first let us give the example of v = 10. We again use the two disjoint KTS(9) K A and K B given at the beginning of this subsection. We do Construction B with the first class C 1 of K B , modifying the block {x 1 , y 1 , z 1 } = {0, 4, 6} of the first class to {0, 6, α} and adding this modified block and {1, 7, 8} and {2, 3, 5}. Note that the pair {x 1 , y 1 } = {0, 6} appears in the block {0, 1, 6} of the 4th class of K A (class C A ). Therefore we will not modify this class in Construction A. We have z 1 = 4, which appears in the block {4, 5, 8} of the 4th class of K A . So, we choose x 2 = 8. We choose C 2 as the second class of K B , replace {2, 4, 8} by {4, 8, α} and add the two other blocks {1, 3, 6} and {0, 5, 7}; here z 2 = 2. Then, adding the blocks of a class of K B different from C 1 and C 2 , we get a well balanced family for b 2p = 30p ≤ b ≤ 30p + 9 = b 2p + 9 where p = 0, 1, 2, 3.

We can instead apply Construction B directly to the classes C 1 and C 2 of K B and then to a third class C 3 of K B by replacing the block {2, 6, 7} with {2, 7, α} (here z 3 = y 1 = 6) and keeping the two blocks {1, 4, 5} and {0, 3, 8}. Note that we are lucky, as the pair {2, 7} is in the triple {2, 3, 7} which belongs also to the unmodified 4th class C A of K A . At that point we have: b = 30p + 9, for p = 0, 1, 2, 3, and λ z1 , λ z2 , λ z3 are one less than the other λ x . We can now add the block {z 1 , z 2 , z 3 } = {2, 4, 6}, which appears in the STS K C = K A + 4, different from K A (it is obtained by adding 4 to {0, 2, 5}). That works if p < 3, as we can choose the 2p STS(6t + 3) used in the proof of Proposition 10 to be K A and 2p -1 blocks different from K C . We can then add the blocks of the 4th class of K B . In K A we can modify by Construction A any class except the 4th one and so we can apply the construction for p = 0, 1, 2.

In summary, we get all the values except b ≡ 14, 15, 16 (mod 30), which we know by Proposition 6 no well balanced family can exist and b = 17, 18, 19, 20 (and b = 100, 101, 102, 103), for which we will prove the existence of a well balanced family later (Construction C). Note that the deletion process provides also solutions for b = 18, 19, 20 (and b = 100, 101, 102).

We can use this construction for v = 6t + 4 and for p < 3t. We apply Construction B to the two blocks {x 1 , y 1 , z 1 } and {z 1 , x 2 , z 2 } in K B , where the pairs {x 1 , y 1 } and {z 1 , x 2 } are in the same class C A of K A which will be not modified in Construction A. Then we choose as third block to be modified a block {z 2 , x 3 , z 3 }, with z 3 = x 1 or y 1 and such that the block

. That is always possible as p < 3t; indeed it suffices to choose as the 2p STS(6t + 3) used in the proof of Proposition 10 both K A and 2p -1 STS(6t + 3) different from K C and, for the modified classes of K A , classes different from C A and perhaps the class C ′ A containing {z 2 , x 3 }. Then using Construction B with the classes C 1 , C 2 , C 3 containing respectively {x 1 , y 1 }, {z 1 , x 2 }, and {z 2 , x 3 } and adding the block {z 1 , z 2 , z 3 } of K C we get a solution for b = b 2p +6t+4. Indeed all the λ x have been increased by exactly 3 and some λ x,y by 1. We can then continue the process easily by adding the blocks of a 4th class of K B , obtaining a well balanced family for b 2p ≤ b ≤ b 2p + 8t + 5.

RR n°7725

Small values of v

We can apply the preceding techniques and other tools to deal with the small values of v verifying for v ≤ 11 in Conjecture 2. We give the proofs and technical details in Appendix 2.

Proposition 20 Let k = 3, for v ≤ 11, there exists a well balanced family for the values of v and b different from that excluded by Propositions 6 and 7. In particular for v = 7, 9 there exists a well balanced family for any b.

Case k > 3

We can generalize Proposition 6 in different ways. The first one concerns the non existence of 2-balanced families.

then there does not exist a 2-balanced family.

Proof Note that the number of possible pairs is v(v-1) 2 and that a block contains k(k-1) 2 pairs. We distinguish 3 cases.

• k(k -1)b = λv(v -1). In that case a 2-balanced family will verify λ x,y = λ for all pairs {x, y} and then we should have

In that case, we cannot have all the λ x,y ≥ λ. So we have one of the λ x,y ≤ λ -1 and if the family is 2-balanced all the λ x,y ≤ λ. But, then

k-1 -rv k-1 . Therefore there does not exist a 2-balanced family if λv(v -1) -rv < k(k -1)b < λv(v -1).

• The case λv(v -1) < k(k -1)b < λv(v -1) + (k -1 -r)v can be handled exactly as the preceding one.

We can also generalize Proposition 6 to ensure non existence of p-balanced families p > 2. We give the result for p = 3.

, then there does not exist a 3-balanced family.

Proof Note that the number of possible triples is v(v-1)(v-2) 6 and that a block contains k(k-1)(k-2) 6 triples. We distinguish 3 cases.

In that case a 3-balanced family will verify λ x,y,z = λ 3 for all triples {x, y, z} and then we should have

In that case we cannot have all the λ x,y,z ≥ λ 3 .

So we have one of the λ x,y,z ≤ λ 3 -1 and if the family is 3-balanced all the λ x,y,z ≤ λ 3 . But, then λ x,y ≤ λ 3 v-2 k-2 and according to the definition of r, λ x,y ≤ λ 3

rv(v-1) 2(k-2) . Therefore there does not exist a 3-balanced family if

RR n°7725

Appendix 1: case v = 16 (proof of Proposition 17) For v = 16 we will use the two disjoint KTS(15) of Example 2 (a) and Example 2 (b), denoted respectively K A and K B . To ease the reading, we substitute ∞ with 13 and ∞ ′ with 14. We start with the solution obtained for b = 80p in the proof of Proposition 10, where the first class of K A is one of the p modified classes in Construction A. We apply Deletion A-B. In the first modified class of K A , we can delete {0, 9, α}, {4, 12, α}, {7, 13, α}. We keep in K B , the blocks {0, 9, 10} (z 1 = 10), {4, 12, 1} (z 2 = 1), and {2, 7, 13} (z 3 = 2) and delete the other blocks of the 7th, 3rd and 6th classes of K B . Then we can delete the block {z 1 , z 2 , z 3 } = {1, 2, 10} which appears in the first class of K B , getting a solution for b, such that 80p -16 ≤ b ≤ 80p. We can continue the process with the deletion still in the first modified class of K A of {5, 11, α} and {6, 14, α}, keeping in K B the blocks {5, 11, 13} (z 4 = 13) and {6, 8, 14} (z 5 = 8), and deleting the other blocks of the 5th and 4th class of K B .

At that point, we can either delete all the blocks of the second class of K B and so we get the values 80p -31 ≤ b ≤ 80p. Or we can delete the blocks in another modified class of K A , but we need p ≥ 2. If p ≥ 2, we can delete the block {4, 5, α} appearing in the 7th modified class of K A and delete the blocks of the second class of K B except {4, 5, 9} (z 6 = 9). Then we can delete the block {z 4 , z 5 , z 6 } = {8, 9, 13} of the first class of K B , getting a solution for 80p -32. Finally, we can also delete the 3 remaining blocks of the first class of K B getting a solution for 80p -35 ≤ b ≤ 80p (p ≥ 2).

Using Proposition 5 and the fact that Construction B. We suppose here that the 7th class of K A is not modified in construction A. Now we apply Construction B, by replacing the block {8, 9, 13} of the first class of K B by {8, 9, α} (x 1 = 8, y 1 = 9, and z 1 = 13), then the block {0, 4, 13} of the 4th class of K B by {0, 13, α} (x 2 = 0, z 2 = 4) and the block {4, 5, 9} of the second class of K B by {4, 5, α}, (x 3 = 5, z 3 = 9), and adding the other blocks of the first, second and 4th class. Note that the pairs {8, 9}, {0, 13}, {4, 5} are in the same class of K A , namely the 7th class. So we get a well balanced family for 80p ≤ b ≤ 80p + 15 for p ≤ 6.

For p ≤ 5, we add the block {z 1 , z 2 , z 3 } = {4, 9, 13} which appears in the KTS K A + 3 as translated from the block {1, 6, 13} (recall that 13 is invariant) and also the blocks of another class. Doing so we get all the 80p ≤ b ≤ 80p + 21 (p ≤ 5).

Appendix 2: Small cases (proof of Proposition 20)

The case v = 9 was settled in Proposition 9 and v = 10 in Proposition 16. We have well balanced families for b = 1 (one block) and b = 2 (two blocks {1, 2, 3} and {1, 4, 5}), but not for b = 3 as we have seen in the example of the introduction (see also Proposition 7). However there exists an optimal solution {1, 2, 3}, {1, 2, 4}, {3, 4, 5} 1-balanced but not 2-balanced (λ 1,2 = 2 but λ 1,5 = λ 2,5 = 0). By Proposition 7, there is no well balanced solution for b = 4; an optimal one consists of the blocks {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {3, 4, 5}. For b = 5 there exists a well balanced solution with λ x = 3 and λ x,y = 1 or 2 and consisting of the 5 blocks {1, 2, 3}, {1, 2, 4}, {1, 3, 5}, {3, 4, 5}, {2, 4, 5}. v = 6. For v = 6, 6 3 = 20 and by Proposition 5 we need to consider only the values of b ≤ 10.

RR n°7725

For b = 5 (and so b = 15), there does not exist a well balanced family (Proposition 6). An optimal solution F * consists of the 5 blocks: {1, 2, 3}, {1, 2, 4}, {1, 5, 6}, {2, 5, 6}, {3, 4, 5} (λ x = 2 or 3 and λ 1,2 = λ 5,6 = 2 but λ 3,6 = λ 4,6 = 0) with P (F * , x) = 4x 2 + 16x as associated polynomial. The proof is obtained by inspection of the different possible cases. Proposition 4 in [START_REF] Jean-Marie | Combinatorial designs and availability[END_REF] also allows us to conclude directly for this case.

For the other values of b, we can construct well balanced families as follows. Let B 1 = {1, 2, 3}, 7 3 = 35; by Proposition 3 and Proposition 5 we have to consider only the values of b ≤ 17. Kirkman proved that there exist two disjoint STS [START_REF] Colbourn | Steiner systems[END_REF]. The first one consists of the 7 blocks C i = {i, i + 1, i + 3}, for 0 ≤ i ≤ 6 and the second one of the 7 blocks D i = {i, i + 2, i + 3}, for 0 ≤ i ≤ 6 (indices modulo 7). Let B 1 = {1, 2, 3}, B 2 = {4, 5, 6}, B 3 = {0, 1, 4}, B 4 = {0, 2, 5}, B 5 = {0, 3, 6}. Note that these 5 blocks are disjoint from the blocks C i and D i . For b = j, 1 ≤ j ≤ 5, take the blocks B i , 1 ≤ i ≤ j. For b = 7 take the first STS [START_REF] Colbourn | Steiner systems[END_REF] (that is all the C i ). For b = 6 delete one block from the STS [START_REF] Colbourn | Steiner systems[END_REF]. For b = 7 + j, 1 ≤ j ≤ 5 add to the STS [START_REF] Colbourn | Steiner systems[END_REF] the blocks B i , 1 ≤ i ≤ j. For b = 14 take the two disjoint STS [START_REF] Colbourn | Steiner systems[END_REF] (that is all the C i and D i ). For b = 13 delete one block from one STS [START_REF] Colbourn | Steiner systems[END_REF]. For b = 14 + j, 1 ≤ j ≤ 5 add to the two disjoint STS [START_REF] Colbourn | Steiner systems[END_REF] the blocks B i , 1 ≤ i ≤ j. Cases 21 ≤ b ≤ 26. We will use again Construction C, starting with the two disjoint STS(7) with blocks C i = {i, i+1, i+3}, for 0 ≤ i ≤ 6 and the second one with blocks D i = {i, i+2, i+3}, for 0 ≤ i ≤ 6 (indices modulo 7). Add the 7 blocks F i = {i, i + 1, α}, 0 ≤ i ≤ 6. We get a solution for b = 21. Note that λ x = 8 except λ α = 7 and λ x,y = 2 except for the pairs {i, i + 1} for which it is 3. Then add the blocks {0, 4, α}, {2, 6, α}, {1, 3, 5} (at that point for b = 24, λ x = 9) and {0, 2, 5}, {1, 4, 6}. Let us now introduce a device which is useful to quickly identify pairs in proposed solutions. To a given block {a, b, c} we associate its "difference family", the (unordered) list made of the three "smallest" differences between values of a block (a pair {a, b} has two possible differences a -b and b -a modulo 11). Note that all the blocks of the class obtained by translating a given block, that is the blocks {a + i, b + i, c + i} (values are taken modulo 11), have the same difference family. The converse is not true; for example blocks with difference family 123 can be in the class {i, i + 1, i + 3} or {i, i + 2, i + 3}.

The solution above is then generated by the 5 difference families: 112, 224, 335, 443, 551. Note that each difference occurs three times. This solution is now used to obtain solutions for the following values of b. Cases 77 ≤ b ≤ 82. For b = 77, take the following 7 classes: (i, i + 1, i + 2), (i, i + 2, i + 4), (i, i + 3, i + 6), (i, i + 4, i + 8), (i, i + 5, i + 10), (i, i + 1, i + 3), (i, i + 1, i + 5). The corresponding difference families are 112, 224, 335, 443, 551, 123, 145. Hence λ x = 21, λ xy = 5 for pairs with difference 1, and 4 for all the pairs with other differences. Now adding some or all the blocks: {0, 2, 5}, {1, 3, 7}, {4, 6, 9}, {2, 8, 10}, {3, 5, 8} gives solution for 78 ≤ b ≤ 82.


Gobrecht

A Gorretta

Potential of proximal hyperspectral imaging to estimate the spatial and temporal variability of soil microbial respiration

[Introduction]

The spatial heterogeneity of soil properties, especially the distribution of organic matter and biological activities, has often been emphasized to understand soil behavior, for example its resistance to stress. It is difficult to understand, quantify and follow the evolution of soil respiration over space and time. Although NIR spectroscopy is not relevant to directly measure carbon dioxide (CO 2 ) emissions, soil respiration involves organic matter degradation thus biochemical changes, which could be estimated with Near Infrared Spectroscopy (NIRS).

The objective of this study was to evaluate the potential of proximal hyperspectral imaging in the Visible-Near Infrared (VIS-NIR) to (i) calibrate a model to predict soil respiration under controlled conditions, and (ii) to determine both spatial and temporal variations in soil respiration at a 0.2-mm scale.

[Materials and methods]

-Calibration database:

The soil studied was a calcic Fersialsol, clayey, from southern France. Two batches (A and B) of 28 soil samples (10g) mixed with variable amounts of straw (0% to 100%) were incubated under controlled temperature and moisture conditions during 28 days. Two soil water potential (-0.01 MPa and -0.1 MPa) were tested. Soil samples were stressed at 60°C (stressed samples) or at 28°C (control samples) for 24h before beginning the incubation assays. Soil respiration (in mgC-CO 2 g -1 soil) was determined at different dates (D0, D1, D3, D7, D14, D21 and D28) using sodium hydroxide traps. At each date, hyperspectral images of these samples were acquired with a HySpex VNIR-1600 camera from Norsk Elektro Optikk (spectral range 415-993 nm) at a distance of 1 m. The mean spectrum of each sample was extracted from the images in order to build a calibration database associating a spectrum (Sp t ) to accumulated respiration (DSR 0-t ) over the period considered (Figure 1).

-Calibration model: Four different models using the Partial Least Square algorithm were built based on the calibration database (n=336). In the first approach, mean sample spectra (Sp t ) at a given date (t) were fitted to accumulated respiration of the sample since D0 (DSR 0-t ). In the second approach, we fit the difference (Sp 0-t ) between the spectra SP 0 measured at D0 and the spectra Sp t measured at Dt with the same accumulated respiration value DSR 0-t . For both strategies, either the whole wavelength range (415 -993 nm) or only the NIR range (700 -993 nm) was used.

-Predicted soil respiration maps:

The first two models were applied to each pixel (0.04 mm²) of the hyperspectral images acquired at the same dates on four soil mesocosms (400 cm²) incubated in similar conditions than the standard sample. The four mesocosms differed by the amount of straw that had been added to soil (0% and 0,04%) and by the application or not of a thermal stress before incubation (24 h at 60°C).

The predicted soil respiration maps of the mesocosms were then visually compared in order to identify possible spatial patterns or hotspots, and their evolution with time.

[Results and discussion]

-Quality of the calibration models : It was possible to use the spectral information from hyperspectral images to predict the amount of CO 2 released by the soil during incubation (Table 1). The quality of the model decreased when the sole NIR part of the spectrum was used (Models 2 and 4), but it was a way to avoid building a prediction model based on the color.

The best calibration strategy (Model 3 > Model1) was to use the difference spectrum (Sp 0-t ) between two dates to predict respiration. The difference spectrum could sign the loss or the transformation of some soil organic matter by microbial activity.

In order to validate the relevance of the soil respiration maps obtained, Model 1 was applied on an image of the standard sample (Batch A) at D28. A value of predicted soil respiration per sample could be extracted from this map by averaging all the pixels of the same sample. The comparison between the measured respiration and the average predicted value from the soil respiration map lead to a correlation coefficient of R² = 0.879 (Figure 2 ).

-Spatial and temporal variability of soil respiration:

Only Model 1 and 2 could be applied on mesocosm hyperspectral images because it was hardly possible to exactly fit images at two consecutive dates to calculate the difference spectra (Sp 0-t ) at each exact pixel.

Although the predicted soil respiration maps obtained by applying models using the whole spectral range (415 -993 nm) on mesocosm hyperspectral images appeared very noisy, some distinctive respiration patterns linked to coarse organic particles or fine roots could be recognized (Figure 3 Comparison of the soil respiration prediction maps (using Model 1) at D1 and D21 in a detailed area

16th International Conference on Near Infrared Spectroscopy, La Grande-Motte, 2-7 juin 2013

containing a root). Comparison between predicted soil respiration maps at different dates (D1 and D21) revealed that the respiration intensity of organic residues decreased with time.

[Conclusion]

This study shows that it is possible to use hyperspectral images to build a soil respiration model. It is also meaningful to apply a model on another image in order to obtain a soil respiration prediction maps.

The interpretation of the prediction map still faces some technical problems such as the fitting of two consecutive images of the same mesocosm.

[Novelty]

Proximal hyperspectral imaging of soils to perform soil respiration calibration;

Application of a prediction model on an hyperspectral image.

[Summary]

The objective of this study was to evaluate the potential of proximal hyperspectral imaging to (i) calibrate a model to predict soil respiration under controlled conditions, and (ii) to determine both spatial and temporal variations in soil respiration at a hundreds of micrometer scale. Calibration models based on spectra and respiration measured on standards were built then applied on hyperspectral images acquired on soil mesocosms (400 cm²), in order to predict their respiration pixel by pixel (0.2 mm²). The quality of the models was acceptable but their application to produce prediction maps faced some technical problems due to hyperspectral technology.

[Keywords]

Soil respiration, proximal hyperspectral imaging, PLS, spatial variability