Otfried Cheong
email: otfried@kaist.edu

Xavier Goaoc
email: goaoc@loria.fr

Cyril Nicaud
email: nicaud@univ-mlv.fr

Set Systems and Families of Permutations with Small Traces *

Let F be a family of permutations on [n] = {1, . . . , n} and let Y = {y1, . . . , ym} ⊆ [n], with y1 < y2 < . . . < ym. The restriction of a permutation σ on [n] to Y is the permutation

Marcus and Tardos proved the well-known conjecture of Stanley and Wilf that for any permutation τ on [m] there is a constant c such that if no permutation in F admits τ as a restriction then F has size O(c n ). In the same vein, Raz proved that there is a constant C such that if the restriction of F to any triple has size at most 5 (regardless of what these restrictions are) then F has size at most C n . In this paper, we consider the following natural extension of Raz's question: assuming that the restriction of F to any m-element subset in [n] has size at most k, how large can F be?

We first investigate a similar question for set systems. A set system on X is a collection of subsets of X and the trace of a set system R on a subset Y ⊆ X is the collection

For finite X, we show that if for any subset Y ⊂ X of size b the size of R |Y is smaller than 2 i (b -i + 1) for some integer i then R consists of O(|X| i ) sets. This generalizes Sauer's Lemma on the size of set systems with bounded VC-dimension. We show that in certain situations, bounding the size of R knowing the size of its restriction on all subsets of small size is equivalent to Dirac-type problems in extremal graph theory. In particular, this yields bounds with non-integer exponents on the size of set systems satisfying certain trace conditions.

We then map a family F of permutations on [n] to a set system R on the pairs of [n] by associating each permutation to its set of inversions. Conditions on the number of restrictions of F thus become conditions on the size of traces of R. Our generalization of Sauer's Lemma and bounds on certain Dirac-type problems then yield a delineation, in the (m, k)-domain, of the main growth rates of F as a function of n.

Introduction

In this paper, we study two problems of the following flavor: how large can a family of combinatorial objects defined on a finite set be if its number of distinct "projections" on any small subset is bounded? We consider set systems, where the "projection" is the standard notion of trace, and families of permutations, where the "projection" corresponds to the notion of containment used in the study of permutations with excluded patterns. One of our motivations for considering these questions is the "geometric permutation problem" in geometric transversal theory, a question that has been open for two decades, and which we explain in the conclusion. Set systems. A set system, also called a range space or a hypergraph, is a pair (X, R) where X is a set, the ground set, and R is a set of subsets of X, the ranges. Given Y ⊆ X, the trace of R on Y , denoted R |Y , is the set {e ∩ Y | e ∈ R}. Given an integer b, let X b denote the set of b-element subsets of X, and define:

f R (b) = max Y ∈( X b ) |R |Y |.
The function f R is called the shatter function of (X, R), and counts the size of the largest trace on a subset of X of size b. Let Sh(n, b, k) denote the maximum number of ranges in a set system (X, R) on |X| = n elements with f R (b) k. The first problem we consider is the following:

Question 1. Given b and k, how large is Sh(n, b, k)?

For k = 2 b -1, the answer is given by Sauer's Lemma [START_REF] Sauer | On the density of families of sets[END_REF] (also proven independently by Perles and Shelah [START_REF] Shelah | A combinatorial problem; stability and order for models and theories in infinitary languages[END_REF] and Vapnik and Chervonenkis [START_REF] Vapnik | On the uniform convergence of relative frequencies of events to their probabilities[END_REF]), which states that Sh n, b,

2 b -1 = b-1 i=0 n i = O(n b-1 ). (1)
The largest b such that f R (b) = 2 b is known as the VC-dimension of ([n], R). The theory of set systems of bounded VC-dimension, and in particular Sauer's Lemma, has many applications, in particular in geometry and approximation algorithms; classical examples include the ε-net Theorem [START_REF] Chazelle | The discrepancy method: randomness and complexity[END_REF] or improved approximation algorithms for geometric set cover [START_REF] Brönnimann | Almost optimal set covers in finite VC-dimension[END_REF].

For the case of graphs, that is, set systems where all ranges have size 2, Question 1 is a classical problem known as a Dirac-type problem: determining the maximum number Ex(n, m, µ) of edges in a graph on n vertices whose induced subgraph on any m vertices has at most µ edges. These problems were extensively studied in extremal graph theory since the 1960's, and we refer to the survey of Griggs, Simonovits and Thomas [START_REF] Griggs | Extremal graphs with bounded densities of small subgraphs[END_REF] for an overview. For the case of general set systems, Chapter 11 of Jukna's book [START_REF] Jukna | Extremal Combinatorics[END_REF] gives an overview. In particular, Frankl [START_REF] Frankl | On the trace of finite sets[END_REF] proved that Sh(n, 3, 6) = t 2 (n) + n + 1 and Sh(n, 4, 10

) = t 3 (n) + n + 1,
where t i (n) denotes the number of edges of the Turán1 graph T i (n). Bollobás and Radcliffe [START_REF] Bollobás | Defect Sauer results[END_REF] showed that if and only if σ(y i ) < σ(y j ). This allows to define the shatter function of a set F of permutations:

φ F (m) = max Y ∈( [n] m ) |F |Y |,
where [START_REF] Raz | VC-dimension of sets of permutations[END_REF] proposed to extend the notion of VC-dimension to sets of permutations by defining the VC-dimension of F as the largest m such that φ F (m) = m!, and the analogue of Question 1 arises naturally for sets of permutations:

F |Y = {σ |Y | σ ∈ F } denotes the set of restrictions of permutations of F to Y . Raz
Question 2. Given m and k, how large can a set F of permutations on [n] be if φ F (m) k?

Raz [START_REF] Raz | VC-dimension of sets of permutations[END_REF] showed that any family of permutations on [n] such that φ F (3) < 6 has size at most exponential in n, and asked whether the same holds whenever k < m!. Cibulka and Kynčl [START_REF] Cibulka | Tight bounds on the maximum size of a set of permutations with bounded VC-dimension[END_REF] answered this question negatively by showing that the maximum size of a family F of permutations on [n] with φ F (4)

< 4! is 2 Θ(n log α(n))
, where α denotes the inverse of the Ackermann function; they also give upper and lower bounds on the maximum size of a family of permutations with VC-dimension m for all m, which are tight for every even m.

Question 2 is related to classical problems on families of permutations with an excluded pattern. We say that a permutation σ on [n] contains a permutation τ on [m] if there is an m-element subset Y ⊆ [n] such that σ |Y = τ . If no permutation in a family F of permutations on [n] contains τ , then F avoids τ and τ is an excluded pattern for F . The study of families of permutations with excluded patterns goes back to a work of Knuth [START_REF] Knuth | Art of Computer Programming[END_REF], motivated by sorting permutations using stacks, and received considerable attention over the last decades. In particular, Stanley and Wilf asked whether for any fixed permutation τ the number of permutations on [n] that avoid τ is at most exponential in n, a question answered in the positive by Marcus and Tardos [START_REF] Marcus | Excluded permutation matrices and the Stanley-Wilf conjecture[END_REF]. If a family of permutations avoids a permutation τ on [m], then its restriction to any m-element subset Y ⊆ [n] has size less than m!, and so its VC-dimension is at most m -1. In this sense Raz's question generalizes that of Stanley and Wilf.

Our results. We present three results. First, we generalize Sauer's Lemma, and show that if 0 i < b n then Sh(n, b,

2 i (b -i + 1) -1) (b -i) 0 j i n j = O(n i ) (Theorem 1)
. Then, we prove that the condition f R (b) = k is, when asymptotic orders of magnitude are considered, equivalent to a Dirac-type problem on graphs for b < k < 4(b -1) (Lemma 2); this implies that Sh(n, b, k) = Θ(n α ) with non-integer α for certain values of k, a behavior not captured by Theorem 1. Finally, we give a reduction of the permutation problem to the set system problem (Lemma 4) from which we deduce the main transitions between the constant, polynomial and at least exponential behaviors for Question 2; we also give a simple condition for propagating exponential upper bounds (Lemma 6).

Sauer's Lemma for set systems with small traces

Our first result is the following generalization of Sauer's Lemma (which is the special case i = b -1): Theorem 1. Let (X, R) be a set system. For any 0

i < b n, if f R (b) < 2 i (b -i + 1) then f R (n) (b -i) 0 j i n j . Proof. Define υ i (b) = 2 i (b -i + 1
) and consider the property:

P (b, i, n) : f R (b) < υ i (b) ⇒ f R (n) (b -i) 0 j i n j .
We prove by induction that P (b, i, n) holds for all choices of integers 0 i < b n.

Initialization. Observe that for any 0 i < b, we have (bi)

0 j i b j (b -i) 0 j i i + 1 j = (b -i)(2 i+1 -1) 2 i (b -i) + 2 i -1 = υ i (b) -1, so P (b, i, b
) holds for any i < b. Next, we show that P (b, 0, n) holds for all b, n 1. We first argue, by induction, that for b 1, for any b + 1 pairwise distinct subsets S 1 , . . . , S b+1 of X there exists Y ⊂ X of size at most b such that the restrictions S j ∩ Y are already pairwise distinct.2 This is obvious for b = 1. Assume it is true for b -1, so that there exists a subset Y 0 of size b -1 for which S 1 ∩ Y 0 , . . . , S b ∩ Y 0 are pairwise distinct; if S b+1 ∩Y 0 is distinct from all other restrictions then we are done, else S b+1 ∩Y 0 = S j ∩Y 0 for exactly one index j; then, for any element y ∈ (S j \ S b+1 ) ∪ (S b+1 \ S j ) the sets S 1 , . . . , S b+1 have pairwise distinct restrictions on Y 0 ∪ {y}, which is of size at most b. As a consequence we have that for all b, n,

f R (b) < b + 1 = υ 0 (b) ⇒ f R (n) b = (b -0) n 0 ,
and P (b, 0, n) holds for all b, n 1.

Induction. We can now adapt the induction of Sauer's original proof to show that if, given i < b n, property P (b , i , n ) holds for all triples (b , i , n ) lexicographically smaller than (b, i, n), then P (b, i, n) also holds. So let (X, R) be a set system such that f R (b) < υ i (b) and let Y be an n-element subset of X.

We pick an element a ∈ Y and let D denote the ranges in R |Y \{a} that are the trace of two distinct ranges from

R |Y . Since f R (b) < υ i (b), it is clear that f R |Y \{a} (b) < υ i (b). Moreover, if |D |Z | υ i-1 (b -1) H H H H H b |R| Θ(1) Θ(n) Θ(n 2 ) Θ(n 3 ) Θ(n 4 ) Θ(n 5 ) 2 1-2 3 3 1-3 4-5 6-
for some subset Z ∈ Y b-1 then |R |Z∪{y} | 2υ i-1 (b -1) = υ i (b) so f R (b) < υ i (b) also implies that f D (b -1) < υ i-1 (b -1). Since |R |Y | = |R |Y \{a} | + |D|,
the induction hypothesis ensures that

