N Douet-Guilbert

J Andrieux

J L Laï

P Morice

J L Demory

A Basinko

V Ugo

N Gueganic

M J Bris

F Morel

M J Le Bris

M De Braekeleer

Isoderivative of deleted chromosome 20 in primary myelofibrosis (PMF) characterized by molecular cytogenetics and array CGH

published or not. The documents may come

Isoderivative of deleted chromosome 20 in primary myelofibrosis (PMF) characterized by molecular cytogenetics and array CGH

Dear Editor, Primary myelofibrosis (PMF) is a BCR-ABL-negative chronic myeloproliferative disorder. Chromosomal abnormalities are heterogeneous but deletion of the long arm of chromosome 20 (del(20q)) is a recurrent abnormality observed in 20-30% in PMF [START_REF] Gfch | Recommandations pour la prise en charge cytogénétique des syndromes myéloprolifératifs autres que la leucémie myéloïde chronique (LMC) établies par le Groupe Français de Cytogénétique Hématologique (GFCH)[END_REF]. A variant of deletion 20q, an isochromosome of the long arm of chromosome 20 with loss of interstitial material (ider(20q)), has recently been described in myeloid hemopathy [START_REF] Li | Clinical and molecular cytogenetic studies in seven patients with myeloid diseases characterized by i(20q-)[END_REF][START_REF] Saunders | Isochromosome of a deleted 20q: a rare but recurrent chromosome abnormality in myelodysplastic syndromes[END_REF][START_REF] Lim | A novel isoderivative chromosome 20 in a patient with chronic myelomonocytic leukemia[END_REF][START_REF] Shetty | Isoderivative chromosome 20 in bone marrow: three new cases[END_REF][START_REF] Douet-Guilbert | Fluorescence in situ hybridization characterization of ider(20q) in myelodysplastic syndrome[END_REF]. To our knowledge, a sole case of primary myelofibrosis with ider(20q) has been published [START_REF] Reilly | Cytogenetic abnormalities and prognostic significance in idiopathic myelofibrosis: a study of 106 cases[END_REF]. Here, we report two further cases.

Patient 1 is a 79-year-old-woman who presented with chronic leukoneutropenia. Physical examination revealed neither hepatosplenomegaly nor lymphadenopathy. Trephine biopsy sections showed reticulin and collagen fibrosis with decreased cellularity. In fibrous tissue, megakaryocytes were dysplastic; granulocytic and erythroid lineages were nonexistent. An abdominal ultrasonography revealed a splenomegaly of 15.5 cm. JAK2 V617F mutation was present. A diagnosis of primary myelofibrosis was made. Six months later, no sign of clinical evolution was observed. During these 6 months, the patient benefited from clinical surveillance, with blood parameters remaining stable.

Hepatosplenomegaly was found at physical examination of a 71 year-old-woman (patient 2). The bone marrow aspirate revealed reticulin fibrosis. The patient received blood transfusions during 1 year, before being lost to follow-up.

Cytogenetic analysis was performed on bone marrow cells at the time of diagnosis for both patients. All 20 metaphases observed after R-banding showed a 46,XX,ider(20)(q10) del (20)(q11q13) for patient 1. For patient 2, conventional analysis after G-banding revealed a 46,XX,del(20)(q11) in four metaphases only.

Metaphase and interphase fluorescent in situ hybridization (FISH) was performed using LSI D20S108 (20q12) Spec-trumOrange probe (Abbott diagnostic, Rungis, France), CEP20 (Qbiogene, Illkirch, France), and TelVysion 20p and 20q probes (Abbott). Breakpoint localization was delineated with an appropriate set of bacterial artificial chromosome (BAC) clones, as previously described [START_REF] Douet-Guilbert | Fluorescence in situ hybridization characterization of ider(20q) in myelodysplastic syndrome[END_REF][START_REF] Douet-Guilbert | Chromosome 20 deletions in myelodysplastic syndromes and Philadelphia-chromosome-negative myeloproliferative disorders: characterization by molecular cytogenetics of commonly deleted and retained regions[END_REF].

For patient 1, LSI D20S108 was deleted. FISH studies showed absence of 20p subtelomeric probe and two copies of 20q subtelomeric probe in all analyzed metaphases. The isoderivative chromosome 20 was found to be dicentric. Interphase FISH studies did not show the presence of a clone with deletion 20q associated with the isoderivative clone. FISH was not performed in patient 2 because of scarcity of metaphases in the medullar sample.

Detection of gene copy number was performed by array comparative genomic hybridization (CGH) experiments following standard and manufacturer's recommendations (Agilent™, Agilent Technologies, Santa Clara, CA, USA) using 44000 oligo probes approximately spaced at 40-100-kb intervals across the genome. A duplication of the regions 20cen→20q11.21 and 20q13.2→20qter was identified by array CGH. This technique also revealed the same proximal breakpoint on the long arm of chromosome 20, in band 20q11.21, for both patients. Distal breakpoints were located in band 20q13.2, at 300 kb apart from each other (Fig. 1a). No additional copy number variation was observed in each case.

Based on array CGH and FISH results, the karyotype could then be rewritten for patients 1 and 2 as 46,XX,idic (20)(p11)del(20)(q11.21q13.2) and 46,XX,ider(20)(q10)del (20)(q11.21q13.2), respectively. Located between KIF3B and DNMT3B genes (Fig. 1b), the proximal breakpoint observed in both patients is different from the recurrent breakpoint described in myelo-dysplastic syndrome with ider(20q) [START_REF] Douet-Guilbert | Fluorescence in situ hybridization characterization of ider(20q) in myelodysplastic syndrome[END_REF]. Distal breakpoints on the long arm of chromosome 20 were located in band 20q13.2 within a 340-kb segment, containing the ATP9A (which protein function is unknown) and SALL4 (a zinc finger transcription factor) genes (Fig. 1c). In patient 2, the distal breakpoint disrupted the NFATC2 gene, a member of the nuclear factor of activated T cell family. Located in the duplicated region, the KIF3B gene, encoding for a protein involved in chromosome movement during mitosis and meiosis, and the ASXL1 gene, described in drosophila enhancing or repressing transcription of contiguous genes, were situated near the breakpoint. ZFP64 encodes for a zinc finger protein which function is unclear [START_REF] Shetty | Isoderivative chromosome 20 in bone marrow: three new cases[END_REF]. The intrachromosomal rearrangement on the long arm could produce a new chimeric gene or modify the expression of genes by connection of KIF3B, ASXL1, NFATC2, and ZFP64 genes.

As in del(20q), candidate genes contained in the deleted region of the long arm of chromosome 20 are suggested but, at present, the target genes remain unknown [START_REF] Douet-Guilbert | Fluorescence in situ hybridization characterization of ider(20q) in myelodysplastic syndrome[END_REF]. Near the proximal breakpoint, the DNMT3B gene, encoding a DNA methyltransferase thought to function in de novo methylation, is deleted. This gene may play a significant role in leukemic process. In addition, many genes contained on the entire short arm of chromosome 20 are lost in this anomaly and could explain the aggressiveness of ider(20q).

In ider(20q), proximal and distal retained chromosomal regions on the long arm of chromosome 20 are duplicated. Amplification of retained oncogenes such as HCK, TNFRSF6B, and DIDO genes is also suggested to explain the worse prognosis of ider(20q) compared to del(20q), although this remains controversial [START_REF] Douet-Guilbert | Fluorescence in situ hybridization characterization of ider(20q) in myelodysplastic syndrome[END_REF].

In PMF, cytogenetic analysis is often difficult because of limited bone marrow aspirate and hypocellularity. Thus, the incidence of ider(20q) could be underestimated in myelofibrosis. Furthermore, the heterogeneity of the chromosomal aberrations identified in PMF prevents us from assessing the clinical impact of these abnormalities.

2 Fig. 1

 21 Fig. 1 Breakpoint location for the two patients and genomic variations of chromosome 20. a Array CGH profile of isoderivative of deleted chromosome 20. The graphic shows the deleted regions on the short arm of chromosome 20 and the long arm of chromosome 20 (green arrows) and the proximal and the distal duplicated regions (red arrows). The dotted line represents breakpoints. b Representation of the proximal breakpoints (dotted line) on the long arm of chromosome 20 for patients 1 and 2, by array CGH and FISH with BACs. Applied BAC clones are bordered; candidate genes are surrounded. c Representation of the distal breakpoints (dotted lines) on the long arm of chromosome 20 for patients 1 and 2, by array CGH and FISH with BACs. Applied BAC clones are bordered; candidate genes are surrounded

