Jaroslav Ne

Patrice Ossona

D E Mendez

Jaroslav Nešetřil
email: nesetril@iuuk.mff.cuni.cz

Patrice Ossona De Mendez

FIRST-ORDER LIMITS, AN ANALYTICAL PERSPECTIVE

Keywords:

In this paper we present a novel approach to graph (and structural) limits based on model theory and analysis. The role of Stone and Gelfand dualities is displayed prominently and leads to a general theory, which we believe is naturally emerging. This approach covers all the particular examples of structural convergence and it put the whole in new context. As an application, it leads to new intermediate examples of structural convergence and to a "grand conjecture" dealing with sparse graphs. We survey the recent developments.

Introduction

Let G 1 , G 2 , . . . , G n be a sequence of graphs with increasing orders. The theory of graph limits allows us to capture some common features of such a sequence by a single structure, the limit object. Such features include property testing and subgraph frequencies. Positive instances of this procedure are related to both dense and sparse graphs. This recently very active area of combinatorics is discussed for instance is [START_REF] Lovász | Large networks and graph limits[END_REF].

Can one demand that the limit object satisfies some further properties such as degree distribution, or bounded diameter, or non-existence of certain subgraphs?

This we approach by the notion of first-order limits of structures, which was introduced in [START_REF]A model theory approach to structural limits[END_REF][START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF].

This approach is based on the combination of model theory and functional analysis, and proved to be useful in dealing with "intermediate" classes, such as the class of trees and forests [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF]. It also generalizes (and as well puts in a new context) several notions of graph convergence studied earlier [START_REF] Borgs | Graph limits and parameter testing[END_REF][START_REF] Lovász | Limits of dense graph sequences[END_REF][START_REF] Benjamini | Recurrence of distibutional limits of finite planar graphs[END_REF][START_REF] Aldous | Processes on unimodular random networks[END_REF].

In Sections 3-6 we review here some of these results. However we also provide a new setting which generalizes and complements the earlier work of the authors [START_REF]A model theory approach to structural limits[END_REF]. We now view our approach as a natural approach, which lies midway between functional analysis approach to quantum theory and limits of graphs. This, perhaps even closer to functional analysis, we tried to explain in Section 2.

Here is an outline of what we do: We generalize aspects of the theory of graph limits, moving from a study a homomorphism and subgraph profiles to considering full statistics of first-order formula satisfaction. In our setting the underlying notion of convergence is, in essence, model theoretic, a relies on the the following notion [START_REF]A model theory approach to structural limits[END_REF]:

For a σ-structure A and a first-order formula φ (in the language of σ, with free variables x 1 , . . . , x p ), we denote by φ(A) the satisfying set of φ in A:

φ(A) = {(v 1 , . . . , v p ) ∈ A p : A |= φ(v 1 , . . . , v p )},
and we define the Stone pairing of φ and A as the probability [START_REF] Adler | Interpreting nowhere dense graph classes as a classical notion of model theory[END_REF] φ, A = |φ(A)| |A| p that A satisfies φ for a (uniform independent) random interpretation of the random variables.

A sequence (A n ) n∈N of finite σ-structures is FO-convergent if the sequence ( φ, A n ) n∈N converges for every first-order formula φ. It is important that one can derive a weakened notion of X-convergence (for a fragment X of first-order logic) by restricting the range of the test formulas φ to X.

We shall see that this abstract generalization of left convergence and local convergence can be seen as a particular (commutative) case of a general framework, which occurs naturally in functional analysis (in its description of quantum physics). This connection not only legitimates some of the constructions introduced to study first-order limits of structures, but it also put the whole framework in perspective, for a possible extension to the non-commutative setting of quantum logic. This connection will be discussed in Section 2, which may be seen as generalization and more uniform treatment of [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF].

Encouraged by this general analytic setting, we show that first-order limits (shortly FO-limits) and, more generally, X-limits can be uniquely represented by a probability measure µ on the Stone space S dual to the Lindenbaum-Tarski algebra of the formulas. In this setting, there is a one-to-one map A → µ A from the class of finite σ-structures to the space of probability measures on S, with

S 1 φ (T ) dµ A (T ) = φ, A , where 1 φ is the indicator function of the clopen subset of S dual to the formula φ in Stone duality. In this setting, a sequence (A n ) n∈N of finite σ-structures is firstorder convergent if and only if the measures µ An converge weakly to some measure µ. In such a case, the probability measure µ represents the limit of the sequence (A n ) n∈N and, for every first-order formula φ it holds This answers in a very general form the problem (originally posed by J. Chayes, see [START_REF] Lovász | Large networks and graph limits[END_REF]Introduction]) whether convergence leads to a limit distribution.

The particular definition (1) of the Stone pairing of a first-order formula and a finite structure can be extended, under certain conditions, to infinite structures. An obvious necessary condition for such an extension is that the domain of the considered infinite structure should be a measurable space, with the property that every first-order definable set is measurable. Note that the difficulty here stands in the fact that the class of definable sets is closed by projections, what is not the case of measurable sets. Consequently, we introduce in Section 5 the following notions: a Relational Sample Space (RSS) is a relational structure, whose domain is a standard Borel space, with the property that every first-order definable subset of a power of the domain is measurable (with respect to Borel product measure). A modeling M [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF] is an RSS equipped with a probability measure denoted ν M . In this setting, we can extend the definition of Stone pairing to modelings: for a modeling M and a first-order formula φ with free variables x 1 , . . . , x p we define [START_REF] Atserias | Preservation under extensions on wellbehaved finite structures[END_REF] φ,

M = • • • 1 φ(M) (v 1 , . . . , v p ) dν M (v 1 ) . . . dν M (v p ),
where 1 φ(M) is the indicator function of the set ( 5)

φ(M) = {(v 1 , . . . , v p ) ∈ M p : M |= φ(v 1 , . . . , v p )}.
This definition naturally leads to the two following representation problems, which can be seen as analogs of celebrated Aldous-Lyons problem on graphings.

Problem 1. Characterize those probability measures µ on X for which there exists a sequence (A n ) n∈N of finite structures such that for every first-order formula φ(x 1 , . . . , x p ) it holds

(6) S 1 φ (T ) dµ(T ) = lim n→∞ φ, A n .
Problem 2. Characterize those first-order convergent sequences of finite structures (A n ) n∈N for which there exists a modeling M such that for every first-order formula φ it holds [START_REF] Bratteli | Inductive limits of finite dimensional C * -algebras[END_REF] φ, M = lim n→∞ φ, A n .

As we shall see, such modeling limits do not exist in general (but sometimes they do) and thus we shall be interested in the following problem. Problem 3. Characterize classes with modeling limits, that is classes C of finite structures, such that for every first-order convergent sequence (A n ) n∈N of structures in C there is a modeling M such that φ, M = lim n→∞ φ, A n for every first-order formula φ.

It appears that this last problem is, perhaps surprisingly, related to the sparsedense dichotomy. The authors introduced in [START_REF]On nowhere dense graphs[END_REF][START_REF] Nešetřil | First order properties on nowhere dense structures[END_REF] a dichotomy of classes of graphs, between (sparse) nowhere dense classes and (dense) somewhere dense classes. This dichotomy, which can be expressed in numerous (and non trivially equivalent) ways, appears to be deeply related to first-order related properties of these classes. Based on a characterization of nowhere dense classes by means of Vapnik-Chervonenkis dimension of model-theoretic interpretations [START_REF] Adler | Interpreting nowhere dense graph classes as a classical notion of model theory[END_REF] and a characterization of random free hereditary classes of graphs [START_REF]Regularity partitions and the topology of graphons, An irregular mind[END_REF], we proved in [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF] that a monotone class of graphs with modeling limits is necessarily nowhere dense. We believe that nowhere dense-somewhere dense dichotomy actually gives the answer to Problem 3.

Conjecture 1 ([33]

). Every monotone nowhere dense class of graphs has modeling limits.

By a combination of model theory and functional analysis methods, we have been able to prove some particular cases: classes of graphs with bounded degree, classes of structures with bounded tree-depth [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF], as well as the class of all forests [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF] admit modeling limits. In this paper, we sketch a generalization to any class of graphs where the maximum degree is bounded by a function of the girth (or unbounded if the graph is acyclic). But before, in the next section, we outline an even more general approach (pointing to a possible non-commutative version).

Abstract Analytic Framework

We introduced in [START_REF]A model theory approach to structural limits[END_REF] the notion of first-order limits of structures as a generalization and unified treatment of various notions of limits. This notions also provided limit objects for new "intermediate classes". However first-order limits are interesting on their own. Particularly, as we show here, they display a rich spectrum of interconnection to the functional analysis approach to quantum theory [START_REF]Handbook of quantum logic and quantum structures: Quantum logic[END_REF]. For instance, the connection to C * -algebras makes more natural the introduction of several spaces and constructions, whose appearance in our framework may have earlier seem a little mysterious.

The formalism we adopt here is indeed close to the one of quantum theory, specially when considering significant objects and spaces. This aspect will be developed in this section, where we consider our approach to structure limits under the lights of statistical and quantum physics, as formalized by functional analysis.

Let us recall some basics: The set of all possible states of a physical system is the phase space of the system. In statistical physics, a statistical ensemble is the phase space of a physical system together with a method of averaging physical quantities, called observables, related to this system. In a classical system with phase space Ω, the observable quantities are real functions defined on Ω, and they are averaged by integration with respect to a certain probability measure µ on Ω. In a quantum system described by vectors in a Hilbert space H, the observable quantities are defined by self-adjoint operators acting on H, and are averaged using a certain positive, normalized functional ρ, defined on the algebra A(H) of operators on H (such functionals on H are called states) [START_REF] Minlos | Encyclopedia of mathematics[END_REF].

2.1. C * -algebras. A new unifying view consists in considering as a primary object the C * -algebra A of observables. Recall that a C * -algebra A is a Banach algebra with an involution x → x * , such that the relation x * x = x 2 holds for any element x ∈ A. The two standard examples of C * -algebras are the following (see [START_REF] Gelfand | On the imbedding of normed rings into the ring of operators in Hilbert space[END_REF] for the standard text):

First example is the space C 0 (X) of all continuous complex-valued functions which vanish at infinity on a locally compact Hausdorff space X, equipped with the uniform norm f = sup x∈X |f (x)|, and involution defined as the complexconjugate: f * (x) = f (x). Gelfand's representation theorem states that every commutative C * -algebra A is isometrically * -isomorphic to the algebra C 0 (Φ A ), where Φ A is the topological space of all the characters of A (that is: of the non-zero homomorphisms f : A → C) equipped with the relative weak- * topology. Given a ∈ A, one defines the Gelfand transform a of a, that is the function a : Φ A → C by a(f ) = f (a). Then the map a → a defines a norm-decreasing, unit-preserving algebra homomorphism from A to C 0 (Φ A ), which is the Gelfand representation of A.