|R |Y \{a} | (b -i) 0 j i n -1 j and |D| (b -i) 0 j i-1 n -1 j ,
we have:

|R |Y | (b -i) + (b -i) 1 j i n -1 j + (b -i) 1 j i n -1 j -1 .
Then, from n-1 j + n-1 j-1 = n j we get that for any n-element subset Y of X,

|R |Y | (b -i) + (b -i) 1 j i n j = (b -i) 0 j i n j ,
and P (b, i, n) holds. This concludes the proof.

For an integer x, let P i (x) denote the set of all partitions of x into a sum of i non-negative integers and define:

λ i (b) = max {b1,...,bi}∈Pi(b) i j=1 (b j + 1).
Consider the following set system (X, R): split the finite ground set X into i roughly equal subsets X 1 , . . . , X i and let R denote the set of all i-element subsets containing exactly one element from each

X j . We have f R (b) λ i (b) and f R (n) = Θ(n i ). This implies that for any k such that λ i (b) k < 2 i (b -i + 1) we have Sh(n, b, k) = Θ(n i ),
and so the order of magnitude given by Theorem 1 is tight. Table 1 summarizes these cases for small values of b. In particular, Theorem 1 gives the correct order of magnitude of Sh(n, b, k) for all b 4, with the exception of Sh(n, 4, 8). We will see in the next section that Sh(n, 4, 8) = Θ(n √ n).

Remark. Theorem 1 asserts, in particular, that for any set system (X, R)

with f R (b) < 2 i (b -i + 1) we have f R (n) = O(n i ). The condition f R (b) < 2 i (b -i + 1)
does not, however, imply that R has VC-dimension at most i. A simple example is given by

X = [n] and R = {A | A ⊂ [i]} ∪ {{x} | x ∈ [n]}, which has VC-dimension i and for which f R (b) = 2 i + b -i is smaller than 2 i-1 (b -i) for b large enough.
3 Fractional exponents from Dirac-type bounds

Recall that Ex(n, m, µ) denotes the maximum number of edges in a graph on n vertices whose induced subgraph on any m vertices has at most µ edges.

Lemma 2. If 0 b < k n then Sh(n, b, k) n + 1 + Ex(n, b, k -b -1) and if k < 4(b -1) then Sh(n, b, k) n + 1 + f R (b) + k • Ex(n, b, k -b -1).
Proof. Let G = (V, E) be a graph on n vertices such that any b vertices span at most µ edges and such that |E| = Ex(n, b, µ). Observe that some b vertices of E must span exactly µ edges by maximality of Ex(n, b, µ).

Putting (X, R) = (V, {∅} ∪ V ∪ E) we obtain a hypergraph such that f R (b) = µ + b + 1, proving the lower bound: Sh(n, b, k) n + 1 + Ex(n, b, k -b -1).
The proof of the upper bound uses two claims: (i) the upper bound in the general case follows from the special case where R is closed under taking subsets, and (ii) if R is closed under taking subsets, the condition f R (b) < 4(b -1) implies that the number of subsets in R of size three or larger is at most f R (b) -1 times the number of subsets in R of size two. Claim (i) is a direct consequence of the classical lemma3 of Alon [START_REF] Alon | Density of sets of vectors[END_REF] and Frankl [START_REF] Frankl | On the trace of finite sets[END_REF] stating that for any set system (X, R) there exists a set system (X, R) such that R is closed under taking subsets, | R| = |R|, and f R(b) f R (b) for every b.

We now prove claim (ii). Assume that R is closed under taking subsets and let e ∈ R be a 2-element subset. Assume that there are d subsets in R that contain e, and let F denote the union of these subsets. We claim that |F | < b; assume, by contradiction, that |F | b and let G be a b-element subset of F containing e. Writing e = {p 1 , p 2 } we get that R contains the sets ∅, {p 1 }, {p 2 }, {p 1 , p 2 } as it is closed under taking subsets. Furthermore, every p ∈ G \ e is part of a subset that contains e, and therefore contains e ∪ {p}. It follows that R also contains the four ranges {p}, {p, p 1 }, {p, p 2 }, and {p,

p 1 , p 2 } for every p ∈ G \ e. Thus, if |F | b then |R |G | 4 + 4(b -2) > f R (b), a contradiction; it must then be that |F | < b and thus: d |R |F | f R (|F |) f R (b -1) f R (b) -1.
In other words, every pair e ∈ R is contained in at most f R (b) -1 elements of R, and claim (ii) follows. Now, let (X, R) be a set system such that |X| = n and f R (b) = k with k < 4(b -1). By claim (i) we can assume that R is closed under taking subsets. After discarding all elements of X that do not appear in a subset in R we have |X| n and still f R (b) = k. Let us recall a few bounds on Ex(n, m, µ) that we use here and in Section 4; once again, we refer to the survey of Griggs, Simonovits and Thomas [START_REF] Griggs | Extremal graphs with bounded densities of small subgraphs[END_REF] for a more detailed overview. (Recall that when H is a graph, Ex(n, H) denotes the maximum number of edges in a graph on n vertices that does not have H as a subgraph.)

• Ex(n, m, m -2) is O(n),
as a graph for which any m vertices span at most m -2 edges has only connected components of size at most m -1. [START_REF] Bondy | Cycles of even length in graphs[END_REF] and is superlinear if m 3 [START_REF] Lazebnik | A new series of dense graphs of large girth[END_REF].

• Ex(n, m, m -1) is O n 1+1/ m/2
• If m s + t and k < st then Ex(n, m, k) Ex(n, K s,t ) = O n 2-1/s by the Kővári-Sós-Turán Theorem [START_REF] Kővári | On a problem of Zarankiewicz[END_REF] (sharper bounds were obtained by Füredi [START_REF] Füredi | New asymptotics for bipartite Turán numbers[END_REF]). Also, note that Ex(n, 2rp -2p + 2, 2rp -p) < 6prn 1+1/r (a consequence of [9, Lemma 1]). When µ is close to m, this implies a stronger bound on Ex(n, m, µ) than the three results above, for instance for r = 3 and p = 2 we get Ex(n, 10, 10) = O(n 4/3 ). These implications hold for values of m that are somewhat large, so we do not elaborate on them. Let z s (n) denote the maximum number of edges in a K s,s -free bipartite graph on n vertices. It is known that z 2 (n) = Θ(n √ n) and that z 3 (n) = Θ(n 5/3 ) (see Blagojević, Bukh and Karasev [START_REF] Blagojević | Turán numbers for K s,t -free graphs: topological obstructions and algebraic constructions[END_REF] for a discussion of these and related results). For small values of n, z 2 (n) was studied by Goddard at al. [START_REF] Goddard | Bipartite Ramsey numbers and Zarankiewicz numbers[END_REF] and z 3 (n) was studied by Guy [START_REF] Guy | A many-facetted problem of Zarankiewicz[END_REF]. Proof. (i) Given a bipartite graph G = (V, E) that is K s,s -free for s 2, the set system (X, R) Remark. The cases s = 2 and s = 3 of Corollary 3 are particularly interesting as they lead to the following tight bounds for b 4:

= (V, {∅} ∪ V ∪ E) satisfies f R (b) b + 1 + z s (b). Since |R| = 1 + n + z s (n), claim (i) follows. (ii) k < 4(b -1) implies by Lemma 2 that Sh(n, b, k) = Θ(n + Ex(n, b, k -b -1)). Since k -b -1 < (s + 1)(b -s + 1) -b -1 = s(b -s) we have Ex(n, b, k -b -1) Ex(n, K s,b-s ) = O(n 2-1/s ). ( iii
Sh(n, b, k) = Θ(n √ n) for z 2 (b) + b + 1 k 3b -4, Sh(n, b, k) = Θ(n 5/3 ) for z 3 (b) + b + 1 k 4b -9.
From the values z 2 (4) = 3, z 2 (5) = 4 and z 2 (6) = 6 [17, Table 3] and z 3 (6) = 8 and z 3 (7) = 10 [19], we deduce, in particular, that [START_REF] Bollobás | Combinatorics[END_REF][START_REF] Chazelle | The discrepancy method: randomness and complexity[END_REF], [START_REF] Bollobás | Combinatorics[END_REF][START_REF] Cheong | Geometric permutations of disjoint unit spheres[END_REF], [START_REF] Bollobás | Defect Sauer results[END_REF][START_REF] Edelsbrunner | The maximum number of ways to stab n convex non-intersecting sets in the plane is 2n -2[END_REF], [START_REF] Bollobás | Defect Sauer results[END_REF][START_REF] Frankl | On the trace of finite sets[END_REF]}, and Sh(n, b, k) = Θ(n 5/3 ) for (b, k) ∈ {(6, 15), [START_REF] Bondy | Cycles of even length in graphs[END_REF][START_REF] Griggs | Extremal graphs with bounded densities of small subgraphs[END_REF], [START_REF] Bondy | Cycles of even length in graphs[END_REF][START_REF] Guy | A many-facetted problem of Zarankiewicz[END_REF]}.