AnnHematol (2009) 88:1157-1159 DOI 10.1007/s00277-009-0753-3 N. Douet-Guilbert : A. Basinko : N. Gueganic : F. Morel : M. De Braekeleer Laboratoire d'Histologie, d'Embryologie et de Cytogénétique, Faculté de Médecine et des Sciences de la Santé, Université de Brest, Brest 29238, France N. Douet-Guilbert : A. Basinko : M. J. Le Bris : F. Morel : M. De Braekeleer Laboratoire de Cytogénétique, Centre Hospitalier Universitaire de Brest, Brest 29609, France N. Douet-Guilbert : V. Ugo : F. Morel : M. De Braekeleer INSERM U613, Brest 29200, France J. Andrieux : J. L. Laï Laboratoire de Génétique Médicale, Hopital Jeanne de Flandre, Centre Hospitalier Régional Universitaire de Lille, Lille 59000, France P. Morice Service de Pneumologie 4 et d'allergologie, Centre Hospitalier Pierre Le Damany, Lannion 22303, France J. L. Demory Département d'Hématologie, Hopital St-Vincent de Paul, GHICL, Lille 59000, France V. Ugo Laboratoire d'Hématologie Biologique, Centre Hospitalier Universitaire de Brest, Brest 29609, France M. De Braekeleer (*) Laboratoire de Cytogénétique, Faculté de Médecine et des Sciences de la Santé, Université de Brest, 22, avenue Camille Desmoulins, CS 93837, 29238 Brest, France e-mail: marc.debraekeleer@univ-brest.fr


Jaroslav Nešetřil

Patrice Ossona De Mendez

Sparse Combinatorial Structures: Classification and Applications

Keywords: Mathematics Subject Classification (2010). Primary 0502; Secondary 05C75, 05C15, 05C83, 05C85, 03C13, 68Q19 graphs, hypergraphs, structures, homomorphism, sparsity, model checking, bounded expansion, property testing, separators, complexity, structural combinatorics

We present results of the recent research on sparse graphs and finite structures in the context of of contemporary combinatorics, graph theory, model theory and mathematical logic, complexity of algorithms and probability theory. The topics include: complexity of subgraph-and homomorphism-problems; model checking problems for first order formulas in special classes; property testing in sparse classes of structures. All these problems can be studied under the umbrella of classes of structures which are Nowhere Dense and in the context of Nowhere Dense -Somewhere Dense dichotomy. This dichotomy presents the classification of the general classes of structures which proves to be very robust and stable as it can be defined alternatively by most combinatorial extremal invariants as well as by algorithmic and logical terms. We give examples from logic, geometry and extremal graph theory. Finally we characterize the existence of all restricted dualities in terms of limit objects defined on the homomorphism order of graphs.

Introduction

In this paper we survey results of the recent research on sparse graphs, hypergraphs and finite structures in the context of some of the key areas of contemporary combinatorics, graph theory, model theory and mathematical logic, complexity of algorithms and probability theory. We list the following areas as related to this paper:

• universal and generic structures of model theory;

• Constraint Satisfaction Problems in the context of descriptive complexity;

• complexity of subgraph-and homomorphism-problems;

• existence of (homomorphism) dualities in the context of the homomorphism order; • fast model checking in first order logic;

• subgraphs statistics and local convergence;

• the existence of sublinear separators; • property testing in sparse classes of structures;

• polynomial on-line and game-colorings of graphs;

• validity of homomorphism preservation theorems.

Although these are very distinct areas it is often easy to see that in all of these problems we have to put some restrictions on the graphs to be considered: in the full generality for finite graphs the answers to most of our questions are known to be negative, or hopelessly hard. But often the answer tend to be negative even for graphs which have many edges what is usually described by the term "dense graphs". In the context of this paper dense graphs are not only those having O(n 2 ) edges but even those having O(n 1+ ) edges (n is the number of vertices). Even such edge sizes do not guarantee positive answers to the above problems.

For such answers we have to look at instances with very few edges. For example subgraph problem has a positive answer for geometrically restricted (such as planar graphs [START_REF]Subgraph isomorphism in planar graphs and related problems[END_REF][START_REF] Eppstein | Subgraph isomorphism in planar graphs and related problems[END_REF]) while the homomorphism preservation theorems hold for classes of bounded degree graphs ( [START_REF] Atserias | On preservation under homomorphisms and unions of conjunctive queries[END_REF]). In contrast with this, the Separator Problem has the negative answer even for cubic (i.e. degree 3) graphs. In this case the answer is again positive for planar graphs [START_REF] Lipton | A separator theorem for planar graphs[END_REF], for graphs with a fixed genus [START_REF] Gilbert | A separator theorem for graphs of bounded genus[END_REF], and for graphs excluding a minor [START_REF]A separator theorem for nonplanar graphs[END_REF][START_REF] Alon | A separator theorem for graphs with excluded minor and its applications[END_REF]. And similar diverse situations occur for the other problems and some sparsity is playing a role there.

But which structures are sparse? Sparsity seems to be an elusive and typically "fuzzy" notion and it seems that the answer to this question depends on the particular problem considered. Yet in this paper we present a classification of graph classes which clarifies the boundary between sparse and dense instances and which proved to be useful in many concrete applications and all of the above problems in particular.

How to define sparsity? Perhaps the good way to define it is by means of the stability with respect to some operations. We aim for sparsity as a self-similarity idea, as the invariance to small changes. This approach is the one taken in this paper. We employ the mixture of geometric and combinatorial approach and define (time) resolution of a structure and of a class of structures. This in turn leads to the surprisingly general dichotomy of classes of structures -there are nowhere dense classes and classes which are somewhere dense. This is stated in Section 2.4 after the introduction in Section 2 of all the relevant notions.