The second standard example is the algebra B(H) of all bounded linear operators on a Hilbert space H, where involution is defined as the adjoint operator, and norm is defined as the operator norm. Gelfand-Naimark theorem states that any C *algebra is isometrically and symmetrically isomorphic to a C * -subalgebra of some C * -algebra of the form B(H) .

In our (discrete) setting, we shall be interested in the specific case where the algebra A of observables is approximately finite [START_REF] Bratteli | Inductive limits of finite dimensional C * -algebras[END_REF], that is in the case where there exists an increasing sequence

A 1 ⊆ A 2 ⊆ • • • ⊆ A of finite-dimensional sub-C * -algebras of A such that the union j A j is norm-dense in A.
Approximately finite C * -algebras (or AF C * -algebras) have been fully classified by Elliott [START_REF] Elliott | On the classification of inductive limits of sequences of semisimple finite-dimensional algebras[END_REF] using K-theory for C * -algebras. In particular, a C * -algebra A is commutative and approximately finite if and only if it is the algebra of continuous functions on the Stone space of a Boolean algebra (follows from [8, Proposition 3.1] and Stone duality). This very particular case corresponds to the framework we used to study structural limits. Fig. 1 describes the different mathematical objects entering this grand picture. In this context, let us recall that to each Boolean algebra B is associated a topological space, denoted S(B), called the Stone space of B, which is a totally disconnected compact Hausdorff space. The points in S(B) are the ultrafilters on B, or equivalently the homomorphisms from B to the two-element Boolean algebra. The mapping K : B → 2 S(B) defined by