Sh(n, b, k) = Θ(n √ n) for (b, k) ∈ {(4, 8),

Families of permutations

In this section we give bounds on the size of a family F of permutations on [n] with a given φ F (b).

Reduction to set systems. An inversion of a permutation σ on [n] is a pair 1 i < j n such that σ(i) > σ(j). The distinguishing pair of two permutations σ 1 and σ 2 is the lexicographically smallest pair (i, j) that is an inversion for one but not the other. If F is a family of permutations on [n] we let I F denote the set of distinguishing pairs for all pairs of permutations from F . Given a permutation σ ∈ F , we let R(σ) denote the set of elements of I F that are inversions of σ, and let R(F ) = {R(σ) | σ ∈ F }; see Fig. 1 for an example. We observe that (I F , R(F )) is a range space and that R is a one-to-one map between F and R(F ). In particular

|F | = |R(F )|. Lemma 4. If F is a family of permutations on [n] and m 2 then f R(F ) ( m 2 ) φ F (m) and |I F | Ex(n, m, φ F (m) -1). Proof. Let b = m 2 , put k = f R(F ) (b), let Y ⊆ I F be a set of b distinguishing pairs such that |R(F ) |Y | = k, and let σ 1 , . . . , σ k be permutations in F such that R(F ) |Y = {R(σ 1 ) |Y , . . . , R(σ k ) |Y }. We set Z = p∈Y p as the subset of elements [n] that appear in a pair in Y . R(σ i ) |Y = R(σ j ) |Y implies σ i|Z = σ j |Z ,
and so the permutations σ 1|Z , . . . , σ k|Z are pairwise distinct. This implies that φ F (|Z|) k and as |Z| 2b m, the first statement follows.

Let s(t) denote the maximum number of distinguishing pairs in a family of t permutations on [n]. We have s(2) = 1, and the following inequality follows from the distinguishing tree structure illustrated in Fig. 1:

s(t) 1 + max 1 i t-1 {s(i) + s(t -i)} , σ 1 = 1234567; R(σ 1 ) = ∅ σ 2 = 1235764; R(σ 2 ) = {(4, 5)} σ 3 = 2134567; R(σ 3 ) = {(1, 2)} σ 4 = 2143765; R(σ 4 ) = {(1, 2), (3, 4)} σ 5 = 2347561; R(σ 5 ) = {(1, 2), (1, 3)} σ 6 = 2354761; R(σ 6 ) = {(1, 2), (1, 3), (4, 5)
}

I F = {(1, 2), (1, 3), (3, 4), (4, 5)} (1, 2) (1, 3) (4, 5) σ6 σ5 (3, 4) σ4 σ3 (4, 5) σ2 σ1
Figure 1: I F and the elements of R(F ) for a set F of six permutations on the set [START_REF] Bondy | Cycles of even length in graphs[END_REF]. On the right, its distinguishing tree: its root is the lexicographically smallest distinguishing pair (i, j), the upper subtree is recursively built with the permutations that do not invert (i, j) and the lower subtree is recursively built with the permutations that invert (i, j).

By induction we obtain s(t) t -1. This implies that in the graph G = ([n], I F ), any m vertices span at most φ F (m) -1 edges, and it follows that

|I F | Ex(n, m, φ F (m) -1),
which concludes the proof.

Main transitions. We can now outline the main transitions in the growth rate of families of permutations according to the value of

φ F (m). Let b = m 2 . Constant. If φ F (m)
F | = O(n 2 ), we get that |F | is O n 2 m 2 -2 .
This bound can of course be refined using the results of Sections 2 and 3 (see Table 3).

At least exponential. If φ F (m) 2 m 2
then |F | can be exponential in n. An example is the family F 2 : all permutations on [n] that differ from the identity by the transposition of any number of pairs of the form (2i, 2i + 1).

F 2 has size 2 n 2 and φ F2 (m) = 2 m 2 .
In particular, any shattering condition either forces the size of the family of permutations to be polynomial or allows it to be exponential. A similar dichotomy was observed for growth rates of families of permutations with excluded patterns: the set of permutations on [n] avoiding a given family of patterns grows either at most polynomially or at least exponentially in n [START_REF] Kaiser | On growth rates of closed permutation classes[END_REF]. A similar result, albeit with a weaker bound, follows easily from our tabulation:

F (m) |F | Θ(1) Θ(n) Ω(n) and O n 2 m 2 -2 Ω(2 n 2 )
Table 2: Maximum size of a family F of permutations as a function of φ F (m).

Exponential upper bounds. Raz [START_REF] Raz | VC-dimension of sets of permutations[END_REF] proved that if φ F (3) 5 then |F | has size at most exponential in n. The following simple observation derives similar bounds for a few other values of φ F (m).

F (m) k. If φ F (m -1) < k then the assumption implies |F | C n D n . We can thus assume φ F (m -1) = k. Let X ∈ [n]
m-1 such that F |X = {σ 1 , . . . , σ k } has size k, and let

F i = {σ ∈ F | σ |X = σ i }.
F is the disjoint union of the F i . For any e ∈ [n] \ X and any i = 1, . . . , k, the family F i restricts to a single permutation on X ∪ {e} since φ F (m) = k. Let a ∈ X, and let Y = [n] \ {a}. By the above, for two distinct permutations σ, τ ∈ F i we have σ |Y = τ |Y . This implies that the family

G i = F i |Y has |G i | = |F i |. But G i
is a family of permutations on [n -1] with φ G i (m) k, and so by the induction assumption we have

|G i | D n-1 . It follows that |F | k i=1 |F i | = k i=1 |G i | k • D n-1 D n , since k D. With Raz's result that φ F (3)
5 implies that |F | is exponentially bounded, we obtain that |F | is exponentially bounded whenever φ F (m) m + 2. Table 3 tabulates our results for small values of m and φ F (m).

Conclusion

A natural open question is the tightening of the bounds for both Questions 1 and 2. In particular, the first case where Lemma 4 no longer guarantees that the reduction from permutations to set systems leads to a ground set with linear size is φ F (m) = m; does that condition still imply that |I F | or |F | are O(n) when m is large enough? How much does Raz's condition need to be weakened, that is, for which values of m and k does φ F (m) k imply that |F | is at most exponential in n? Can this question be tackled by a shifting technique similar to the lemma of Alon and Frankl used in the proof of Lemma 2?

A line intersecting a collection C of pairwise disjoint convex sets in R d induces two permutations, one reverse of the other, corresponding to the order in which each orientation of the line meets the sets.

3 2 Θ(n) 2 Θ(n) 2 Θ(n) n! - - - - 4 2n 3 + 1 2 Θ(n) 2 Θ(n) 2 Θ(n) 2 Ω(n) 2 Ω(n) 2 Ω(n) 2 Ω(n) 5 n 2 + 1 2 Θ(n) 2 Θ(n) 2 Θ(n) 2 Θ(n) 2 Ω(n) 2 Ω(n) 2 Ω(n) 6 3 Θ(n) Θ(n) O(n 8/3 ) O(n 3 ) 2 Θ(n) 2 Ω(n) 2 Ω(n) 7 3 Θ(n) Θ(n) O(n 2 ) O(n 8/3 ) 2 Θ(n) 2 Θ(n)
2 Ω(n) The pair of these permutations is called a geometric permutation of C. Let g(d, n) denote the maximum number of geometric permutations of a collection of n pairwise disjoint sets in R d . While the exact value of g(2, n) is known to be 2n -2 [START_REF] Edelsbrunner | The maximum number of ways to stab n convex non-intersecting sets in the plane is 2n -2[END_REF], determining the asymptotic order of magnitude of g(d, n) for d 3 has been one of the main open questions in geometric transversal theory [START_REF] Wenger | Helly-type theorems and geometric transversals[END_REF] for the last two decades (see for instance [START_REF] Aronov | On geometric permutations induced by lines transversal through a fixed point[END_REF][START_REF] Asinowski | The maximal number of geometric permutations for n disjoint translates of a convex set in R 3 is ω(n)[END_REF][START_REF] Cheong | Geometric permutations of disjoint unit spheres[END_REF][START_REF] Sharir | On neighbors in geometric permutations[END_REF]). The upper bound on g(d, n) was recently improved to O(n 2d-3 log n) [START_REF] Rubin | Improved bounds for geometric permutations[END_REF], and the best known lower bound is Ω(n d-1 ) [START_REF] Smorodinsky | Sharp bounds on geometric permutations for pairwise disjoint balls in R d[END_REF]. We can pick from each geometric permutation one of its elements so that the resulting family F has the following property: if any m members of C have at most k distinct geometric permutations then φ F (m -2) k. One interesting question is whether bounds such as the one we obtained could lead to new results on the geometric permutation problem.

Sh+ 1 except for n = 6 .

 6 There has also been interest in the case where b = αn and b = n -Θ(1); we refer to Jukna's book or the article of Bollobás and Radcliffe for these results. Permutations. Let σ be a permutation on [n] = {1, . . . , n} and let Y = {y 1 , . . . , y m } ⊆ [n], with y 1 < y 2 < . . . < y m . The restriction of σ to Y is the permutation σ |Y on [m] such that σ |Y (i) < σ |Y (j)

  For t 0 let R t denote the family of subsets in R of size t. It is clear that |R 0 | = 1 and |R 1 | = |X| n. It follows from claim (ii) that t 3 R t (k-1)|R 2 |. Now, if |X| < b then |R| f R (b) = k and the upper bound holds. Otherwise, (X, R 2 ) is a graph on at most n vertices where any b vertices span at most kb -1 edges, so |R 2 | Ex(n, b, kb -1) and the upper bound follows.

Corollary 3 .

 3 For b 4, we have:(i) If s 2 and k z s (b) + b + 1, then Sh(n, b, k) n + 1 + z s (n). (ii) If s 2, k < 4(b -1), and k < (s + 1)(bs + 1), then Sh(n, b, k) = O n 2-1/s . (iii) Sh(n, b, 2b) is O n 1+2/band is superlinear.

  ) By Lemma 2 we have Sh(n, b, 2b) = Θ(n + Ex(n, b, b -1)) and claim (iii) follows from the known bounds on Ex(n, b, b -1).

m 2 then

 2 , by Lemma 4, f R(F ) (b) b and Theorem 1 with i = 0 yields that |F | = |R(F )| = O(1).Linear. Assume that m 2 < φ F (m) < 2 m 2 . Then, by Lemma 4, f R(F ) (b) < 2b and Theorem 1 with i = 1 yields that |F | = |R(F )| = O(|I F |) = O(Ex(n, m, m -2)) = O(n).A matching lower bound is given by the family F 1 : the identity and all permutations on [n] that differ from the identity by the transposition of a single pair of the form (2i, 2i + 1).

F 1 1 .

 11 has size 1 + n 2 and φ F1 (m) = m 2 + Polynomial. If φ F (m) < 2 m 2 then, by Lemma 4, f R(F ) (b) < 2 b and (I F , R(F )) has VC-dimension at most b-1. It follows, from Sauer's Lemma, that |F | = |R(F )| = O(|I F | b-1 ), and since |I

Corollary 5 .

 5 Let Σ be a set of permutations (possibly of different sizes) and for n ∈ N let Forb n (Σ) denote the set of size-n permutations that contain no element of Σ as a restriction. Either there is a constant c, depending on Σ, such that |Forb n (Σ)| n c for all n 1 or |Forb n (Σ)| 2 n 2 for all n 1.

  φ

Lemma 6 .

 6 If, for given integers m and k there isC > 0 such that φ F (m -1) k -1 implies |F | C n for a family F of permutations on [n], then φ F (m) k implies |F | D n for D = max{C, k}.Proof. We prove the statement by induction over n. It is trivial for n = m, as then |F | = φ F (n) = φ F (m) k. So assume n > m and let F be a family of maximum size with φ

5 ) 1 m 2 |IFTable 3 :

 5123 |I F | Ex(n, m, m -2) = O(n) |I F | Ex(n, m, m -1) = O n 1+ | Ex(n, m, 2m -5) = O(n √ n) Maximumsize of a family F of permutations on [n] with φ F (m) = k. We use the bound on Sh |I F |, m 2 , k from Sections 2 and 3, and the shading of the cell indicates which of the three bounds on Ex(n, m, µ) mentioned in Section 3 is used to control the size of I F . For example, for m = 8 and k = 8 we have |I F | Ex(n, 8, 7) = O(n 5/4 ) and |F | Sh(|I F |, 4, 8) = O(|I F | 3/2 ) = O(n 15/8 ).