In Section 4 we show how this dichotomy, which may appear on the first glance arbitrary, can be described in several very different ways. In fact almost all the basic extremal combinatorial parameters are suitable for the description of this dichotomy: In Section 3.1 we deal with edge densities, in Section 2.4 with clique number ω, in Section 4.1 with the chromatic number χ, in Section 4.2 with the independence number α (and of course for the space limitations we do not mention all relevant characterizations, see [START_REF]On nowhere dense graphs[END_REF][START_REF]Sparsity (graphs, structures, and algorithms[END_REF]). All of this shows that the nowhere dense -somewhere dense dichotomy is not just an accident or a combinatorial curiosity but rather a natural, stable and robust dichotomy.

Nowhere dense classes Somewhere dense classes

There is a further evidence which goes beyond the α, χ, ω. Very recently this list was complemented by the counting (densities of subgraphs) (see Section 4.3) and also by results in mathematical logic: the nowhere dense -somewhere dense dichotomy induces exactly the dividing line between (monotone) classes of graphs for which the model checking for first order logic s is Fixed Parameter Tractable (FPT) and those classes for which model checking is hard, see [START_REF] Dawar | Parametrized complexity of first-order logic[END_REF][START_REF] Dvořák | A linear time for deciding first-order properties on classes with bounded expansion[END_REF]. We treat this in Section 4.2 where (based on our earlier analysis of Nowhere Dense structures) we extend these result to general structures. Some of these applications will be mentioned in Section 5 and Section 6 in a greater detail. The core of many of these applications is a possibility to approximate (with arbitrary precision) any graph in a nowhere dense class by a graph defined by finitely many data. Technically this takes form of Low Tree Depth Decomposition which for the illustration we formulate here for the case of a bounded expansion class C of structures (defined in Section 8): Theorem 1. (Low Tree Depth Decomposition) For every bounded expansion class C and for every positive integer p there exists an integer N = N (p, C) such that every structure A ∈ C has a decomposition X A = X 1 ∪ . . . ∪ X N with the following property:

A restricted to any set i∈I X i where |I| ≤ p, has tree depth at most |I| (particularly, this substructure cannot include a path of length 2 |I| .

(See Sections 4 and 8 for more details.) As there are only finitely many core graphs with tree depth at most p [START_REF]Tree depth, subgraph coloring and homomorphism bounds[END_REF] a Low Tree Depth Decomposition can be approximated by a finite set of data and this decomposition is much in the spirit of Szemerédi regularity lemma, [START_REF] Szemerédi | Regular partitions of graphs[END_REF].

The research covered by this paper is related to the recent development which is based on the study of homomorphisms of structures. The main idea is to study the local structure of a large structure A by counting the homomorphisms from various small graphs F into A (this relates to the area called property testing), and to study the global structure of A by counting its homomorphisms into various small graphs C (sometimes interpreted as templates). Regularity is viewed here as a structural approximation in a proper metric and also as a convergence. For a survey of this development, see [START_REF] Borgs | Counting graph homomorphisms[END_REF]. This approach proved to be very fruitful and relates (among others) to the notion of quasi-random graphs, see e.g. [START_REF] Chung | Quasi-random graphs[END_REF], and to the general results characterizing testable properties, see e.g. [START_REF] Alon | A characterization of the (natural) graph properties testable with one-sided error[END_REF][START_REF] Borgs | Counting graph homomorphisms[END_REF][START_REF]Parameter testing in bounded degree graphs of subexponential growth[END_REF][START_REF] Rödl | Property testing in hypergraphs and the removable lemma[END_REF][START_REF] Schramm | Hyperfinite graph limits[END_REF][START_REF] Austin | On the testability and repair of hereditary hypergraph properties[END_REF].

In this paper we take a similar, yet different, approach. We start our analysis with the homomorphism order. We shall see that in this setting, at a proper level of generality, some of the results for dense graphs can be extended to the world of sufficiently sparse classes of graphs. Along these lines we mention also results related to the universality problems for the homomorphism order (and we mention several results obtained jointly with Jan Hubička, [START_REF]A finite presentation of the rational Urysohn space[END_REF][START_REF]Finite paths are universal[END_REF][START_REF]Universal partial order represented by means of oriented trees and other simple graphs[END_REF]). This then naturally relates to the problems of finite dualities (which we characterized jointly with Claude Tardif [START_REF] Nešetřil | Duality theorems for finite structures (characterizing gaps and good characterizations)[END_REF]) and then to restricted dualities which will be characterized (in Section 9) by means of the completion of the homomorphism order. After all the existential theorem related to the homomorphism order we return to the counting and describe (in the case of graphs) the Nowhere Dense-Somewhere Dense dichotomy by means of the counting functions (see Section 4.3).

Preliminaries

2.1. Graphs vs Structures. Let us review some basic notions which will be used. Our graphs are finite simple undirected graphs, except when explicitly stated otherwise and we denote by Graph the class of all such graphs. We use standard graph theory terminology (see e.g. [START_REF] Matoušek | Invitation to discrete mathematics[END_REF]). We find it useful to introduce the following: for a graph G = (V, E), we denote by |G| the order of G (that is: |V |) and by G the size of G (that is: |E|). Similarly, a finite set system (or hypergraph, we shall use both notions) is a pair (X, M) where M is a collection of subsets of X. It is customary to call these sets edges again. If all the edges have k elements then we speak simply about a k-graph. (Thus graphs are just 2-graphs.)

The distance in a graph G between two vertices x and y is the minimum length of a path linking x and y (or ∞ if x and y do not belong to the same connected component of G) and is denoted by dist G (x, y). Let G = (V, E) be a graph and let d be an integer.

A class C of graphs is hereditary if every induced subgraph of a graph in C belongs to C, and it is monotone of every subgraph of a graph in C belongs to C.

The notion of a finite relational structure is more involved and in fact it appears in two different formalisms.

One possibility is that we specify a language L which accepts standard logic and sets involves relational symbols R, S, . . . each with an appropriate arity. In such case we speak about relational structures with a given signature L.

Sometimes we want to be more explicit and we specify a finite sequence (type) of positive integers ∆ = (δ i : i ∈ I) which we call type. A relational structure A of type ∆ is then a pair (X, (R i : i ∈ I)) where R i ⊂ X δi is an d i -ary relation on X. In this case we also put X = X A and R i = R A i . The notions of a homomorphism (monomorphism) are standardly defined as mappings (injective mappings) preserving all relations. In a difference to algebras the embeddings need a little more care: An injective mapping f : X A -→ X B is called an embedding of A to B if the following hods for every relation R A :

(x i : i = 1, . . . , ) ∈ R A if and only if (f (x i ) : i = 1, . . . , ) ∈ R B .
The category of all finite graphs and all homomorphisms between them will be denoted again by Graph, the category of all finite relational structures of type ∆ and all homomorphisms between them Rel(∆) and the category of all finite set systems (i.e. hypergraphs) or k-graphs and all their homomorphisms is denoted by Hyp or Hyp(k).

The relationship of very simple models (as presented by graphs) and more general relational systems is very interesting and far from trivial. Recently this connection got several new impulses. For example the connection to Constraint Satisfaction Problems, first order definability and to descriptive algorithmic complexity recently were intensively studied [START_REF] Kun | NP for combinatorialists[END_REF][START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory[END_REF][START_REF] Alon | Efficient testing of large graphs[END_REF][START_REF] Hubička | Homomorphism and embedding universal structures for restricted classes[END_REF]. We report some of this research in Section 4.2.

There are various connection between relational structures of different types. For example if the two signatures are in inclusion (i.e. if ∆ ⊂ ∆ ) then we speak about an extension (sometimes the name lift is used). This corresponds to enrichment of the original structures A ∈ Rel(∆) by new relations, such as colors of vertices, edges, orderings, etc. The inverse construction is the reduct (sometimes shadow): We start with an object A ∈ Rel(∆ ) and define the object A ∈ Rel(∆) by considering only those relations from type ∆ (and forgetting about the others), see e.g. [START_REF] Hodges | Model theory[END_REF].

The reduct and extension are powerful operations (as expected; we are changing the language itself). For example, it has been proved in [START_REF] Kun | NP for combinatorialists[END_REF] (extending earlier works by [START_REF] Fagin | Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation[END_REF][START_REF] Feder | The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory[END_REF]) that the question whether there exists a lift with finitely many prescribed local properties is polynomially equivalent to a general problem in the class NP. Similarly reducts are related to some of the classical combinatorial (Ramsey type) statements, see [START_REF] Thomas | Reducts of the random graph[END_REF] (using [START_REF] Nešetřil | Partitions of relational and set systems[END_REF]).

There are other constructions which reduce one signature to another. In the logical context perhaps the most widely used is the following construction:

1. Gaifman Graph. To a relational structure A we associate its Gaifman graph Gf(A) = (V, E) by putting V = X A and {x, y} ∈ E if x = y and x and y appear in a same tuple of A. (In combinatorics this construction is known as 2-section, [START_REF] Berge | Graphes[END_REF].)

Gaifman graphs allow us to translate many graph notions to general systems. This transformation has several advantages (the main one being perhaps its simplicity) but there are disadvantages too and the sparsity (which is our central theme here) is often not preserved. The relational system may be quite sparse and of a very simple form, yet the corresponding Gaifman graph may be as complicated as possible. For example the Gaifman graph of any edge is a complete graph. Other examples (with bounded arities) include Gaifman graph of any Steiner Triple System (X, M) which is the complete graph on the set X. An even simpler example can be constructed on any set X ∪ { * } as follows: M is formed by all triples of form {x, x , * }, x = x ∈ X. The Gaifman graph is again a complete graph.

As a result of examples like these, more sensitive transformations were devised:

2. Block graph. The block graph Inc(A) of A (sometimes called Incidence graph) is defined as follows: The vertices are formed by X A together with the set of all pairs (i, (x 1 , . . . , x δi )), i ∈ I. The edges are formed by all incidences between x and (x 1 , . . . , x δi ). This construction has many forms: edges may be directed, vertices may have colors, it is either simple graph or a multigraph, etc.

3. Path graph. The path graph Path(A) of A is defined as follows: Vertices are X A with a tuple (x 1 , . . . , x δi ) ∈ R A being replaced by a directed path x 1 → x 2 → . . . → x δi (thus in this for this is a directed graph). For example this is used in [START_REF] Nešetřil | Duality theorems for finite structures (characterizing gaps and good characterizations)[END_REF] to classify the dualities.

4. Star selectors. We formulate this for a hypergraph (X, M): For an edge M ∈ M a star selector is any star with the vertex set M . A star selector of a hypergraph (X, M) is then the union of the edge sets of star selectors of the edges of M. This is not uniquely defined as we may get several graphs (with very different properties). But perhaps because of this flexibility this is often the best transformation. Let us give an example: For a hypergraph A ∈ C, we denote by Sel(A) the set of the star selectors of A and by Sel(C) we denote the set of all the function ζ : C → Graph such that ζ(A) ∈ Sel(A). We have then for example the following result (see Section 2.3 for the definition of G d):

Theorem 2. Let C be a class of hypergraphs. Then the following conditions are equivalent: We use all of these constructions according to what is most fitting for a particular result. In the context of sparse hierarchies of structures, the relationship of various models of relational structures is not yet clarified. Perhaps the situation is reminiscent to a long development of the Szemerédi regularity lemma for hypergraphs and finite structures, see e.g. [START_REF]Szemerédi lemma for the analyst[END_REF][START_REF] Tao | The dichotomy between structure and randomness, arithmetic progression, and the primes[END_REF][START_REF] Gowers | Hypergraph regularity and the multidimensional Szemerédi theorem[END_REF][START_REF]Regular partitions of hypergraphs: Regularity lemmas[END_REF].

1. ∀d ∈ N ∃ζ d ∈ Sel(C) : sup A∈C ω(ζ d (A) d) < ∞; 2. C is a S-
Yet another direction to extend the results for graphs to more general structures is to consider an edge version of low tree depth decomposition. This naturally generalizes to matroids [START_REF] Nešetřil | Generalized acyclic edge colorings and generalized arboricity[END_REF].

Homomorphism order. The central role (and indeed the leitmotiv)

in our paper is played by the simplification of the above categories. This takes the following form: Given structures A, B we write A ≤ B to denote the existence of a homomorphism f : A -→ B. The relation ≤ is clearly a quasiorder on Rel(∆) or Graph or Hyp. The relation ≤ is called homomorphism order which will be indicated as (Graph, ≤), (Rel(∆), ≤), (Hyp, ≤). The homomorphism order can be reduced to a partial order in two steps:

• First, we consider cores of all structures. A core is any minimal retract of a structure (this term was coined in [START_REF] Hell | Graphs and homomorphisms[END_REF]); • Then, we consider the isomorphism types of core structures. If a more precision is needed then we denote by [A] the isomorphism type determined by the structure A.

In most of the paper there is no danger of confusion and thus we also denote by (Graph, ≤), (Rel(∆), ≤), (Hyp, ≤) the corresponding partial orders of isomorphism types of the corresponding core structures.

The homomorphism order has spectacular properties, some of which will be reviewed here: Theorem 3. (Universality of the homomorphism order) For every countable partial order P there is an embedding of P into (Graph, ≤). Not only that, but a much smaller variety of graphs suffices: For every countable partial order P there is an embedding of P into the suborder of (Graph, ≤) induced by planar graphs with all degrees bounded by 3. This is a classical result proved in [START_REF] Hedrlín | On universal partly ordered sets and classes[END_REF]. The second part is much more recent and it presented a well known problem, see e.g. [START_REF] Nešetřil | Path homomorphisms[END_REF], which was finally proved by Jan Hubička and J. Nešetřil [START_REF]Universal partial order represented by means of oriented trees and other simple graphs[END_REF][START_REF]Finite paths are universal[END_REF]. Theorem 4. (Density of the homomorphism order) With "a few exceptions" the homomorphism order is dense. Explicitly, for most pairs A, B with A ≤ B and B ≤ A (with "a few exceptions", there exists

C such that A ≤ C ≤ B and B ≤ C ≤ A.
This result is proved in [START_REF] Nešetřil | Duality theorems for finite structures (characterizing gaps and good characterizations)[END_REF] (extending earlier result of [START_REF] Welzl | Color families are dense[END_REF] for undirected graphs). In fact, again with "a few exceptions", every interval in the homomorphism order is itself universal (an unpublished result; see [START_REF] Nešetřil | Aspects of structural cominatorics -graph homomorphisms and their use[END_REF]).

What are "few exceptions"? They are important and they are completely characterized. Basically the only exceptions to the density are induced by trees. More explicitly, a pair (A, B) of structures is called a gap in the homomorphism order if A ≤ B, B ≤ A and there is no C strictly in between A and B. One of the main results of [START_REF] Nešetřil | Duality theorems for finite structures (characterizing gaps and good characterizations)[END_REF] is that all gaps (A, B), B connected, in Rel(∆) are induced by trees. Explicitly, for every relational tree T there exists (uniquely determined) predecessor structure P (T) such that the pair P (T) ≤ T forms a gap. (Other gaps are not connected and they are also related to trees [START_REF] Nešetřil | Duality theorems for finite structures (characterizing gaps and good characterizations)[END_REF].) What is a relational tree? We can use above reductions. A relational tree is a structure such that its path graphs (as above) is (an orientation of) a tree.

The homomorphism order has the rich algebraic structure. There is a beautiful (and surprising) connection of gaps to the dual description of graph classes which goes under name homomorphism dualities (defined in [START_REF] Nešetřil | On classes of relations and graphs determined by subobjects and factorobjects[END_REF]). This can be outlined as follows (compare [START_REF] Hell | Graphs and homomorphisms[END_REF]):

A singleton duality is a pair of objects (F, D) with the following property: For every object A of the same type as (F, D) holds:

A -→ D if and only if F --→ A.
For undirected graphs there are just two trivial dualities. However already for oriented graphs we have infinitely many dualities and these dualities are important as they relate to the chromatic number of graphs (by means of Gallai -Hasse -Roy -Vitaver theorem, [START_REF]From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits[END_REF]). The notion of duality is motivated by algorithmic considerations and particularly the dual description of homomorphisms into a fixed template D by means of a simple obstacle F. It is the more than surprising that this simple notion is in one to one correspondence with the purely order-theoretic notion of a gap: Theorem 5. (Gaps and Dualities [START_REF] Nešetřil | Duality theorems for finite structures (characterizing gaps and good characterizations)[END_REF]) There is one to one correspondence between singleton dualities (F, D) and gap-pairs (P (A), A) where A is a connected structure.

In fact this characterization of dualities is of a categorical nature and it can be extended to the much more general situation of Heyting algebras [START_REF] Foniok | Dualities and dual pairs in heyting algebras[END_REF].

All these dualities are class dependent. They hold in the class of structures with a fixed signature (i.e. in classes Rel(∆)). This is also clear from yet another reformulation of the duality pair (F, D). First, let us define the class Forb(F) as the class of all structures (of a given signature) A for which there is no homomorphism F -→ A:

Forb(F) = {A : F --→ A}.
(Similarly we define Forb(F) for a finite set F of structures.) Now (F, D) is a duality pair if and only if the object D is the (finite) maximum of the class Forb(F) in the homomorphism order. This point of view is taken in [START_REF]Cuts and bounds, Discrete Mathematics, Structural Combinatorics -Combinatorial and Computational Aspects of Optimization[END_REF] and it allows to treat universal and generic structures together with dualities, [START_REF] Kun | NP for combinatorialists[END_REF][START_REF] Hubička | Homomorphism and embedding universal structures for restricted classes[END_REF]. In yet another interpretation every finite duality is the equation of two classes Forb(F) (for a finite set F) and CSP(D) defined as a principal ideal in the homomorphism order:

CSP(D) = {A : A -→ D}.
Let us note by passing that finite dualities (i.e. equations Forb(F) = CSP(D)) are exactly those Constraint Satisfaction Problems (i.e. membership problems for classes CSP(D), in this setting D is usually called template) which are first order definable: Only for duals of tree structures is the corresponding Constraint Satisfaction Problem decidable by a first order formula. This follows from [START_REF] Nešetřil | Duality theorems for finite structures (characterizing gaps and good characterizations)[END_REF] and [START_REF] Atserias | On digraph coloring problems and treewidth duality[END_REF].

In Section 9 we define more general notion of restricted dualities and prove that our sparse classes have all restricted dualities. We then go on by characterizing this phenomenon (see Theorem 18). Advancing this we include the schematic Figure which hods for any planar graph G:

PLANAR PLANAR
This was (in retrospect) one of our motivating examples [START_REF] Nešetřil | Colorings and homomorphisms of minor closed classes[END_REF][START_REF]Cuts and bounds, Discrete Mathematics, Structural Combinatorics -Combinatorial and Computational Aspects of Optimization[END_REF]. The homomorphism orders are fascinating structures with a rich algebraic and combinatorial contents.

Sparsity via Resolution in Time.

Let us start this section by considering undirected graphs.

As remarked earlier, the notion of a sparsity of graphs is a fuzzy notion. First it does not relate to any particular graph but rather to a set, or sequence, or a class of graphs. Secondly the notion should be (certainly from naive point of view) be invariant to some small changes of a graph. Third, to be a sparse graphs is clearly a global property and the property should be hereditary.

Combining these observations and motivated by numerous particular cases we are led to the following definitions:

For any graphs H and G and any integer d, the graph H is said to be a shallow minor of G at depth d ( [START_REF] Plotkin | Shallow excluded minors and improved graph decomposition[END_REF] attribute this notion, called then low depth minor to Ch. Leiserson and S. Toledo) if there exists a subset {x 1 , . . . , x p } of G and a collection of disjoint subsets V 1 , . . . , V p of vertices of G, each inducing a connected subgraph of G, such that x i ∈ V i , every vertex in V i is at distance at most d from x i in the subgraph of G induced by V i , and so that H is a subgraph of the graph obtained from G by contracting each V i into x i and removing loops and multiple edges (see Fig. 1).

G ∈ G 0 ⊆ G 1 ⊆ • • • ⊆ G d ⊆ . . . G ∞.
We extend this definition to arbitrary class of graphs C by:

C d = G∈C G d.
We have the following (time dependent) hierarchy of classes

C ⊆ C 0 ⊆ C 1 ⊆ • • • ⊆ C d ⊆ . . . C ∞.
We call this sequence minor resolution of the class C and denote it by C . Note that C 0 is the monotone closure of C and that C ∞ is the minor closed class generated by C. If an infinite class is not somewhere dense, it is nowhere dense.

It follows directly from the definition of the minor resolution that a class C is nowhere dense if and only if for every d the supremum of ω(G) for G ∈ C d is finite (here ω(G) is the the clique number of graph G, i.e. the maximal order of a complete graph in G). (It is perhaps surprising, as we shall see in Section 4.2, that nowhere dense classes may be defined by their independence number as well.)

For relational structures and hypergraphs we can define analogous notions. If an infinite class is not I-somewhere dense, it is I-nowhere dense.

For path-graphs and star selectors we first observe that our resolutions are defined by means of distances and this "symmetric" neighborhoods. After that we define the dichotomy for these two constructions as well (P -somewhere dense/Pnowhere dense and S-somewhere dense/S-nowhere dense). Although in many instances are these approaches equivalent in general they differ and it is convenient to use all these definitions simultaneously.

Trichotomy for Binary Structures

We consider graph models in this section. For general structures the situation is more complicated and although we get analogous results we need stronger results (particularly the subgraph counting presented in Section 4.3).

Classification by Edge Densities.

Let C be an infinite class of graphs and let f : C → R be a graph invariant. Let Inj(N, C) be the set of all injective mappings from N to C. Then we define:

lim sup G∈C f (G) = sup φ∈Inj(N,C) lim sup i→∞ f (φ(i))
Notice that lim sup G∈C f (G) always exist and is either a real number or ±∞.

Theorem 6 (Trichotomy theorem). Let C be an infinite class of graphs (asymptotically not all edgeless). Then the limit

dens(C ) = lim i→∞ lim sup G∈C i log G log |G|
may take only three values, namely 0, 1 and 2. Moreover, we have:

dens(C ) =      0, iff sup G∈C G < ∞, 0 or 1, iff C is nowhere dense, 2,
iff C is somewhere dense.

For a proof see [START_REF]On nowhere dense graphs[END_REF]. It can be seen easily that dens(C ) ≤ 0 if and only if the class C contains only graphs with at most k 0 edges. These essentially finite classes can be non-trivial. A prime example is the class of all core graphs with tree depth bounded (see Section 4.1 for the definition of the tree depth).

It is very interesting (and we feel surprising) that this theorem has a topological version which counts the edges in shallow subdivisions. (Recall that a graph G is a subdivision of a graph G if G arises from G by adding vertices (of degree 2) on edges of G.) Thus in the topological sense we have homeomorphic graphs: all edges of G are replaced by simple openly disjoint paths. If all these paths have length ≤ 2d + 1 we say that G is a d-shallow subdivision of G. Conversely, we say that H is topological shallow minor at depth d of a graph G if there exists a subgraph H of G such that H is a shallow subdivision of H at depth d. Having defined this we can proceed similarly as for the shallow minors and define the notion of topological minor resolution. For a proof of the topological version of Theorem 6 see [START_REF]On nowhere dense graphs[END_REF]. (This extends work of Zdeněk Dvořák [START_REF] Dvořák | Asymptotical structure of combinatorial objects[END_REF][START_REF]On forbidden subdivision characterizations of graph classes[END_REF].) Also, the property that there exists a critical value τ (C) at which the topological resolution stabilizes to Graph is equivalent to the existence of a critical value τ (C) at which the minor resolution stabilizes to Graph. Notice that, according to Theorem 6, the existence of a critical value τ (C) is equivalent to the existence of a value T (C) such that there exists > 0 with lim sup

G∈C T (C) log G log |G| = 1 + .
Moreover, the difference between τ (C) et T (C) is actually bounded by a function of (see Fig . 2).

lim sup However, for nowhere dense classes, the asymptotic behavior of the resolution varies. For instance, the class D 3 of graphs with maximum degree at most 3 is such that

G∈C x G |G| 2 1 1 + T (C) T (C) + k( ) x (log scale) τ (C) 1 + 2 2 -log(2(x -T (C)) + 1)
D 3 ∞ = Graph but D 3 ∞ = D 3 .
Why do we state this topological variant of shallow minors, when we then claim just analogous results? The main reason is that this connection is surprising and non-trivial. The fact that minors and topological minors lead to the same classification of classes is interesting in the context of graph-minor theory where minors and topological minors lead often to very different results (as demonstrated for example by Hajós and Hadwiger's conjectures), see [START_REF]On nowhere dense graphs[END_REF][START_REF]Structural properties of sparse graphs[END_REF] for more details.

Some Alternative Characterizations

We mention just 3 characterizations. Yet they should indicate the robustness of our dichotomy classification of classes.

Classification by Decomposition -Chromatic Numbers.

First we consider the graph case. The building blocks of our decompositions will be induced by trees.

A rooted forest is a disjoint union of rooted trees. The height of a vertex x in a rooted forest F is the number of vertices of the path from the root (of the tree to which x belongs to) to x and is noted height(x, F ). The height of F is the maximum height of the vertices of F . Let x, y be vertices of F . The vertex x is an ancestor of y in F if x belongs to the path linking y and the root of the tree of F to which y belongs to. The closure clos(F ) of a rooted forest F is the graph with vertex set V (F ) and edge set {{x, y} : x is an ancestor of y in F, x = y}. A rooted forest F defines a partial order on its set of vertices: x ≤ F y if x is an ancestor of y in F . The comparability graph of this partial order is obviously clos(F ).

The tree-depth td(G) of a graph G is the minimum height of a rooted forest F such that G ⊆ clos(F ) [START_REF]Tree depth, subgraph coloring and homomorphism bounds[END_REF] (see Fig 3) A principal property of the class of all graphs with td(G) ≤ k is that this class is finite when restricted to core graphs (or core structures). This holds more generally for colored graphs and for relational structures in general. This has also a number of consequences. For example the class of all graphs with td(G) ≤ k is well quasi ordered with respect to induced subgraph ordering. Nevertheless one should remark that the number of core graphs with td(G) ≤ k has an Ackermann growth.

In [START_REF]Tree depth, subgraph coloring and homomorphism bounds[END_REF] we introduced the following parametrized generalization of the chromatic number: for any integer p, χ p (G) denotes the minimum number of colors one shall use to color the vertices of G in such a way that for every subset I of at most p colors, the subgraph G I of G induced by the vertices with color in I has tree-depth at most |I|. Thus χ 1 is the usual chromatic number of a graph (i.e. no edge is monochromatic) and χ 2 is minimal coloring with the property that no path with 4 vertices gets less than 3 colors.

These generalized chromatic numbers characterize nowhere dense classes ( [START_REF]Grad and classes with bounded expansion II. algorithmic aspects[END_REF][START_REF]On nowhere dense graphs[END_REF]): Theorem 7. Let C be an infinite class of graphs. Then the following conditions are equivalent:

• C is nowhere dense,

• for every integer p, lim sup

G∈C log χ p (G) log |G| = 0
Thus any graph G in a (fixed) nowhere dense class C can be decomposed into a small number of classes such that the subgraphs induced by any ≤ p classes of the partition have components of only finitely many (homomorphism) types. Thus p is then parameter expressing the precision of such decomposition. Moreover such a decomposition can be found in almost linear number of steps. This has a number of algorithmic consequences which are not covered here, see ( [START_REF]Linear time low tree-width partitions and algorithmic consequences[END_REF][START_REF]Grad and classes with bounded expansion II. algorithmic aspects[END_REF]. Such a decomposition is called Low Tree Depth Decomposition (LTDD).

Let us return to structures. We formulate this time the result for G-nowhere dense classes. The Theorem 8. Let C be an infinite class of structures. Then the following conditions are equivalent:

• C is G-nowhere dense,

• for every integer p, lim sup

G∈Gf(C) log χ p (G) log |G| = 0
Of course we can define χ p (A) directly and it has a similar meaning as for graphs.

Classification by Independence.

The homomorphism preservation theorem [START_REF] Lyndon | Properties preserved under homomorphism[END_REF] states that a first-order formula is preserved under homomorphisms on all structures (finite and infinite) if and only if it is equivalent to an existential-positive formula. Answering a long-standing question in finite model theory [START_REF]Homomorphism closed vs. existential positive[END_REF], Ben Rossman proved [START_REF] Rossman | Homomorphism preservation theorems[END_REF] that the homomorphism preservation theorem remains valid when restricted to finite structures (unlike many other classical preservation theorems, including the Loś-Tarski theorem and Lyndon's positivity theorem). It is interesting to note that one of the main tools of Rossman's proof is the notion of tree depth (which corresponds to the quantifier depth). In the context of relativizations of this theorem to specific classes of structures Anuj Dawar [START_REF] Dawar | Finite model theory on tame classes of structures[END_REF] introduced the following notion of quasi-wideness:

Let d ≥ 1 be an integer. A subset A of vertices of a graph G is d-independent if the distance between any two distinct elements of A is strictly greater than d. Note that if we denote by α d (G) the maximum size of an d-independent set of G, then α 1 (G) is the usual independence number α(G) of graph G.

A graph G is quasi-wide if there is a function s : N → N such that for every integers d and m, every sufficiently big graph G ∈ C (i.e. of order at least F (d, m)) contains a subset S of size at most s = s(d) so that the graph α d (G -S) ≥ m.

The quasi-wide property is not hereditary. Thus we introduce the following, stronger version:

A graph G is uniformly quasi-wide if there is a function s : N → N such that for every integers d and m, every sufficiently big subset A of vertices of a graph G ∈ C (i.e. such that |A| ≥ F (d, m)) is such that G contains a subset S of size at most s = s(d) so that G -S contains a d-independent set of size at least m included in A.

It appears that uniform quasi-wideness is strongly related to our classification:

Theorem 9. Let C be an infinite class of graphs. Then the following conditions are equivalent:

• C is nowhere dense, • the hereditary closure of C is quasi-wide, • C is uniformly quasi-wide.
This is a non-trivial results with several consequences, see [START_REF]First order properties on nowhere dense structures[END_REF]. Combined with Low Tree Depth Decomposition one deduces (via an appropriate data structure) that the model checking problems for first order formulas is Fixed Parameter Tractable for a monotone class C of structures if and only if the class C is nowhere dense (assuming standard hardness assumption in parametrized complexity). Thus the nowhere dense classes can be defined by the validity of arithmetic meta-theorems, see [START_REF] Dawar | Parametrized complexity of first-order logic[END_REF][START_REF] Dvořák | Finding subgraphs and testing FOL properties in sparse graphs[END_REF] for graph case. For structures we can use I-Nowhere dense definition.

Classification by Counting. The trichotomy theorem (Theorem 2)

is related to counting the numbers of copies of K 2 in a graph. This may be extended (using the decomposition theorem) if we consider homomorphism or induced copies of any non-trivial graph F . (Recall that hom(F, G) denotes the number of homomorphisms from F to G and that #F ⊆ G denotes the number of induced subgraphs of G which are isomorphic to F .) Theorem 10. Let F be a (connected) non trivial graph (i.e. with at least one edge). Then the following limits

lim i→∞ lim sup G∈C i log hom(F, G) log |G| , lim i→∞ lim sup G∈C i log hom(F, G) log |G| , lim i→∞ lim sup G∈C i log #F ⊆ G log |G| , and
lim i→∞ lim sup G∈C i log #F ⊆ G log |G|
can only take the values -∞, 0, 1, . . . , α(F ) and |F |, where α(F ) stands for the independence number of F . Moreover, C is somewhere dense if and only if the limit is |F |.

For a proof, see [START_REF]How many F's are there in G?[END_REF]. There is more to this than meets the eye. The recent theory of graph limits developed by Laci Lovász with his coauthors, see e.g. [START_REF] Lovász | A forbidden subgraph characterization of Gauss codes[END_REF][START_REF] Lovász | Generalized quasirandom graphs[END_REF][START_REF]Szemerédi lemma for the analyst[END_REF][START_REF] Lovász | Limits of dense graph sequences[END_REF] deals with counting of homomorphisms from small graphs, or alternatively, with probabilities that a random map is a homomorphism. In this context the last alternative description is very pleasing as it may be seen as bridging the gap between these approaches and an approach based on the analysis of the homomorphism order, i.e. with existence of homomorphism (see [START_REF]From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits[END_REF]). For structures is the situation more involved and we do not state it here.

There are other alternative descriptions of nowhere dense -somewhere dense dichotomy (related to on-line colorings and game chromatic numbers). We refer to the forthcoming book [START_REF]Sparsity (graphs, structures, and algorithms[END_REF]. From manyfold applications we mention (in the next two sections) only two recent ones (and refer to e.g. [START_REF]Sparsity (graphs, structures, and algorithms[END_REF][START_REF]Linear time low tree-width partitions and algorithmic consequences[END_REF][START_REF]First order properties on nowhere dense structures[END_REF][START_REF] Nešetřil | Characterizations and examples of graph classes with bounded expansion[END_REF] instead).

Vertex Separators

Let G be a graph of order n. Recall that an α-vertex separator of G is a subset S of vertices such that every connected component of G -S contains at most αn vertices.

Sub-exponential ω-expansion. A celebrated theorem of Lipton

and Tarjan [START_REF] Lipton | A separator theorem for planar graphs[END_REF] states that any planar graph has a separator of size O( √ n). Alon, Seymour and Thomas [START_REF] Alon | A separator theorem for graphs with excluded minor and its applications[END_REF] showed that excluding K h as a minor ensures the existence of a separator of size at most O(h 3/2 √ n). Gilbert, Hutchinson, and Tarjan [START_REF] Gilbert | A separator theorem for graphs of bounded genus[END_REF] further proved that graphs with genus g have a separator of size O( √ gn) (this result is optimal). Plotkin et al. [START_REF] Plotkin | Shallow excluded minors and improved graph decomposition[END_REF] introduced the concept of limited-depth minor exclusion and have shown that exclusion of small limited-depth minors implies the existence of a small separator. Precisely, Plotkin et al. prove in [START_REF] Plotkin | Shallow excluded minors and improved graph decomposition[END_REF] that any graph excluding K h as a depth l minor (i.e. any graph G such that K h ∈ G l) has a separator of size O(lh 2 log n + n/l) hence proving that excluding a K h minor ensures the existence of a separator of size O(h √ n log n).

We combine this with the following variant of expansion: The ω-expansion of a class C is the mapping i → sup

G∈C i ω(G),
where ω(G) stands for the clique number of G, i.e. the order of the largest complete subgraph of G. Notice that a class has bounded ω-expansion if and only if it is nowhere dense.

A class C has sub-exponential ω-expansion if lim sup i→∞ sup G∈C i log ω(G) i = 0.
Theorem 11. Let C be a class of graphs with sub-exponential ω-expansion.

Then the graphs of order n in C have separators of size s(n) = o(n) which may be computed in time O(ns(n)) = o(n 2 ). . As random cubic graphs almost surely have bisection width at least 0.101n [START_REF] Kostochka | On bounds of the bisection width of cubic graphs[END_REF], they have almost surely no separator of size smaller than n/20 It follows that if log f (x) = (log 2)x, the graphs have no sublinear separators any more. This shows the optimality of Theorem 11.

6. Property Testing and Weak Hyperfiniteness 6.1. Property testing. Property testing has been introduced by Blum, Luby and Rubinfeld [START_REF] Blum | Self-testing/correcting with applications to numerical problems[END_REF] and Rubinfeld and Sudan [START_REF] Rubinfeld | Robust characterization of polynomials with applications to program testing[END_REF] (in the context of program testing), and by Arora, Lund, Motwani, Sudan, and M. Szegedy [START_REF] Arora | Proof verification and the hardness of approximation problems[END_REF] and Arora and Safra [START_REF] Arora | Probabilistic checking of proofs: a new characterization of NP[END_REF] (in the context of probabilistically checkable proofs). Testing graph properties was first investigated by Goldreich, Goldwasser, and Ron [START_REF] Goldreich | Property testing and its connection to learning and approximation[END_REF]. ¿From a "mathematical" point of view, the main ingredients of property testing are:

• a random sampling of the large structure, • a suitable notion of distance between objects.

Let P be a class of graphs (called graph property in this context). A graph G is said to have property P if G ∈ P; it is said to be -far for satisfying P if no graph at distance at most from G satisfies P. A testing algorithm (or tester) for graph property P and accuracy is an algorithm that distinguishes with probability at least 2/3 between graphs satisfying P from graphs that are -far from satisfying it. More precisely, the property testing algorithm

• should accept with probability at least 2/3 every input graph that belongs to P, • should reject with probability at least 2/3 every input graph that has distance more than from any graph in P, i.e. if its -far from satisfying P.

A graph property P is testable if for any > 0, there is a constant time randomized algorithm that can distinguish with high probability between graphs satisfying P from those that are -far from satisfying it. One should notice that the introduction of the parameter will make some properties impossible to distinguish. Precisely, two properties P and Q are indistinguishable if for every > 0 there exists N = N ( ) such that:

• for every graph G ∈ P with order at least N there exists H ∈ Q with the same order such that dist(G, H) < , • for every graph H ∈ Q with order at least N there exists G ∈ P with the same order such that dist(G, H) < .

As proved in [START_REF] Alon | Efficient testing of large graphs[END_REF] (in the context of dense graphs, but easily extended to the general case), if two properties are indistinguishable then either they are both testable or none of them is testable. Dense graphs (and more generally structures) seem to be well understood and we refer here to a spectacular chain of results [START_REF]A characterization of the (natural) graph properties testable with one-sided error[END_REF][START_REF] Alon | A characterization of the (natural) graph properties testable with one-sided error[END_REF][START_REF]Generalizations of the removal lemma[END_REF][START_REF] Rödl | Property testing in hypergraphs and the removable lemma[END_REF][START_REF] Avart | Every monotone 3-graph property is testable[END_REF][START_REF] Ishigami | Removal lemma for infinitely-many forbidden hypergraphs and property testing[END_REF][START_REF] Austin | On the testability and repair of hereditary hypergraph properties[END_REF] to name just a sample of this development (which starts with Szemerédi regularity lemma [START_REF] Szemerédi | Regular partitions of graphs[END_REF]). For sparse graphs the situation seems to be much less understood. Extending earlier results [START_REF] Goldreich | Property testing in bounded-degree graphs[END_REF][START_REF] Benjamini | Recurrence of distibutional limits of finite planar graphs[END_REF][START_REF] Aldous | Processes on unimodular random networks[END_REF][START_REF] Schramm | Hyperfinite graph limits[END_REF] most general result is using the notion hyperfiniteness: A class C of (finite) graphs is hyperfinite if for every positive real > 0 there exists a positive integer K( ) such that every graph G ∈ C has a subset of at most |G| edges whose deletion leaves no connected component of order greater than K( ) (see e.g. [START_REF] Lipton | Applications of a planar separator theorem[END_REF][START_REF] Elek | The combinatorial cost[END_REF][START_REF]L 2 -spectral invariants and convergent sequences of finite graphs[END_REF][START_REF]A regularity lemma for bounded degree graphs and its applications: Parameter testing and infinite volume limits[END_REF][START_REF] Hassidim | Local graph partitions for approximation and testing[END_REF].

In [START_REF] Benjamini | Every minor-closed property of sparse graphs testable[END_REF], Benjamini, Schramm and Shapira showed that every minor-closed graph property can be tested with a constant number of queries in the bounded degree model. For instance, planarity is testable in the bounded degree model. Actually, they prove a much stronger theorem: Theorem 12 ( [START_REF] Benjamini | Every minor-closed property of sparse graphs testable[END_REF]). Every monotone hyperfinite graph property is testable.

Using a detailed analysis of bounded expansion classes with an sub-exponential growth we can extend the range of applications of this result.

Weakly hyperfinite classes. A class C of graphs is weakly hyperfinite

if for any > 0 there exists K( ) such that every G ∈ C has a subset of at most |G| vertices whose deletion leaves no connected component of order greater than K.

Although it is obvious that a monotone class of graphs needs to have bounded degrees in order to be hyperfinite, weakly hyperfinite classes may have unbounded degrees. Moreover, it is straightforward that any hyperfinite class is also weakly hyperfinite.

The relation between the two notions will be made precise by the following result:

Theorem 13. For a positive integer D, denote by ∆ D the class of the graphs having maximum degree at most D. Let C be a monotone class of graphs with bounded average degree.

The class C is weakly hyperfinite if and only if for every integer D the class C ∩ ∆ D is hyperfinite.

A key advantage of the notion of weak hyperfinite class is its connection with the existence of sublinear vertex separators. For space limitations we leave out details and we just state the following: Theorem 14. Every monotone class of graphs with sublinear vertex separators is weakly hyperfinite. Consequently we have: Let C be a monotone class of graphs with sublinear vertex-separators and bounded average degree and let D be a positive integer. Then the subclass of C including those graphs in C which have maximum degree at most D is hyperfinite.

Combining with our results about vertex separators we arrive to the following: Theorem 15. Let P be a monotone class of graphs with sub-exponential ω-expansion.

Then the property G ∈ P is testable in the bounded degree model.

Selected Examples

1. Classical Sparse Classes. Fig. 4 shows the inclusion map of some important hereditary nowhere dense classes which were studied in combinatorial as well as algorithmic context.

= 2π -1/2 (d/2)! 1/d ∼ 2d/(eπ).
A simplicial graph of aspect ratio α means a simplicial graph coming from a complex in which every d-simplex has aspect ratio at most α.

Classes of simplicial graphs with bounded aspect ratio exclude big shallow complete minors as proved by Plotkin, Rao and Smith [START_REF] Plotkin | Shallow excluded minors and improved graph decomposition[END_REF]. It follows that such classes are nowhere dense.

High Girth Graphs.

A standard example of a monotone nowhere dense class of graphs is the class of the graphs whose maximum degree does not exceed some function of the girth, i.e. B φ = {G : ∆(G) ≤ φ(girth(G))}.

Such classes may have average degree as big as n o(1) as a consequence (see for instance [START_REF] Chandran | A high girth graph construction[END_REF]): For every positive integer n and an "expected degree" k (where k < n/3), there exists a graph G of order n, size nk/2 , vertex degrees in {k-1, k, k+1} and whose girth g is such that g > log k (n) + O(1). Hence, for any decreasing function f : R + → R + such that lim x→∞ f (x) = 0 there exists a constant C such that the class B φ defined by φ(x) = (f -1 (1/x) + C) 1/x contains graphs with order n, girth at least 1/f (n) and degrees k ± 1 with k ≈ n f (n) . Classes with bounded expansion include [START_REF] Nešetřil | Characterizations and examples of graph classes with bounded expansion[END_REF] • classes excluding a topological minor (this includes classes excluding a minor, like planar graphs, and also classes with bounded maximum degree), • k-non-repetitively colorable graphs (see [START_REF] Grytczuk | Nonrepetitive colorings of graphs-a survey[END_REF] for more details on non-repetitive colorings), • geometrically defined classes like classes with bounded stack number and classes with bounded queue number,

Bounded Expansion Classes

• classes of highly subdivided graphs (allowing to construct examples of classes with arbitrary non-decreasing expansion function), • sparse random graphs (in the sense that for every positive real d there exists a class R d with bounded expansion such that random graphs with edge probability d/n asymptotically almost surely belong to R d ).

For an extensive study of bounded expansion classes we refer the reader to [START_REF]Grad and classes with bounded expansion I. decompositions[END_REF], [START_REF]Grad and classes with bounded expansion II. algorithmic aspects[END_REF], [START_REF]Grad and classes with bounded expansion III. restricted graph homomorphism dualities[END_REF], [START_REF] Dvořák | Asymptotical structure of combinatorial objects[END_REF], [START_REF]On forbidden subdivision characterizations of graph classes[END_REF], [START_REF] Nešetřil | Characterizations and examples of graph classes with bounded expansion[END_REF].

(See [START_REF] Nešetřil | Characterizations and examples of graph classes with bounded expansion[END_REF] for the definition of stack and queue numbers. This paper contains further examples of bounded expansion classes.)

As for nowhere dense classes, several equivalent characterizations exist for classes with bounded expansion: Theorem 16. Let C be a class of graphs. The following properties are equivalent:

• C has bounded expansion, • for every integer p, sup G∈C χ p (G) < ∞.

Thus any graph G in a (fixed) bounded expansion class C can be decomposed into a fixed number N p (G) of classes such that the subgraphs induced by any ≤ p classes of the partition have components of only finitely many (homomorphism) types. Thus p is then parameter expressing the precision of such decomposition. Moreover such decomposition can be found in a linear number of steps. Not surprisingly, this has a number of algorithmic consequences ( [START_REF]Linear time low tree-width partitions and algorithmic consequences[END_REF][START_REF]Grad and classes with bounded expansion II. algorithmic aspects[END_REF]. Such a decomposition is called Low Tree Depth Decomposition and it was described explicitely in the Introduction.

Restricted Dualities -a Characterization

In the Introduction we described homomorphism dualities for general relational systems. Clearly if we restrict the universe of the considered structures G then we can expect more "dual phenomena". In such cases we speak about restricted dualities. Explicitly, a (singleton) Crestricted duality is formed by a pair (F, D) such that for every structure A ∈ C holds:

F --→ A ⇐⇒ A -→ D.
. Note that we do not assume that D ∈ C. In the interpretation of the homomorphism order this just amounts to Forb(F) ∩ C = CSP(D) ∩ C.

In the extremal case that for every connected F ∈ C there exists D F such that F, D F form a C-restricted duality we say that C has all restricted dualities [START_REF]Grad and classes with bounded expansion III. restricted graph homomorphism dualities[END_REF].

These two examples actually fit to a much more a general setting which has been proved by [START_REF]Grad and classes with bounded expansion III. restricted graph homomorphism dualities[END_REF]: Theorem 17. Every class of structures with G-bounded expansion has all restricted dualities.

Explicitly: For every bounded expansion class C and for any finite set F = {F 1 , F 2 , . . . , F t } of connected graphs there exists a structure D F such that D F ∈ Forb(F and A -→ D F for every A ∈ C and A ∈ Forb(F).

A characterization of classes with all restricted dualities was not known until recently (see e.g. [START_REF]Structural properties of sparse graphs[END_REF]). One can deduce such a characterization using the following notions (related to the completion of the homomorphism order): Given two structures A, B we define their distance dist(A, B) as 2 -L where L is the minimal order |C| of a structure C which distinguishes A and B either from left or right. This has the following meaning: distinguishing from left means that either C ≤ A and C ≤ B or C ≤ A and C ≤ B; similarly, distinguishing from right means that either A ≤ C and B ≤ C or A ≤ C and B ≤ C. dist(A, B) is an ultrametric on the class Rel(∆) which can be used to define the completion of the homomorphism order. This completion has interesting properties particularly with respect to dualities (see [START_REF]From sparse graphs to nowhere dense structures: Decompositions, independence, dualities and limits[END_REF]). Let us just state here the following:

For a structure A and a real > 0, define φ (A) as a minimum order of a structure B such that A → B and dist(A, B) ≤ (we arbitrarily choose between those structures which have these properties, by using, for instance, some arbitrary linear order on Rel(∆); such structure B we can call -retract of A). Theorem 18. Let C be a class of structures. Then C has all restricted dualities if and only if for every > 0 we have sup A∈C φ (A) < ∞.

Moreover, for every connected structure F, there is a sequence D t (F) ← D t+1 (F) ← . . . of duals of F relative to C which converges to sup(C + ∩ Forb(F)), where C + denotes the closure of C by all finite disjoint unions of structures in C.

  nowhere dense class of hypergraphs, meaning that there exists ζ ∈ Sel(C) such that ζ(C) is a nowhere dense class of graphs; 3. ∃ζ ∈ Sel(C) ∀d ∈ N : sup A∈C ω(ζ(A) d) < ∞.

Figure 1 .

 1 Figure 1. A shallow minor of depth r of a graph G is a simple subgraph of a minor of G obtained by contracting vertex disjoints subgraphs with radius at most r The set of all shallow minors of G at depth d is denoted by G d. In particular, G 0 is the set of all subgraphs of G. Hence we have the following non decreasing

2. 4 .

 4 The Nowhere Dense -Somewhere Dense Dichotomy. The minor resolution of a class naturally leads to a classification of general classes and to their interesting properties. The following are the key definitions of this paper: Definition 1. (The Nowhere Dense -Somewhere Dense Dichotomy) An infinite class of graphs C is somewhere dense if there exists an integer d such that C d = Graph. Thus C is somewhere dense if every graph is a bounded depth shallow minor of a graph in C. In other words: we get all graphs in a fixed time.

Definition 2 .

 2 (The Nowhere Dense -Somewhere Dense Dichotomy via Gaifman) An infinite class of structures C is G-somewhere dense if the class Gf(C) of all Gaifman graphs of structures in C is somewhere dense. In other words: C is somewhere dense if every graph is a bounded depth shallow minor of the Gaifman graph Gf(A) of a structure A ∈ C.If an infinite class is not G-somewhere dense, it is G-nowhere dense. Definition 3. (The Nowhere Dense -Somewhere Dense Dichotomy via Incidence) An infinite class of structures C is I-somewhere dense if the class Inc(C) of all incidence graphs of structures in C is somewhere dense. In other words: C is somewhere dense if every graph is a bounded depth shallow minor of the incidence graph Inc(A) of a structure A ∈ C.

Figure 2 .

 2 Figure 2. Evolution of the upper logarithmic density dens(C ) of the topological resolution of a typical somewhere dense class C

  .

Figure 3 .

 3 Figure 3. The tree-depth of the 3 × 3 grid is 4.

Figure 4 .

 4 Figure 4. Inclusion map of some important hereditary nowhere dense classes.

2 .

 2 Simplicial Graphs. A k-dimensional simplex, or k-simplex, is the convex hull of k + 1 affinely independent points in R d space. A d-dimensional simplicial complex is a collection of k-simplexes, k ≤ d, closed under sub-simplex and intersection. For example, a 3-dimensional simplicial complex is a collection of cells (3-simplexes), faces (2-simplexes), edges (1-simplexes) and vertices (0-simplexes). A d-dimensional simplicial graph is the collection of edges and vertices of a d-dimensional simplicial complex. The aspect ratio of a body is its diameter divided dth root of its volume[START_REF] Miller | Geometric separators for finite-element meshes[END_REF]. The volume of a regular dsimplex, d-cube, and d-ball of unit diameter are respectively 2 -d/2 √ d + 1/d!, d -d/2 and 2 -d π d/2 /(d/2)!. Hence the aspect ratios of a d-simplex, d-cube, and d-ball are respectively α s = 2 1/2 (d!) 1/d (d + 1) -1/(2d) ∼ √ 2d/e, α c = √ d, and α b

A

  specific example of classes which are nowhere dense are classes with bounded expansion. These classes have been introduced in [64]. A class C has bounded expansion if there exists a function f : N → R (called expansion function) such that ∀d ∈ N sup G∈C d G |G| ≤ f (d). The value sup G∈C d G |G| is denoted by ∇ d (C) and, in the particular case of a single element class {G}, ∇ d (G) is called the greatest reduced average density (grad) of G of rank d.

Sparse Combinatorial Structures: Classification and Applications

* Supported by grant 1M0545 of the Czech Ministry of Education