K(φ) = {T ∈ S(B : φ ∈ T }
gives a one-to-one correspondence between elements of B and clopen subsets of S(B). The topology on S(B) is generated by a basis consisting of all (clopen) sets of the form {x ∈ S(B) | b ∈ x}, where b is an element of B. For every Boolean algebra B, S(B) is a compact totally disconnected Hausdorff space, and Stone representation theorem [START_REF] Stone | The theory of representations of Boolean algebras[END_REF] states that every Boolean algebra B is isomorphic to the algebra of clopen subsets of its Stone space S(B). Note that the Stone dual of a countable Boolean algebra is a compact Polish space. The similarity of Stone duality with Gelfand representation is not surprising, if one considers the motivation that led Stone to this theorem: "The writer's interest in the subject, for example, arose in connection with the spectral theory of symmetric transformations in Hilbert space and certain related properties of abstract integrals." (M.H. Stone [START_REF] Stone | The theory of representations of Boolean algebras[END_REF]) 2.2. Structural Limits. In the context of structural limits, the general picture of Fig. 1 takes more concrete form depicted on Fig. 2. This is a refinement of the approach the authors presented in [START_REF]A model theory approach to structural limits[END_REF][START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF][START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF]. Let us explain the role of the different spaces entering this scheme: We consider the class FO(σ) of all first-order formulas constructed with equality and the symbols in the considered signature σ, and the Boolean algebra B defined as the Lindenbaum-Tarski algebra of FO(σ), that is the Boolean algebra of the classes of these formulas with respect to logical equivalence. For instance, in the case of undirected graphs, formulas are constructed from the symbols of equality and adjacency, as well as standard connectives (conjunctions, disjunction, negation) and quantification over vertices.

Observables Algebra A = C(Ω)
The Stone space S(B) associated to B is a topological space, whose topology is generated by clopen subsets, which correspond exactly to first-order formulas (up to logical equivalence), that is to elements of B. A point in S(B) corresponds to a maximal set of consistent formulas.

As to each formula φ is associated a clopen subset K(φ) of S(B), the indicator functions 1 K(φ) of clopen subsets of S(B) are continuous functions from S(B) to R. An algebra A can be constructed from B as the algebra of formal finite real linear combinations of elements of B quotiented by the relation φ

+ ψ = φ ∧ ψ + φ ∨ ψ.
Each such finite linear combination can be written as a sum x = n i=1 α i φ i where φ i ∧ φ j = 0 whenever i = j. It turns out that x = max i |α i | is independent of the chosen decomposition, and defines a norm on A (this norm is nothing but the ∞ norm on C(S(B))). The completion of A for this norm is the Banach algebra C(S(B)) of all continuous functions from S(B) to R. (Note that if we consider for A complex linear combinations, we similarly construct the C * -algebra of all complex valued functions on S(B).) Finite σ-structures embed injectively in the space of additive functions on the Boolean algebra B by A → • , A , where

φ, A = |{(v 1 , . . . , v p ) ∈ A p : A |= φ(v 1 , . . . , v p )}| |A| p .
The following fact is worth noticing:

Fact 1.
There is a one-to-one correspondence between probability measures µ on S(B) and additive functions f µ : B → [0, 1] such that f (1) = 1, with the property that for every probability measure µ on S(B) and every φ ∈ B it holds

f µ (φ) = µ(K(φ)).
This fact, which we proved in [START_REF]A model theory approach to structural limits[END_REF] as a lemma, is actually known in the more general setting of MV-algebras [START_REF] Kroupa | Every state on semisimple MV-algebra is integral[END_REF][START_REF] Panti | Invariant measures in free MV-algebras[END_REF]. We give here a short proof for the sake of completeness:

Proof. The vector space V (B) generated by the indicator functions

1 K(φ) for φ ∈ B forms a subalgebra of C(S(B)). The subalgebra V (B) separates points of S(B): if T 1 , T 2 ∈ S(B), then there exists φ ∈ T 1 \ T 2 thus 1 K(φ) (T 1 ) = 1 K(φ) (T 2 ).
As the constant 1 function (corresponding to the maximum of the Boolean algebra) belongs to V (B), the subalgebra V (B) is dense in C(S(B)), according to Stone-Weierstrass theorem. As S(B) is a Radon-space, probability measures µ on S(B) correspond (in a one-to-one correspondence) to positive functionals F µ on C(S(B)) such that F µ (1) = 1 (according to Riesz representation theorem). As V (B) is dense in C(S(B)), every positive functional on C(S((B)) is uniquely determined by its restriction on V (B), and conversely every positive functional on V (B) uniquely extend (by continuity) to a positive functional on C(S((B)). Moreover, a norm 1 positive functional on V (B) is uniquely determined by its values on the generating set {1 K(φ) : φ ∈ B}, that is by the function

f µ : B → [0, 1] defined by f µ (φ) = µ(K(φ)). It is easily checked that f µ satisfies f µ (1) = 1 and φ ∧ ψ = 0 =⇒ f µ (φ ∨ ψ) = f µ (φ) + f µ (ψ),
and that every function f satisfying these inequalities uniquely defines a norm 1 positive functional on V (B), hence a measure µ on S(B), such that f = f µ .

It follows that finite σ-structures embed injectively in the space P (S(B)) of probability distributions on S(B): to a structure A with domain A we associate the unique measure µ A such that for every φ ∈ FO(σ) with free variables x 1 , . . . , x p it holds

S(B) 1 K(φ) dµ ⊗p A = φ, A .
Then, a sequence (A n ) n∈N is FO-convergent if and only if the probability measures µ An converge weakly. More can be said when considering convergence of finite σ-structures. The group S ω of permutations of N acts naturally on FO(σ) by permuting the free variables: for a formula φ with free variables x i1 , . . . , x ip and for a permutation τ , the formula τ • φ with free variables x j1 , . . . , x jp where j k = τ (i k ) is defined by

(τ • φ)(x j1 , . . . , x jp ) := φ(x i1 , . . . , x ip ).
It follows that S ω acts on the Boolean algebra B, and the action S ω B defines an action S ω S(B) on the Stone space of B. As it is clear that for every σ-structure A, every permutation τ , and every first-order formula φ it holds

τ • φ, A = φ, A .
Hence if a sequence (A n ) n∈N is FO-convergent, then the measures µ An converge weakly to some S ω -invariant probability measure on S(B). More generally, every injection f : N → N defines a transformation P f : S(B) → S(B), which is continuous, which is a homeomorphism if (and only if) f is bijective (that is a permutation on N). The set of the transformations P f has a monoid structure, as P f • P g = P f •g . Every measure µ that is obtained either from a finite structure or as weak limit of measures associated to finite structures is invariant under every P f . Hence (S(B), Σ S(B) , µ, P ) is a measure preserving dynamical system, where Σ S(B) is the Borel σ-algebra of S(B) and P is the monoid of transformations indexed by injections f : N → N.

We summarize the situation as follows:

Theorem 2. Let σ be an at most countable signature, let X ⊆ FO(σ) be a fragment of first-order logic, let B be the Lindenbaum-Tarski algebra of X, let S be the Stone dual of B, and let P (S) be the space of probability distributions on S. Then: To each σ structure A corresponds a measure µ A such that for every formula φ ∈ X with free variables in {x 1 , . . . , x p } it holds

S 1 K(φ) dµ A = φ, A ; A sequence (A n ) n∈N of σ-structures is X-convergent if
and only if the associated measures µ An converge weakly to some measure µ ∈ P (S). In such a case, for every formula φ ∈ X with free variables in {x 1 , . . . , x p } it holds

lim n→∞ φ, A n = S 1 K(φ) dµ.
Moreover, if Γ is a group of automorphisms of B (for instance the group of permutations of the free variables), then Γ acts naturally on S; if all the measures µ A associated to finite σ-structures are Γ-invariant, then so are all the measures obtained as weak limits of measures associated to finite σ-structures.

The proof is an easy modification of the proof given in [START_REF]A model theory approach to structural limits[END_REF], where we proved Theorem 2 without the appendix on group.

2.3.

Limits with respect to Parameters. The above abstract setting can be combined with ideas underlying left limits of graphs (as explained in [START_REF] Lovász | Large networks and graph limits[END_REF]) and, particularly, by property testing. The universal framework, complementing the approach of [START_REF]A model theory approach to structural limits[END_REF], and using some of the above theory, is to build a notion of limits as follows:

We consider a set O, whose elements we shall call objects, and a set F of bounded mappings f : O → R, which we call parameters. Then we define the notion convergence of a sequence of objects with respect to the family of parameters.

Because we are looking for a notion of limits with respect with the mappings in F, we consider on O the initial topology with respect to F, that is the coarsest topology that makes every mapping f ∈ F continuous. Note that O is not Hausdorff in general. Then the space C b (O, R) of bounded continuous functions on O with sup norm f = sup O∈O |f (O)| is a commutative Banach algebra (that can be extended to a commutative C * -algebra). According to Gelfand representation theorem, C b (O, R) is isometrically isomorphic to the algebra of continuous functions on a compact Hausdorff space, which is known to be homeomorphic to the Stone-Čech compactification βO of O. Recall that the the Stone-Čech compactification βO of O is the largest compact Hausdorff space generated by O, in the sense that any map from O to a compact Hausdorff space factors (in a unique way) through βO.

Let Profile : O → [0, 1] F denote the mapping defined by

Profile(O) = (f (O)) f ∈F ,
and let ∼ be the equivalence relation

O 1 ∼ O 2 ⇐⇒ Profile(O 1 ) = Profile(O 2 ).
Then KO = O/ ∼ is the Kolmogorov quotient of O, and βO is homeomorphic to the closure of {Profile(O)

: O ∈ O} in [0, 1] F .
This leads to the following natural notion of convergence of a sequence of objects of O with respect to parameters in F:

Definition 3. A sequence (O n ) n∈N is F-convergent if, for every f ∈ F the sequence (f (O n )) n∈N is convergent.
Note that the limit of an F-convergent sequence of objects in O is uniquely defined as a point of βO.

If P ∈ R[x 1 , . . . , x p ] is a real polynomial and f 1 , . . . , f p ∈ F, we denote by P (f 1 , . . . , f p ) the mapping from O to R defined by

P (f 1 , . . . , f p ) : O → P (f 1 (O), . . . , f p (O)).
Let A(O, F) be the sub-algebra of C b (O) formed by above mappings. Stone-Weierstrass theorem on uniform approximation of continuous functions by polynomials extends in this setting (and this is a folklore):

Lemma 4. The sub-algebra A(O, F) is dense in C b (O) = C(βO).
Proof. The algebra A(O, F) contains a non-zero constant (because of constant polynomials) and A(O, F) separates the points of βO (as it separates the points of KO). Thus the result follows from Stone-Weierstrass theorem.

Note that above results are very general, as we made no assumptions on our objects or parameters. Nevertheless, even that has some direct applications of this point of view to the theory of left-convergence.

Let hom(F, G) denote the number of homomorphisms from F to G, and let t(F, G) be the homomorphism density of F is G defined by

t(F, G) = hom(F, G) |G| |F | ,
that is the probability that a random map from F to G is a homomorphism.

Proposition 1. Let O be the set of all finite graphs, and let F be the set of all the mappings G → t(F, G) considered as mappings

t(F, • ) : O → [0, 1].
Then the notion of convergence defined above is the left-convergence, and βO is homeomorphic to the space of graphons.

Let SQ denote the algebra of standard quantum graphs, that is the commutative algebra constructed from vector space with basis formed by {K 1 } and all the finite graphs without isolated vertices, by defining multiplication by linearity from the case of finite graphs, defining the unit of the algebra as K 1 , and the product of two graphs without isolated vertices F 1 and F 2 as their disjoint union.

We shall make use of the following Lemma [23, Corollary 5.45, p. 74]:

Lemma 5. The graph parameters hom(F, • ) (where F ranges over simple graphs) are linearly independent. Equivalently, the graph parameters hom(F, • ) (where F ranges over connected simple graphs) are algebraically independent.

Proposition 2. Let O be the set of all finite graphs, and let F be the set of homomorphism densities

t(F, • ) : O → [0, 1].
Then the mapping

T : SQ → A(O, F) i=1 a i F i → i=1 a i t(F i , • )
is an algebra isomorphism of SQ and A(O, F).

Proof. The algebraic independence of the parameters t(F, • ) for graphs without isolated vertices will follow from the linear independence of the parameters t(F, • ) for simple graphs F either equal to K 1 or without isolated vertices , which we now prove: Assume that there exist non-isomorphic simple graphs F 1 , . . . , F (all of them being either K 1 or without isolated vertices) and reals a 1 , . . . , a such that i=1 a i t(F i , G) = 0 holds for every graph G. Let N = max i=1 |F i |, and let F i be the graph obtained from F i by adding

N -|F i | isolated vertices. Then hom(F i , G) = |G| |F i | t(F i , G) = |G| N t(F i , G).
Hence the equation i=1 a i hom(F i , G) = 0 holds for every graph G. As no two graphs F i are isomorphic, it follows from Lemma 5 that a 1 , . . . , a l are all zero.

Let us give two direct consequences of this lemma. The first consequence can be seen as an analog Stone Weierstrass uniform approximation of a continuous function by polynomials.

Say that a graph parameter f is left continuous if the sequence (f (G n )) n∈N converges for every left convergent sequence of graphs (G n ) n∈N . Proposition 3. For every left-continuous graph parameter f and every > 0 there exists a quantum graph F = i=1 a i F i such that for every graph G it holds

|t(F, G) -f (G)| < .
Proof. This is an immediate consequence of the density of T (SQ) in C(βO).

Say that a quantum graph F is non-negative (which we denote by F ≥ 0) if t(F, G) ≥ 0 for every graph G. The non-negativity of quantum graphs was subject to intensive study (see [START_REF] Lovász | Large networks and graph limits[END_REF]). The second consequence gives yet another characterization of this property. Proposition 4. Let F be a quantum graph. Then F ≥ 0 if and only if for every > 0 there exists a quantum graph H such that H ≥ 0 and F -H 2 < , that is:

inf G t(H, G) ≥ 0 and sup G |t(F, G) -t(H 2 , G)| < .
Proof. One direction is clear. For the other direction, assume F ≥ 0. Let h be the left-continuous graph parameter defined by h(G) = (t(F, G) + /2) 1/2 . Let H be a quantum graph such that h -T (H) < α, where α(

F + /2K 1 1/2 + α) < /2. Then inf G t(H, G) ≥ inf G t(h, G) -α ≥ ( /2) 1/2 -α ≥ 0. Moreover, (F+ /2K 1 )-H 2 = h 2 -T (H 2 ) ≤ h+T (H) h-T (H) ≤ (2 h +α)α < /2. Thus F -H 2 ≤ (F + /2K 1 ) -H 2 + /2K 1 < .
It is also pleasant to note that the sup norm defined on C b (O) defines naturally (by identification of SQ and A(O, F)) defines a norm

i a i F i = sup G∈O i a i t(F i , G)
for quantum graphs.

As we shall see later on, left-convergence of graphs is equivalent to (structural) QF --convergence, where QF -is the fragment of quantifier-free formula without equality. The global situation, which we just outlined, is depicted on Fig. 3 3.

Fragments of Interest

We review here a more detailed analysis of the convergence notions based of Lindenbaum-Tarski algebras of different fragments, in the context of Section 2 and of our earlier approach [START_REF]A model theory approach to structural limits[END_REF]. We consider the following fragments: Let us review some particular important cases of our theory induced by specific fragments of first-order logic. 3.1. Elementary Limits. Our starting case consists in considering elementary convergence: A sequence (A n ) n∈N is elementary convergent if, for every sentence (that is formulas without any free variables) θ there is an integer N such that either all the A n with n ≥ N satisfy θ, or no A n with n ≥ N satisfies θ. In other words, elementary convergence is convergence defined by the fragment FO 0 (σ) of first-order sentences. The Stone dual S of the Lindenbaum-Tarski algebra of firstorder sentences is the space of complete theories. Recall that a complete theory is a maximal consistent set of sentences. Gödel's celebrated completeness theorem of first-order logic asserts that every complete theory theory has a model. In other words, for every consistent set T ⊂ FO 0 (σ) of sentences there exists a σ-structure A that is a model of T , that is such that A satisfies every sentence in T . Moreover, according to Löwenheim-Skolem theorem, if the signature σ is at most countable then every consistent theory T ⊂ FO 0 (σ) has a model whose domain is at most countable.

Conversely, to each σ-structure A one associates the complete theory Th(A) of A, which is the set of all the sentences satisfied by A. Although it is easily checked to the mapping A → Th(A) is 1 -1 on finite structures, this is not the case for infinite structures; two structures A and B sharing the same complete theory are said to be elementary equivalent.

In such a context, the Stone bracket φ, A gets only values 0 (if A |= φ) or 1 (if A |= φ) , and the measure µ A associated to A is a Dirac measure at the point Th(A). The class of all finite σ-structures can accordingly be identified with an open subset O of S. The elementary limits of FO 0 -convergent sequences of finite σ-structures correspond to the points of the closure of O, which correspond to the complete theories T having the finite model property, that is the complete theories T such a every finite subset of T has a finite model.

It follows that every FO 0 -convergent sequence of finite σ-structures has a limit that can be represented as a σ-structure with an at most countable domain.

Note that characterizing elementary limits of finite structures is essentially difficult, as finite model property is not decidable in general. However, it is worth noticing that first-order formulas without functional symbols where all existential quantifications appear first in the formula, has the finite model property. Precisely, Ramsey [START_REF] Ramsey | On a problem of formal logic[END_REF] showed that a sentence ∃x 1 . . . ∃x n ∀y 1 . . . ∀y m φ (where φ is quantifier-free and has no function symbols) has a model if and only if it has a model of size bounded by n plus the number of constants in φ.

3.2.

Left limits and the Quantifier Free Fragment. We can precise our intuition by considering the case of undirected graphs with convergence driven by the fragment QF -of quantifier free formulas without equality (meaning that the equality symbol cannot be used). It is easily checked that the corresponding notion of convergence of a sequence (G n ) n∈N of graphs is nothing but the left-convergence introduced by Lovász et al., which is based on the convergence of the homomorphism profile t, which associates to each finite graph F the probability t(F, G n ) that a random map from F to G n is a homomorphism (that is an adjacency-preserving map). The Stone dual S(QF -) of the Lindenbaum-Tarski algebra of QF -can be described as follows: each point p ∈ S(QF -) is a maximal consistent set of formulas QF -, hence is uniquely determined by either x i ∼ x j or ¬(x i ∼ x j ) for each pair (i, j) ∈ N 2 , stating that x i is adjacent or not to x j . Each point p can thus be represented by means of a (labeled) countable graph with vertex set N, and the left limit of a sequence of graphs can be represented as an S ω -invariant probability distribution on the Stone space, that is as an infinite exchangeable random graph. Then it follows from Aldous and Hoover extentions of de Finetti's theorem to exchangeable arrays [START_REF] Aldous | Exchangeability and related topics, École d'été de probabilités de Saint-Flour[END_REF][START_REF] Hoover | Relations on probability spaces and arrays of random variables[END_REF] that left limits of graphs can be represented by means of a graphon, that is a symmetric measurable function W : [0, 1] × [0, 1] → [0, 1]. However, note that in the case of the fragment QF -, the mapping G → µ G is not injective, as two vertices that can be uniformly blown up in order to obtain a same graph are mapped to the same probability measure. This special aspect is due to the weakness of expressive power of the QF -fragment, and it disappears when one considers the fragment QF of all quantifier-free formulas, which essentially defines the same notion of convergence. fragment. We now consider the case of undirected graphs with degree at most D, and the fragment FO local 1 of local formulas with a single free variable. Recall that a formula φ is t-local if its satisfaction only depends on a distance t-neighborhood of the free variables, and that φ is local if it is t-local for some t ∈ N.

Local limits and the FO

Local convergence of graphs with bounded degree has been defined by Benjamini and Schramm [START_REF] Benjamini | Recurrence of distibutional limits of finite planar graphs[END_REF]. In our setting, local convergence can be defined as follows: A sequence (G n ) n∈N of graphs with maximum degree D is locally-convergent if, for every r ∈ N, the distribution of the isomorphism types of the distance r-neighborhood of a random vertex of G n converges as n goes to infinity. Local convergence witnesses the particular importance of the fragment FO local 1 : As each isomorphism type T of the distance r-neighborhood of a vertex can be characterized by the satisfaction of an r-local formula formula φ T (x) (where x stands for the root vertex), it follows that FO local 1 -convergence implies local convergence. Conversely, as the satisfaction of an r-local formula with a single free variable only depends on the isomorphism type of the (rooted) distance r-neighborhood of the free variable, FO is the space of all (isomorphism classes of) rooted connected countable graphs with maximum degree D.

Interrelations of Fragments and Reductions.

A peculiar feature of the fragments FO 0 and FO local , stated as Theorem 7, is a consequence of Gaifman locality theorem [START_REF] Gaifman | On local and non-local properties[END_REF]. This we recall now: Theorem 6. For every first-order formula φ(x 1 , . . . , x n ) there exist integers t and r such that φ is equivalent to a Boolean combination of t-local formulas ξ s (x i1 , . . . , x is ) and sentences of the form

(8) ∃y 1 . . . ∃y m 1≤i<j≤m dist(y i , y j ) > 2r ∧ 1≤i≤m ψ(y i )
where ψ is r-local. Furthermore, we can choose r ≤ 7 qrank(φ)-1 , t ≤ (7 qrank(φ)-1 -1)/2, m ≤ n + qrank(φ), and, if φ is a sentence, only sentences (8) occur in the Boolean combination. Moreover, these sentences can be chosen with quantifier rank at most f (qrank(φ)), for some fixed function f .

The proof of the following reduction theorem essentially uses Theorem 6.

Theorem 7 ([30]

). Let (A n ) be a sequence of finite λ-structures. Of course, if we constrain the class of structures on which we study limits, we get stronger reductions. For example, we now prove that in the case of a sequence of vertex-transitive structures in a wide class, most of the hierarchy of X-convergence collapses. Recall that a class of graphs C is wide if, for every integers d, m there is an integer N (d, m) such that every graph G ∈ C with order at least N (d, m) contains a subset of m vertices pairwise at distance at least d [START_REF] Atserias | Preservation under extensions on wellbehaved finite structures[END_REF]. (In particular, every class of graphs with bounded degree is wide.) Lemma 8. For every sentence θ there exists constants r, m and a formula φ ∈ FO local 1 such that for every vertex-transitive λ-structure A with at least m vertices pairwise at distance greater than 2r it holds

Then (A n ) is FO-convergent if
A |= θ ⇐⇒ A |= ∃x φ(x) ⇐⇒ ∀x φ(x) ⇐⇒ φ, A = 1.
Proof. If A is vertex-transitive then for every u, v ∈ A and every

φ ∈ FO 1 it holds A |= φ(u) if and only if A |= φ(v). Hence A |= ∃x φ(x) is equivalent to A |= ∀x φ(x).
According to Theorem 6, the sentence θ is equivalent to a Boolean combination of sentences of the form

A |= ∃y 1 . . . ∃y m 1≤i<j≤m dist(y i , y j ) > 2r ∧ 1≤i≤m ψ(y i ) ⇐⇒ A |= ∃y 1 . . . ∃y m 1≤i<j≤m dist(y i , y j ) > 2r ∧ ∃y 1≤i≤m ψ(y) ⇐⇒ A |= ∃y 1≤i≤m ψ(y)
(where the first equivalence comes from vertex-transitivity, and the second from the existence of m vertices far apart.) Moreover, by vertex transitivity, for every

φ 1 , φ 2 ∈ FO local 1 it holds A |= (∃x 1 φ 1 (x 1 )) ∧ (∃x 1 φ 2 (x 2 )) ⇐⇒ A |= (∃x φ 1 (x) ∧ φ 2 (x)).

It follows that the Boolean combination of the conditions

A |= ∃y 1≤i≤m ψ(y) is equivalent to the condition A |= ∃x φ(x) for some φ ∈ FO local 1 .
As a consequence, we obtain the following:

Theorem 9.
Let C be a wide class of vertex-transitive λ-structures. Then, for every sequence (A n ) n∈N with A n ∈ C and |A n | → ∞ the following conditions are equivalent:

(1) the sequence

(A n ) n∈N is FO-convergent, ( 2
) the sequence (A n ) n∈N is FO local 1 -convergent, (3) for every φ ∈ FO local 1
, either (∃x) φ(x) is satisfied by all but finitely many A n or (∃x) φ(x) is satisfied by only finitely many A n , (4) the sequence (A n ) n∈N is FO 0 -convergent.

Proof. That (1) implies ( 2) is trivial. That ( 2) is equivalent to (3) follows from vertex-transitivity. That (3) implies (4) follows from Lemma 8 and that (4) implies (3) is trivial. That (2) implies FO local convergence is a consequence of Gaifman locality theorem and wideness of C. Finally, that (4) together with FO local convergence implies (1) follows from Theorem 7.

Let us formulate the following consequence for Cayley graphs.

Corollary 1. Let d ∈ N, and let (G n ) n∈N be a sequence of (edge-colored directed) Cayley graphs generated by d elements of groups with orders going to infinity. Then the following conditions are equivalent:

(1) the sequence

(G n ) n∈N is FO-convergent, ( 2
) the sequence (G n ) n∈N is FO local 1 -convergent, (3) the sequence (G n ) n∈N is FO 0 -convergent.
We have already noticed (Theorem 7) that FO-convergence can be reduced to FO 0 -convergence and to FO local -convergence (thanks to Gaifman locality theorem). Furthermore, for wide classes (like classes with bouded degree), FO local -convergence is equivalent to FO local 1 -convergence. This explains the particular importance of the fragments FO local and FO local 1 .

Limit Connectivity

The importance of the fragments reviewed in the previous section also appears in the study of the limit notion of "connected components" for a convergent sequence of λ-structures. Note that connectivity of structures (which fails to be first-order definable) plays an important and non-trivial aspect of convergence of sparse graphs. The relative size and the speed of convergence plays a role here. Part of this problem is expressed by the following notions:

For a σ-structure A, a vertex v ∈ A, and an integer d, we define B d (A, v) as the substructure of A induced by vertices at distance at most d from v in A (that is at distance at most d from v in the Gaifman graph of A).

Definition 10 (Residual sequence). A sequence (A

n ) n∈N of λ-structures is residual if lim d→∞ lim sup n→∞ sup v∈An ν An (B d (A n , v)) = 0.
In other words, a sequences is residual if its limit has only zero-measure connected components

Definition 11. A sequence (A n ) n∈N of λ-structures is non-dispersive if lim d→∞ lim inf n→∞ sup v∈An ν An (B d (A n , v)) = 1.
In other words, a non-dispersive sequence is a sequence whose limit is essentially connected.

For a σ-structure A and a vertex ρ ∈ A, we denote by (A, ρ) the rooting of the structure A at ρ, that is the σ • -structure (where σ • is obtained by adding a unary symbol R to signature σ) obtained from A by putting exactly ρ in relation R.

In the case of rooted structures, we usually want a stronger statement that the structures remain concentrated around their roots: a sequence

(A n , ρ n ) n∈N of rooted λ-structures is ρ-non-dispersive if lim d→∞ lim inf n→∞ ν An (B d (A n , ρ n )) = 1.
The notion of non-dispersiveness is only an approximation of connectiveness. As such it is not supported by a single equivalence relation. However, we can introduce the notion of a component relation system, which approximates component equivalence.

Definition 12. A component relation system for a class C of λ-structures is a sequence d of equivalence relations such that for every d ∈ N and for every A ∈ C there is a partition of the d -equivalence classes of A into two parts E 0 ( d , A) and

E + ( d , A) such that: • every class in E 0 ( d , A) is a singleton; • ν A ( E 0 ( d , A)) < (d) + η(|A|) (where lim d→∞ (d) = lim n→∞ η(n) = 0); • two vertices x, y in E + ( d , A) belong to a same connected component of A if and only if A |= d (x, y) (i.e. iff
x and y belong to a same class).

Definition 13 ([33]

). A family of sequence (A i,n ) n∈N (i ∈ I) of λ-structures is uniformly elementarily convergent if, for every formula φ ∈ FO 1 (λ) there is an integer N such that it holds

∀i ∈ I, ∀n ≥ n ≥ N, (A i,n |= (∃x)φ(x)) =⇒ (A i,n |= (∃x)φ(x)).
(Note that if a family (A i,n ) n∈N (i ∈ I) of sequences is uniformly elementarily convergent, then each sequence (A i,n ) n∈N is elementarily convergent.)

Now that we have introduced all the necessary notions, we can state the following fundamental result, which allows to study FO local -convergent sequences (and more generally FO-convergent sequences) of disconnected λ-structures essentially component-wise.

Theorem 14 (Extended comb structure [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF]). Let (A n ) n∈N be an FO local -convergent sequence of finite λ-structures with component relation system d .

Then there exist I ⊆ N ∪ {0} and, for each i ∈ I, a real α i and a sequence

(B i,n ) n∈N of λ-structures, such that A n = i∈I B i,n (for all n ∈ N), i∈I α i = 1,
and for each i ∈ I it holds

• α i = lim n→∞ |Bi,n| |An| , and α i > 0 if i = 0; • if i = 0 and α 0 > 0 then (B i,n ) n∈N is FO local -convergent and residual; • if i > 0 then (B i,n ) n∈N is FO local -convergent and non-dispersive. Moreover, if (A n ) n∈N is FO-convergent we can require the family {(B i,n ) n∈N : i ∈ I} to be uniformly elementarily-convergent.
The proof of Theorem 14 is elaborated as it needs a detailed analysis of the speed of growth of components and we refer to [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF] for proof. An important consequence of this theorem is to reduce the problem of the construction of limit objects to the basic cases of residual sequences and non-dispersive sequences, see for instance Theorem 19.

Limit Objects of Sparse Structures

5.1. Borel Structures. Given a signature σ, Borel σ-structure is a σ-structure A, whose domain A is a standard Borel space, such that:

• for every relational symbol R ∈ σ with arity r, the set

R A = {(v 1 , . . . , v r ) ∈ A r : A |= R(v 1 , . . . , v r } of R in A is a Borel subset of A r ;
• for every functional symbol f ∈ σ with arity r, the corresponding map

f A : A r → A is a Borel map.
Note that Borel structures are a natural generalization of Borel graphs (see [START_REF] Kechris | Borel chromatic numbers[END_REF]).

It is easily checked that if A is a Borel σ-structure and if ν is a probability measure on A, then for every quantifier-free formula φ ∈ QF(σ), the set φ(A) is Borel. Whence we can extend the definition of Stone bracket to pairs formed by a Borel structure A equipped with a probability measure ν and a quantifier free formula φ with free variables in x 1 , . . . , x p by φ, (A, ν) = ν ⊗p (φ(A)).

Then, we shall say that a Borel σ-structure A equipped with a probability measure ν is a QF-limit of a sequence (F n ) n∈N of finite σ-structures if for every quantifier free formula φ it holds φ,

(A, ν) = lim n→∞ φ, F n . Example 15. Let (G n ) n∈N be a left convergent sequence with |G n | → ∞.
Then there exists a Borel graph G with a probability measure ν such that (G, ν) is a QF-limit of the sequence (G n ) n∈N if and only if the sequence (G n ) n∈N converges to a random-free graphon, that is a graph which is {0, 1}-valued almost everywhere. Some more exotic examples can be obtained by considering functional symbols:

Example 16 ([9]). A tree semi-lattice is a structure A whose signature only contains a binary functional symbol ∧, which satisfies the following axioms:

(1) the operation (defined by) ∧ is associative, commutative, and idempotent;

(2) for every x, y, z such that x ∧ z = x and y ∧ z = y it holds x ∧ y ∈ {x, y}.

Every QF-convergent sequence (T n ) n∈N of tree semi-lattices with k-colored domain there exists a Borel tree semilattice L with k-colored domain and a probability measure ν such that (L, ν) is a QF-limit of the sequence (T n ) n∈N .

Example 17. In this example, let (G n ) n∈N be a sequence of finite nonabelian groups with increasing orders. Assume each G n is either simple or is a symmetric group. Then the sequence (G n ) n∈N is QF-convergent and GL(2, R) (with Haar probability measure) is a QF-limit of (G n ) n∈N .

Indeed, according to [START_REF] Dixon | Residual properties of free groups and probbilistic methods[END_REF], the probability that a non-trivial fixed word w equals identity tends to 0 as n goes to infinity, and the same holds for the sequence of symmetric groups, according to [START_REF] Gamburd | On the girth of random Cayley graphs[END_REF]. Thus, for every quantifier formula φ(x 1 , . . . , x p ), the probability that φ(x 1 , . . . , x p ) will hold in G n for n going to infinity for independent uniform random assignments of x 1 , . . . , x p tends either to 1 or 0, depending on the fact that φ(x 1 , . . . , x p ) holds trivially or not. Also, according to [START_REF] Epstein | Almost all subgroups of Lie group are free[END_REF], the the probability that a non-trivial fixed word w equals identity is 0 for a connected finite-dimensional nonsolvable Lie groups (for instance GL(2, R)). Thus GL(2, R) is a QF-limit of (G n ) n∈N . 5.2. Modelings. We introduced in [33] -as candidate for a possible limit object of sparse structures -the notion of modeling, which extends the notion of graphing introduced for bounded degree graphs. A relational sample space is a relational structure A (with signature λ) with additional structure: The domain A of A is a standard Borel space (with Borel σ-algebra Σ A ) with the property that every subset of A p that is first-order definable in FO(λ) is measurable (in A p with respect to the product σ-algebra). A modeling is a relational sample space equipped with a probability measure (denoted ν A ). For brevity we shall use the same letter A for structure, relational sample space, and modeling. The definition of modelings allows us to extend Stone pairing naturally to modelings: the Stone pairing φ, A of a first-order formula φ (with free variables in {x 1 , . . . , x p }) and a modeling A, is defined by

φ, A = ν ⊗p (φ(A)), where φ(A) = {(v 1 , . . . , v p ) ∈ A p : A |= φ(v 1 , . . . , v p )}.
Note that every finite structure canonically defines a modeling (with same universe, discrete σ-algebra, and uniform probability measure) and that in the definition above matches the definition of Stone pairing of a formula and a finite structure introduced earlier. Also note that every modeling σ-structure is obviously a Borel σ-structure, but that the converse does not have to hold in general, as projections of Borel sets are not Borel in general.

For a fragment X of FO, we shall say that a sequence (A n ) n∈N is X-convergent to a modeling L (or that L is a modeling X-limit of (A n ) n∈N ), and we shall note A n X -→ L, if for every φ ∈ X it holds lim n→∞ φ, A n = φ, L . We shall say that a class C of λ-structures has modeling X-limits if, every X-convergent sequence (A n ) n∈N of λ-structures with A n ∈ C has a modeling X-limit. For instance, we proved in [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF] that classes of graphs with bounded degrees and classes of graphs with bounded tree-depth have modeling FO-limits, and we proved in [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF] that the class of rooted (k vertex-colored) trees has modeling FO-limits. However, the notion of modeling limit is, in some sense, only applicable to sparse structures: Theorem 18 ( [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF]). Let C be a monotone class of graphs.

If C has modeling FO-limits then C is nowhere dense, that is: for every integer p there exists an integer N = N (C, p) such that no graph in C contains the p subdivision of K N as a subgraph.

For more on nowhere dense graphs, we refer the reader to [START_REF] Nešetřil | First order properties on nowhere dense structures[END_REF][START_REF]Sparse combinatorial structures: Classification and applications[END_REF][START_REF]On nowhere dense graphs[END_REF][START_REF]Sparsity (graphs, structures, and algorithms[END_REF]. The importance of nowhere dense classes and the strong relationship of this notion with first-order logic is exemplified by the recent result of Grohe, Kreutzer, and Siebertz [START_REF] Grohe | Deciding first-order properties of nowhere dense graphs[END_REF], which states that (under a reasonable complexity theoretic assumption) deciding first-order properties of graphs in a monotone class C is fixed-parameter tractable if and only if C is nowhere dense. Motivated by strong model theoretical properties and manifold characterizations of nowhere dense classes, we conjectured that the above theorem is tight. This may be seen as the most challenging problem of this paper.

Conjecture 1. Every nowhere dense class of graphs has modeling FO-limits.

The problem of the existence of a modeling limit can be reduced to the study of FO local -convergence, and then to two "typical" particular cases: A modeling A with universe A satisfies the Finitary Mass Transport Principle if, for every φ, ψ ∈ FO 1 (λ) and every integers a, b such that

φ (∃ ≥a y) (x 1 ∼ y) ∧ ψ(y) ψ (∃ ≤b y) (x 1 ∼ y) ∧ φ(y) it holds a φ, A ≤ b ψ, A .
It is clear that every finite structure satisfies the Finitary Mass Transport Principle, hence every modeling FO-limit of finite structures satisfies the Finitary Mass Transport Principle, too.

The following stronger version of this principle, which is also satisfied by every finite structure, does not automatically hold in the limit.

A modeling A with universe A satisfies the Strong Finitary Mass Transport Principle if, for every measurable subsets X, Y of A, and every integers a, b, the following property holds:

If every x ∈ X has at least a neighbors in Y and every y ∈ Y has at most b neighbors in X then a ν A (X) ≤ b ν A (Y ).

The importance of residual and non-dispersive sequences appears again in the following result, which complements Theorem 14.

Theorem 19 ([32]). Let C be a hereditary class of structures.

Assume that for every A n ∈ C and every ρ n ∈ A n (n ∈ N) the following properties hold:

(1) if (A n ) n∈N is FO local 1 -convergent and residual, then it has a modeling FO local 1 limit;

(2) if (A n , ρ n ) n∈N is FO local -convergent and ρ-non-dispersive then it has a modeling FO local -limit. Then C has modeling FO-limits. Moreover, if in cases ( 1) and ( 2) the modeling limits satisfy the Strong Finitary Mass Transport Principle, then C has modeling FO-limits that satisfy the Strong Finitary Mass Transport Principle.

Constructions

In this section we add two useful extensions of some of the above results, by means of two basic operations. The first is the notion of (linear) convex combination of modelings. This may be used to give an inverse theorem for the comb structure Theorem 14. The second introduces the powerful tool of interpretation schemes, which gives the possibility to transport results from a class of λ-structures to a class of σ-structures. This also leads to a new characterization of nowhere dense classes.

Convex Combinations.

Definition 20 (Convex combination of Modelings). Let H i be λ-modelings for i ∈ I ⊆ N and let (α i ) i∈I be positive real numbers such that i∈I α i = 1.

Let H be the disjoint union of the

H i , let Σ H = { i X i : X i ∈ Σ Hi } and, for X ∈ Σ H , let ν H (X) = i α i ν Hi (X ∩ H i ).
Then H is the convex combination of modelings H i with weights α i and we denote it by i∈I (H i , α i ).

The following converse of Theorem 14 is proved in [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF]: Theorem 21. Assume J is a countable set, α i (i ∈ I) are reals, and

(B i,n ) n∈N (i ∈ I) are sequences of λ-structures such that α i = lim n→∞ |Bi,n| | j∈I Bj,n| (∀i ∈ I), i∈I α i = 1, and for each i ∈ I, (B i,n ) n∈N is FO local -convergent. Then A n = i∈I B i,n is FO local -convergent. Also, if there exist λ-modelings L i (i ∈ I) such that for each i ∈ I, B i,n FO local ----→ L i , then A n FO local ----→ i∈I (L i , α i ). Moreover, if the family {(B i,n ) n∈N : i ∈ I} is uniformly elementarily-convergent, then (A n ) n∈N is FO-convergent. Also, if there exist λ-modelings L i (i ∈ I) such that for each i ∈ I it holds B i,n FO --→ L i (for i > 0 and i = 0 if α 0 > 0) and B 0,n FO0 ---→ L 0 (if α 0 = 0) then A n FO --→ i∈I (L i , α i ).
6.2. Interpretation Schemes. Interpretation Schemes (introduced in this setting in [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF]) generalize to other logics than first-order logic. Definition 22. Let L be a logic (here either first-order logic or L ω1ω ). For p ∈ N and a signature λ, L p (λ) denotes the set of the formulas in the language of λ in logic L, with free variables in {x 1 , . . . , x p }.

Let κ, λ be signatures, where λ has q relational symbols R 1 , . . . , R q with respective arities r 1 , . . . , r q . An L-interpretation scheme I of λ-structures in κ-structures is defined by an integer k -the exponent of the L-interpretation scheme -a formula E ∈ L 2k (κ), a formula θ 0 ∈ L k (κ), and a formula θ i ∈ FO rik (κ) for each symbol R i ∈ λ, such that:

• the formula E defines an equivalence relation of k-tuples;

• each formula θ i is compatible with E, in the sense that for every 0 ≤ i ≤ q it holds 1≤j≤ri E(x j , y j ) θ i (x 1 , . . . , x ri ) ↔ θ i (y 1 , . . . , y ri ),

where r 0 = 1, boldface x j and y j represent k-tuples of free variables, and where θ i (x 1 , . . . , x ri ) stands for θ i (x 1,1 , . . . , x 1,k , . . . , x ri,1 , . . . , x ri,k ).

For a κ-structure A, we denote by I(A) the λ-structure B defined as follows:

• the domain B of B is the subset of the E-equivalence classes [x] ⊆ A k of the tuples x = (x 1 , . . . , x k ) such that A |= θ 0 (x); • for each 1 ≤ i ≤ q and every v 1 , . . . , v si ∈ A kri such that A |= θ 0 (v j ) (for every 1 ≤ j ≤ r i ) it holds B |= R i ([v 1 ], . . . , [v ri ]) ⇐⇒ A |= θ i (v 1 , . . . , v ri ).
From the standard properties of model theoretical interpretations (see, for instance [START_REF] Lascar | La théorie des modèles en peu de maux[END_REF] p. 180), we state the following: if I is an L-interpretation of λ-structures in κ-structures, then there exists a mapping Ĩ : L(λ) → L(κ) (defined by means of the formulas E, θ 0 , . . . , θ q above) such that for every φ ∈ L p (λ), and every κstructure A, the following property holds (while letting B = I(A) and identifying elements of B with the corresponding equivalence classes of A k ):

For every

[v 1 ], . . . , [v p ] ∈ B p (where v i = (v i,1 , . . . , v i,k ) ∈ A k ) it holds B |= φ([v 1 ], . . . , [v p ]) ⇐⇒ A |= Ĩ(φ)(v 1 , . . . , v p ).
It directly follows from the existence of the mapping Ĩ that

• an FO-interpretation scheme I of λ-structures in κ-structures defines a continuous mapping from S(B(FO(κ))) to S(B(FO(λ))); • an L ω1ω -interpretation scheme I of λ-structures in κ-structures defines a measurable mapping from S(B(FO(κ))) to S(B(FO(λ))).

Definition 23. Let κ, λ be signatures. A basic L-interpretation scheme I of λstructures in κ-structures with exponent k is defined by a formula θ i ∈ L kri (κ) for each symbol R i ∈ λ with arity r i . For a κ-structure A, we denote by I(A) the structure with domain A k such that, for every R i ∈ λ with arity r i and every v 1 , . . . , v ri ∈ A k it holds

I(A) |= R i (v 1 , . . . , v ri ) ⇐⇒ A |= θ i (v 1 , . . . , v ri ).
It is immediate that every basic L-interpretation scheme I defines a mapping Ĩ : L(λ) → L(κ) such that for every κ-structure A, every φ ∈ L p (λ), and every We deduce the following general properties:

Proposition 5 ( [START_REF]A unified approach to structural limits (with application to the study of limits of graphs with bounded tree-depth)[END_REF]). Let I be an FO-interpretation scheme of λ-structures in κ-structures.

Then, if a sequence (A n ) n∈N of finite κ-structures is FO-convergent then the sequence (I(A n )) n∈N of (finite) λ-structures is FO-convergent. Proposition 6 ([32]). Let I be a basic L ω1ω -interpretation scheme of λ-structures in κ-structures.

For every κ-modeling A, I(A) is a λ-modeling such that for every φ ∈ L p (λ) it holds φ, I(A) = Ĩ(φ), A .

Interpretations are a powerful tool. For a recent application to graph polynomials, see [START_REF] Goodall | Strongly polynomial sequences as interpretations[END_REF].

Open Problems

Our main conjecture here is Conjecture 1, which asserts that every monotone nowhere dense class of graphs has modeling limits.

There is a modest progress toward a resolution of this conjecture:

• any monotone class of graphs with bounded degree has modeling limit [START_REF]A model theory approach to structural limits[END_REF],

• the class of (colored rooted) forests has modeling limits [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF]. As an extension of the results in [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF], every FO-convergent sequence (G n ) n∈N with girth(G n ) → ∞ has a modeling limit. From this follows the first positive result concerning nowhere dense classes which do not have bounded average degree. Then the class C f has modeling limits.

Note that such classes include in particular all classes with bounded degree, and more generally classes of graphs in which the maximum degree is bounded by a function of the girth. Proposition 7 is currently our most general result toward Conjecture 1.

Problem 4. We consider 2-colored linear order, that is transitive tournaments with vertices colored black or white. Do every FO-convergent sequence of 2-colored linear order admit a modeling FO-limit? Note that if the answer to Problem 4 is yes, then it follows (by suitable interpretation) that every class of graphs with bounded pathwidth has modeling FO-limits. Similarly, if the above Example 16 extends to FO-convergence in the sense that every FO-convergent sequence of tree semilattices with k-colored domain has a modeling FO-limit then it would imply that every class of graphs with bounded treewidth has modeling FO-limits.

Quantifier-free fragment corresponds to the best known (and thoroughly investigated) type of convergence, which is left-convergence in the case of graphs and hypergraphs. However, our knowledge of QF-convergence is far from being complete. First, it is not completely clear what form the limit object should have in case of a relational structures with several non-unary relations. More important, the extension of the theory (notions of (hyper)graphons, cut metric, regularity theorem) in the simple case of a signature reduced to a single binary function is completely open. In general this problem might be too difficult to be directly addressed. It appears that a natural restriction consists in limiting the power of the binary function: Problem 5. Let σ be a signature reduced to a single binary function * (denoted as an operation), and let T 0 be a finite set of universal formulas (in the first-order language of σ). Assume that there exists a function f such that for every p, every model A of T 0 , and every v 1 , . . . , v p ∈ A, the σ-structure A v 1 , . . . , v p generated by v 1 , . . . , v p -that is the substructure of A whose domain is the smallest subset of A which contains v 1 , . . . , v p and is closed under the operation * -has a domain of cardinality at most f (p).

Does there exist a graphon-like limit object for QF-convergent sequences of finite models of T 0 ? Does there exist a regularity theorem for finite models of T 0 ? Note that in some simple cases, we can answer positively. For instance in the case of tree-semilattices [START_REF] Charbit | Random free limits of structures and the example of tree-semilattices[END_REF], which corresponds to associative, commutative, idempotent operation * with the additional property However, this case is too simple in the sense that limit objects are Borel treesemilattices, which means that tree-semilattices form a "random-free" class.

A possible candidate for a tractable non random-free example is the class of general semilattices, defined by general associative, commutative, idempotent operations * .

We can also consider signatures σ only containing unary functional symbols. In the case of a signature σ reduced to a single unary function, it appears that not only a limits of QF-convergent sequences of finite structures can be represented by a Borel σ-structure, but the class of these σ-structures actually admit modeling FOlimits, as an extension of the results in [START_REF]Modeling limits in hereditary classes: Reduction and application to trees[END_REF]. Note that for a signature σ consisting of at least two unary functional symbols, there is no hope to have modeling FO-limits (as such a class is sufficiently general to allow in it an interpretation of the class of all directed graphs)

S 1 φ

 1 (T ) dµ(T ) = lim n→∞ S 1 φ (T ) dµ An (T ) = lim n→∞ φ, A n .

1 Figure 1 .

 11 Figure 1. The different spaces in the standard case

Figure 2 .

 2 Figure 2. The spaces considered in the study of structural limits

• 1 :

 1 FO 0 : the fragment of sentences; • FO p : the fragment of formulas with free variables included in {x 1 , . . . , x p }; • QF: the fragment of quantifier-free formulas; • FO local : the fragment of local formulas; • FO local the fragment of local formulas with single free variable.

Figure 3 .

 3 Figure 3. and Structural QF --convergence.

  local

1

 1

v 1 ,

 1 . . . , v p ∈ A k it holds I(A) |= φ(v 1 , . . . , v p ) ⇐⇒ A |= Ĩ(φ)(v 1 , . . . , v p )

Proposition 7 .

 7 For a graph G, we denote by b 1 (G) the cyclomatic number of G (i.e. b 1 (G) = G -|G| + 1), and by Diam(G) its diameter. Let f : N → N be a mapping and let C f be the monotone nowhere dense class of all (colored) graphs G such that for every graph G ∈ C it holds b 1 (G) ≤ f (Diam(G)).

  ∀x ∀y ∀z [(x * z = x) ∧ (y * z = y)] → [(x * y = x) ∨ (x * y = y)].

  As we consider graphs with bounded degrees, we know that two rooted connected countable graphs with maximum degree at most D are elementarily equivalent if and only if they are isomorphic. It follows that in this case the Stone dual of FO local 1

		local 1	-convergence is
	equivalent local convergence.
	In general, points of the Stone dual of FO local 1	correspond to the complete theories
	of rooted connected structures.

  and only if it is both FO local -convergent and FO 0 -convergent. Precisely, (A n ) is FO p -convergent if and only if it is both FO local

	p	-convergent and
	FO 0 -convergent.

Supported by grant ERCCZ LL-1201 and CE-ITI P202/12/G061, and by the European Associated Laboratory "Structures in Combinatorics" (LEA STRUCO).

Supported by grant ERCCZ LL-1201 and by the European Associated Laboratory "Structures in Combinatorics" (LEA STRUCO).


Olivier Doaré
email: olivier.doare@ensta-paristech.fr

Sébastien Michelin
email: sebastien.michelin@ladhyx.polytechnique.fr

Miguel Pineirua
email: miguel.pineirua@ensta-paristech.fr

Yifan Xia
email: yifan.xia@ladhyx.polytechnique.fr

FLOW ENERGY HARVESTING WITH PIEZOELECTRIC FLAGS

In this article, energy harvesting with a fluttering cantilevered plate covered by piezoelectric patches in an axial flow is adressed. A theoretical model is presented which is then discretized and numerically integrated to perform a parametric study of the energy harvesting efficiency of the system. When one, two or three piezoelectric patches cover the plate, the optimal distributions of the patches that maximize the efficiency are obtained. Experimental results are presented, which are in good agreement with the model. When a significantly high number of patches of small size are considered, a continuous model is used to study the influence of a resonant harvesting circuit. A lock-in phenomenon is evidenced, which is able to significantly increase the efficiency.

Published in the proceedings of 33rd International Conference on Ocean, Offshore and Arctic Engineering OMAE2014, June 8-13, 2014, San Fransisco, USA Paper no OMAE2014-23867

I -INTRODUCTION

Recent efforts in the developement of new energy harvesting methods have been focused on the study of fluid-solid coupled systems that allow the conversion of the kinetic energy of flows into electrical energy [START_REF] Westwood | Ocean power: Wave and tidal energy review[END_REF][START_REF] Elvin | Advances in energy harvesting methods[END_REF]. Apart from the classical technologies such as wind and water turbines, other techniques involving the deformation of elastic structures under the action of fluid forces have attracted the attention of several research groups. The present study is focused on the energy harvesting from the fluttering of a piezoelectric flag in an axial flow [START_REF] Allen | Energy harvesting eel[END_REF][START_REF] Taylor | The Energy Harvesting Eel: A Small Subsurface Ocean/River Power Generator[END_REF]. A flexible plate in an axial flow can become unstable and develop self sustained flapping if the flow velocity exceeds a critical value. If the flapping plate is made of a piezoeletric material, the plate's deformation can be transformed into electrical energy. Previous works [START_REF] Doaré | Piezoelectric coupling in energy-harvesting fluttering flexible plates: linear stability analysis and conversion efficiency[END_REF][START_REF] Michelin | Energy harvesting efficiency of piezoelectric flags in axial flows[END_REF] have studied the fully coupled dynamics of a flexible plate covered by an infinite number of piezoelectric patches connected to simple resistive circuits. The case of a unique piezoelectric patch covering the entire length of the plate has also been considered [START_REF] Akcabay | Hydroelastic response and energy harvesting potential of flexible piezoelectric beams in viscous flow[END_REF]. The first question addressed in the present paper is the influence of the number and dimensions of the piezoelectric patches on the harvesting efficiency. Existing studies on the damping of vibrations with piezoelectric patches connected to passive circuits considered the influence of a resonant circuit [START_REF] Hagood | Damping of structural vibrations with piezoelectric materials and passive electrical networks[END_REF]. This motivates the second question in the present paper: what is the influence of a resonant circuit on the non-linear dynamics of the system, and the resulting harvesting efficiency?

The paper is organized as follows. In section II, we present a non linear dynamic model of a plate in an axial flow coupled to electrical circuits trough piezoelectric patches. Continuous and discrete configurations are presented. The numerical methods are also briefly described. Next, a parametric study of the influence on the number and geometries of the piezoelectric patches is presented. In this section, some experimental results are also compared to numerical results. Finally, a study of the influence of a resonant circuit on the energy harvesting efficiency is presented.

II -MODELING

Euler-Bernoulli beam in an axial flow coupled to electrical circuity via piezoelectricity Consider an elastic flexible plate of length L, width H and lineic density µ immersed in an axial flow of uniform velocity U ∞ , as sketched on figure 1. The fluid's density is ρ. The plate is inextensible and clamped at its leading edge. The local orientation of the plate is noted θ(S, T ), where S is the curvilinear coordinate along the streamwise direction and T is time. For simplicity only the 2D motion of the plate in the (xy) plane is taken into account. Piezoelectric patches of length l p , width H and thickness h p are fixed on both sides of the plate. The negative electrodes of the piezo-eletric patches are shunted across the plate while their positive electrodes are connected to an external circuit. The surface density of the charge in each piezo pair is given by [START_REF] Preumont | Vibration Control of Active Structures: An Introduction[END_REF]:

Q i = χ l i [θ] x + i x - i + cV i , (1)
where l i = x - i -x + i and V i is the voltage between the positive electrodes of the i th piezo pair whose left and right edges are positioned at x - i and x + i respectively. cl i is the equivalent capacity of the piezo pair and χ is the mechanical/piezoelectrical conversion factor of the piezoelectric material. The electrodes are connected to an external circuit. Voltage and charge density are then linked through the following generic relation,

F (Q i , V i ) = 0, (2)
whose exact expression depends on the circuits considered. The voltage V i between both electrodes also generates an internal torque in the piezoeletric patches and thus on the flexible plate. The total internal torque of the bent plate will then be given by M = B∂θ/∂S -χ i V i F i , where B is the flexural rigidity of the plate and piezoeletric patches assembly (see [START_REF] Doaré | Piezoelectric coupling in energy-harvesting fluttering flexible plates: linear stability analysis and conversion efficiency[END_REF]) and F i is the polarization function of the i th patch. In the present approach,

F i = H s (x -x - i ) -H s (x -x + i
), with H s the Heaviside step function.

Non-dimensional equations

To obtain the numerical results presented in the following, non-dimensional equations have been derived with L, L/U ∞ , U ∞ µ/c et U ∞ √ µc as characteristic length, time, voltage and charge respectively. Using the conservation of momentum [START_REF] Michelin | Energy harvesting efficiency of piezoelectric flags in axial flows[END_REF], the non-dimensional equation describing the non-linear dynamics of the system are,

∂ 2 x ∂t 2 = ∂ ∂s f t τ - 1 U * 2 ∂ 2 θ ∂s 3 n + α U * i v i δ (x - i ) -δ (x + i ) n -M * p res -M * H * m a p reac , (3)
q i = v i + α U * γ [θ] x + i x - i , (4)
f (q i , v i ) = 0, (5)
where p reac and p resis are respectively the reactive and resistive forces exerted by the flow on the plate and m a is the non-dimensional added mass coefficient of the local cross-section, namely m a = π/4 for a flat plate. They have been introduced in the context of slender fish locomotion [START_REF] Taylor | Analysis of the Swimming of Long and Narrow Animals[END_REF][START_REF] Lighthill | Large-amplitude elongated-body theory of fish locomotion[END_REF][START_REF] Candelier | Three-dimensional extension of Lighthill's large-amplitude elongated-body theory of fish locomotion[END_REF],

p reac = ẇ -(wu) + 1 2 w 2 κ (6)
p resis = 1 2 C d |w|w, (7)
where w and u are respectively the normal and longitudinal non dimensional components of the plate's velocity relative to the fluid flow.

The set of equations [START_REF] Allen | Energy harvesting eel[END_REF][START_REF] Taylor | The Energy Harvesting Eel: A Small Subsurface Ocean/River Power Generator[END_REF][START_REF] Doaré | Piezoelectric coupling in energy-harvesting fluttering flexible plates: linear stability analysis and conversion efficiency[END_REF] depends on the following non-dimensional parameters,

U * = LU ∞ µ B , M * = ρHL µ , H * = H L , α = χ √ Bc , (8)
which are respectively the dimensionless flow velocity, mass ratio, aspect ration and piezoelectric coupling factor. In the following, two kinds of electrical circuits will be considered. The first one consists in a shunted resistance of conductance per unit length g. In this case, equation ( 5) becomes,

β qi + v i = 0, (9)
The second circuit consists in a resistance and an inductance in parallel. The lineic admittance of the inductance is 1/L. The dynamic equation modeling the circuit is here,

β qi + vi + βω 2 0 v i = 0, (10)
The two additional electrical parameters that are then introduced in the model are,

β = U ∞ c Lg , ω 0 = L U ∞ √ cL (11)
Finally, a plate clamped upstream and free downstream is considered.

Discrete and continuous distributions of electrodes

The model described above consider a discrete distributions of piezoelectric electrodes, as well as a finite number of corresponding circuits. If the length of the electrodes is small compared to the typical lengthscale of the plate's deformation, it is possible to consider the limit of electrodes of infinitesimal length, as considered in refs [START_REF] Doaré | Piezoelectric coupling in energy-harvesting fluttering flexible plates: linear stability analysis and conversion efficiency[END_REF][START_REF] Michelin | Energy harvesting efficiency of piezoelectric flags in axial flows[END_REF]. Charge density q and voltage v are now condinuous functions of space and non-dimensional equations read,

∂x ∂t = ∂ ∂s f t τ - 1 U * 2 ∂ 2 θ ∂s 2 n + α U * ∂v ∂s n -M * p res -M * H * m a p reac , (12)
q = v + α U * γ θ , (13)
f (q, v) = 0. ( 14
)
Equations ( 9) and ( 10) remain unchanged, with the indices i ommited.

Efficiency of the system

The definition of the efficiency used in the present article is similar to that classically used in windmill studies. It is defined as the ratio between the mean harvested power and the kinetic energy flux through the surface occupied by the energy harvesting system,

η = P e P f . (15)
In the present approach, the harvested power is that dissipated in the resistance. The definition of the surface occupied by the harvesting system is less trivial in the present case than that of windmill, where this surface is the disc occupied by the rotating windmill. Here, we have chosen the rectangle defined by the width of the plate and its maximum displacement during the oscillation.

Numerical methods

Following [START_REF] Eloy | The origin of hysteresis in the flag instability[END_REF], equation ( 5) is projected onto x and y in order to obtain two equations for x(s, t) and y(s, t) respectively. The x projection is used to eliminate the tension term from the y projection. Finally, x and its derivatives are eliminated using the inextensibility condition. Two kinds of numerical approaches have then been used to obtain the results presented in the following. In the case of a discrete system, the equations for y(s, t) are first written in a weakly non-linear form by keeping only terms up to O(y 3 ), as done in [START_REF] Eloy | The origin of hysteresis in the flag instability[END_REF] in the uncoupled case. A Galerkin discretization is next used: the displacement y is written as a sum of N clamped-free beam modes and the equilibrium equations are projected on these beam modes. One obtain a set of N + N p ordinary differential equations which are integrated using an implicit numerical scheme.

In the case of a continuous system, nonlinear equations [START_REF] Candelier | Three-dimensional extension of Lighthill's large-amplitude elongated-body theory of fish locomotion[END_REF][START_REF] Eloy | The origin of hysteresis in the flag instability[END_REF][START_REF] Alben | Simulating the dynamics of flexible bodies and vortex sheets[END_REF] are solved using an implicit second order timestepping scheme [START_REF] Alben | Simulating the dynamics of flexible bodies and vortex sheets[END_REF]. The flag is meshed by Chebyshev-Lobatto nodes, and a Chebyshev collocation method is used to compute spatial derivatives and integration. At each time step, the resulting nonlinear system is solved using Broyden's method [START_REF] Broyden | A class of methods for solving nonlinear simultaneous equations[END_REF]. The simulation is started with a perturbation in the flag's orientation (θ(s, t = 0) = 0), and is carried out over a sufficiently long time frame so as to reach a permanent regime. The quantities necessary for evaluating the efficiency are then obtained as follows: the harvested energy is computed as the time average of the dissipation in the resistive elements, and the flapping amplitude is defined as the root-mean-square amplitude of the trailing edge, both within the permanent regime.

III -RESULTS

In this section, different parametric studies of the efficiency of the system are presented. We focus only on the postcritical dynamics of the system, once flutter instability has appeared. Only a few representative sets of mechanical parameters M * and U * are investigated. The coupling coefficient is fixed at 0.3, which corresponds to reasonable values one could obtain using PZT patches on steel plates [START_REF] Doaré | Piezoelectric coupling in energy-harvesting fluttering flexible plates: linear stability analysis and conversion efficiency[END_REF].

At first we show the number and geometry of the electrodes affect the efficiency of the system. The cases of 1, 2 and 3 electrodes are successively considered. Next, we present a numerical/experimental compraison of the efficiency for a piezoelectric patch of variable length. The circuit is a purely resitive circuit. Finally a case of a continuous distribution is considered, where the harvesting circuit also contains an inductance.

Influence of the number and distribution of electrodes

Case I: one electrode We consider here that one piezoelectric patch of length l p covers partially the surface of the plate. It is fixed at a distance δ from the clamped end. In the present approach, it is supposed that the present piezoelectric patch does not affect the density and bending rigidity of the sandwich plate. For a study that takes into account this effect, one could refer for instance to reference [START_REF] Thomas | Vibrations of an elastic structure with shunted piezoelectric patches: efficient finite element formulation and electromechanical coupling coefficients[END_REF], in the context of the passive damping of vibrating beams.

Figure 3 presents the efficiency of the harvesting system in the (δ, l p ) plane, for two values of the mass ratio M * , just above the instability threshold. Each colored rectangle of these plots corresponds to one numerical simulation where the value of β was adjusted to reach maximum efficiency.

For M * = 0.6, the maximum efficiency is achieved for δ ∼ 0.4 and l p ∼ 0.5. In this case, the electrode resides mainly at the second half of the clamped-free plate. This result differ significantly to that obtained in works on energy harvesting from vibrating beams, where the piezoelectric patch is generally placed at the clamp or covering the whole length [START_REF] Dunnmon | Power extraction from aeroelastic limit cycle oscillations[END_REF][START_REF] Akcabay | Hydroelastic response and energy harvesting potential of flexible piezoelectric beams in viscous flow[END_REF].

For M * = 10, three local maxima of the efficiency in the (δ, l p ) plane can be observed. They correspond to an electrode of length l p ∼ 0.3 at δ ∼ 0.3, 0.5 and 0.75 respectively. The presence of more local maxima with shorter electrodes is explained by the fact that the higher is M * , the higher is the number of spatial oscillation is the unstable mode [START_REF] Eloy | Aeroelastic instability of cantilevered flexible plates in uniform flow[END_REF].

Case II: two electrodes The case with two electrodes covering the whole plate is now considered. The parametric study now depends on one parameter only: the length of the first electrode, noted x c . On figure 4, the parametric study is done in the same two cases: M * = 0.6 and M * = 10, with U * chosen just above the instability threshold, U * = 13 and 8.5 respectively. For M * = 0.6, the maximum value of η is found for x c ∼ 0.35 and is approximately twice the minimum efficiency η. For M * = 10 we find two local maxima, around x c = 0.5 and x c = 0.7 respectively. These maxima represent a significant improvement of the efficiency. Indeed, in this case, the maximum efficiency is approximately 9 times larger than the minimum efficiency. The contribution of each piezoelectric pair on the efficiency is also plotted on this figures, showing that when the optimal efficiency is reached, the contribution of the downstream piezoelectric pair is significantly higher than the upstream one. This is consistent with the results of case I presented above.

Case III: three electrodes The case with three electrodes covering the entire plate is now adressed in the same two configurations as before. There are now two parameters, x c1 and x c2 , which are the junctions between two piezoelectric patches.

For M * = 0.6 the maximum efficiency is reached for x c1 ∼ 0.4 and x c2 ∼ 0.9. In this configuration, the second piezoelectric patch is approximately the same as in the one of case I, the two other patches covering the remaining space on the plate. For M * = 10, the point of maximum efficiency (x c1 = 0.5, x c2 = 0.7) can not be related to the optimal configuration of case I. For this large value of the mass ratio, the sensibility of the efficiency with the parameters is important and it will be consequently more difficult to reach the optimal efficiency in practical applications. Before the presentation of some experimental results, let us discuss briefly the main results of this section. First of all, we have presented results obtained by a weakly nonlinear model discretized using a small set of Galerkin modes, allowing fast computations. Considering one, two or three electrodes covering entierely or partially the plate, we have revealed the geometrical distributions that maximize the efficiency. We show that the optimal distributions strongly depend on the mass ratio M * . In the single-electrode case, we also showed that letting an extremity of the electrode be at the clamp is far from being the optimal configuration. It is indeed possible to increase the efficiency by a factor 2 at M * = 0.6 and 10 at M * = 10 when looking for the best position and length of the electrode.

Experiments

A series of experimental measurements is now presented. A schematic view of the experimental setup is given in Fig. 6. Two experiments have been conducted, which consist basically in considering the case I, with one extremity of the electrode fixed at x = 0 or x = 1. The former (experiment I on Fig. 6) is achieved by fixing δ = 0 and varying l p from 0 to 1. The latter (experiment II on Fig. 6) is achieved by varying δ and imposing l p = 1 -δ. In both experiments the studied plates are composed of a mylar sheet of length 12 cm, width 2.5 cm and thickness 100 µm. A piezoelectric PVDF film fixed on each side of the sheet. The width of the piezoelectric sheet in the spanwise direction is smaller than the width of the plate, in order to reduce the influence of δ and l p on the local flexural rigidity and lineic mass of the system. PVDF films are covered with an external Cr/Au which serves as the electrode. During the experiments the Cr/Au layer is sectioned in order to adjust the desired value of δ and l p . The thickness of the PVDF film in experiment 1 is 40 µm while in experiment 2 is 50 µm. The system is placed in a wind tunnel of rectangular transversal section 10 cm wide and 5 cm high with transparent walls that allow taking images from the outside. At a given velocity above the instability threshold, the voltage is measured across the electrodes of the piezoelectric patches with a variable resistance adjusted so that the dissipated power is maximum. The efficiency is then calculated using equation [START_REF] Broyden | A class of methods for solving nonlinear simultaneous equations[END_REF].

On figure 7, the efficiency is plotted against l p for δ = 0. Numerical and experimental results are plotted on the same figure, and show a good agreement. The maximum efficiency is achieved when the piezoelectric patch occupy the whole length of the plate. On figure 8, the efficiency is plotted against l p with l p = 1-δ, so that the piezoelectric patch lies between x = δ and x = 1. Here again, there is a good agreement between numerical results and experiments. The maximum efficiency is reached when the piezoelectric patch upstream extremity is a x ∼ 0.1.

Hence, there is an overall good agreement between theory and experiments with respect to the influence of the geometry of the electrode on the efficiency of the harvester. The slight discrepancies might be due difficulties of controlling the parameters during the manufacturing process and to the influence of the piezoelectric patch on the local bending rigidity and density, which is not taken into account bythe model.

IMPROVEMENT OF EFFICIENCY BY A LOCK-IN MECANISM

In this section, a different harvesting circuit is considered. It now consists in a resistance and an inductance in parallel. Due to the fact that the piezoelectric patch behaves like a capacitor, the resulting circuit consists in an RLC circuit that can enter in resonnance with the forcing coming from the piezoelectric coupling. In the present case, the continuous limit is considered and numerical results using the full non-linear model are presented.

On figure 9(a), the efficiency is plotted against ω 0 for different values of β. The other parameters are fixed to M * = 1, U * = 13, H * = 0.5 and α = 0.3. In a range of ω 0 around unity, the efficiency reach a maximum of the order of 10 -2 , which is significantly higher than what can be achieved with purely resistive circuits. The flapping frequency is plotted on figure 9 and shows that when high efficiencies are obtained, the flapping frequency ω = ω 0 . This phenomenon is referred to as a frequency lock-in, and is mainly reported in works on Vortex-Induced Vibration (VIV), [START_REF] Williamson | Vortex-induced vibrations[END_REF]. In this phenomenon, the frequency of an active oscillator (the flapping flag) is dictated by the natural frequency of a coupled passive oscillator (the circuit).

The deformation of the flag during one period of oscillation is plotted on figure 10 in a case without lock-in (ω 0 = 3.25), and in a case with lock-in (ω 0 = 4.12). This plot shows that when the lock-in occurs, the fluttering amplitude of the flag is significantly larger. This emphasizes that the efficiency is increased not only because of a resonance in the RLC circuit, but also because of an increase of the flapping amplitude.

CONCLUSION

In this article a model of a piezoelectric flag coupled with energy harvesting circuits has been presented. The discrete and continuous configurations have been defined. When the number of piezoelectric patches tends to infinity and their length is small compared to the typical deformations of the flag, a continuous electrical model can be used.

In all the paper, we focused on the energy harvesting efficiency of the system, whose definition is similar to that used in windmill studies. First, the influence of the number and arrangement of the piezoelectric patches has been characterized. Optimal positions have been found, which depends on the mass ratio M * . As in previous studies [START_REF] Doaré | Piezoelectric coupling in energy-harvesting fluttering flexible plates: linear stability analysis and conversion efficiency[END_REF][START_REF] Michelin | Energy harvesting efficiency of piezoelectric flags in axial flows[END_REF], higher efficiencies are obtained at higher mass ratios, but then the sensibility to the geometrical parameters is larger. Finally, a lock-in phenomenon has been evidenced. The latter appears when a resonant circuit is considered and corresponds to a situation where the flapping frequency is dictated by the frequency of the electrical circuit. In the theoretical configuration presented above, this phenomenon is able to significantly increase the efficiency of the harvester. Experiments should now be performed to assess the effectiveness of the efficiency increase after introducing inductive elements to the energy harvesting circuits. acknowledgment This work received financial support from the "Laboratoire d'Excellence" LASIPS ("PIEZOFLAG"project), This work was supported by the "Laboratoire d'Excellence" LASIPS ("PIEZOFLAG"project) and by the French National Research Agency ANR (Grant ANR-2012-JS09-0017). S. M. also acknowledges the support of a Marie Curie International Reintegration Grant within the 7th European Community Framework Programme (PIRG08-GA-2010-276762).

iFigure 1 :

 1 Figure 1: Top: two dimensional flapping of a flexible plate covered by pires of piezoeletric patches. Bottom: flexible plate flapping in uniform axial flow.

Figure 2 :

 2 Figure 2: Schematic view and notations in the three studied cases: one, two or three electrodes.

Figure 3 :

 3 Figure 3: Case of one electrode per side of the flag. Effect of the electrode's position and length on the energy harvesting efficiency, at U * = 13, M * = 0.6 (top) and M * = 10 (bottom). For each pair of geometrical parameters, β is varied to reach the maximum efficiency.

Figure 4 :Figure 5 :

 45 Figure 4: Case of two electrodes per side of the flag. Effect of the position of the cut between the two electrodes on the energy harvesting efficiency, at U * = 13, M * = 0.6 (top) and M * = 10, U * = 8.5 (bottom). For each value of M * , β is varied to reach the maximum efficiency. Solid black line shows the total efficiency of the configuration. Red and green lines show the individual contribution of each electrode.

Figure 6 :

 6 Figure 6: Experimental setup and description of the two tested configurations.

Figure 7 :

 7 Figure 7: Numerical and experimental energy harvesting efficiency η as function of the dimensionless length of the piezoelectric patch l p with δ = 0, U * = 14.6, M * = 0.68, H * = 0.3, α = .073. The shunting resistance is adjusted so get maximum dissipated power.

Figure 8 :Figure 9 :

 89 Figure 8: Numerical and experimental energy harvesting efficiency η as function of the dimensionless length of the piezoelectric patch l p with δ = 1 -l p , U * = 15.7, M * = 0.61, H * = 0.3, α = 0.062. The shunting resistance is adjusted so get maximum dissipated power.

Figure 10 :

 10 Figure 10: Flag's deformation during one flapping cycle, comparison between no lock-in (a) and lock-in (b) cases. For all figures, α = 0.3, M * = 1 and U * = 13.