Table 1 :

 1 Values of k for which the condition λ i (b) k < 2 i (b-i+1) indicates that the order of magnitude of the bound of Theorem 1 on Sh(n, b, k) is tight.

				7
	4	1-4	5-7	9-11	12-15
	5	1-5	6-9	12-15 18-23 24-31
	6	1-6	7-11 16-19 27-31 36-47 48-63
	7	1-7	8-13 20-23 36-39 54-63	∅

The Turán graph T i (n) has n vertices, partitioned into i subsets, each of size n/i or n/i , with an edge between any two vertices from different subsets.

A fact sometimes referred to as Bondy's Theorem[START_REF] Bollobás | Combinatorics[END_REF].

See Jukna[START_REF] Jukna | Extremal Combinatorics[END_REF] Chapter 11], Bollobás[START_REF] Bollobás | Combinatorics[END_REF] Chapter 17] and the survey of Füredi and Pach[START_REF] Füredi | Traces of finite sets: Extremal problems and geometric applications[END_REF] for more details.

Acknowledgments

The authors thank Olivier Devillers and Csaba Tóth for their helpful comments. We also thank the two anonymous referees for their many valuable comments and in particular for pointing out Corollary 5.

* The cooperation of O.C. and X.G. was supported by the INRIA Équipe Associée KI. O.C. was supported by the Korea Science and Engineering Foundation Grant R01-2008-000-11607-0 funded by the Korean government.

Proof. Assume that we are not in the latter case and there exists n 0 such that |Forb n0 (Σ)| < 2 n 0 2

. By definition of Forb n (Σ), for any 1 α β and any α-element subset S ⊆ [β], we have Forb β (Σ) |S ⊆ Forb α (Σ). In particular, for any n n 0 , any restriction of Forb n (Σ) to an n 0 -element subset has size at most |Forb n0 (Σ)| < 2


François Berteloot

Thomas Gauthier

ON THE GEOMETRY OF BIFURCATION CURRENTS FOR QUADRATIC RATIONAL MAPS

HAL is

Introduction.

For any holomorphic family (f λ ) λ∈M of degree d rational maps on P 1 , the bifurcation locus is the subset of the parameter space M where the Julia sets J λ of f λ does not move continuously with λ. In their seminal paper [MSS], Mañé, Sad and Sullivan have shown that the bifurcation locus is nowhere dense in M and coincides with the closure of the set of parameters for which f λ admits a non-persistent neutral cycle. For the quadratic polynomial family z 2 + λ λ∈C , the bifurcation locus is the boundary of the Mandelbrot set and, in particular, is bounded. The situation is much more complicated for quadratic rational maps. Their moduli space M 2 can be identified with the complement in a complex projective space P 2 of a line at infinity L ∞ around which the behaviour of the bifurcation locus is far to be completely understood. The first results in this direction are due to J. Milnor [M] who studied the curves Per n (w) := {[f ] ∈ M 2 s.t. f has a n-cycle of multiplier w} in the projective space P 2 (see Proposition 2.3). Sharper results have then been obtained by A. Epstein [E] and yields a precise description of the intersections of Per n (w) with L ∞ (see Proposition 4.1). It should be stressed that the deformations of the Mandelbrot set, provided by intersecting the bifurcation locus with the lines P er 1 (t) for |t| < 1 (see Proposition 2.4), play a central role in these investigations. In particular, the work of C. Petersen [P] on the collapsing of limbs (see the beginning of the fourth section) is crucial in Epstein's proof.

Currents not only provide an appropriate framework for studying bifurcations from a measure-theoretic viewpoint, but are also very well suited to investigate the asymptotic distribution of the hypersurfaces Per n (w). Let us recall that L. DeMarco has proved that the bifurcation locus of any holomorphic family supports a closed, positive (1, 1)-current [START_REF] Demarco | Dynamics of rational maps: a current on the bifurcation locus[END_REF]. This current is denoted T bif and called bifurcation current. We refer the reader to the survey [Du] or the lecture notes [Be] for a report on recent results involving bifurcation currents and further references. The link between the bifurcation current T bif and the hypersurfaces Per n (w) relies on the fact that the Lyapunov exponent L(λ) of f λ (with respect to its maximal entropy measure) is a global potential for T bif (see [START_REF] Demarco | Dynamics of rational maps: Lyapunov exponents, bifurcations, and capacity[END_REF] or [START_REF] Bassanelli | Bifurcation currents in holomorphic dynamics on P k[END_REF]). G. Bassanelli and the first author have indeed deduced from this property the convergence of the weighted integration currents on Per n (w) lim n 1 d n [Per n (w)] = T bif for |w| < 1 or for any w ∈ C when the hyperbolic parameters are dense in M (see [START_REF] Bassanelli | Lyapunov exponents, bifurcation currents and laminations in bifurcation loci[END_REF]).

The present paper is devoted to the study of the behaviour at infinity of the bifurcation current in the moduli space M 2 of quadratic rational maps. We first show that this current extends naturally to a closed, positive (1, 1)-current Tbif on P 2 . We relate this current with the hypersurfaces Per n (w) and precise its support (see Theorem 3.1). We then use Epstein's result to compute the Lelong numbers of Tbif at any point of the line at infinity L ∞ and get a precise description of the measure Tbif ∧ [L ∞ ] (see Theorem 4.2). We finally describe the support of the so-called bifurcation measure T bif ∧ T bif and compare this measure with Tbif ∧ Tbif (see Propositions 5.1 and 5.2).

Notations. The complex plane will be denoted C and the euclidean unit disc in C will be denoted D. The k-dimensional complex projective space is denoted P k . A ball of radius r centered at x in some metric space is denoted B(x, r).

Preliminaries.

2.1. Lelong numbers and currents in P 2 .

Let T be a closed, positive, (1, 1)-current in P 2 . The mass of T on an open set U ⊂ P 2 is given by

T U := U T ∧ ω
where ω is the Fubini-Study form on P 2 . When V is an algebraic curve in P 2 and [V ] is the integration current on V , then [V ] P 2 = deg(V ).

For any x ∈ P 2 , the Lelong number of T at x is given by ν(T, x) := lim r→0 1 r 2 T B(x,r) . These numbers somehow measure the singularities of T . If V is an algebraic curve in P 2 , then ν([V ], x) is the multiplicity of V at x. We will mainly use the two following properties of Lelong numbers (see [Dem] Proposition 5.12 page 160 and Corollary 7.9 page 169).

Theorem 2.1 (Demailly).

(1) If T n -→ T , then for any

x ∈ P 2 , ν(T, x) ≥ lim sup n→+∞ ν(T n , x).
(2) If T 1 and T 2 are such that T 1 ∧ T 2 is well-defined, then for any

x ∈ P 2 , ν(T 1 ∧ T 2 , x) ≥ ν(T 1 , x) • ν(T 2 , x).
2.2. The moduli space M 2 of quadratic rational maps.

The space Rat 2 of quadratic rational maps on P 1 may be viewed as a Zarisky-open subset of P 5 on which the group of Möbius transformations acts by conjugation. The moduli space M 2 is, by definition, the quotient resulting from this action. Denote by α, β, γ the multipliers of the three fixed points of f ∈ Rat 2 and σ 1 = α+ β + γ, σ 2 = αβ + αγ + βγ and σ 3 = αβγ the symmetric functions of these multipliers. Milnor has proved that (σ 1 , σ 2 ) is a good parametrization of M 2 (see [M]).

Theorem 2.2 (Milnor). The map

[f ] ∈ M 2 -→ (σ 1 , σ 2 ) ∈ C 2 is a canonical biholomor- phism.
To study the curves Per n (w)

:= {[f ] ∈ M 2 s.t. f has a n-cycle of multiplier w}, it is useful to compactify M 2 . In this context, it turns out that the projective compactifi- cation [f ] ∈ M 2 / / [σ 1 : σ 2 : 1] ∈ P 2 is suitable. Denote by L ∞ the line at infinity of M 2 , i.e. L ∞ = {[σ 1 : σ 2 : 0] ∈ P 2 / (σ 1 , σ 2 ) ∈ C 2 \ {0}}.
Milnor has described the behavior of Per n (w) at infinity as follows (see [M] Lemmas 3.4 and section 4).

Proposition 2.3 (Milnor).

(1) For any w ∈ C the curve Per 1 (w) is a line in P 2 whose equation in C 2 is (w 2 + 1)λ 1wλ 2 -(w 3 + 2) = 0 and which intersects the line at infinity L ∞ at the point [w : w 2 + 1 : 0].

(2) For any n ≥ 2 and any w ∈ C, the curve Per n (w) is an algebraic curve in P 2 whose degree equals the number

d(n) ∼ 2 n-1 of n-hyperbolic components of the Mandelbrot set. In addition, the intersection Per n (w) ∩ L ∞ is contained in the set {[1 : u + 1/u : 0] ∈ P 2 / u q = 1 with q ≤ n}.
For reasons which will appear to be clear later, we shall denote by L ∞,bif the subset of L ∞ defined by L ∞,bif := {[1 : e iθ + 1/e iθ : 0] ∈ P 2 /θ ∈ [0, 2π]}. Golberg and Keen showed how the Mandelbrot set M determines the connectedness locus for quadratic rational maps having an attracting fixed point (see [GK] Section 1 and [BB2] Theorem 5.4 for a potential theoretic approach).

Theorem 2.4 (Goldberg-Keen, Bassanelli-Berteloot). There exists a holomorphic motion

σ : D × Per 1 (0) -→ C 2 such that M t := σ t (M) ⋐ Per 1 (t) ∩ C 2 is the connectedness locus of the line Per 1 (t). Moreover, if |w| ≤ 1 and n ≥ 1, then Per 1 (t) ∩ Per n (w) ⊂ M t . 2.3. Bifurcation currents in M 2 .
Every rational map f of degree d ≥ 2 on the Riemann sphere admits a maximal entropy measure µ f . The Lyapunov exponent of f with respect to this measure is defined by

L(f ) = P 1 log |f ′ |µ f . It turns out that the function L : Rat 2 -→ L(f ) is p.
s.h and continuous on Rat 2 . We still denote by L the function induced on M 2 . The bifurcation current T bif is a closed positive (1, 1)-current on M 2 which may be defined by

T bif = dd c L.
As it has been shown by DeMarco [START_REF] Demarco | Dynamics of rational maps: Lyapunov exponents, bifurcations, and capacity[END_REF], the support of T bif concides with the bifurcation locus of the family in the classical sense of Mañe-Sad-Sullivan (see also [START_REF] Bassanelli | Bifurcation currents in holomorphic dynamics on P k[END_REF], Theorem 5.2). Using properties of the Lyapounov exponent, Bassanelli and the first author proved that the curves Per n (0) equidistribute the bifurcation current (see [START_REF] Bassanelli | Lyapunov exponents, bifurcation currents and laminations in bifurcation loci[END_REF]).

Theorem 2.5 (Bassanelli-Berteloot). The sequence 2

