A Batou
email: anas.batou@univ-paris-est.fr

C S O I Z E A

S Audebert

Model identification in computational stochastic dynamics using experimental modal data

Keywords: Structural dynamics, Model identification, Computational stochastic dynamics, Mode crossing, Experimental modal analysis

This paper deals with the identification of a stochastic computational model using experimental eigenfrequencies and mode shapes. In presence of randomness, it is difficult to construct a one-to-one correspondence between the results provided by the stochastic computational model and the experimental data because of the random modes crossing and veering phenomena that may occurs from one realization to another one. In this paper, this correspondence is constructed by introducing an adapted transformation for the computed modal quantities. Then the transformed computed modal quantities can be compared with the experimental data in order to identify the parameters of the stochastic computational model. The methodology is applied to a booster pump of thermal units for which experimental modal data have been measured on several sites.

Introduction

In industrial context, the quantification of the confidence in computational models must be established so that they can be used either in design purpose or in expertise purpose. A given dynamical system can operate at design conditions, at off-design conditions and at failure-mode conditions that apply in accident scenarios. An adapted way to take into account their generic characteristics and their capability to reproduce the behavior of the whole family of nominally-identical structures is to consider no more deterministic but stochastic computational models (SCM), using experimental data. The objective of this paper consists in identifying a SCM using some natural frequencies and the associated mass-normalized mode shapes, measured for a family of structures.