-n [Per n (0)] converges to T bif in the sense of currents in M 2 . Moreover, 2 -n [Per n (0)]| Per 1 (0) converges weakly to ∆(L| Per 1 (0) ) = 1 2 µ M , where µ M is the harmonic measure of M.
As the function L is continuous, one can define the bifurcation measure µ bif of the moduli space M 2 as the Monge-Ampère mass of the function L, i.e.

µ bif := (dd c L) 2 := dd c (Ldd c L). This measure has been introduced by Bassanelli and the first author [START_REF] Bassanelli | Bifurcation currents in holomorphic dynamics on P k[END_REF]. Buff and Epstein also studied it in [BE]. Recall that a rational map f is said to be strictly poscritically finite if each critical point of f is preperiodic but not periodic. We denote by SPCF the set of classes of quadratic strictly postcritically finite rational maps. We also denote by the set of Shishikura maps, i.e.

S := {[f 0 ] ∈ M 2 / f 0 has 2 distinct neutral cycles}.
Combining the work of Bassanelli and the first author with that of Buff and Epstein, we have the following.

Theorem 2.6 (Bassanelli-Berteloot, Buff-Epstein).

supp(µ bif ) = SPCF = S.

These results are still valid in moduli spaces of degree d rational maps for any d ≥ 2. Notice that Buff and the second author [BG] have proved that flexible Lattès maps belong to supp(µ bif ).

Extension of the bifurcation current to Milnor's compactification.

As the current T bif is a weak limit of weighted integration currents on curves which are actually defined on P 2 , one may expect to naturally extend it to P 2 . We will show how this is possible and prove some basic properties of the extended current. More precisely, we establish the following result which may be considered as a measure-theoretic counterpart of Milnor's description of the bifurcation locus in M 2 .

Theorem 3.1. There exists a closed positive (1, 1)-current Tbif on P 2 whose mass equals 1/2 and such that:

(1) Tbif | C 2 = T bif , (2) 2 -n [Per n (0)] converges to Tbif in the sense of currents on P 2 , (3) supp( Tbif ) = supp(T bif ) ∪ L ∞,bif .
We shall use the two following lemmas which are of independant interest. The first one is essentially due to Milnor (see Theorem 4.2 in [M] or Theorem 2.3 in [START_REF] Bassanelli | Lyapunov exponents, bifurcation currents and laminations in bifurcation loci[END_REF]). The second one will be proved at the end of the section.

Lemma 3.2. [Per n (0)] P 2 ∼ 2 n-1 . Lemma 3.3. n≥1 Per n (0) ∩ L ∞ = L ∞,bif .
Proof. We first justify the existence of Tbif . According to the Skoda-El Mir Theorem (see [Dem] Theorem 2.3 page 139), the trivial extension of T bif through the line at infinity L ∞ is a closed positive (1, 1)-current on P 2 if T bif has locally bounded mass near L ∞ . The Lemma 3.2, combined with the fact that 2 -n [Per n (0)] converges to T bif on C 2 (see Theorem 2.5), immediatly yields T bif C 2 ≤ 1/2. The extension Tbif of T bif therefore exists and Tbif P 2 ≤ 1/2.

Let us now prove that 2 -n [Per n (0)] converges to Tbif on P 2 and Tbif P 2 = 1/2. By Lemma 3.2, (2 -n [Per n (0)]) n≥1 is a sequence of closed positive (1, 1)-currents with uniformly bounded mass on P 2 . According to the compactness porperties of such families of currents, it suffices to show that Tbif is the only limit value of 2 -n [Per n (0)].

Assume that 2 -n k [Per n k (0)] converges to T on P 2 . By Siu's Theorem (see [Dem] Theorem 8.16 page 181), one has T = S + α[L ∞ ], where S has no mass on L ∞ . But, by Lemma 3.3, the line L ∞ is not contained in supp(T ). Thus α = 0 and T has no mass on L ∞ . Since

T | C 2 = lim k 2 -n k [Per n k (0)] = T bif ,
this shows that T is actually the trivial extension of T bif through L ∞ and therefore, according to the first part of the proof, equals Tbif . Now, Lemma 3.2 immediatly yields Tbif P 2 = 1/2.

Proof of Lemma 3.3. Let σ : Per 1 (0) × D -→ |u|<1 Per 1 (u) be the holomorphic motion given by Theorem 2.4. Let us set M u := σ u (M). As M is compact and σ is continuous one has

|u|≤r<1 M u ⋐ C 2 for all 0 < r < 1.
Let us also recall that Per n (0) ∩ Per 1 (u) ⊂ M u for n ≥ 2 and u ∈ D.

We now proceed by contradiction and assume that there exists

ζ ∈ n Per n (0) ∩ L ∞ \ L ∞,bif . By Proposition 2.3, ζ ∈ Per 1 (u 0 ) for some u 0 ∈ D. Let us pick λ k ∈ Per n k (0) such that λ k → ζ.
Then there exists u k ∈ D such that u k → u 0 and λ k ∈ Per 1 (u k ), which is impossible since

λ k ∈ Per n k (0) ∩ Per 1 (u k ) ⊂ M u k ⊂ |u|<r M u
for some |u 0 | < r < 1.

Lelong numbers of the bifurcation current at infinity.

The aim of the present section is to compute the Lelong numbers of Tbif at any point. This is related to previous works of Petersen ([P]) and Epstein ( [E]) which we briefly describe.

Let ♥ be the main cardioid of the Mandelbrot set and L p/q the p/q-limb of M (see [Br] page 84). Denote by d p/q (n) the number of n-hyperbolic component of L p/q and set

D p/q (n) = d p/q (n) if p/q = 1/2, 2d p/q (n) otherwise.
Let σ be the holomorphic motion of Per 1 (0) given by Theorem 2.4 and ∞ p/q := [1 : 2 cos(2πp/q) : 0] if 1 ≤ p ≤ q/2 and p ∧ q = 1. Petersen has proved that the limb σ u (L p/q ) of M u disappears when u tends non-tangentially to e -2iπp/q . Using this result, Epstein has precisely described the intersection Per n (w) ∩ L ∞ . He namely proved the following:

Proposition 4.1 (Epstein). For any w ∈ C and any n ≥ 2,

[Per n (w)] ∧ [L ∞ ] = 1≤p≤q/2≤n/2 p∧q=1 ν([Per n (w)], ∞ p/q )δ ∞ p/q = 1≤p≤q/2≤n/2 p∧q=1 D p/q (n)δ ∞ p/q .
From the above Proposition and by using the previous section, we deduce the following.

Theorem 4.2.

(1) The Lelong numbers of Tbif are given by

ν( Tbif , a) =    1/6 if a = ∞ 1/2 , 1/(2 q -1) if a = ∞ p/q and , q ≥ 3 0 if a ∈ P 2 \ {∞ p/q / p ∧ q = 1, 1 ≤ p ≤ q/2}.
(

) The measure Tbif ∧ [L ∞ ] is discrete and given by Tbif ∧ [L ∞ ] = 1≤p≤q/2 p∧q=1 ν( Tbif , ∞ p/q )δ ∞ p/q . 2
The proof requires the two following lemmas. The first one is a consequence of Theorem 3.1 and the second one relies on a simple computation. They will be proved at the end of the section.

Lemma 4.3. The measure Tbif ∧ [L ∞ ] is a well-defined positive measure on P 2 of mass 1/2. Lemma 4.4. Let µ := 1 6 δ ∞ 1/2 + 1≤p≤q/2 p∧q=1, q≥3 1 2 q -1 δ ∞ p/q , then µ has mass 1/2.
Proof. First observe that ν( Tbif , a) = 0 when a / ∈ L ∞,bif , since then Tbif has a continuous potential in a neighborhood of a. Let us now pick 1 ≤ p ≤ q/2 such that p ∧ q = 1. By item (3) of Theorem 3.1 and Theorem 2.1, we have

ν( Tbif , ∞ p/q ) ≥ lim sup n→∞ ν(2 -n [Per n (0)], ∞ p/q ).
Proposition 4.1 states that ν([Per n (0)], ∞ p/q ) = D p/q (n) is the number of n-hyperbolic components of the union L p/q ∪ L -p/q of limbs of the Mandelbrot set. Thus, by Theorem 2.5,

2 -n ν([Per n (0)], ∞ p/q ) -→ 1 2 µ M (L p/q ∪ L -p/q
). On the other hand, Bullett and Sentenac have proved that µ M (L p/q ) = µ M (L -p/q ) = 1 2 q -1 (see [BS]). This gives ν( Tbif ,

∞ p/q ) ≥ 1 2 q -1 if p/q = 1/2 and ν( Tbif , ∞ 1/2 ) ≥ 1 2(2 2 -1) = 1 6 . Let a ∈ L ∞ . By Theorem 2.1 , we have ν( Tbif ∧[L ∞ ], a) ≥ ν( Tbif , a)ν([L ∞ ], a). As L ∞ is a line, we get ν( Tbif ∧[L ∞ ], a) ≥ ν( Tbif , a). For a = ∞ p/q , we thus have ν( Tbif ∧[L ∞ ], ∞ p/q ) ≥ 1 2 q -1 if q ≥ 3 and ν( Tbif ∧ [L ∞ ], ∞ 1/2 ) ≥ 1 6 , which we restate as Tbif ∧ [L ∞ ] ≥ µ.
Since, according to Lemmas 4.3 and 4.4, the positive measures Tbif ∧ [L ∞ ] and µ have the same mass, this yields Tbif ∧ [L ∞ ] = µ. We thus get point (2) and ν( Tbif , ∞ p/q ) = 1 2 q -1 for q ≥ 3 and ν( Tbif

, ∞ 1/2 ) = 1 6 . From Tbif ∧ [L ∞ ] ≥ ν( Tbif , a)δ a for any a ∈ L ∞ and Tbif ∧ [L ∞ ] = µ we get ν( Tbif , a) = 0 for a = ∞ p/q .
Proof of Lemma 4.3. Let us first remark that, by Theorem 3.1, supp( Tbif )∩L ∞ = L ∞,bif and let us decompose P 2 as the disjoint union of the line Per 1 (0) and (a copy of) C 2 . Let us stress that with these notations one has

L ∞ \ Per 1 (0) ∩ L ∞ ⊂ C 2 . By Proposition 2.3, the set L ∞,bif is compact in C 2 . By definition, the current Tbif has a potential u in C 2 which is continuous in C 2 \ L ∞ . By item (3) of Theorem 3.1, this potential is actually continuous in C 2 \ L ∞,bif . Let B 1 be a ball of C 2 containing L ∞,bif and (B i ) i≥2 be a covering of C 2 \ B 1 by balls such that B i ∩ L ∞,bif = ∅ for all i ≥ 2.
As {u is unbounded} ⊂ L ∞,bif and L ∞,bif ∩ ∂B i = ∅ and B i is pseudoconvex for any i ≥ 1, a result of Demailly asserts that Tbif

| C 2 ∧ [L ∞ ] = dd c u ∧ [L ∞ ]
is well-defined (see [Dem] Proposition 4.1 page 150). Since, by Proposition 2.3 and Theorem 4.2, L ∞ and supp( Tbif ) don't intersect in a neighborhood of Per 1 (0), the measure Tbif ∧ [L ∞ ] is a welldefined positive measure on P 2 .

Finally, Bézout Theorem asserts that Tbif ∧

[L ∞ ] P 2 = Tbif P 2 • [L ∞ ] P 2 = 1/2.
Proof of Lemma 4.4. Denote by φ(n) the Euler function. As the sets {p s.t. 1 ≤ p ≤ q/2, p ∧ q = 1} and {qp s.t. 1 ≤ p ≤ q/2, p ∧ q = 1} have same cardinality, we get

µ(P 2 ) = 1 6 + 1≤p≤q/2, p∧q=1, q≥3 1 2 q -1 = 1 2(2 2 -1) + 1 2 1≤p<q, p∧q=1, q≥3 1 2 q -1 = 1 2 q≥2    1≤p<q, p∧q=1 1 2 q -1    = 1 2 q≥2 φ(q) 2 q -1 .
A classical result (see [HW] Theorem 309 page 258) asserts that the series n≥1 φ(n) x n 1-x n locally uniformly converges on D and that its sum is x (1-x) 2 . Therefore,

µ(P 2 ) = 1 2   q≥1 φ(q) 2 q -1 -φ(1)   = 1 2   q≥1 φ(q)( 1 2 ) q 1 -( 1 2 ) q -φ(1)   = 1 2 .
5. Behavior of the bifurcation measure near infinity.

One often compares the moduli space M 2 of quadratic rational maps with the moduli space P 3 of cubic polynomials. In this section, we enlight some important differences between these two spaces. We first show that the bifurcation measure is not compactly supported in M 2 .

Proposition 5.1. The cluster set of the support of µ bif in P 2 is precisely L ∞,bif .

Proof. By Theorem 3.1, it suffices to show that L ∞,bif is accumulated by points of supp(µ bif ).

Recall that Per 1 (e 2iπν )∩L ∞ = {[1 : 2 cos(2πν) : 0]} for any 0 ≤ ν ≤ 1 (see Proposition 2.3).

Let us fix 0 < θ 0 < 1. For θ > 0 small enough, the lines Per 1 (e 2iπθ 0 ) and Per 1 (e 2iπ(θ-θ 0 ) ) do not intersect on L ∞ and therefore, {λ(θ)} := Per 1 (e 2iπθ 0 ) ∩ Per 1 (e 2iπ(θ-θ 0 ) ) ⊂ C 2 .

Since λ(θ) has two distinct neutral fixed points, it belongs to supp(µ bif ) (see Theorem 2.6).

It remains to check that lim θ→0 λ(θ) = [1 : 2 cos(2πθ 0 ) : 0]. By the holomorphic index formula (see [M]), the multiplier γ(θ) of the third fixed point of λ(θ) is given by

γ(θ) = 2 -(e 2iπθ 0 + e 2iπ(θ-θ 0 ) ) 1 -e 2iπθ .
As lim θ→0 |γ(θ)| = +∞, one has lim θ→0 λ(θ) = +∞. The conclusion follows, since λ(θ) stays on Per 1 (e 2iπθ 0 ) and Per 1 (e 2iπθ 0 ) ∩ L ∞ = {[1 : 2 cos(2πθ 0 ) : 0]}.

We would like to extend µ bif as a reasonable bifurcation measure on P 2 . To this aim, we compare µ bif with ( Tbif ) 2 . We prove the following.

Proposition 5.2. There exists a positive measure µ ∞ supported by L ∞,bif such that

Tbif ∧ Tbif = µ bif + 1 36 δ ∞ 1/2 + 1≤p≤q/2 p∧q=1,q≥3 1 (2 q -1) 2 δ ∞ p/q + µ ∞ .
Les us stress that our previous results ensure the existence of µ ∞ as a non-negative measure. A recent result due to Kiwi and Rees concerning the number of (n, m)-hyperbolic components of M 2 allows to see that µ ∞ is actually a positive measure.

Proof. Arguing exactly as in the proof of Lemma 4.3, one sees that Tbif ∧ Tbif is a welldefined positive measure on P 2 . By definition, Tbif ∧ Tbif and µ bif coincide on C 2 . To prove the existence of µ ∞ , it thus only remains to justify that

Tbif ∧ Tbif ≥ µ bif + 1 36 δ ∞ 1/2 + 1≤p≤q/2 p∧q=1,q≥3
1 (2 q -1) 2 δ ∞ p/q . By Theorem 2.1 and Theorem 4.2, we have ν( Tbif ∧ Tbif , ∞ p/q ) ≥ ν( Tbif , ∞ p/q ) 2 = 1 (2 q -1) 2 , when q ≥ 3 and ν( Tbif ∧ Tbif , ∞ 1/2 ) ≥ 1/36. The existence of µ ∞ then follows, since Tbif ∧ Tbif L∞ ≥ 1≤p≤q/2 p∧q=1 ν( Tbif ∧ Tbif , ∞ p/q )δ ∞ p/q .

Let us now show that µ ∞ > 0. One easily deduce from the convergence of 2 -n [Per n (0)] towards T bif in any family (see [START_REF] Bassanelli | Lyapunov exponents, bifurcation currents and laminations in bifurcation loci[END_REF]) that µ bif = lim m lim n 2 -(n+m) [Per n (0) ∩ Per m (0)] on C 2 . Thus µ bif (C 2 ) ≤ lim sup m lim sup n 2 -(n+m) [Per n (0) ∩ Per m (0)](C 2 ). Kiwi and Rees proved recently that the number of (n, m)-hyperbolic components in C 2 is at most

  5 48 2 n - 1 8 n q=2 φ(q)ν q (n) 2 q -1   2 m + O(2 m ),
where ν q (n) ∼ 2 n-1 /(2 q -1) and ν q (n) ≥ 2 n-1 /(2 q -1) -1/2 (see [KR] Theorem 1.1). A standard transversality statement asserts that this number actually coincides with [Per n (0) ∩ Per m (0)](C 2 ) (see [START_REF] Bassanelli | Lyapunov exponents, bifurcation currents and laminations in bifurcation loci[END_REF] Theorem 5.2). Thus µ bif (C 2 ) ≤ 5 48 -1 16 q≥2 φ(q) (2 q -1) 2 .

Let us now proceed by contradiction, assuming that µ ∞ = 0. Since Tbif has mass 1/2, Bézout Theorem gives Tbif ∧ Tbif P 2 = 1/4. Therefore,

1 4 = µ bif + 1 36 + 1≤p≤q/2 p∧q=1,q≥3
1 (2 q -1) 2 = µ bif + 1 2 q≥2 φ(q) (2 q -1) 2 -1 36 , which yields 25 56 ≤ q≥2 φ(q)

(2 q -1) 2 . We then have 25 56 ≤ q≥2 φ(q) (2 q -1) 2 ≤ φ(2) 6 + φ(3) 28 + 1 8 q≥4 φ(q) 2 q -1 which is impossible, since q≥1 φ(q) 2 q -1 = 2 (see proof of Lemma 3.2), φ(2) = 1 and φ(3) = 2.

Remark 5.1. To underline the contrast with the moduli space of cubic polynomials P 3 , we recall that the bifurcation measure is compactly supported and coincides with T 2 bif in P 3 .


S Bezzaoucha

B Marx

D Maquin

J Ragot

State and Parameter Estimation for Time-varying Systems: a Takagi-Sugeno Approach

Keywords: Time-varying linear systems, polytopic linear models, sector nonlinearity approach, convex polytopic transformation, state and parameter observer, linear matrix inequality

The contribution of this paper is to propose a systematic approach to the observer design for linear time-varying systems. It is based on the exact rewriting of the original time-varying system into a polytopic linear model (PLM). This transformation uses the sector nonlinearity approach based on the convex polytopic transformation. Then a joint state and parameter observer can be designed for the PLM and the estimation errors convergence are proved.

INTRODUCTION

Due to an increasing demand for higher performances, safety and reliability, model-based fault diagnosis (detection and isolation) is of practical importance and has received considerable interest these past years. The state estimation problem can be viewed as the heart of control systems and model-based diagnosis [START_REF] Chen | Robust model based fault diagnosis for dynamic systems[END_REF]), [START_REF] Basseville | On-board component fault detection and isolation using the statistical local approach[END_REF]). The design of observers, reconstructing state variables out of a limited set of measurements, is a possible approach for dealing with the measurement problem. But, due to time-varying behaviour of dynamical processes, the introduction of time-varying parameters in the system models leads to a higher level of complexity with more challenging problems in estimation. In this case, conventional observers essentially developped for time invariant systems cannot directly be used, and so-called adaptive observers developed for joint state and unknown parameter estimation has to be implemented. However, the difficulty in estimating such models is augmented by the fact that one has no idea regarding the way that the parameters may vary. In the present work, a focus is made on the linear time varying parameter (LPV) systems where the parameter variations are mostly inaccessible (non measurable) and may be considered as faults (acting as disturbances or/and uncertainties). Some methods have been published in this subject. They assume the existence of some Lyapunov function satisfying particular conditions and there is no systematic way to check their applicability to a given system [START_REF] Zhang | Implicit adaptive observers for a class of nonlinear systems[END_REF]), [START_REF] Rajamani | Adaptive observer for active automotive suspensions-theory and experiment[END_REF]), [START_REF] Besanc ¸on | Remarks on nonlinear adaptive observer design[END_REF]), [START_REF] Cho | A systematic approach to adaptive synthesis for nonlinear systems[END_REF]). Other methods make assumption that the estimated parameters are constant during the identification process. Control algorithms exploiting this type of parameter need to be updated on-line in order to increase their performances [START_REF] Kenne | Nonlinear systems time-varying parameter estimation: Application to induction motors[END_REF]). In some bioprocess, the concept of elemental balances of some components in the bioreactor is used to obtain indirect measurements of various time-varying parameters. The reconstruction of the immeasurable state variables and of the time-varying parameters is carried out on the basis of Extended Kalman filter algorithm using the indirect measurements. But these algorithms are difficult to implement in practice, since very few sensors are able to provide reliable and on-line measurements of state variables [START_REF] Lubenova | State adaptive algorithm for simultaneous estimation of time-varying parameters and state variables in aerobic bioprocesses[END_REF]). For discrete time systems, recursive algorithm design for joint state and parameter estimation can be found, but with the assumption of some canonical form for the system matrices [START_REF] Guyader | Adaptive observer for discrete time linear time varying systems[END_REF]). A natural idea for joint state and parameter estimation is to apply the Kalman filter to the extended system obtained by appending the unknown parameter into the state vector. However, the application of classical results requires uniform complete observability, which is difficult to chek for the extended system [START_REF] Guyader | Adaptive observer for discrete time linear time varying systems[END_REF]). In the present paper, a systematic procedure is presented to deal with the state and parameter estimation for time-varying systems. It consists in transforming the original system into a polytopic linear model based on the sector nonlinearity approach and the convex polytopic transformation. This transformation has the major interest to represent exactly the system without any loss of informations since the considered nonlinearities are bounded (each parameter varies between two known values). Up to our knowledge, this is the first contribution where the time-varying problem is treated is such a way. The main advantage is to give a systematic procedure in order to rewrite the nonlinearities and establish the convergence conditions of the state and parameter estimation errors, which will be expressed in linear matrix inequalities (LMI) formulation using the Lyapunov method. The paper is organized as follows. Section 2 introduces the polytopic structure for modelling and some preliminary results. It is followed by the representation of the nonlinear timevarying parameter by a polytopic structure in section 3. In section 4, observers for joint state and unknowm time-varying parameters estimation are implemented. In section 5, an extension for the case where a noise affects the output measurement with filter synthesis is applied in order to attenuate the influence of the parameter variation and the measurement noise on the state and parameter estimation errors. A numerical example and some simulation results are given in section 6. Conclusions are detailed in section 7.