The identification or updating methods of deterministic computational dynamic models using modal data have been intensively studied during the last four decades. Efficient methods have been proposed (see for instance [START_REF] Ljung | System Identification: Theory for the User[END_REF][START_REF] Walter | Identification of Parametric Models from Experimental Data[END_REF][START_REF] Friswell | Finite Element Model Updating in Structural Dynamics[END_REF]) and are now commonly used in industry. There are two main types of methods: the global methods (see for instance [START_REF] Baruch | Optimisation procedure to correct stiffness and flexibility matrices using vibration data[END_REF][START_REF] Friswell | Direct updating of damping and stiffness matrices[END_REF][START_REF] Schultz | Model updating using constrained eigenstructure assignment[END_REF][START_REF] Zimmerman | Model correlation using multiple static load and vibration tests[END_REF]) which consist in directly modifying the stiffness and mass matrices and the local methods which consists in updating some physical parameters (see for instance [START_REF] Bollinger | Finite element model updating for FEA/EMA modal correlation via constrained optimization theory[END_REF][START_REF] Cogan | An improved frequency response residual for model correction[END_REF]). The latter method can be described in three steps: [START_REF] Amsallem | An online method for interpolating linear parametric reduced-order models[END_REF] The first one consists in constructing a nominal computational model (NCM) for which the parameters are set to nominal values. These parameters can be related to material properties (Young's modulus, mass density, and so on), geometry (CAD, thickness, area moments of inertia, and so on) and boundary conditions. [START_REF] Avalos | Stochastic modeling of structural uncertainty/variability from ground vibration modal test data[END_REF] The second step consists in performing a sensitivity analysis of the quantities of interest with respect to the parameters in order to select the most-sensitive parameters which have to be updated (see for instance [START_REF] Ben-Haim | Selective sensitivity in the frequency domain: Theory[END_REF][START_REF] Cogan | Model order reduction by selective sensitivity[END_REF]). [START_REF] Baruch | Optimisation procedure to correct stiffness and flexibility matrices using vibration data[END_REF] The third step consists in updating the most-sensitive parameters using experimental data. In general, this step is carried out by reducing a "distance" between the experimental modal data (eigenvalue, mode shape, modal mass, modal damping) and the corresponding computed quantities using the NCM.

We consider the random context for which the available experimental data are related to a family of several experimental configurations of a given dynamical structure. The observed variability between the experimental configurations of this family is induced [START_REF] Amsallem | An online method for interpolating linear parametric reduced-order models[END_REF] by the uncontrolled differences that can appear during the manufacturing process (manufacturing tolerances) and during the life cycle of the structure (natural damage, incidents, etc) and (2) by some slight differences which are controlled and are related, for instance, to the boundary conditions, the embedded equipments, etc. These two types of variability induce differences for the data measured on two configurations of the given dynamical structure. It should be noted that the measurement errors can also yield fluctuations in the measured data. This last source of variability induced by the experimental process is not addressed in this paper because it is assumed to be of second-order with respect to the other sources of variability for the application which is presented.

In such a random context, we have to construct a stochastic computational model (SCM) for which two sources of uncertainties have to be taken into account (see for instance [START_REF] Soize | Stochastic modeling of uncertainties in computational structural dynamics -Recent theoretical advances[END_REF]): [START_REF] Amsallem | An online method for interpolating linear parametric reduced-order models[END_REF] the uncertainties relative to some model parameters of the NCM and (2) the modeling errors. The first one includes both the uncertainties induced by the above-mentioned observed variability (also called aleatory uncertainty in the literature) and the uncertainties induced by the lack of knowledge related to some uncertain parameters of the SCM (also called epistemic uncertainty in the literature). With respect to the computational model, this first source of uncertainty yields the model-parameter uncertainties while the uncertainties induced by the modeling errors yield the model uncertainties. The stochastic computational model which is constructed with these two sources of uncertainties (and with additional input and output noises if measurement errors are significant) must have the capability of representing the variability of all the measured configurations (as explained above).

In this paper, the uncertainties are taken into account using a probabilistic approach and then the SCM is constructed including both the modelparameter uncertainties and the model uncertainties in a separate way (using the generalized probabilistic approach of uncertainties proposed in [START_REF] Soize | Generalized probabilistic approach of uncertainties in computational dynamics using random matrices and polynomial chaos decomposition[END_REF][START_REF] Soize | Stochastic modeling of uncertainties in computational structural dynamics -Recent theoretical advances[END_REF]). Usually, a SCM is controlled by a set of hyperparameters such as mean values, coefficients of variation, and so on. These hyperparameters have to be identified using experimental data and realizations of the SCM. Several types of observation can be used in order to perform such an identification and the choice depends on the quantities of interest for the developed SCM (see for instance, [START_REF] Mares | Stochastic model updating, Part 1: Theory and simulated example[END_REF][START_REF] Mottershead | Stochastic model updating, Part 2: Application to a set of physical structures[END_REF][START_REF] Faverjon | An updating method for structural dynamics models with uncertainties[END_REF][START_REF] Goller | Robust model updating with insufficient data[END_REF][START_REF] Goller | Evidence-based identification of weighting factors in Bayesian model updating using modal data[END_REF] for model-parameter uncertainties, and [START_REF] Soize | Robust updating of uncertain computational models using experimental modal analysis[END_REF][START_REF] Soize | Probabilistic model identification of uncertainties in computational models for dynamical systems and experimental validation[END_REF][START_REF] Capiez-Lernout | Robust updating of uncertain damping models in structural dynamics for low-and medium-frequency ranges[END_REF][START_REF] Cheung | Bayesian model updating using hybrid Monte Carlo simulation with application to structural dynamic models with many uncertain parameters[END_REF][START_REF] Batou | Experimental identification of an uncertain computational dynamical model representing a family of structures[END_REF][START_REF] Avalos | Stochastic modeling of structural uncertainty/variability from ground vibration modal test data[END_REF][START_REF] Soize | Bayesian posteriors of uncertainty quantification in computational structural dynamics for low-and medium-frequency ranges[END_REF] for both model-parameter uncertainties and model uncertainties). For example, if the computational model is devoted to the prediction of responses in the low-frequency band of analysis and if the resonances are relatively well-separated, then the modal quantities (eigenfrequencies, mode shapes) are suitable observations. In a random context and for the low-frequency dynamical analysis, the eigenfrequencies can be used if a one-to-one correspondence can be constructed between the computational modes and the experimental modes [START_REF] Soize | Robust updating of uncertain computational models using experimental modal analysis[END_REF][START_REF] Batou | Experimental identification of an uncertain computational dynamical model representing a family of structures[END_REF][START_REF] Avalos | Stochastic modeling of structural uncertainty/variability from ground vibration modal test data[END_REF]. This means that the experimental variability and the randomness in the SCM should not induce mode crossing phenomena or mode veering phenomena (see [START_REF] Perkins | Comments on a curve veering in eigenvalue problems[END_REF][START_REF] Pierre | Mode localization and eigenvalue loci veering phenomena in disordered structures[END_REF][START_REF] -P. Morand | Fluid-Structure Interaction[END_REF]) for the experimental modes and for the computed stochastic modes. This is true if the variability is sufficiently small and if the resonances are well-separated. If this is not the case, information on the mode shapes have to be used in order to construct a one-to-one correspondence between the experimental data and the corresponding computational quantities.

It should be noted that in industrial context, the quantification of the confidence in computational models must be established so that they can be used either in design purpose or in expertise purpose. For example, the system presented in the application can operate at design conditions, at offdesign conditions and at failure-mode conditions that apply in accident scenarios. An adapted way to take into account their generic characteristics and their capability to reproduce the behavior of the whole family of nominallyidentical structures is to consider no more deterministic but stochastic computational models, using experimental data. This is the main motivation for the development of the general approach proposed.

The objective of this paper consists in identifying the hyperparameters of a SCM using natural frequencies and mass-normalized mode shapes measured for a family of structures. The methodology proposed introduces a random transformation of the computational observations (computational eigenfrequencies and computational mode shapes) in order to match them to the experimental observation of each measured structure. This methodology automatically takes into account the mode crossings and the mode veerings which can appear between two experimental configurations or between two computational realizations of the SCM. In Section 2, the construction of the SCM is summarized. Section 3 is devoted to the identification of the hyperparameters of the SCM using a new methodology. Finally, in Section 4, an application devoted to an industrial pump of a thermal unit is presented.

Construction of the stochastic computational model

The construction of an adapted SCM can be carried out using different approaches (a state-of-the-art concerning stochastic modeling of uncertainties can be found, for instance, in [START_REF] Schueller | A state-of-the-art report on computational stochastic mechanics[END_REF][START_REF] Schueller | Uncertain linear systems in dynamics: Retrospective and recent developments by stochastic approaches[END_REF][START_REF] Soize | Stochastic modeling of uncertainties in computational structural dynamics -Recent theoretical advances[END_REF]). The objective of this section is to construct a parameterized SCM based on the use of the generalized probabilistic approach of uncertainties proposed in [START_REF] Soize | Generalized probabilistic approach of uncertainties in computational dynamics using random matrices and polynomial chaos decomposition[END_REF][START_REF] Soize | Stochastic modeling of uncertainties in computational structural dynamics -Recent theoretical advances[END_REF], for which both the model-parameter uncertainties and the model uncertainties are taken into account and are separately identified. First, the NCM is constructed using the Finite Element (FE) method. The probabilistic model of model-parameter uncertainties is constructed by replacing the uncertain model parameters by random variables and the probabilistic model of model uncertainties is constructed by replacing the mass and stiffness matrices by adapted random matrices. The prior probability distributions of the uncertain model parameters and of the random matrices depend on unknown parameters (called the hyperparameters) for which the identification is addressed in Section 3.

Construction of the nominal computational model

The NCM is constructed using the FE method and the boundary conditions of the structure are such that there are no rigid body modes. This computational model exhibits n p uncertain model parameters denoted h 1 ,...,h np . Let be h =(h 1 ,...,h np ) belonging to an admissible set, C h .L e t[ M(h)] and [K(h)] be the mass and stiffness (m × m) real matrices of the NCM. For all h in C h , we are interested in calculating the first n (with n<m) eigenvalues 0 <λ 1 (h) ≤ ... ≤ λ n (h) and the associated mode shapes, φ 1 (h),...,φ n (h). These modal quantities are the solutions of the following generalized eigenvalue problem related to the NCM,

[K(h)] φ(h)=λ(h)[M(h)] φ(h) . (1)
Let [Φ(h)] be the m × n matrix whose columns are the first n mode shapes.

We then introduce the n × n mass and stiffness reduced matrices

, [M(h)] = [Φ(h)] T [M(h)] [Φ(h)] and [K(h)] = [Φ(h)] T [K(h)] [Φ(h)].
For convenience, the mode shapes are normalized with respect to the mass matrix such that

[M(h)] = [I n ] , (2)
in which

[I n ]i st h en × n identity matrix. The diagonal n × n real matrix [K(h)] is then written as [K(h)] = diag(λ 1 (h),...,λ n (h)) . (3)

Construction of the probabilistic model of uncertain model parameters

The probabilistic model of uncertain model parameters is constructed by replacing vector h of the uncertain model parameters by the random vector H with values in R np , defined on a probability space (Θ par , T par , P par ) and for which the probability density function (pdf) p H (h) with respect to dh depends on hyperparameters which can be mean values, coefficients of variation, Lagrange multipliers (in case of a Maximum Entropy construction [START_REF] Shannon | A mathematical theory of communication[END_REF][START_REF] Jaynes | Information theory and statistical mechanics[END_REF][START_REF] Kapur | Entropy Optimization Principles with Applications[END_REF]), and so on. The first n random eigenvalues 0 < Λ par 1 ≤ ... ≤ Λ par n associated with the random mode shapes φ par 1 ,...,φ par n are the solutions of the following random generalized eigenvalue problem,

[K(H)] φ par =Λ par [M(H)] φ par . (4)
Let [Φ par ]bethem×n random matrix whose columns are the first n random mode shapes. We then introduce the n×n random mass and stiffness reduced matrices

[M par ]=[ Φ par ] T [M(H)] [Φ par ]a n d[ K par ]=[ Φ par ] T [K(H)] [Φ par ].
The random mode shapes are normalized (almost surely) with respect to the random mass matrix such that

[M par ]=[I n ] , (5)
and thus, the random diagonal n × n real matrix [K par ] is written as

[K par ]=diag(Λ par 1 ,...,Λ par n ) . (6)
By construction, the random matrices [M par ]an d[ K par ] are positive definite (almost surely) and therefore, their Cholesky decompositions yield,

[M par ]=[L M ] T [L M ] , [K par ]=[L K ] T [L K ] . (7)
From Eqs. ( 5) to [START_REF] Berge | Orthogonal rotations to maximal agreement for two or more matrices of different column orders[END_REF], it can be deduced that

[L M ]=[ I m ]a n d[ L K ]= diag(Ω par 1 ,...,Ω par n )w h e r eΩ par j = Λ par j
is the j th random eigenfrequency (in rad/s). Let α par be the vector whose components are the hyperparameters of the pdf p H (h) which is then rewritten as p H (h; α par ). The vector-valued hyperparameter α par must be identified using experimental modal data.

Construction of the generalized probabilistic model of uncertainties

Let (Θ mod , T mod , P mod ) be another probability space. To take into account model uncertainties (induced by modeling errors), the dependent random matrices [M par ]a n d[ K par ] are replaced by the dependent random matrices [M tot ], [K tot ], defined on a probability space (Θ = Θ par × Θ mod , T = T par ⊗T mod , P = P par ⊗P mod ), such that for all θ =( θ par ,θ mod )i nΘ=

Θ par × Θ mod , [M tot (θ)] = [L M (θ par )] T [G M (θ mod )][L M (θ par )] , [K tot (θ)] = [L K (θ par )] T [G K (θ mod )][L K (θ par )] , (8)
in which the probability distributions of the random matrices [G M ]and[G K ], defined on (Θ mod , T mod , P mod ), are explicitly given in [START_REF] Soize | A nonparametric model of random uncertainties for reduced matrix models in structural dynamics[END_REF] in the context of the nonparametric probabilistic approach of uncertainties. The probability distributions of [G M ]and[G K ] depend on the dispersion parameters δ M and δ K respectively. Let α mod be the vector of the dispersion parameters such that α mod =(δ M ,δ K ). The random matrices [M tot ]a n d[ K tot ] are not diagonal. In order to calculate the random eigenfrequencies and the random mode shapes of the SCM with both the model-parameter uncertainties and the model uncertainties, the following small-dimension random generalized eigenvalue problem is introduced. Let 0 < Λ 1 ≤ ... ≤ Λ n be the first n random eigenvalues associated with the random eigenvectors φ tot 1 ,...,φ tot n which are the solutions of the following random reduced generalized eigenvalue problem

[K tot ] φ tot =Λ[M tot ] φ tot . (9) Let [Φ tot ]=[ φ tot 1 ,...,φ tot n ]
. These random modes are normalized with respect to the random mass matrix [M tot ],

[M]=[Φ tot ] T [M tot ][Φ tot ]=[I n ] , (10)
and we have

[K]=[Φ tot ] T [K tot ][Φ tot ]=diag(Λ 1 ,...,Λ n ) . (11)
Then the first n random eigenvalues of the SCM, with both the modelparameter uncertainties and the model uncertainties, are 0 < Λ 1 ≤ ... ≤ Λ n and the associated random vectors are φ 1 ,...,φ n such that the m×n random matrix [Φ]=[φ 1 ,...,φ n ] is written as

[Φ]=[Φ par ][Φ tot ] . (12)
Finally the SCM is parameterized by the vector-valued hyperparameter α = (α par , α mod ) which has to be identified using experimental modal data. The admissible space for vector α is denoted by C.

Identification of the SCM using experimental modal data

The objective of this section is to identify the parameter α of the SCM using experimental modal data (eigenfrequencies and mass-normalized mode shapes) and realizations of the modal data calculated using the SCM.

Experimental modal data as observations

It is assumed that n exp experimental configurations of the structure (simply called "configurations") have been tested. For each configuration j, n j modes have been experimentally identified using an experimental modal analysis method (see [START_REF] Ewins | Modal Testing: Theory and Practice[END_REF][START_REF] Mcconnel | Vibration Testing. Theory and Practice[END_REF]). For two given configurations, the number of modes, the number and locations of the sensors can be different. For each configuration j, n j experimental eigenfrequencies ω exp,j 1 ,...,ω exp,j n j associated with n j mass-normalized experimental mode shapes ϕ exp,j 1 ,..., ϕ exp,j n j have been identified for m j degrees of freedom (DOFs). Let [ Φ exp,j ]=[ ϕ exp,j 1 ... ϕ exp,j

n j ]b e the m j × n j matrix of the n j experimental mode shapes of the configuration j. It is assumed that n j <n<m j <mfor all j in {1,...,n exp }.T h ee x p e rimental reduced mass matrix and the experimental reduced stiffness matrix are then written as

[ M exp,j ]=[I n j ] , [ K exp,j ]=diag(λ exp,j 1 ,...,λ exp,j n j ) , (13)
in which λ exp,j i =(ω exp,j i ) 2 .

Transformation of the modal data

For all j in {1,...,n exp },let[P j ]bethem j × m matrix that performs the projection from the m DOFs of the SCM to the m j DOFs of the experimental configuration j. Then the projected random modal basis [ Φ j ] of the SCM is defined by

[ Φ j ]=[P j ][Φ]. ( 14
)
The experimental modes [ Φ exp,j ] cannot directly be compared to the computational modes [ Φ j ] because, in general, there is not a one-to-one correspondence between the experimental modes and the computational modes. Indeed, some modes may be missing in the experimental modal basis or in the computational modal basis. Furthermore, due to the experimental variability (variability of the configurations) and the computational randomness (uncertainties), some mode crossing and/or mode veering [START_REF] Perkins | Comments on a curve veering in eigenvalue problems[END_REF][START_REF] Pierre | Mode localization and eigenvalue loci veering phenomena in disordered structures[END_REF][START_REF] -P. Morand | Fluid-Structure Interaction[END_REF] phenomena may occur. The classical mode tracking methods [START_REF] Kim | Mac-based mode tracking in structural topology optimization[END_REF][START_REF] Brüls | The global modal parameterization for non-linear model-order reduction in flexible multibody dynamics[END_REF] based on the MAC criterion [START_REF] Ewins | Modal Testing: Theory and Practice[END_REF] are efficient to detect mode missings and mode crossings but are not able to detect mode veerings (see [START_REF] Amsallem | An online method for interpolating linear parametric reduced-order models[END_REF], [START_REF] -P. Morand | Fluid-Structure Interaction[END_REF]). In Ref. [START_REF] Amsallem | An online method for interpolating linear parametric reduced-order models[END_REF], in the context of the interpolation of reduced-order models (ROM), the authors have introduced a transformation for a given ROM,

{[ Φ], [K], [M]},i nw h i c h[ Φ]
is a reduced-order basis, [K] is a reduced stiffness matrix and [M] is a reduced mass matrix, in order to match it with a reference ROM,

{[ Φ ref ], [K ref ], [M ref ]},
of the same dimension. The transformed ROM is constructed using a congruence transformation and is then written as

{[ Φ] [Q], [Q] T [K][Q], [Q] T [M][Q]},inwhich[Q] is a square orthogo- nal matrix that minimizes the distance [ Φ] [Q]-[ Φ ref ] F
,where . F is the Frobenius norm. Such a transformation is also used in the context of modal expansion methods (see [START_REF] Smith | Simultaneous expansion and orthogonalization of measured modes for structure identification[END_REF][START_REF] Levine-West | Mode shape expansion techniques for prediction -Experimental evaluation[END_REF] for instance). In the present paper, a similar method is introduced in order to construct a one-to-one correspondence between the random ROM calculated using the SCM and the experimental ROM.

For each experimental configuration j, the above reference ROM is chosen as the experimental ROM, {[ Φ exp,j ], [ K exp,j ], [ M exp,j ]}. The ROM to be transformed is the projected computational ROM, {[ Φ j ], [K], [M]} which is not of the same dimension as the experimental ROM. Therefore, the projected computational ROM,

{[ Φ j ], [K], [M]}, is transformed into the following ROM, {[ Φ j ], [ K j ], [ M j ]}, such that [ Φ j ]=[ Φ j ][Q opt,j ] , (15)
[ K j ]=[Q opt,j ] T [K][Q opt,j ] , (16)
[ M j ]=[Q opt,j ] T [M][Q opt,j ] , (17)
in which [Q opt,j ] is a random n×n j real matrix for which each realization [Q]= [Q opt,j (θ)], for θ in Θ, must belong to the Stiefel manifold [START_REF] Edelman | The geometry of algorithms with orthogonality constraints[END_REF], OSt(n, n j ), defined by

OSt(n, n j )={[Q] ∈ R n×n j , [Q] T [Q]=[I n j ]} . ( 18
)
We then have the following properties for the random n j × n j real matrices,

[ K j ]a n d[ M j ], [ K j ] is with values in M + n j (R) , [ M j ]=[I n j ] , (19)
in which M + n j (R) is the set of all the positive-definite n j × n j real matrices. For all θ in Θ, orthogonal matrix [Q opt,j (θ)] is calculated by minimizing the distance between the computational modal basis [ Φ j (θ)] and the experimental modal basis [ Φ exp,j ],

[Q opt,j (θ)] = arg min

[Q]∈OSt(n,n j ) [ Φ j (θ)] [Q] -[ Φ exp,j ] F . (20)
The minimization problem ( 14) is referred as a Procruste problem [START_REF] Berge | Orthogonal rotations to maximal agreement for two or more matrices of different column orders[END_REF][START_REF] Bojanczyk | The procrustes problem for orthogonal Stiefel matrices[END_REF]. Contrary to a classical Procruste problem (for which [Q] is searched in the square orthogonal matrices ensemble [START_REF] Golub | Matrix Computations[END_REF]), this Procruste problem does not have an explicit solution. Nevertheless, a solution can be calculated iteratively (see [START_REF] Berge | Orthogonal rotations to maximal agreement for two or more matrices of different column orders[END_REF]) using the Algorithm 1. The number of iterations n iter1 is determined through a convergence analysis of the error [ Φ

j (θ)] [Q opt,j (θ)] -[ Φ exp,j ] F .
In general, this error does not converge to zero. This convergence analysis can be performed for all the realizations [ Φ j (θ)] or can be performed only one time using the mode shapes of the NCM. In this case, the transformed

nominal ROM {[ Φ(h)], [ K (h)], [ M (h)]} such that [ Φ j (h)] = [ Φ j (h)] [Q opt,j (h)] , (21)
[

K j (h)] = [Q opt,j (h)] T [K(h)][Q opt,j (h)] , (22)
[ M j (h)] = [Q opt,j (h)] T [M(h)][Q opt,j (h)] , (23)
in which [ Φ j (h)] = [P j ][Φ(h)] and [Q opt,j (h)] is calculated by minimizing the distance between the nominal modal basis [ Φ j (h)] and the experimental modal basis [ Φ exp,j ].

Algorithm 1: Algorithm for solving the Procruste problem.

Initialization :

[C]=[ Φ j (θ)] T [ Φ j (θ)] ;
[W ]: matrix of the (n -n j ) eigenvectors of [C];

[A]=[[ Φ exp,j ] , [ Φ j (θ)][W ]] ;
Loop :

for ℓ =1,...,n iter1 do

[P ]=[ Φ j (θ)] T [A]; [U][S][V ] T =[P ]( S V D ); [ Q]=[U][V ] ∈OSt(n, n); [Q 1 ,Q 2 ]=[ Q], with [Q 1 ] ∈OSt(n, n j )and[Q 2 ] ∈OSt(n, n -n j ); [Q opt,j (θ)] = [Q 1 ] [A]=[ Φ exp,j , [ Φ j (θ)][Q 2 ]] ;
If the experimental mode shapes ϕ exp,j 1 ,..., ϕ exp,j nexp are not mass-normalized (because the modal masses have not been identified with a good precision) then the transformation defined by Eqs. [START_REF] Cogan | Model order reduction by selective sensitivity[END_REF] to [START_REF] Friswell | Finite Element Model Updating in Structural Dynamics[END_REF] is not enough to make the random computational mode shapes close enough to the experimental mode shapes. It is then necessary to include an external scaling loop to Algorithm 1 so that the columns of matrices [ Φ exp,j ]and[ Φ

j (θ)] = [ Φ j (θ)][Q opt,j (θ)]
have the same norm. This external loop is summarized in Algorithm 2.

Algorithm 2: Scaling external loop for the Procruste problem.

Initialization :

Scale the columns of [ Φ exp,j ] with respect to the first n j columns of [ Φ j (θ)] ;

Loop :

for ℓ =1,...,n iter2 do Solve [Q opt,j (θ)] = arg min [ Φ j (θ)] [Q] -[ Φ exp,j ] F ; [ Φ j (θ)] = [ Φ j (θ)][Q opt,j (θ)] ;
Scale the columns of [ Φ exp,j ] w.r.t. the columns of [ Φ j (θ)] ;

It should be noted that, in [START_REF] Avalos | Stochastic modeling of structural uncertainty/variability from ground vibration modal test data[END_REF], the authors have proposed an alterna-tive solution to take into account mode crossings and mode veerings in the identification of the hyperparameters of a SCM. Their solution consists in projecting the experimental mode shapes in the modal basis of the NCM and in letting the eigenfrequencies unchanged. A similar procedure has recently been proposed in [START_REF] Brincker | A local correspondence principle for mode shapes in structural dynamics[END_REF].

Computational modal quantities as observations

For j =1 ,...,n exp ,t h ee x p e r i m e n t a lR O M{[ Φ exp,j ], [ K exp,j ], [ M exp,j ]} has to be compared to the projected computational ROM,

{[ Φ j ], [ K j ], [ M j ]}, calculated using the SCM. Since [ M j ]=[ M exp,j ]=[ I n j ],
only the mode shapes and the stiffness matrices have to be compared. Before proceeding to the identification, it is convenient to represent the experimental modal data and the corresponding computational modal quantities in an Euclidean space. Such a representation can be achieved through logarithm maps [START_REF] Amsallem | An online method for interpolating linear parametric reduced-order models[END_REF].

Concerning the modal basis, we define [ Φ obs,j ] such that

[ Φ obs,j ]=[ Φ j ] -[ Φ exp,j ] , (24)
and the corresponding experimental observation [ Φ exp,obs,j ] is defined by

[ Φ exp,obs,,j ]=[0]. ( 25
)
Concerning the stiffness matrix, we define [ K obs,j logm ] such that

[ K obs,j logm ] = logm([ K exp,j ] -1 2 [ K j ][ K exp,j ] -1 2 ) , (26)
in which logm is the logarithm for matrices. The corresponding experimental observation [ K exp,obs,j logm ] is such that

[ K exp,obs,j logm ]=[0], (27)
Let n obs,j =( m j × n j + n j × (n j +1)/2). We then introduce the random observation vector, W j , with values in R n obs,j containing the m j × n j entries of random matrix [ Φ obs,j ]andthen j ×(n j +1)/2 entries of the upper triangular part of random matrix [ K obs,j logm ]. The corresponding experimental observation vector is zero. For the observations, this representation has the advantage to belong to Euclidean space R n obs,j and therefore, the probability distribution of the vector-valued random observation will be easier to estimate since its support is not a complex manifold.

Identification of hyperparameter α

Hyperparameter α of the SCM is identified using the maximum likelihood method and experimental modal data. Then the optimal values α opt is solution of the following optimization problem

α opt =argmax α∈C nexp j=1 log(p W j (0; α)) , (28)
where p W j (w; α) is the probability density function (pdf) of random vector W j . This pdf is estimated using the Monte Carlo simulation method [START_REF] Rubinstein | Simulation and the Monte Carlo Method[END_REF] and a multi-dimensional kernel density estimator (see [START_REF] Wand | Kernel Smoothing[END_REF]). As proposed in [START_REF] Soize | Generalized probabilistic approach of uncertainties in computational dynamics using random matrices and polynomial chaos decomposition[END_REF], a statistical reduction can be performed for random vector W j in order to reduce the statistical dimension of the random observation and then to facilitate the estimation of its pdf. Furthermore, a good predictor of α opt can be obtained by assuming a Gaussian pdf for random vector W j . Since random vector W j is with values in R n obs,j , such an assumption is admissible. For the predictor, the optimization problem defined by Eq. ( 28) is then replaced by the following one

L(α)= nexp j=1 {-n obs,j log(2 π) - 1 2 log(det([C W j (α)])) - 1 2 w j (α) T [C W j (α)] -1 w j (α)} , ( 29
)
in which the mean value w j and the covariance matrix [C W j (α)] of random vector W j are estimated using the Monte Carlo simulation method. In high dimension, the determinant of the covariance matrix can be calculated using the eigenvalues {σ j k (α),k=1,...,n obs,j } of the covariance matrix [C W j (α)]. In this case, the optimization problem defined by Eq. ( 29) can be rewritten as

L(α)= nexp j=1 {-n obs,j log(2 π) - 1 2 n obs k=1 log(σ j k (α)) - 1 2 w j (α) T [C W j (α)] -1 w j (α)} . ( 30
)
In general, the optimization problem defined by Eq. ( 28) (or by Eq. ( 29) is non-convex and has to be solved using evolutionary algorithms and random search algorithm (see [START_REF] Walter | Identification of Parametric Models from Experimental Data[END_REF][START_REF] Eiben | Introduction to Evolutionary Computing[END_REF][START_REF] Spall | Introduction to Stochastic Search and Optimization[END_REF] and, for example, [START_REF] Levin | Dynamic finite element model updating using simulated annealing and genetic algorithms[END_REF] for an application to model updating in structural dynamics).

Application

Industrial mechanical system and experimental modal data

We are interested in the dynamical behavior of a one-stage booster pump used by Electricité de France (EDF) company in its thermal units (see Fig. 1). This pump is made up of a diffuser and a volute, with axial suction and vertical delivery, and is mounted on a metallic frame. It has been designed forty years ago by Sulzer Pumps. An experimental modal analysis has been carried out on two specimens of this pump located at two different thermal units. Therefore, there are n exp = 2 experimental configurations (denoted as Pump 1 and Pump 2) which are measured. There are slight differences between Pump 1 and Pump 2 concerning the joints between the pumps and their metallic frame. The pumps have been disconnected to the adjacent piping before being equipped. The experimental meshes for the two pumps are not the same and are represented in Fig. 2. Pump 1 and Pump 2 have respectively been equipped with 55 and 113 triaxial accelerometers. Therefore m 1 = 165 and m 2 = 339. An experimental modal analysis has been figures, it can be seen that, except for the first mode, it is not easy to make a correspondence between the modes of Pump 1 and the modes of Pump 2. This is due the variability of the configurations (as explained in the introduction). For both Pump 1 and Pump 2, the experimental mode shapes are not normalized with respect to the mass.

Construction of the stochastic computational model 4.2.1. Construction of the nominal computational model

The finite element mesh of the NCM is plotted in Fig. 5. The nominal steel, the Young's modulus y c of the cast iron, the thicknesses t 1 , t 2 and t 3 of the plates 1, 2 and 3 of the metallic frame (see Fig. 6) and the stiffnesses k 1 , k 2 , k 3 and k 4 of the discrete springs normal to the metallic frame (see Fig. 6). The NCM for Pump 1 and the NCM for Pump 2 are the same but the updated NCM for these two pumps are different. The differences between the two updated NCM are relative to the values of some (but not all) parameters that have been chosen as updating parameters. The values of the parameters for the updated NCM related to the two pumps are reported in Table 1. An infinite for a discrete spring means that this discrete spring has been replaced by a direct coupling.

k 1 k 2 k 3 k 4 Plate 1 Plate 2 Plate 3
The uncertain model parameters are the eight parameters which have been updated. Let h =( y s ,y c ,t 1 ,t 2 ,t 3 ,k 1 ,k 2 ,k 3 ,k 4 ) be the vector of these uncertain model parameters. between the projected computed mode shapes of the updated NCM and the experimental mode shapes is plotted in Fig. 9. For h = h 2 , the first 6 eigen- MAC matrix between the projected computation mode shapes of the updated NCM and the experimental mode shapes is plotted in Fig. 11. It can be seen for Pump 1 and Pump 2 that the MAC indices are low. Therefore, there is no clear correspondence between the experimental modes and the modes calculated with the updated NCM. The transformed modal bases [ Φ 1 (h 1 )] and [ Φ 2 (h 2 )] are calculated using Eq. [START_REF] Friswell | Direct updating of damping and stiffness matrices[END_REF]. The MAC matrix between the experimental modal basis [ Φ exp,1 ] and the transformed computational modal basis [ Φ 1 (h 1 )] is plotted in Fig. 12 and the MAC matrix between the experimental modal basis [ Φ exp,2 ] and the transformed computational modal basis [ Φ 2 (h 2 )] is plotted in Fig. 13. In Figs. 12 and 13, it can be seen that the new MAC matrix between the transformed modal bases of the updated NCM and the experimental modal bases are good.

Construction of the stochastic computational model

The vector h is modeled by a random vector H =(Y s ,Y c ,T 1 ,T 2 ,T 3 ,K 1 ,K 2 , K 3 ,K 4 ). The Maximum Entropy principle has been used for constructing the probability distribution of H. Taking into account the available information, it can be deduced that (1) all the components of H are independent random mental variability and due to modeling errors introduced in the NCM. These dispersions could be partly decreased by constructing a more accurate NCM.

Mean value

m T 3 =0.01 m δ T 3 =0.09 Stiffness K 1 m K 1 =8.01 × 10 8 N/m δ K 1 =0.19 Stiffness K 2 m K 2 =5.74 × 10 9 N/m δ K 2 =0.13 Stiffness K 3 m K 3 =6.30 × 10 7 N/m δ K 3 =0.34 Stiffness K 4 m K 4 =2.68 × 10 8 N/m δ K 4 =0.42

Validation of the results

For α = α opt , the marginal pdf of the first six eigenvalues of the matrices [ K 1 ]a n d[ K 2 ] are shown in Figs. 14 and15 respectively. It can be seen in these figures that the first 5 experimental eigenvalues for Pump 1 and Pump 2 are predicted by the SCM with a high probability level (very high for Pump 1). The 6 th experimental eigenvalue for Pump 1 and Pump 2 are also within the interval of prediction of the SCM but with a lower probability level.

For Pump 1, the mean value of the MAC matrix between the random modal basis [ Φ 1 ] (before transformation) of the SCM and the experimental modal basis [ Φ exp,1 ] is plotted in Fig. 16, while for Pump 2, the mean value of MAC matrix is plotted in Fig. 17 ] is plotted in Fig. 18 while for Pump 2, the mean value of MAC matrix is plotted in Fig. 19. In Figs. 18 and19, it can be seen that the random transformation of the random mode shapes of the SCM allows to achieve a good correspondence between the random computational modes of the SCM and the experimental modes.

Conclusion

A new methodology has been presented for the identification of a stochastic computational model using experimental eigenfrequencies and mode shapes with experimental variabilities. The model-parameter uncertainties and the modeling errors are taken into account in the framework of a generalized probabilistic approach of uncertainties. A transformation of the computational modal quantities is introduced in order to construct a correspondence between the experimental modal data and the computational modal quantities. This method allows us to take into account mode crossings and mode veerings that may occur. The methodology has been applied to the construction a stochastic computational model representing a family of booster pumps of thermal units. The first 5 experimental eigenvalues for Pump 1 and Pump 2 are predicted by the SCM with a high probability level. The dispersion of the probability distributions for model uncertainties that have been identified are relatively high due to the experimental variability and due to modeling errors introduced in the NCM. These dispersions could be partly decreased by constructing a more accurate NCM with a better representation of the bolted joints and the boundary conditions. The experimental variabilities induced by the measurements errors have not The introduction of a proper stochastic model of measurement errors which could be done by introducing additive random noises could also partly decrease the values of the dispersions of model uncertainties which have been identified, but in counter part, a stochastic model of such additive random noises must be constructed and must experimentally be identified.

Figure 1 :

 1 Figure 1: Industrial mechanical system.

Figure 2 :

 2 Figure 2: Experimental meshes: Pump 1 (left) and pump 2 (right).

  carried for each pump. For Pump 1, n 1 = 6 modes have been identified with eigenfrequencies 76.8 Hz, 134.4 Hz, 162.0 Hz, 211.9 Hz, 233.4H za n d 251.2H z . F o rP u m p2 ,n 2 = 11 modes have been identified with eigenfrequencies 69.9Hz,84.6 Hz, 151.8 Hz, 160.6 Hz, 166.3 Hz, 167.8 Hz, 202.5Hz, 224.6 Hz, 244.3 Hz, 252.1 Hz and 288.3 Hz. The first six mode shapes for Pump 1 and Pump 2 are plotted in Figs. 3 and 4 respectively. In these

Figure 3 :

 3 Figure 3: Pump 1: First six experimental mode shapes (Thick black line).

Figure 4 :

 4 Figure 4: Pump 2: First six experimental mode shapes (Thick black line).

Figure 5 :

 5 Figure 5: Finite element mesh of the NCM.

Figure 6 :

 6 Figure 6: Metallic frame (bottom view).

× 10 9

 9 For the updated NCM of Pump 1 and Pump 2, the updated values of h are denoted by h 1 and h 2 . For each updated NCM, n = 20 modes are calculated . For h = h 1 , the first 6 eigenfrequencies are 76.4H z ,8 1 .2 Hz, 143.1 Hz, 163.5 Hz, 185.5 Hz, 200.1H za n dt h efi r s tt w o mode shapes φ 1 (h 1 )a n dφ 2 (h 1 ) are plotted in Fig. 7. For Pump 1, the first 6 projected mode shapes are plotted in Fig. 8. For Pump 1, the MAC matrix Pump 1 Pump 2 Young's modulus steel y s (Pa) 1.43 × 10 11 1.40 × 10 11 Young's modulus cast iron y c (Pa) 8.2 × 10 10 8.0 × 10 10 Thickness t 1 (m) Stiffness k 2 (N/m) ∞ 1.0 × 10 10 Stiffness k 3 (N/m) 1.0 × 10 8 ∞ Stiffness k 4 (N/m) 3.0 × 10 8 1.0 × 10 8

Figure 7 :

 7 Figure 7: Mode shapes φ 1 (h 1 )a n dφ 2 (h 1 ) for Pump 1.

Figure 8 :

 8 Figure 8: First 6 projected mode shapes for Pump 1.

Figure 10 :

 10 Figure 10: First 6 projected mode shapes for Pump 2.

Figure 11 :Figure 12 :

 1112 Figure 11: MAC matrix for the updated NCM of Pump 2.

  . The comparison of Figs. 16 and 17 with Figs. 9 and 11 shows that the randomness of the SCM introduces random mode crossings and random mode veerings which modify the correspondence. For Pump 1, the mean value of the MAC matrix between the random modal basis [ Φ 1 ] (after transformation) of the SCM and the experimental modal basis [ Φ exp,1

Figure 14 :

 14 Figure 14: Probability density function for the first six eigenvalues of [ K 1 ]. Vertical lines: corresponding experimental values (eigenvalues of [ K exp,1 ]).

Figure 15 :Figure 16 :

 1516 Figure 15: Probability density function for the first six eigenvalues of [ K 2 ]. Vertical lines: corresponding experimental values (eigenvalues of [ K exp,2 ]).

Figure 17 :Figure 18 :Figure 19 :

 171819 Figure 17: For Pump 2, mean value of the MAC matrix between the random mode shapes of the SCM and the experimental mode shapes before transformation.

Table 1 :

 1 Values of the parameters for updated NCM of Pump 1 and Pump 2.

  Figure 9: MAC matrix for the updated NCM of Pump 1. frequencies are 78.6Hz,82.4 Hz, 140.7 Hz, 157.4 Hz, 181.6 Hz, 192.9Hzand the first 6 projected mode shapes are plotted in Fig. 10. For Pump 2, the

	Experiments	3 4 5 6 1 2	0.2 0.4 0.6 0.8
		1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
		NCM

  Coefficient of variation Young's modulus steel Y s m Ys =1.33 × 10 11 Pa δ Ys =0.2 Young's modulus cast iron Y c m Yc =7.57 × 10 10 Pa δ

			Yc =0.17
	Thickness T 1	m T 1 =0.013 m	δ T 1 =0.12
	Thickness T 2	m T 2 =0.011 m	δ T 2 =0.57
	Thickness T 3

Table 2 :

 2 Components of α opt par .

Acknowledgements

This research work has been carried out in the context of the FUI 2012-2015 SICODYN Project (pour des SImulations crédibles via la COrrélation calculs-essais et l'estimation des incertitudes en DYNamique des structures). The support of the FUI (Fonds Unique Interministériel) is gratefully acknowledged.

has 18 components to be identified and α =(α par , α mod ) has 20 components to be identified.

Identification of the optimal hyperparameter α opt .

The vector α opt is given by the optimization problem defined by Eq. ( 28) which is solved using a genetic algorithm. For each value of α, the probability density functions p W 1 (w; α)a n dp W 2 (w; α) are estimated using 800 realizations of the observation vectors W 1 and W 2 calculated with the SCM. The components of α opt par are given in Table 2. The two components of α opt mod are δ opt M =0.52 and δ opt K =0.43. These optimal dispersions of the probability distributions for model uncertainties are relatively high due to the experi-


A J Goodall

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

P Ossona De Mendez

Strongly Polynomial Sequences as Interpretations

Keywords: graph homomorphism, graph polynomial, relational structure, interpretation scheme Subject classification (MSC 2010) Primary: 05C31, 05C60 Secondary: 03C13, 03C98

A strongly polynomial sequence of graphs (Gn) is a sequence (Gn) n∈N of finite graphs such that, for every graph F , the number of homomorphisms from F to Gn is a fixed polynomial function of n (depending on F ). For example, (Kn) is strongly polynomial since the number of homomorphisms from F to Kn is the chromatic polynomial of F evaluated at n. In earlier work of de la Harpe and Jaeger, and more recently of Averbouch, Garijo, Godlin, Goodall, Makowsky, Nešetřil, Tittmann, Zilber and others, various examples of strongly polynomial sequences and constructions for families of such sequences have been found.

We give a new model-theoretic method of constructing strongly polynomial sequences of graphs that uses interpretation schemes of graphs in more general relational structures. This surprisingly easy yet general method encompasses all previous constructions and produces many more. We conjecture that, under mild assumptions, all strongly polynomial sequences of graphs can be produced by the general method of quantifier-free interpretation of graphs in certain basic relational structures (essentially disjoint unions of transitive tournaments with added unary relations). We verify this conjecture for strongly polynomial sequences of graphs with uniformly bounded degree.

Introduction

The chromatic polynomial P (G, x) of a graph G, introduced by Birkhoff over a century ago, is such that for a positive integer n the value P (G, n) is equal to the number of proper n-colorings of the graph G. Equivalently, P (G, n) is the number hom(G, K n ) of homomorphisms from G to the complete graph K n . It can thus be considered that the sequence (K n ) n∈N defines the chromatic polynomial by means of homomorphism counting.

A strongly polynomial sequence of graphs is a sequence (G n ) n∈N of finite graphs such that, for every graph F , the number of homomorphisms from F to G n is a polynomial function of n (the polynomial depending on F and the sequence (G n ), but not on n). A sequence (G n ) n∈N of finite graphs is polynomial if this condition holds for sufficiently large n ≥ n F . The sequence of complete graphs (K n ) provides a classical example of a strongly polynomial sequence. A homomorphism from a graph F to a graph G is often called a G-colouring of F , the vertices of G being the "colours" assigned to vertices of F and the edges of G specifying the allowed colour combinations on the endpoints of an edge of F .

The notion of (strongly) polynomial sequences of graphs was introduced by de la Harpe and Jaeger [START_REF] De La Harpe | Chromatic invariants for finite graphs: theme and polynomial variations[END_REF] (as a generalization of the chromatic polynomial), in a paper which includes a characterization of polynomial sequences of graphs via (induced) subgraph counting and the construction of polynomial sequences by graph composition. The notion of a (strongly) polynomial sequence extends naturally to relational structures, thus allowing the use of standard yet powerful tools from model theory, like interpretations.

The "generalized colourings" introduced in [START_REF] Makowsky | Polynomial invariants of graphs and totally categorical theories[END_REF] include only colourings invariant under all permutations of colours, which holds for K n -colourings (that is, proper n-colourings), but not in general for G n -colourings for other sequences of graphs (G n ). However, generalized colourings in the sense defined in [START_REF] Makowsky | Polynomial invariants of graphs and totally categorical theories[END_REF] do include harmonious colourings (proper colourings with the further restriction that a given pair of colours appears only once on an edge) and others not expressible as the number of homomorphisms to terms of a graph sequence. Makowsky [START_REF] Makowsky | From a zoo to a zoology: towards a general theory of graph polynomials[END_REF] moves towards a classification of polynomial graph invariants, but one that does not include the class of invariants we define in this paper.

Garijo, Goodall and Nešetřil [START_REF] Garijo | Polynomial graph invariants from graph homomorphisms[END_REF] focus on constructing strongly polynomial sequences. They give a construction involving coloured rooted trees that produces a large class of strongly polynomial sequences, that in particular incorporates the Tittmann-Averbouch-Makowsky polynomial [START_REF] Tittmann | The enumeration of vertexinduced subgraphs with respect to the number of components[END_REF] (not obtainable by graph composition and other previously known operations for building new polynomial sequences from old).

We extend the scope of the term "strongly polynomial" to sequences of general relational structures. The property of a sequence of relational structures being strongly polynomial is preserved under a rich variety of transformations afforded by the model-theoretic notion of an interpretation scheme. We start with "trivially" strongly polynomial sequences of relational structures, made from basic building blocks, and then by interpretation project these sequences onto graph sequences that are also strongly polynomial. The interpretation schemes that can be used here are wide-ranging (they need only be quantifierfree in their specification), and therein lies the power of the method. All constructions of strongly polynomial sequences that have been devised in [START_REF] De La Harpe | Chromatic invariants for finite graphs: theme and polynomial variations[END_REF] and [START_REF] Garijo | Polynomial graph invariants from graph homomorphisms[END_REF] are particular cases of such interpretation schemes for graph structures. Indeed, we conclude the paper with the conjecture that (under mild assumptions) all strongly polynomial sequences of graphs might be produced by the schema we describe here. This is verified for the case of sequences of graphs with uniformly bounded degree.

Preliminaries 2.1 Relational structures

A relational structure A with signature λ is defined by its domain A, a set whose elements we shall call vertices, and relations with names and arities as defined in λ. A relational structure will be denoted by an uppercase letter in boldface and its underlying domain by the corresponding lightface letter; for brevity we refer to a relational structure A with signature λ as a λ-structure, and may just give the type (list of arities given by λ) when the symbols used for the corresponding relations are not of importance. A 1-ary relation defines a subset of the domain and will be called a label, or a mark (a special type of labelling defined at the end of this section). A 2-ary relation defines edges of a digraph on vertex set the domain, and a graph when the relation is symmetric. When the signature λ contains only arities 1 and 2 we have a digraph together with labels on edges and vertices: relations of arity 1 are labels on vertices (where in general a vertex may receive more than one label) and relations of arity 2 are labelled edges (two vertices may be joined by edges of different labels). A Cayley graph on a group Γ with finite generating set S ⊂ Γ is an example of a labelled digraph, a directed edge joining x to y bearing label s ∈ S such that y = xs.

The symbols of the relations and constants defined in λ define the non-logical symbols of the first-order language FO(λ) associated with λ-structures. We take first-order logic with equality as a primitive logical symbol and which is always interpreted as standard equality, so the equality relation does not appear in the signature λ. In what follows λ will be finite, in which case FO(λ) is countable. The variable symbols will be taken from the set {x i : i ∈ N} or {y i : i ∈ N}, or, when double indexing is convenient, from {x i,j : i, j ∈ N}. The subset of FO(λ) consisting of formulas with exactly p free variables is denoted by FO p (λ). The fragment of FO(λ) consisting of quantifier-free formulas is denoted by QF(λ), and QF p (λ) denotes those quantifier-free formulas with exactly p free variables.

For a formula φ ∈ FO p (λ) and a λ-structure A we define the satisfaction set

φ(A) = {(v 1 , . . . , v p ) ∈ A p : A |= φ(v 1 , . . . , v p )},
where φ(v 1 , . . . , v p ) is the formula obtained upon substituting v i for each free variable x i of φ, i = 1, . . . , p. A homomorphism from a λ-structure A to a λstructure B is a mapping f : A → B that preserves relations, that is, which has the property that for each relation R in λ of any given arity r it is the case that

R(f (v 1 ), . . . , f (v r )) in B whenever R(v 1 , . . . , v r ) in A.
When A is a graph and R the relation representing adjacency of vertices this is a graph homomorphism as usually defined.

The number of homomorphisms from A to B is denoted by hom(A, B). A κ-structure A and a λ-structure B are weakly isomorphic, denoted by A ≈ B, if there exists a bijection t between the symbols in κ and the symbols in λ and a bijection f : A → B such that, for every R ∈ κ, the relations R and t(R) have the same arity (here denoted by r) and for every v 1 , . . . , v r ∈ A we have

A |= R(v 1 , . . . , v r ) ⇐⇒ B |= t(R)(f (v 1 ), . . . , f (v r )
). In other words, A ≈ B if A and B are the same structure, up to renaming of the relations and relabelling of the vertices.

For signatures κ and λ, we denote by κ ⊔ λ the signature obtained from the disjoint union of κ and λ, The strong sum A ⊕ B of a κ-structure A and a λ-structure B is the κ ⊕ λ-structure whose domain is the disjoint union A ⊔ B of the domains of A and B, where for every R ∈ κ and S ∈ λ (with respective arities r and s) and for every v 1 , . . . , v max(r,s) in A ⊔ B it holds that

A ⊕ B |= R(v 1 , . . . , v r ) ⇐⇒ (v 1 , . . . , v r ) ∈ A r and A |= R(v 1 , . . . , v r ), A ⊕ B |= S(v 1 , . . . , v s ) ⇐⇒ (v 1 , . . . , v s ) ∈ B s and S |= S(v 1 , . . . , v s ).
Note that the strong sum is not commutative, but we do have

A ⊕ B ≈ B ⊕ A. A class C of λ-structures is marked by a relation U ∈ λ if U is unary, and for every A ∈ C we have A |= (∀x) U (x).

Sequences of relational structures

We begin with a definition of the notion that is the subject of this paper.

Definition 2.1. A sequence (A n ) n∈N of λ-structures is strongly polynomial if for every quantifier-free formula φ there is a polynomial P φ such that |φ(A n )| = P φ (n) holds for every n ∈ N.

Remark 2.2. A sequence is polynomial if for every quantifier-free formula φ there is a polynomial P φ and an integer n φ such that |φ(A n )| = P φ (n) holds for every integer n ≥ n φ . We shall only consider strongly polynomial sequences in this paper, but occasionally it will help to clarify what is involved in the property of being a strongly polynomial sequence by giving examples of sequences that are polynomial but not strongly polynomial. We begin by formulating equivalent criteria for a sequence of structures to be strongly polynomial in terms of homomorphisms or induced substructures (Theorem 2.5 below). For graph structures this will make a direct connection to the notion as originally defined by de la Harpe and Jaeger [START_REF] De La Harpe | Chromatic invariants for finite graphs: theme and polynomial variations[END_REF].

For this we require the following lemma:

Lemma 2.3. Let λ be a signature for relational structures. For every formula φ in QF(λ), there exist λ-structures F 1 , . . . , F ℓ and integers c 1 , . . . , c ℓ such that for every λ-structure A we have

|φ(A)| = i c i hom(F i , A).
Proof. Let φ ∈ QF(λ) be quantifier-free with free variables x 1 , . . . , x p . We first put φ in disjunctive normal form, with basic terms (x i = x j ) (for 1 ≤ i < j ≤ p) and R(x i1 , . . . , x ir ) for relation R in λ with arity r and i 1 , . . . , i r in {1, . . . , p}. Thus φ is logically equivalent to

P ζ P ∧ φ P , (1)
where the disjunction runs over partitions P of {1, . . . , p}, where ζ P is the conjunction of all equalities and non-equalities that have to hold between free variables x 1 , . . . , x p in order that P induces the partition of free variables into their k (1 ≤ k ≤ p) equality classes, and where φ P is a formula with k free variables defining the λ-structure F P induced by x i1 , . . . , x i k for arbitrary choice of representatives i 1 , . . . , i k of the parts of P. As all the terms in (1) are mutually exclusive, we have

|φ(A)| = P ind(F P , A),
where ind(F, A) denotes the number of injective mappings f : F → A defining an isomorphism between F and its image. We wish to rewrite this sum in terms of induced substructures as one in terms of homomorphism numbers, and we achieve this in two steps. First we move from counting induced substructures to counting injective homomorphisms,

inj(F, A) = F ′ :F ′ =F ∀R∈λ R(F ′ )⊇R(F) ind(F ′ , A),
in which inj(F, A) denotes the number of injective homomorphisms from F into A and R(F) = {(v 1 , . . . , v r ) ∈ F r : R(v 1 , . . . , v r )} is the set of tuples satisfying the r-ary relation R in F, and similarly R(F ′ ) denotes those tuples satisfying the relation R in F ′ . From this identity, by inclusion-exclusion we obtain ind(F, A) =

F ′ :F ′ =F ∀R∈λ R(F ′ )⊆R(F) R∈λ (-1) |R(F)|-|R(F ′ )| inj(F ′ , A).
The second step is to move from counting injective homomorphisms to counting all homomorphisms, the relationship between which is given by hom

(F, A) = Θ inj(F/Θ, A),
where the sum is over partitions Θ of the domain F of F and F/Θ is the structure obtained from F by identifying elements of its domain F that lie in the same block of Θ. We then obtain

inj(F, A) = Θ µ(Θ)hom(F/Θ, A), where µ(Θ) = I∈Θ (-1) |I|-1 (|I|-1)!
is the Möbius function of the lattice of partitions of F . The statement of the lemma now follows.

Remark 2.4. In the context of graphs (structures with signature comprising a symmetric binary relation) the identities used in the proof of Lemma 2.3 between counts of induced subgraphs, homomorphisms and injective homomorphisms find widespread application (see for example [START_REF] Borgs | Counting graph homomorphisms[END_REF]).

We now come to the promised reformulation of the notion of a strongly polynomial sequence of structures.

Theorem 2.5. The following are equivalent for a sequence (A n ) n∈N of λstructures:

(i) The sequence (A n ) n∈N is strongly polynomial;

(ii) For each quantifier-free formula φ there is a polynomial

P φ such that |φ(A n )| = P φ (n) for each n ∈ N;
(iii) For each λ-structure F there is a polynomial

P F such that hom(F, A n ) = P F (n) for each n ∈ N;
(iv) For each λ-structure G there is a polynomial

P G such that ind(G, A n ) = P G (n) for each n ∈ N.
Proof. Items (i) and (ii) are equivalent by definition. As homomorphisms and finite induced substructures can be expressed in QF, items (iii) and (iv) are both special cases of (ii). Finally, Lemma 2.3 shows that (iii) implies (ii), and the proof of the same lemma that (iv) also implies (ii).

Remark 2.6. In Theorem 2.5, the equivalence also holds with weaker conditions in which the existence of a polynomial function is replaced by the existence of a rational function. Indeed, assume f (x) = P (x)/Q(x) is a rational function, where P and Q are polynomials. Then there exist polynomials R(x), S(x) such that f (x) = S(x) + R(x)/Q(x) and deg R < deg Q. For sufficiently large n, it follows that -1 < R(x)/Q(x) < 1. As f (x) takes only integral values on integers, it follows that R(n)/Q(n) = 0 for sufficiently large n. Hence R = 0 and f is a polynomial function.

Remark 2.7. Assume κ is a signature that is a subset of another signature λ. Then every κ-structure can be considered as a λ-structure. The notion of strongly polynomial sequence is robust in the sense that a sequence (A n ) n∈N of κ-structures is strongly polynomial if and only if (A n ) n∈N (considered as a sequence of λ-structures) is strongly polynomial: indeed, for every λ-structure F, either F contains a relation not in κ and thus hom(F, A n ) = 0 for every n ∈ N, or F can be considered as a κ-structure, and the number of homomorphisms from F to A n does not depend on the signature considered.

We end this section with a few statements on the invariance of strongly polynomial sequences with respect to various operations.

Lemma 2.8. Let (A i,n ) n∈N be strongly polynomial sequences of λ i -structures, for 1 ≤ i ≤ k. Then the sequence ( k i=1 A i,n ) n∈N is strongly polynomial. Proof. By Lemma 2.3 it is sufficient to check polynomiality of hom(F, k i=1 A i,n ).
Let F 1 , . . . , F ℓ be the connected components of F. Then the proof follows from the identity hom(F,

k i=1 A i,n ) = ℓ j=1 hom(F j , k i=1 A i,n ) = ℓ j=1 k i=1 hom(F j , A i,n ).
(Note that in the last equality we consider each A i,n as a k i=1 λ i -structure, which it is safe to do according to Remark 2.7.) Lemma 2.9. Let (A n ) n∈N be a strongly polynomial sequence of λ-structures and let P be a polynomial such that P (n) ∈ N for n ∈ N. Then the sequence (P (n) A n ) n∈N is strongly polynomial, where P (n) A n denotes the λ-structure obtained as the disjoint union of P (n) copies of A n .

Proof. By Lemma 2.3 it is sufficient to check polynomiality of hom(F, P (n)A n ). Let F 1 , . . . , F ℓ be the connected components of F. Then the proof follows from the identity

hom(F, P (n) A n ) = ℓ j=1 hom(F j , P (n) A n ) = ℓ j=1 (P (n) hom(F j , A n )).
Lemma 2.10. Let (A n ) n∈N be a strongly polynomial sequence of λ-structures and let P be a polynomial such that P (n) ∈ N for n ∈ N. Then the sequence

(A P (n) ) n∈N is strongly polynomial. Proof. For every φ ∈ QF(λ) there is a polynomial Q such that |φ(A n )| = Q(n) for each n ≥ 1, as (A n ) n∈N is a strongly polynomial sequence. Thus |φ(A P (n) )| = Q • P (n).
It follows that the sequence (A P (n) ) n∈N is strongly polynomial.

Basic structures

Two special types of marked structures will be of particular interest in this paper:

• E is a structure whose domain is a singleton, and whose signature is a single unary relation U that satisfies (∀x) U (x);

• T n is a transitive tournament of order n. Precisely, the domain of T n is

[n] = {1, . . . , n} and its signature contains a single binary relation S with T n |= S(i, j) ⇐⇒ i < j, and a single unary relation U , which satisfies (∀x) U (x).

Definition 3.1. A basic structure with parameters (k, ℓ) is a structure

B = ℓ times E ⊕ • • • ⊕ E ⊕ k times T N1 ⊕ • • • ⊕ T N k .
which is the strong sum of ℓ marked vertices and k marked transitive tournaments of respective orders N 1 (B), . . . , N k (B). We denote by B k,ℓ the class of all basic structures with parameters (k, ℓ) and by β k,ℓ the signature of these structures. It will be notationally convenient to assume that the relations in

β k,ℓ are U E 1 , . . . , U E ℓ , U T 1 , . . . , U T k , S 1 , . . . , S k . A basic sequence is a sequence (B n ) n∈N of basic structures B n ∈ B k,ℓ (for some fixed k, ℓ ∈ N) such that there are non-constant polynomials Q i , 1 ≤ i ≤ k with Q i (n) = N i (A n ) (for every 1 ≤ i ≤ k and n ∈ N).
It follows directly from Lemmas 2.10 and 2.8 that every basic sequence is strongly polynomial.

Strongly polynomial sequences by interpretations

The basic building blocks we use for constructing strongly polynomial graph sequences are marked tournaments (T P (n) ) on a polynomial number of vertices, and the constant sequence (E) consisting of a single marked vertex. From these we can produce all the strongly polynomial sequences given in [START_REF] De La Harpe | Chromatic invariants for finite graphs: theme and polynomial variations[END_REF] and [START_REF] Garijo | Polynomial graph invariants from graph homomorphisms[END_REF] and much more. (In Section 5.1 we give a large selection of examples of strongly polynomial graph sequences that exhibits their diversity.) To do this we need just two operations: strong sum and graphical interpretation of structures. The latter is a potent operation for it produces graph sequences from strongly polynomial sequences of λ-structures of arbitrary signature λ, while strong sum is an essential operation for gluing together separately constructed sequences, from which a sequence of larger structures can be made. (Note that one could equivalently consider disjoint union and QF-interpretation in place of strong sum and QF-interpretation.)

Interpretation schemes

We begin with the definition of an interpretation scheme that we shall require.

Definition 4.1. Let κ, λ be signatures, where the signature λ has q relational symbols R 1 , . . . , R q with respective arities r 1 , . . . , r q . An interpretation scheme I of λ-structures in κ-structures with exponent p is a tuple I = (p, ρ 0 , . . . , ρ q ), where p is a positive integer, ρ 0 ∈ FO p (κ), and

ρ i ∈ FO pri (κ), for 1 ≤ i ≤ q.
For κ-structure A, we denote by I(A) the λ-structure B with domain B = ρ 0 (A) and relations defined by

B |= R i (v 1 , . . . , v ri ) ⇐⇒ A |= ρ i (v 1 , . . . , v ri ) (for 1 ≤ i ≤ q and v 1 , . . . , v ri ∈ B).
Definition 4.2. A QF-interpretation scheme is an interpretation scheme in which all the formulas ρ i , 0 ≤ i ≤ q, used to define it in Definition 4.1 are quantifier-free. • Lift, the canonical injection of κ-structures into a λ-structures (same relations);

• Forget, the canonical projection of λ-structures onto κ-structures (filters out relations not in κ);

• Merge, which maps λ ⊔ λ-structures into λ-structures by merging similar relations (so that Merge(A ⊕ B) = A + B);

• Mark, which maps λ-structures into λ + -structures (where λ + is the signature obtained by adding to λ a new unary relation U ) by putting every element in the relation U .

Since our goal is to construct strongly polynomial sequences of graphs, we shall have a particular use for interpretation schemes of graph structures in κ-structures. Definition 4.4. A graphical interpretation scheme I of κ-structures is a triple (p, ι, ρ), where p is a positive integer, ι ∈ FO p (κ), and ρ ∈ FO 2p (κ) is symmetric (that is, such that ⊢ φ(x, y) ↔ φ(y, x)). For every κ-structure A, the interpretation I(A) has vertex set V = ι(A) and edge set

E = {{u, v} ∈ V × V : A |= ρ(u, v)}.
We have already mentioned a graphical interpretation scheme of digraph structures: that which interprets an orientation of a graph as the underlying undirected graph simply by forgetting the edge directions (for example K n from T n ). Taking the complement of a graph G is a graphical interpretation scheme (of graph structures) with p = 1 in which we take ι = 1 (constantly true), and ρ(x, y) = ¬R(x, y), where R(x, y) represents adjacency between x and y. The square of the graph G, joining vertices x and y when they are adjacent or share a common neighbour, is a graphical interpretation scheme (of graph structures) with p = 1, ι = 1, and ρ(x, y) = R(x, y) ∨ (∃z R(x, z) ∧ R(z, y)) (this one requires a quantifier). The line graph of a simple undirected graph G can be realized indirectly: orient the edges G and use a graphical interpretation scheme of digraph structures with p = 2, by taking ι(x, y) = R(x, y), where R is the antisymmetric relation representing oriented edges of G, and ρ(x

1 , y 1 , x 2 , y 2 ) = [(x 1 = y 2 )∨(y 1 = y 2 )∨(x 1 = y 2 )∨(x 2 = y 1 )]∧¬[(x 1 = x 2 )∧(y 1 = y 2 )]∧¬[(x 1 = y 2 )∧(x 2 = y 1 )].
A more natural way to define a graphical interpretation scheme (of graph structures) for the operation of taking the line graph requires the general interpretation schemes discussed in Section 8. Compare also Remark 5.2 in Section 5.1.2.

The following standard result from model theory (see for example [8, Section 3.4]) underlies the key role interpretation will play in moving from one strongly polynomial sequence of structures to another.

Let I = (p, ρ 0 , . . . , ρ q ) be an interpretation scheme of λ-structures in κstructures. We inductively define the mapping M I from terms in FO(λ) to terms in FO(κ) by:

• M I (x i ) = (x i,1 , . . . , x i,p ) for variable x i ; • M I (R i (t 1 , . . . , t ri )) = ρ i (M I (t 1 ), . . . , M I (t ri )); • M I (φ ∨ ψ) = M I (φ) ∨ M I (ψ); • M I (φ ∧ ψ) = M I (φ) ∧ M I (ψ); • M I (¬φ) = ¬M I (φ); • M I ((∃x) φ) = (∃x 1 . . . ∃x p ) p i=1 ρ 0 (x i ) ∧ M I (φ); • M I ((∀x) φ) = (∀x 1 . . . ∀x p ) p i=1 ρ 0 (x i ) → M I (φ).
Then we define the mapping Ĩ : FO(λ) → FO(κ) by

Ĩ(φ) = k i=1 ρ 0 (x i ) ∧ M I (φ),
where x 1 , . . . , x k are the free variables of φ.

Note that if all the ρ i are quantifier-free then Ĩ maps quantifier-free formulas to quantifier-free formulas.

Lemma 4.5. If I is an interpretation scheme of λ-structures in κ-structures then for every φ ∈ FO r (λ) and every κ-structure A we have

φ(I(A)) = Ĩ(φ)(A).
As a corollary of Lemma 4.5 we have Corollary 4.6. If (A n ) n∈N is a strongly polynomial sequence of κ-structures and if I is a QF-interpretation scheme of λ-structures in κ-structures, then (I(A n )) n∈N is a strongly polynomial sequence of λ-structures.

The interest of marked structures is that marking provides a way to track components of strong sums, thus allowing the combination of componentwise defined interpretation schemes, as shown by the next lemma. Lemma 4.7. Let I i (1 ≤ i ≤ k) be interpretation schemes of λ i -structures in κ i -structures with exponent p i . Assume that each κ i contains a unary relation U i .

Then there exists an interpretation I scheme of k i=1 λ i -structures in k i=1 κ istructures with exponent p = max p i such that, for every κ i -structure A i marked by U i (1 ≤ i ≤ k), we have

I k i=1 A i = k i=1 I i (A i ).
Moreover, if all the I i 's are QF-interpretation schemes, we can require I to be a QF-interpretation scheme.

Proof. For 1 ≤ i ≤ k, let I i = (p i , ρ i 0 , . . . , ρ i qi )
, where ρ i j has r i,j p i free variables (1 ≤ j ≤ q i ). We define the interpretation scheme

I = (p, ρ 0 , ρ i,j ) (1 ≤ i ≤ k, 1 ≤ j ≤ q i ) with exponent p of k i=1 λ i -structures in k i=1 κ i -structures as follows: the formula ρ 0 is ρ 0 : k i=1 pi j=1 U i (x j ) ∧ p j=pi (x j = x p ) ∧ ρ i 0 (x 1 , . . . , x pi )
and the formula ρ i,j (with r i,j p free variables) is defined by ρ i,j : ri,j p ℓ=1 U i (x ℓ )∧ρ i j (x 1 , . . . , x pi , x p+1 , . . . , x p+pi , . . . , x (ri,j -1)p+1 , . . . , x (ri,j -1)p+pi ).

Then I obviously satisfies the requirements of the lemma statement.

QF-interpretation schemes of strong sums are instrumental in the construction of strongly polynomial sequences, as exemplified by the next result.

Corollary 4.8. Let (A n ) n∈N and (B n ) n∈N be strongly polynomial sequences of graphs. Then

(A n + B n ) n∈N , (A n × B n ) n∈N , (A n B n ) n∈N , (A n ⊠ B n ) n∈N , and (A n [B n ]
) n∈N are strongly polynomial sequence of graphs (formed respectively by disjoint union, direct product, Cartesian product, strong product, and lexicographic product).

Proof. This follows from Corollary 4.6 and Lemma 2.8, by noticing that all the constructions listed here are QF-interpretations of Mark(A n ) ⊕ Mark(B n ).

Many more constructions can be used to combine strongly polynomial sequences of structures by means of strong sum and QF-interpretations, of which the following is an example. Example 4.9. Let t be a fixed odd integer, and let (A i,n ) n∈N (1 ≤ i ≤ t) be a strongly polynomial sequences of graphs. We define B n as the graph with vertex set A 1,n × • • • × A t,n where (u 1 , . . . , u t ) is adjacent to (v 1 , . . . , v t ) in B n if there is a majority of i ∈ {1, . . . , t} such that u i is adjacent to v i in A i,n . Then (B n ) n∈N is a strongly polynomial sequence.

Interpretations of basic sequences

As already noted in Section 3, every basic sequence is strongly polynomial. It follows from Lemma 4.6 that this is also the case for their QF-interpretations: Corollary 5.1. If (B n ) is a basic sequence and I is a QF-interpretation of λ-structures in β k,ℓ -structures, then (I(B n )) is a strongly polynomial sequence of λ-structures.

The class P of sequences (A n ) n∈N that can be obtained by QF-interpretations of basic sequences is quite rich. In particular, it is closed under the following operations, which we know can be used to construct new strongly polynomial sequences from old ones:

• Extracting a subsequence (A P (n) ), where P is a polynomial such that P (n) ∈ N for n ∈ N (as (B P (n) ) n∈N is a basic sequence);

• Applying a QF-interpretation scheme (as the composition of two QFinterpretation schemes defines a QF-interpretation scheme);

• Strong sums (according to Lemma 4.7);

• Multiplying by a polynomial P such that P (n) ∈ N for n ∈ N (as

P (n) A n is a QF-interpretation of T P (n) ⊕ A n ).

Concrete examples

Crown graphs

We start from the basic sequence A n = E ⊕ E ⊕ T n . Consider the graphical interpretation scheme I = (2, ι, ρ), where

ι(x 1 , x 2 ) : U T 1 (x 1 ) ∧ ¬U T 1 (x 2 ) ρ(x 1 , x 2 , y 1 , y 2 ) :¬(x 1 = y 1 ) ∧ ¬(U E 1 (x 2 ) ↔ U E 1 (y 2 )).
Then the graph obtained is the crown graph S n (K n,n minus a perfect matching), and it follows that (S n ) n∈N is a strongly polynomial sequence. Similarly, for every integer k, the sequence (KG n,k ) n∈N of the Kneser graphs is strongly polynomial.

Generalized Johnson graphs

We start from the basic sequence A n = T n and consider, for fixed integer k and subset D ⊆ [k], the graphical interpretation scheme I = (k, ι, ρ), where ι(x 1 , . . . , x k ) :

k-1 i=1 S 1 (x i , x i+1 ) ρ(x 1 , . . . , x k , y 1 , . . . , y k ) : I,J⊆[k] |I|=|J| |I|∈D i ∈I,j ∈J ¬(x i = y j ) ∧ i∈I j∈J (x i = y j )
Then I(A n ) is the generalized Johnson graph J n,k,D , which is the graph with vertices Then the sequence of graphs (H n ) n∈N is strongly polynomial. In particular, the sequence (L(G n )) n∈N of line graphs is strongly polynomial.

Vertex-blowing of a fixed graph

Let F be a fixed graph with vertex set [k]. To each vertex i of F is associated a polynomial P i such that

P i (n) ∈ N for n ∈ N. Let A n = k i=1 T Pi(n)
. We define the graphical interpretation scheme I = (1, ι, ρ) by

ι(x) : 1 ρ(x, y) : ij∈E(F ) U T i (x) ∧ U T j (y)
Then I(A n ) is the vertex-blowing of F , in which vertex i is replaced by P i (n) twin copies of i.

Tree-blowing of a fixed rooted tree

Let F be a rooted tree with edge set E = {2, . . . , k}. To each edge e ∈ E is associated a polynomial P e such that P e (n) ∈ N for n ∈ N and let P 1 be another such polynomial (for the root). Let A n = k i=1 T Pi(n) . An F -path will be a sequence (1, e 1 , . . . , e i ) corresponding to a path from the root of F . Define the graphical interpretation scheme I = (k, ι, ρ) by ι(x 1 , . . . , x k ) :

F -path (a1,...,at) t i=1 U T ai (x i ) ∧ k i=t+1 (x i = x t ) ρ(x 1 , . . . , x k , y 1 , . . . , y k ) : ρ ′ (x 1 , . . . , x k , y 1 , . . . , y k ) ∨ ρ ′ (y 1 , . . . , y k , x 1 , . . . , x k )
where

ρ ′ (x 1 , . . . , x k , y 1 , . . . , y k ) : k-1 i=1 i j=1 (x j = y j ) ∧ (x i = x k ) ∧ ¬(y i = y k ) ∧ (y i+1 = y k )
Then I(A n ) is the tree-blowing of F (in [START_REF] Garijo | Polynomial graph invariants from graph homomorphisms[END_REF] this operation on rooted trees is called "branching").

Union of stars of orders 1, . . . , P (n)

We consider the graphical interpretation scheme I = (2, ι, ρ) defined by

ι(x, y) :S 1 (y, x) ρ(x 1 , y 1 , x 2 , y 2 ) :(y 1 = y 2 ) ∧ [(x 1 = y 1 ) ∧ S 1 (x 2 , y 2 ) ∨ (x 2 = y 2 ) ∧ S 1 (x 1 , y 1 )]
Then, for A n = T P (n) , we have

I(A n ) = P (n) i=1 S i ,
where S i is the star of order i.

Half graphs

Let A n = E⊕E⊕T n . Consider the graphical interpretation scheme I = (2, ι, ρ) where:

ι(x 1 , x 2 ) : U T 1 (x 1 ) ∧ ¬U T 1 (x 2 ) ρ(x 1 , x 2 , y 1 , y 2 ) :S 1 (x 1 , y 1 ) ∧ U E 1 (x 2 ) ∧ U E 2 (y 2 ) ∨ S 1 (y 1 , x 1 ) ∧ U E 1 (y 2 ) ∧ U E 2 (x 2 )
The graph I(A n ) is the half graph on 2n vertices (see Fig. 1).

Intersection graphs of chords

Let A n = T n . Consider the graphical interpretation scheme I = (2, ι, ρ) where:

ι(x 1 , x 2 ) : S 1 (x 1 , x 2 ) ρ(x 1 , x 2 , y 1 , y 2 ) :S 1 (x 1 , y 1 ) ∧ S 1 (y 1 , x 2 ) ∧ S 1 (x 2 , y 2 )
The graph I(A n ) is the intersection graph of chords of a convex n-gon (see Fig. 2).

Sequences of bounded degree graphs

In this section we completely characterize strongly polynomial sequences of graphs of uniformly bounded degree.

Theorem 5.3. Let (A n ) n∈N be a sequence of graphs of uniformly bounded degree. Then the following conditions are equivalent:

1. the sequence (A n ) n∈N is strongly polynomial; 2. there is a finite set {F 1 , . . . , F k } of graphs and polynomials P 1 , . . . , P k such that

A n = k i=1 P i (n) F i ;
3. the sequence (A n ) n∈N is a QF-interpretation of a basic sequence.

Proof. Assume that the sequence (A n ) n∈N is strongly polynomial. Let P (n) = |A n |, d = deg P and, for a graph F, let P F (n) be the number of copies of F in A n . As ∆(A n ) ≤ D for some fixed bound D, we have

P F (n) ≤ D |F |-1 P (n)
and so all the polynomials P F have degree at most d. It follows that P F = 0 if and only if there exists i ≤ d + 1 such that P F (i) = 0, that is, if and only if F is an induced subgraph of d+1 i=1 A i . Let F 1 , . . . , F k be the connected induced subgraphs of d+1 i=1 A i . As every connected component of A n belongs to {F 1 , . . . , F k }, we infer that there exist polynomials P 1 , . . . , P k such that A n = k i=1 P i (n) F i , as can be proved by induction on k as follows. Let F be a connected maximal induced subgraph of d+1 i=1 A i . Without loss of generality, we can assume F = F k . Let P k = P F k . Then A n contains P k (n) copies of F k , each of them being a connected component of A n (by maximality of F k ). Hence we can define the sequence (B n ) n∈N by requiring that A n = B n + P k (n) F k . The sequence (B n ) n∈N is obviously strongly polynomial. Moreover, the connected induced subgraphs of d+1 i=1 B i form a proper subset of the set of the connected induced subgraphs of d+1 i=1 A i . Without loss of generality, these induced subgraphs are F 1 , . . . , F ℓ (for some ℓ < k). Hence, by induction hypothesis, there are polynomials P 1 , . . . , P ℓ such that B n =

ℓ i=1 P i (n) F i . Thus A n = ℓ i=1 P i (n) F i + P k (n) F k .
Assume that there is a finite set {F 1 , . . . , F k } of graphs and polynomials P 1 , . . . , P k such that

A n = k i=1 P i (n) F i . Then the sequence (A n ) n∈N is obvi- ously a QF-interpretation of a basic sequence.
Assume that the sequence (A n ) n∈N is a QF-interpretation of a basic sequence. Then by Corollary 5.1 it is strongly polynomial, .

6 Left limits of strongly polynomial sequences Lovász and Szegedy [START_REF] Lovász | Regularity partitions and the topology of graphons[END_REF] define a graph property (or equivalently a class of graphs) C to be random-free if every left limit of graphs in C is random-free. They prove the following: Theorem 6.1 (Lovász and Szegedy [START_REF] Lovász | Regularity partitions and the topology of graphons[END_REF]). A hereditary class C is random-free if and only if there exists a bipartite graph F with bipartition (V 1 , V 2 ) such that no graph obtained from F by adding edges within V 1 or within V 2 is in C. This theorem has, in our setting, the following corollary, which gives a necessary condition for a sequence of graphs to be strongly polynomial. Theorem 6.2. Every strongly polynomial sequence of graphs (G n ) n∈N converges to a random-free graphon.

Proof. Consider a strongly polynomial sequence of graphs (G n ) n∈N . Let P (n) = |G n | and d = deg P . For every graph F , the probability that a random map from F to G n is a homomorphism is a fixed rational function of n, hence converges as n → ∞. It follows that the sequence (G n ) n∈N converges to some graphon W .

For k ∈ N, consider the bipartite graph

F k = (V 1 , V 2 , E), where |V 1 | = k, |V 2 | = 2 k ,
and the neighbourhoods of vertices in V 2 are pairwise distinct. Let F ′ be any graph obtained from F k by adding some edges whose endpoints both belong to V 1 or both to V 2 . There are 2 k k ways to choose k vertices from V 2 , which together with the k vertices of V 1 induce a subgraph of F ′ of order 2k, which is unique up to the choice of the ordered part of k vertices corresponding to V 1 . Hence there are at least

2 k k /(k! 2k k ) = 2 k 2 (1-o(1)
) distinct induced subgraphs of F ′ of order 2k. Thus, if a hereditary class C of graphs is not random-free, there exists for every integer k, according to Theorem 6.1, a graph F ′ derived from F k that belongs to C. Hence the number of graphs of order 2k in C is at least 2 k 2 (1-o(1)) .

To the sequence (G n ) corresponds a hereditary class F = {F : ∃n F ⊆ i G n }, consisting of graphs F that occur as an induced subgraph of some G n . If a graph F of order k belongs to F, then it is an induced subgraph of a graph G n with n ≤ kd + 1. Indeed, the degree of the polynomial P F counting F is at most kd, hence if P F (n) = 0 for every n ≤ kd + 1, then P F = 0. It follows that the number of induced subgraphs of order k is bounded by

kd+1 i=1 P (i) k = 2 o(k 2 )
. It follows that every strongly polynomial sequence converges to a random-free graphon.

The converse of the implication stated by Theorem 6.2 does not hold in general. Indeed, the set of strongly polynomial sequences is not closed under the operation of subsequence extraction, while the set of sequences converging to a random-free graphon does have this property.

Going further

We have seen that QF-interpretations of basic sequences form strongly polynomial sequences. We now extend this construction to generalized basic sequences, as a way to generate new strongly polynomial sequences from old. For n ∈ N, the λ + -structure T A n is obtained from the disjoint union n i=1 A n by adding relations S and U as follows:

• for every vertex x, T A n |= U (x);

• for all vertices x ∈ A i and y ∈ A j , T A n |= S(x, y) if i < j.

Lemma 7.2. Let (A n ) n∈N be a strongly polynomial sequence of λ-structures. Let λ + be the signature obtained from λ by adding a new binary relation S and a unary relation symbol U . Then (T A n ) n∈N is a strongly polynomial sequence of λ + -structures.

Proof. Let F be a connected λ + -structure. Say that F is nice if F can be partitioned as F = k i=1 F i , with the property that for every (x, y) ∈ F i × F j it holds that F |= S(x, y) if and only if i < j and F |= (∀x)U (x). Then the number inj(F, T A n ) of injective homomorphisms f :

F → T A n is given by inj(F, T A n ) =        0, if F is not nice, 1≤i1<•••<i k ≤n k j=1 inj(F j , A ij ), otherwise,
where F j is the substructure of F induced on F j . As (A n ) n∈N is strongly polynomial, there are polynomials P 1 , . . . , P k such that inj(F j , A n ) = P j (n).

For every n ∈ N, we have

1≤i1<•••<i k ≤n k j=1 P j (i j ) = n i1=1 P 1 (i 1 )   n i2=i1+1 P 2 (i 2 )   • • • n i k =i k-1 +1 P k (i k ) . . .     .
But for each k there exists a polynomial Q k such that

n i k =i k-1 +1 P k (i k ) = Q k (n) -Q k (i k-1
), in which i 0 = 0. By induction on k, it follows that there exists a polynomial Q F such that for every n ∈ N we have

Q F (n) =        0, if F is not nice, 1≤i1<•••<i k ≤n k j=1 P j (i j ), otherwise.
It follows that the sequence (T A n ) n∈N is strongly polynomial.

Definition 7.3. A generalized basic structure with parameter

(((A 1 n ) n∈N , . . . , (A k n ) n∈N ), (B 1 , . . . , B ℓ ))
is any structure of the form

C = ℓ i=1 B i ⊕ k j=1 T A j Nj ,
with N 1 , . . . , N k ∈ N. These integers will be also be denoted by N 1 (C), . . . , N k (C).

A generalized basic sequence is a sequence (C n ) n∈N of generalized basic structures C n with the same parameter (((A 1 n ) n∈N , . . . , (A k n ) n∈N ), (B 1 , . . . , B ℓ )), such that there are non-constant polynomials

Q i , 1 ≤ i ≤ k with Q i (n) = N i (C n ) (for every 1 ≤ i ≤ k and n ∈ N).
Theorem 7.4. For every generalized basic sequence (C n ) n∈N and every QFinterpretation scheme I, the sequence (I(C n )) n∈N is strongly polynomial.

Proof. As the sequence (T A n ) n∈N is strongly polynomial, this theorem is a direct consequence of Lemmas 2.10 and 2.8.

Discussion

The notion of interpretation scheme introduced in this paper could be made even more general by introducing a formula ̟ (with 2p free variables) defining an equivalence relation on the set of p-tuples compatible with the formulas ρ i , in the sense that ri j=1 ̟(x j , y j ) ⊢ ρ i (x 1 , . . . , x ri ) ↔ ρ i (y 1 , . . . , y ri ) (see for instance [START_REF] Lascar | La théorie des modèles en peu de maux[END_REF]). For a general interpretation scheme I of λ-structures in κ-structures and a κ-structure A, the vertex set of I(A) is then the set of ̟-equivalence classes [x] of p-tuples x such that A satisfies ρ 0 (x).

In such a context, we can prove the following generalization of Corollary 4.6.

Theorem 8.1. Let (A n ) n∈N be a strongly polynomial sequence of κ-structures and let I = (p, ̟, ρ 0 , . . . , ρ k ) be a general interpretation scheme of λ-structures in κ-structures such that all the formulas ̟, ρ 0 , . . . , ρ k are quantifier-free. Assume that all the ̟-equivalence classes have polynomial quantifier-free definable cardinalities. More precisely, we assume that there exists an integer N , polynomials Q 1 , . . . , Q N (such that Q i (n) ∈ N for every 1 ≤ i ≤ N and every n ∈ N), and quantifier-free formulas η 1 , . . . , η N (with p free variables) such that N i=1 η i = 1 and for every n ∈ N and every (v 1 , . .

. , v p ) ∈ A p n the ̟-equivalence class [(v 1 , . . . , v p )] of (v 1 , . . . , v p ) in A p n has cardinality exactly Q i (n) if A n |= η i (v 1 , . . . , v p ).
Then (I(A n )) n∈N is a strongly polynomial sequence of λ-structures.

Proof. Let I ′ = (p, ρ 0 , . . . , ρ k ) and let φ ∈ QF q (λ) be a quantifier-free formula.

According to Lemma 4.5, for every κ-structure A we have φ(I ′ (A)) = Ĩ′ (φ)(A). For f : [q] → [N ], define the quantifier free formula ψ f ∈ QF q (λ) as follows:

ψ f (x 1 , . . . , x p ) : Ĩ′ (φ)(x 1 , . . . , x p ) ∧ N i=1 η f (i) (x i ).
By hypothesis it is immediate that for every n ∈ N we have

|φ(I(A n ))| = f :[q]→[N ] |ψ f (A n )| q i=1 Q i (n)
.

Hence |φ(I(A n ))| is a rational function of n, thus a polynomial function of n (according to Remark 2.6).

General interpretation schemes allow the definition of new constructions preserving the property of a sequence being strongly polynomial. For instance:

• G → Ġ, which maps a graph to its 1-subdivision (that is, the graph obtained from G by replacing each edge by a path of length 2);

• G → L(G), which maps a simple graph to its line graph.

However, if we restrict ourselves to the class of basic structures, introducing an equivalence relation with bounded class cardinalities does not in fact lead to the definition of any new transformations. By a fine study of quantifier-free definable equivalence relations, one can prove the following result. Theorem 8.2. Let k, ℓ be integers and let I = (p, ̟, ρ 0 , . . . , ρ k ) be a general interpretation scheme of λ-structures in β k,ℓ -structures defined by quantifier-free formulas such that there exists an integer N with the property that, for every B ∈ B k,ℓ and every (v 1 , . . . , v p ) ∈ B p , the ̟-equivalence class of (v 1 , . . . , v p ) has cardinality at most N .

Then there exists a (restricted) QF-interpretation scheme Î = (ρ 0 , ρ 1 , . . . , ρ k ) of λ-structures in β k,ℓ -structures such that for every B ∈ B k,ℓ , the λ-structures I(B) and Î(B) are isomorphic.

Proof sketch. Consider the graphical interpretation scheme I ′ = (p, ρ 0 , ̟). The condition that ̟-equivalence classes have cardinality at most N translates to the fact that for every B ∈ B k,ℓ the maximum degree of I ′ (B) is at most N -1.

A (k, ℓ)-pattern of length p is a surjective mapping

F : [p] → I ∪ j∈J {j} × [n j ],
where

I ⊆ [ℓ], [J] ⊆ [k]
, and 1 ≤ n j ≤ p. The profile of F is the k-tuple (n 1 , . . . , n k ). For F (i) / ∈ I, we denote by F (i) 1 and F (i) 2 the two coordinates of F (i) (so that

F (i) = (F (i) 1 , F (i) 2 ).
To a (k, ℓ)-pattern F of length p we associate the quantifier-free formula

τ F : i:F (i)∈I U E F (i) (x i ) ∧ i:F (i) / ∈I U T F (i)1 (x i ) ∧ i,j:F (i)=F (j) (x i = x j ) ∧ i,j:F (i),F (j) / ∈I and F (i)1=F (j)i and F (i)2<F (j)2 S F (i)1 (x i , x j ).
(

) 2
Then it is easily checked that for k, ℓ ∈ N and every A ∈ B k,ℓ there exists a unique (k, ℓ)-pattern F A such that A |= τ F A (A). Also, for every quantifier-free formula φ ∈ QF p there exists a finite family F of (k, ℓ)-patterns such that for every A ∈ B k,ℓ and every v 1 , . . . , v p ∈ A it holds that

A |= φ(v 1 , . . . , v p ) ⇐⇒ A |= F ∈F τ F (v 1 , . . . , v p ).
To every p-tuple v = (v 1 , . . . , v p ) ∈ A p , with A ∈ B k,ℓ , we associate the vector v of distinct coordinates of v belonging to tournaments, taken in order. A vector u is packed if u = u. The profile of a vector u is the profile of F u . Note that u and u have the same profile. Note also that ζ : v → (v, F v ) is a bijection between A p and pairs (u, F ) such that u is packed and has the same profile as F . For given F , we denote by Ω(A, F ) the packed vectors with coordinates in A having the same profile as F . For k, ℓ ∈ N and φ ∈ QF p (β k,ℓ ), there exists a set F of (k, ℓ)-patterns, such that φ(A) = F ∈F {ζ -1 (u, F ) : u ∈ Ω(A, F )}, where the union is a disjoint union.

From the hypothesis that ̟ is an equivalence relation with bounded classes, we deduce that there exists a collection {F 1 , . . . , F t } of disjoint sets of (k, ℓ)patterns with the same profile, such that each connected component of I ′ (B) is a clique with vertex set K t,x = {ζ -1 (x, F ) : F ∈ F t }, where x is any compressed vector with the same profile as F ∈ F t . (This is shown by proving that for an equivalence relation ̟ of a different form we can construct A with at least one arbitrarily large equivalence class).

Consider an arbitrary linear order on (k, ℓ)-patterns. Let ρ0 ∈ QF p be the quantifier-free formula ρ0 (x 1 , . . . , x p ) : ρ 0 (x 1 , . . . , x p ) ∧ t i=1 τ min Fi (x 1 , . . . , x p ).

Then ρ0 selects exactly one vertex in each ̟-equivalence class, and the statement of the lemma now follows.

We do not include the full lengthy technical proof of Theorem 8.2.

Conclusion and open problems

A natural problem arising from this paper is to figure out whether the strongly polynomial sequences we have constructed from basic sequences constitute the general case, as suggested by Theorem 5.3.

A strongly polynomial sequence of graphs (G n ) n∈N is induced monotone if G n is an induced subgraph of G n+1 for each n ∈ N. Equivalently, (G n ) n∈N is induced monotone if there exists a countable graph G such that G n is the subgraph induced by vertices 1, . . . , f (n), where f is a monotone (non-decreasing) function.

Problem 9.1. Can all strongly polynomial induced monotone sequences of graphs be obtained by QF-interpretation schemes from generalized basic sequences (as defined in Definition 7.3)?

There is more to this than meets the eye. By Theorem 6.2, we know that every strongly polynomial sequence converges to a random-free graphon. In some sense, we are asking here whether, under the stronger assumption that the sequence of graphs has an inductive countable limit, the countable limit itself may be an interpretation of a countable "basic" structure.

The Paley graph indexed by q a prime power congruent to 1 modulo 4 is defined as the Cayley graph on F q with edges joining vertices whose difference is a non-zero square in F q . Paley graphs form a quasi-random sequence and so as a consequence of Theorem 6.2 any strongly polynomial sequence of graphs can contain only finitely many distinct Paley graphs. Nonetheless, a corollary of [START_REF] De La Harpe | Chromatic invariants for finite graphs: theme and polynomial variations[END_REF]Prop. 8] is that when F is a 2-degenerate graph (for example, a series-parallel graph) the number of homomorphic images of F in the Paley graph on q vertices is a polynomial in q (dependent only on F ).

In [START_REF] Garijo | Polynomial graph invariants from graph homomorphisms[END_REF] it is shown that for the hypercube Q n = Cayley(F n 2 , S 1 ), where S 1 is the set of n vectors of Hamming weight 1, for each F the quantity hom(F, Q n ) is a polynomial in 2 n and n (dependent only on F ).

These examples prompt the following question concerning sequences of Cayley graphs: In another direction, perhaps one should try to approach by means of interpretations other (multivariate) polynomials, such as the Bollobás-Riordan coloured Tutte polynomial [START_REF] Bollobás | A Tutte polynomial for colored graphs[END_REF].

Example 4 . 3 .

 43 Let us consider two signatures κ and λ with κ ⊂ λ. Then the following transformations are easily (and almost trivially) checked to be definable by QF-interpretation schemes:

  [n] k and where X and Y are adjacent whenever |X ∩ Y | ∈ D. Remark 5.2. Similarly, let k be an integer and let D ⊆ [k], and let (G n ) n∈N be a strongly polynomial sequence of graphs. For n ∈ N define H n as the graph whose vertices are the k-cliques of G n , where two k-cliques of G n are adjacent in H n if the cardinality of their intersection belongs to D.

Figure 1 :

 1 Figure 1: Half graphs form a strongly polynomial sequence

Figure 2 :

 2 Figure 2: Intersection graphs of chords of a convex n-gon form a strongly polynomial sequence

Definition 7 . 1 .

 71 Let (A n ) n∈N be a sequence of λ-structures. Let λ + be the signature obtained from λ by adding a new binary relation S and a unary relation symbol U .

Problem 9 . 2 .

 92 Let (A n ) be a sequence of groups and (B n ) a sequence of subsets, B n ⊆ A n , that are closed under inverses. When is it the case that hom(F, Cayley(A n , B n )) is a fixed bivariate polynomial (dependent on F ) in |A n | and |B n | for sufficiently large n ≥ n 0 (F )? If here |A n | and |B n | are both polynomial in n then this is to ask whether the sequence (Cayley(A n , B n ) ) is a polynomial sequence of graphs (see Section 1). Remark 9.3. By a variation of the argument given in [7, Prop.2], when A n = Z n and B n = B ∩ [-(n -1), n -1] for B ⊆ Z, B = -B, the sequence (Cayley(A n , B n )) is polynomial if and only if B is finite or cofinite. Is it true for instance that the sequence (Cayley(Z n , D n )) where D n = [a n , b n ] is an interval of length o(n) is a polynomial sequence?

* Supported by grant ERCCZ LL-1201 of the Czech Ministry of Education † Supported by grant ERCCZ LL-1201 of the Czech Ministry of Education, CE-ITI P202/12/G061 of GA ČR, and LIA STRUCO ‡ Supported by grant ERCCZ LL-1201 of the Czech Ministry of Education and LIA STRUCO, and partially supported by ANR project Stint under reference ANR-13-BS02-0007