PRELIMINARIES: POLYTOPIC LINEAR STRUCTURE FOR MODELING

The polytopic model may have different names, such as fuzzy model (Takagi-Sugeno model), multi-model, local model networks, ect. It allows the representation of the nonlinear behavior of systems by the interpolation of a set of linear submodels. Each submodel contributes to the global behavior of the nonlinear system through a weighting function µ i (ξ (t)) [START_REF] Tanaka | Fuzzy Control Systems Design and Analysis: A Linear Matrix Inequality Approach[END_REF]). The polytopic structure is given by

       ẋ(t) = r ∑ i=1 µ i (ξ (t))(A i x(t) + B i u(t)) y(t) = r ∑ i=1 µ i (ξ (t))(C i x(t) + D i u(t)) (1)
where x(t) ∈ R n x is the system state variable, u(t) ∈ R n u is the control input and y(t) ∈ R m is the system output. ξ (t) ∈ R q is the decision variable vector assumed to be measurable (as the system output) or known (as the system input). The weighting functions µ i (ξ (t)), also known as the scheduling functions, of the r submodels satisfy the convex sum property

   r ∑ i=1 µ i (ξ (t)) = 1 0 ≤ µ i (ξ (t)) ≤ 1, i = 1, . . . , r (2)
In the remaining of the paper, the following lemma is used: Lemma 1. Consider two matrices X and Y with appropriate dimensions, a time-varying matrix ∆(t) and a positive scalar ε. The following property is verified

X T ∆ T (t)Y +Y T ∆(t)X ≤ εX T X + ε -1 Y T Y (3) for ∆ T (t)∆(t) ≤ I.

POLYTOPIC MODELLING OF TIME-VARYING PARAMETERS

The main contribution of this work is to jointly estimate the state variables and the time-varying parameters of a LPV system, using the PLM representation. For that, each time-varying parameter is rewritten under a particular form.

Scalar time varying parameter

Let us consider the time-varying linear system represented by equation ( 4)

ẋ(t) = A(t)x(t) + B(t)u(t) y(t) = Cx(t) (4) with A(t) = A 0 + θ (t)A 1 , θ (t) ∈ [θ , θ ] B(t) = B 0 + θ (t)B 1 (5)
A 0 , A 1 , B 0 and B 1 are known matrices with suitable dimensions. θ (t) ∈ R is a time-varying parameter, it is non measurable but bounded and affects both matrices A and B.

Using the so-called sector nonlinearity approach, the bounded parameter θ (t) can be rewritten as:

θ (t) = µ 1 (θ (t))θ + µ 2 (θ (t))θ (6) with        µ 1 (θ (t)) = θ -θ (t) θ -θ µ 2 (θ (t)) = θ (t) -θ θ -θ (7)
such that the weighting functions µ 1 (θ (t)) and µ 2 (θ (t)) verify the convex sum property (2) with r = 2. Replacing ( 6) and ( 5) in equation ( 4), the initial linear system with the time-varying parameter θ (t) is now expressed as a PLM, such that :

ẋ(t) = 2 ∑ i=1 µ i (θ (t))(A i x(t) + B i u(t)) (8) with A 1 = A 0 + θ A 1 , B 1 = B 0 + θ B 1 A 2 = A 0 + θ A 1 , B 2 = B 0 + θ B 1 (9)

Extension to the vector case

Let us now consider the time-varying linear system represented by (10) with n parameters θ i (t)

ẋ(t) = A(t)x(t) + B(t)u(t) y(t) = Cx(t) (10) with          A(t) = A + n ∑ j=1 θ j (t)A j B(t) = B + n ∑ j=1 θ j (t)B j (11)
Remark 1. In ( 11), it is supposed that the matrices A(t) and B(t) depend on the same parameters. If a parameter θ j (t) does not affect A(t) (resp. B(t)), then the corresponding matrix Ā j (resp. B j ) is null.

Each parameter θ i (t) is expressed as:

θ i (t) = µ 1 i (θ i (t))θ i + µ 2 i (θ i (t))θ i (12) with the definitions:        µ 1 i (θ i (t)) = θ i -θ i (t) θ i -θ i µ 2 i (θ i (t)) = θ i (t) -θ i θ i -θ i (13)
satisfying the constraint:

µ 1 i (θ i (t)) + µ 2 i (θ i (t)) = 1, ∀t, i = 1, .
. . , n Finally, by replacing ( 11) and ( 12) in equation ( 10), we get:

     ẋ(t) = n ∑ i=1 2 ∑ j=1 µ j i (θ i (t))(A j i x(t) + B j i u(t)) y(t) = Cx(t) (14) A 1 i = A 0 + θ i A 1 i , B 1 i = B 0 + θ i B 1 i A 2 i = A 0 + θ i A 1 i , B 2 i = B 0 + θ i B 1 i (15)

STATE AND TIME-VARYING PARAMETER OBSERVER

Based on the obtained PLM, a simultaneous state and parameter observer may be designed and implemented. An L 2 attenuation is proposed to minimize the effect of the time-varying parameters on the state estimation errors, since these parameters are unknown.

The state and parameter observer is taken as the following 16) where L j i ∈ R n x ×m , K j i ∈ R n×m and α j i ∈ R n×n are the gain matrices to be determined in such a way that simultaneously the observer state and parameter converge to the system state and parameter. It may be noted here that the estimation problem is not trivial since the activation functions in the system (14) depend on θ (t), while those of the observer ( 16) depend on its estimate θ (t). Let us define the state estimation error e x (t) as e x (t) = x(t)x(t) (17) Its dynamics cannot be directly computed from (17) since the weighting functions depend on the unmeasurable variable (θ (t)). That is why, based on the convex sum property of the weighting functions, the state equation ( 14) is rewritten as follows

                     ẋ(t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t))(A j i x(t) + B j i u(t)) + L j i (y(t) -ŷ(t)) θ (t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t))(K j i (y(t) -ŷ(t)) -α j i θ (t)) ŷ(t) = C x(t) (
ẋ(t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) A j i x(t) + B j i u(t) + n ∑ i=1 2 ∑ j=1 µ j i (θ i (t)) -µ j i ( θi (t) A j i x(t) + B j i u(t) (18)
This form allows a better comparison of x(t) with x(t), since µ j i ( θi (t)) appears in the two expressions ( 16) and ( 18). Let us define:

∆A i (t) = 2 ∑ j=1 (µ j i (θ i (t)) -µ j i ( θi (t)))A j i = A i Σ A i (t)E A ∆B i (t) = 2 ∑ j=1 (µ j i (θ i (t)) -j i ( θi (t)))B j i = B i Σ B i (t)E B ( 19
)
with

A i = A 1 i A 2 i , Σ A i (t) = δ 1 i (t)I n x 0 0 δ 2 i (t)I n x , B i = B 1 i B 2 i , Σ B i (t) = δ 1 i (t)I n u 0 0 δ 2 i (t)I n u , E A = [ I n x I n x ] T , E B = [ I n u I n u ] T ( 20
)
Thanks to the property (2), for i = 1, 2, it holds

δ j i (t) = µ j i (θ i (t)) -µ j i ( θi (t)) -1 ≤ δ j i (t) ≤ 1 (21)
which implies from definition (20)

Σ T A i (t)Σ A i (t) ≤ I, Σ T B i (t)Σ B i (t) ≤ I (22)
The system (18) is then written as an uncertain-like system given by (see [START_REF] Ichalal | State and unknown input estimation for nonlinear systems described by Takagi-Sugeno models with unmeasurable premise variables[END_REF]):

ẋ(t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) (A j i + ∆A i (t))x(t) + (B j i + ∆B i (t))u(t) (23)
From equations ( 23), ( 16) and ( 17), the dynamics of the state estimation error are given by ėx

(t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) (A j i -L j i C)e x (t) + ∆A i (t)x(t) + ∆B i (t)u(t) (24)
Let us now define the parameter estimation error e θ (t) as e θ (t) = θ (t) -θ (t) (25) From equation ( 16), the dynamics of this error is given by ėθ

(t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) θ (t) -K j i Ce x (t) + α j i θ (t) -α j i e θ (t)
(26) Due to the coupling between the errors e θ (t) and e x (t), it is convenient to consider the augmented vectors e a (t) and ω(t)

e a (t) = e x (t) e θ (t) , ω(t) =    x(t) θ (t) θ (t) u(t)    ( 27
)
in order to obtain the augmented system describing the state and parameter estimation errors.

ėa (t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) Φ j i e a (t) + Ψ j i (t)ω(t) (28)
with

Φ j i = A j i -L j i C 0 -K j i C -α j i Ψ j i (t) = ∆A i (t) 0 0 ∆B i (t) 0 α j i I 0 ( 29
)
Our objective is to design the joint state and parameter observer with a minimal L 2 -gain of the transfer from ω(t) to e a (t).

The computation of the observer gains is detailed in the next theorem.

Theorem 1. There exists a joint robust state and parameter observer ( 16) for a linear time-varying parameter system (10) with an L 2 -gain from ω(t) to e a (t) bounded by β if there exists

P 0 = P T 0 > 0, P 1 = P T 1 > 0, β > 0, λ 1i , λ 2i , Γ 0 2 , Γ 1 2 , Γ 2 2 , Γ 3 2 > 0, α j
i , F j i and R j i solution of the optimization problem (30) under LMI constraints (32), for i = 1, . . . , n and j = 1, 2: min

P 0 ,P 1 ,R j i ,F j i ,α j i ,λ 1i ,λ 2i ,Γ 0 2 ,Γ 1 2 ,Γ 2 2 ,Γ 3 2 β (30) Γ k 2 < β I, for k = 0, 1, 2, 3 (31)
The observer gains are given by   

L j i = P -1 0 R j i K j i = P -1 1 F j i α j i = P -1 1 α j i ( 33
)
Proof 1. Let us consider the following quadratic Lyapunov function V (e a (t)) = e T a (t)Pe a (t), P = P T > 0 (34) its time derivative is given by

V (t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t))(e T a (t)((Φ j i ) T P + PΦ j i )e a (t) +e T a (t)PΨ j i (t)ω(t) + ω T (t)(Ψ j i ) T (t)Pe a (t)) (35)
Considering equation ( 28), the goal of the observer design is to attenuate the effect of the input ω(t) on e a (t). So, in order

            P 0 A j i + (A j i ) T P 0 -R j i C -C T (R j i ) T + I n x -C T (F j i ) T 0 0 0 0 P 0 A i P 0 B i * -α j i -(α j i ) T + I n 0 α j i P 1 0 0 0 * * -Γ 0 2 + λ 1 E T A E A 0 0 0 0 0 * * * -Γ 1 2 0 0 0 0 * * * * -Γ 2 2 0 0 0 * * * * * -Γ 3 2 + λ 2 E T B E B 0 0 * * * * * * -λ i1 I 0 * * * * * * 0 -λ i2 I             < 0 (32)
to guarantee the stability of ( 28) and the boundedness of the transfer from ω(t) to e a (t), the following criterion is considered

V (t) + e T a (t)e a (t) -ω T (t)Γ 2 ω(t) < 0 (36) with Γ 2 = diag(Γ k 2 ), Γ k 2 < β I, for k = 0, 1, 2, 3
(37) such that Γ 2 allows to attenuate the transfer of some ω(t) components to e a (t) components. From ( 35), ( 36) becomes:

n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) e a (t) ω(t) T (Φ j i ) T P + PΦ j i + I j i (t) (Ψ j i (t)) T (t)P -Γ 2 e a (t) ω(t) < 0 (38)
The main difficulty for satisfying (38) is the presence of timevarying terms. Then, the idea is to isolate and bound these terms. For that purpose, a block diagonal structure for the Lyapunov matrice P is considered: P = diag(P 0 , P 1 ) (39) From ( 25), ( 37) and ( 39), ( 38) is explicited as

n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) Q j i + Q i (t) + Q T i (t) < 0 ( 40
)
with:

Q j i =         (Q j i ) 11 -C T (K j i ) T P 1 0 0 0 0 * (Q j i ) 22 0 P 1 α j i P 1 0 * * -Γ 0 2 0 0 0 * * * -Γ 1 2 0 0 * * * * -Γ 2 2 0 * * * * * -Γ 3 2         (41) (Q j i ) 11 = P 0 A j i + (A j i ) T P 0 -C T (L j i ) T P 0 -P 0 L j i C + I n x (Q j i ) 22 = -P 1 α j i -(α j i ) T P 1 + I (42)
Based on ( 19) and ( 22), the time-varying term of ( 40) can be expressed as:

Q i =        P 0 A i 0 0 0 0 0        ( 0 0 Σ A (t)E A i 0 0 0 ) +        P 0 B i 0 0 0 0 0        ( 0 0 0 0 0 Σ B (t)E B i ) (43)
Using Lemma 1, there exists positive scalars λ 1i and λ 2i such that

Q i (t) + Q T i (t) <        Q 1 i 0 0 0 0 0 0 0 0 0 0 0 0 0 λ 1i E T A E A 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 λ 2i E T B E B        (44)
with: 44) and with the variable changes (33), the LMI ( 32) implies ( 40) and then implies the L 2 -gain attenuation of the transfer from ω(t) to e a (t), which achieves the proof.

Q 1 i = λ -1 1i P 0 A i A T i P 0 + λ -1 2i P 0 B i B T i P 0 (45) From inequality (
In order to improve the obtained results, the conditions (32) may be relaxed using the convex sum property (2). Since

µ 2 i (t) = 1 -µ 1 i (t) (46) (23) becomes: ẋ(t) = n ∑ i=1 2 ∑ j=1 µ 1 i ( θi (t)) (A j i + ∆A i (t))x(t) + (B j i + ∆B i (t))u(t) (47) ∆A i (t) = δ 1 i (t)(A 1 i -A 2 i ) ∆B i (t) = δ 1 i (t)(B 1 i -B 2 i ) δ 1 i (t) = µ 1 i (θ (t)) -µ 1 i ( θ (t)) (48)
Based on the same developments as previously, the following theorem can be established: Theorem 2. There exists a robust state and parameter observer (16) for the linear time-varying parameter system (10) with a bounded L 2 gain β of the transfer from ω(t) to e a (t) (β > 0) if there exists P 0 = P T 0 > 0,

P 1 = P T 1 > 0, β > 0, Λ 1i , Λ 2i , Γ 0 2 , Γ 1 2 , Γ 2
2 , Γ 3 2 > 0, α j i , F j i and R j i solution of the optimization problem (49) under LMI constraints (51), for i = 1, . . . , n and j = 1, 2: min

P 0 ,P 1 ,R j i ,F j i ,α j i ,Λ 1i ,Λ 2i ,Γ 0 2 ,Γ 1 2 ,Γ 2 2 ,Γ 3 2 β (49) Γ k 2 < β I for k = 0, 1, 2, 3 (50)
where Λ 1i and Λ 2i are matrices (instead of scalars for the previous development) and where:

Λ Ai = (A 1 i -A 2 i ) T Λ 1i (A 1 i -A 2 i ) Λ Bi = (B 1 i -B 2 i ) T Λ 2i (B 1 i -B 2 i ) (52)
The observer gains are still given by (33). Proof 2. The proof is omitted for space limitation but is similar to the previous one.

NOISE MEASUREMENT AND FILTER SYNTHESIS

In order to prove the efficiency of our approach, we consider the presence of measurement noise. The system is then described by the following equations:

           P 0 A j i + (A j i ) T P 0 -R j i C -C T (R j i ) T + I n x -C T (F j i ) T 0 0 0 0 P 0 P 0 * -α j i -(α j i ) T + I n 0 α j i P 1 0 0 0 * * -Γ 0 2 + Λ Ai 0 0 0 0 0 * * * -Γ 1 2 0 0 0 0 * * * * -Γ 2 2 0 0 0 * * * * * -Γ 3 2 + Λ Bi 0 0 * * * * * * -Λ 1i 0 * * * * * * 0 -Λ 2i            < 0 (51) ẋ(t) = A(t)x(t) + B(t)u(t) y(t) = Cx(t) + Gb(t) (53)
where b(t) is the noise measurement and matrices A(t) and B(t) have been already defined in (5).

The state and parameter observer is chosen as:

             ẋ(t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t))(A j i x(t) + B j i u(t)) + L j i (y(t) -ŷ(t)) θ (t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t))(K j i (y(t) -ŷ(t)) -α j i θ (t)) ŷ(t) = C x(t) (54
) Let us consider the augmented vectors e a (t) and ω(t)

e a (t) = e x (t) e θ (t) , ω(t) =      x(t) θ (t) θ (t) u(t) b(t)      (55)
where ω(t) takes now into account the noise b(t).

It follows:

ėa (t) = n ∑ i=1 2 ∑ j=1 µ j i ( θi (t)) Φ j i e a (t) + Ψ j i (t)ω(t) (56)
with

Φ j i = A j i -L j i C 0 -K j i C -α j i Ψ j i (t) = ∆A i (t) 0 0 ∆B i (t) -L j i G 0 α j i I 0 -K j i G (57)
Our objective is to attenuate the effect of the parametric variation and the noise on the state and parameter estimations. The computation of the observer gains is detailed in the next theorem.

Theorem 3. There exists a robust state and parameter observer (54) for a linear time-varying parameters system (53) subject to noise measurement with a bounded L 2 gain β of the transfer from ω(t) to e a (t) (β > 0) if there exists P 0 = P T 0 > 0,

P 1 = P T 1 > 0, β > 0, Λ 1i , Λ 2i , Γ 0 2 , Γ 1 2 , Γ 2 2 , Γ 3 2 > 0, Γ 4 2 > 0, α j i , F j i
and R j i solution of the optimization problem (58) under LMI constraints (60), for i = 1, . . . , n and j = 1, 2: min

P 0 ,P 1 ,R j i ,F j i ,α j i ,Λ 1i ,Λ 2i ,,Γ 0 2 ,Γ 1 2 ,Γ 2 2 ,Γ 3 2 β (58) Γ k 2 < β for k = 0, 1, 2, 3, 4 (59) with: Λ Ai = (A 1 i -A 2 i ) T Λ 1i (A 1 i -A 2 i ) Λ Bi = (B 1 i -B 2 i ) T Λ 2i (B 1 i -B 2 i ) (61)
The observer gains are given by (33).

Proof 3. The proof for Theorem 3 is based on the same development as the two previous results.

NUMERICAL EXAMPLE

The proposed approach is illustrated by an academic example. Let consider the linear time-varying system defined by: Considering a measurement noise defined by a normal distribution with zero mean and standard deviation 15% of the output magnitude affecting the system (53) with G = I 2 , the observer gains are calculated from theorem 3. The actual and estimated states and parameters are depicted in fig. 3 and4. The initial conditions for the system are taken x 0 = ( 2 1 2 ) for the system and and x0 = ( 0 0 0 0 0 ) for the joint state and parameter observer. From the depicted figures, one can conclude that, even if the the measurements are affected by noises, acceptable state and time-varying parameters estimations are obtained.

ẋ(t) = A 0 + θ 1 (t)A 1 1 + θ 2 (t)A 1 2 x(t) + Bu(t) (62) A 0 = -0.3 -1 -0.3 0.1 -2 -0.5 -0.1 0 -0.1 , A 1 1 = 0 -1.1 0 0 0 0 0 0 0 A 1 2 = 0 0 0 0 0 0 0 0 -1.1 , B = 1 0.5 0.25 , C = 1 0 0 0 0 1 Parameters θ 1 (t)
             P 0 A j i + (A j i ) T P 0 -R j i C -C T (R j i ) T + I n x -C T (F j i ) T 0 0 0 0 -R j i G P 0 P 0 * -α j i -(α j i ) T + I n 0 α j i P 1 0 -F j i G 0 0 * * -Γ 0 2 + Λ Ai 0 0 0 0 0 0 * * * -Γ 1 2 0 0 0 0 0 * * * * -

CONCLUSION

In the present paper, a new systematic procedure is presented to deal with the state and parameter estimation for time-varying systems. It consists in transforming the original system into a Takagi-Sugeno model based on the sector nonlinearity approach and the convex polytopic transformation. This transformation has the major interest to exactly represent the system without any loss of information. Then, it is used for state and parameter observer design. The observer gains are given by LMI optimization in order to minimize the L 2 gain from the inputs to the estimation errors. Relaxed conditions are also given based on the convex sum property of the weighting functions. The case with measurement noise is also studied. As future work, the same approach may be applied for nonlinear system with time-varying parameters.

Figure 1 .

 1 Figure 1. Nominal system (blue) -with parametric variation (red)

  Figure 2. System input

Figure 4 .

 4 Figure 4. Time-varying parameters and their estimates