Jean-Florent Raymond
email: jean-florent.raymond@mimuw.edu.pl

Dimitrios M Thilikos

Recent techniques and results on the Erdős-Pósa property

Keywords: Erdős-Pósa property, min-max theorems, tree decompositions, tree partitions, girth, graph minors, topological minors, graph immersions

Several min-max relations in graph theory can be expressed in the framework of the Erdős-Pósa property. Typically, this property reveals a connection between packing and covering problems on graphs. We describe some recent techniques for proving this property that are related to tree-like decompositions. We also provide an unified presentation of the current state of the art on this topic.

Introduction

A considerable part of combinatorics has been developed around min-max theorems. Min-max theorems usually identify dualities between certain objects in graphs, hypergraphs, and other combinatorial structures. The target is to prove that the absence of the primal object implies the presence of the dual one and vice versa.

A classic example of such a duality is Menger's theorem: the primal concept is the existence of k internally disjoint paths between two vertex sets S and T of a graph G, while the dual concept is a collection of k vertices that intersect all (S, T )-paths. Another example is Kőnig's theorem where the primal notion is the existence of a matching with k edges in a bipartite graph and the dual one is the existence of a vertex cover of size k. It is also known that, in case of general graphs, this duality becomes an approximate one, i.e., a vertex cover of size 2k. In both aforementioned examples, the duality relates the notions of packing and covering of a collection C of combinatorial objects of a graph. In Menger's theorem C consists of all (S, T )-paths of G while in Kőnig's theorem C is the set of all edges of G. That way, both aforementioned min-max theorems can be stated, for some class of graphs G (called host class) and some gap function f : N → N, as follows:

For every graph G in G, either G contains k-vertex disjoint objects in C or it contains f (k) vertices intersecting all objects in C that appear in G.

Clearly, for the case of Menger's theorem the host class is the class of all graphs while in the case of Kőnig's theorem the host class is restricted to the class of bipartite graphs. In both cases the derived duality is an exact one in the sense that f is the identity function. However, this is not the case if we want to extend the duality of Kőnig's theorem in the case of all graphs, where we can consider f : k → 2k (i.e., we have an approximate duality).

One of the most celebrated results about packing/covering dualities was obtained by Paul Erdős and Lajos Pósa in 1965 where the object to cover and pack was the set of all cycles of G [START_REF] Erdős | On independent circuits contained in a graph[END_REF]. In this case the host class contains all graphs, while f : k → O(k • log k). Moreover, Erdős and Pósa proved that this gap is optimal in the sense that it cannot be improved to a function f : k → o(k • log k). This result motivated a long line of research for min-max dualities that are exact or approximate. Since then, a multitude of results on the Erdős-Pósa property have appeared for several combinatorial objects, including extensions to digraphs [LY78, Sey96, RRST96, HM13, GT11], rooted graphs [KK15, PW12, Joo14, BJS14], labeled graphs [START_REF] Kawarabayashi | Non-zero disjoint cycles in highly connected group labelled graphs[END_REF], signed graphs [START_REF] Hochstättler | Two disjoint negative cycles in a signed graph[END_REF][START_REF] Aracena | Positive and negative circuits in discrete neural networks[END_REF], hypergraphs [START_REF] Alon | Covering a hypergraph of subgraphs[END_REF][START_REF] Bousquet | Hitting sets: VC-dimension and Multicut[END_REF][START_REF] Bousquet | Vc-dimension and Erdős-Pósa property[END_REF], matroids [START_REF] Geelen | The Erdős-Pósa property for matroid circuits[END_REF], and other combinatorial structures [START_REF] Gyárfás | A Helly-type problem in trees[END_REF] (see [START_REF] Reed | Tree width and tangles: A new connectivity measure and some applications[END_REF] for a survey on this topic). Also it is worth to stress that Erdős-Pósa dualities have been useful in more applied domains. For example, in bioinformatics, they were useful for upper-bounding the number of fixed-points of a boolean networks [START_REF] Aracena | Maximum number of fixed points in regulatory boolean networks[END_REF][START_REF] Aracena | Positive and negative circuits in discrete neural networks[END_REF][START_REF] Aracena | Number of fixed points and disjoint cycles in monotone Boolean networks[END_REF].

The purpose of this paper is twofold. We first describe some recent techniques for proving Erdős-Pósa-type results, mainly based on techniques related to tree-like decompositions of graphs (Section 3) and the parameter of girth (Section 4). We focused our presentation to the description of general frameworks that, we believe, might be useful for further investigations. In Section 5, we present negative results on classes defined by containment relations. Lastly, in Section 6, we provide an extensive update of results on the Erdős-Pósa property, reflecting the current progress on this vibrant area of graph theory.

Definitions

Unless otherwise mentioned, graphs in this paper are finite, undirected, do not have loops and they may have multiple edges. We call a graph nontrivial if it contains at least one edge. We denote by V (G) and E(G) the vertex and edge sets of a graph G, respectively, and we set |G| = |V (G)| and G = |E(G)| (counting multiplicities). For every set X of vertices of a graph G, the subgraph of G induced by X, that we write G[X], is the graph X, E ∩ X 2 . For every set X of vertices (resp. edges), we define G \ X as the graph G[V (G) \ X] (resp. (V (G), E(G) \ X)). The degree of a vertex v of a graph G, that we write deg G (v) is the number of vertices adjacent to v in G. We drop the subscript when there is no ambiguity.

For x ∈ {v, e}, and G a graph, let

A x (G) = V (G) if x = v and A x (G) = E(G) if x = e.
In this sense we use symbols v and e in order to distinguish the vertex and the edge variants of the properties/parameters that we are dealing with. A graph is subcubic its maximum degree is bounded by 3. For every t ∈ N, we denote by θ t the graph with two vertices and t edges.

Local operations. The operation of contracting an edge {x, y} in a graph G introduces a new vertex v xy and makes it adjacent with all neighbors of x and y and then deletes x and y. The operation of lifting a pair of edges {x, y}, {y, z} in a graph G increases by one the multiplicity of the edge {x, z} (or introduces this edge if it does not exist) and then reduces by one the multiplicities of {x, y} and {y, x}.

Partial orders on graphs. Given two graphs H and G, we say that H is an induced subgraph of G if H can be obtained from G after removing vertices. Additionally, H is a subgraph of G if it can be obtained by some induced subgraph of G after removing edges. We also say that H is a minor (resp. topological minor) of G if it can be obtained by some subgraph of G after contracting edges (after contracting edges with some endpoint of degree at most 2). Finally, we say that a graph H is an immersion of a graph G if it can be obtained from some subgraph of G after lifting pairs of edges that share some common endpoint.

Given a graph H, we denote by M(H), T (H), I(H) the class of all graphs that contain H as a minor, topological minor, or immersion respectively.

Packings and covers. Let H be a family of graphs and let x ∈ {v, e}. An x-H-cover of G is a set C ⊆ A x (G) such that G \ C does not contain any subgraph isomorphic to a member of H. An x-H-packing in G is a collection of x-disjoint subgraphs of G, each being isomorphic to some graph of H.

We denote by x-pack H (G) the maximum size of an x-H-packing and by x-cover H (G) the minimum size of an x-H-cover in G. Clearly, by definition, it always hold that x-pack H (G) ≤ x-cover H (G), for every graph G.

The Erdős-Pósa property. Let G and H be two graph classes, and let x ∈ {v, e}. We refer to G as the host graph class and by H as the guest graph class. We say that H has the x-Erdős-Pósa property for G if there is a function f : N → N such that the following holds:

∀G ∈ G, x-cover H (G) ≤ f (x-pack H (G)).
Any function f satisfying the above inequality is called a gap of the x-Erdős-Pósa property of H for G. When a class of graphs has the x-Erdős-Pósa property for the class of finite graphs, we simply say that it has the x-Erdős-Pósa property.

Rooted trees. A rooted tree is a pair (T, s) where T is a tree and s ∈ V (T ) is a vertex referred to as the root. Given a vertex x ∈ V (T ), the descendants of x in (T, s), denoted by desc (T,s) (x), is the set containing each vertex w such that the unique path from w to s in T contains x. If y is a descendant of x and is adjacent to x, then it is a child of x.

Tree partitions. A tree partition of a graph G is a pair D = (X , T ) where T is a tree and

X = {X t } t∈V (T ) is a partition of V (G) such that either |T | = 1 or for every {x, y} ∈ E(G), there exists an edge {t, t } ∈ E(T ) where {x, y} ⊆ X t ∪ X t . Given an edge f = {t, t } ∈ E(T ),
we define E f as the set of edges with one endpoint in X t and the other in X t . The width of D is defined as

max{max{|X t |} t∈V (T ) , max{ G[X t ] } t∈V (T ) , max{|E f |} f ∈E(T ) }.
The tree partition width of G is the minimum width over all tree partitions of G and will be denoted by tpw(G). Tree partitions have been introduced in [START_REF] Seese | Tree-partite graphs and the complexity of algorithms[END_REF] (see also [START_REF] Halin | Tree-partitions of infinite graphs[END_REF]) and tree partition width has been defined for simple graphs in [START_REF] Ding | On tree-partitions of graphs[END_REF]. The extension of this definition for multigraphs is due to [START_REF] Chatzidimitriou | (log OP T )-approximation for covering and packing minor models of θ r[END_REF].

A rooted tree partition of a graph G is a triple D = (X , T, s) where (T, s) is a rooted tree and (X , T ) is a tree partition of G.

Tree decompositions. A tree decomposition of a graph G is a pair (T, X ), where T is a tree and X is a family {X t } t∈V (T ) of subsets of V (G) (called bags) indexed by elements of V (T ), such that the following holds

(i) t∈V (T ) X t = V (G);
(ii) for every edge e of G there is an element of X containing both ends of e;

(iii) for every v ∈ V (G), the subgraph of T induced by {t ∈ V (T ), v ∈ X t } is connected.
The width of a tree decomposition (T, X ) is defined as equal to max t∈V (T ) |X t | -1. The treewidth of G, written tw(G), is the minimum width of any of its tree decompositions.

The Erdős-Pósa property from graph decompositions

Let H be a graph class, p be a graph parameter, and x ∈ {v, e}. We say that a function

f : N ≥0 → N ≥0 is a ceiling for the triple (p, H, x) if for every graph G, p(G) ≤ f (x-pack H (G)).
Intuitively, there is a ceiling for the triple (p, H, x) if a large value of p on a graph forces a large x-packing of elements of H.

Given a graph parameter p and an integer k, we denote

G p≤k = {G, p(G) ≤ k}.
Theorem 3.1. Let H be a class of graphs, x ∈ {v, e}, p be a graph parameter, let f : N → N be a function and let h r : N → N be a function, for every r ∈ N. Suppose that the following two conditions hold:

A. f is a ceiling for the triple (p, H, x);

B. for every r ∈ N, H has the x-Erdős-Pósa property for G p≤r with gap h r ;

then H has the x-Erdős-Pósa property with gap k → h f (k) (k).

Proof. Let G be a graph and let k = x-pack H (G). We have p(G) ≤ f (k), by definition of a ceiling. Therefore, G ∈ G p≤f (k) , and thus x-cover

H (G) ≤ h f (k) (k).
Theorem 3.1 will be used as a master theorem for the results of this section.

Vertex version and tree decompositions

In a breakthrough paper [START_REF] Chekuri | Large-treewidth graph decompositions and applications[END_REF], Chekuri and Chuzhoy proved that every graph of large treewidth can be partitioned into several subgraphs of large treewidth, with a polynomial dependency between the treewidth of the original graph, the one of the subgraphs, and the number of subgraphs. In particular they proved the next result.

Theorem 3.2 ([CC13a, Theorem 1.1]). Let G be a graph with tw(G) = k, and let h, r be two integers with hr 2 ≤ k/ polylog k. Then there is a partition G 1 , . . . , G h of G into vertex-disjoint subgraphs such that tw(G i ) ≥ r for every i ∈ {1, . . . , h}.

Besides, the results in [START_REF] Chekuri | Polynomial Bounds for the Grid-Minor Theorem[END_REF] provide a polynomial bound for the grid exclusion theorem. The (p × q)-grid (for p, q ∈ N) is the graph with vertex set {1, . . . , p} × {1, . . . , q} and edge set {{(i, j), (i , j )}, |i -i | + |j -j | = 1}.

Theorem 3.3 ([CC13c, Theorem 1.1]).

There is constant δ such that every graph of treewidth k contains as a minor a (Ω(k δ ) × Ω(k δ ))-grid.

As every planar graph G is a minor of the every (p × p)-grid for p = |G| + 2 G ( [RST94, 1.5]), these two results can be combined to give the following polynomial ceiling for planar graphs.

Corollary 3.4 (see also the proof of [CC13a, Theorem 5.4]). There is a function 1) such that, for every planar graph H on h edges, f h is a ceiling for the triple (tw, M(H), v).

f h (k) = h O(1) • k • (log k) O(
Indeed, according to Theorem 3.2, every graph of large treewidth can be partitioned into many disjoint subgraphs each with treewidth large enough (i.e. polynomial, according to Theorem 3.3) to force a large grid as a minor, which in turn contains the desired planar graph.

A function f : R → R is said to be superadditive if f (x) + f (y) ≤ f (x + y) for every pair x, y of positive reals. The following argument has been first used in [START_REF] Fedor | Strengthening Erdős-Pósa property for minor-closed graph classes[END_REF] (see also [START_REF] Chekuri | Large-treewidth graph decompositions and applications[END_REF][START_REF] Raymond | An edge variant of the Erdős-Pósa property[END_REF][START_REF] Chatzidimitriou | (log OP T )-approximation for covering and packing minor models of θ r[END_REF]).

Lemma 3.5. Let H be a family of connected graphs. If f is a superadditive ceiling for (tw, H, v) then H has the v-Erdős-Pósa property with gap k → 6 • f (k) log(k + 1).

Proof. Let us show the following for every integer k:

for every graph G, if v-pack H (G) = k then v-cover H ≤ 6f (k) log(k + 1).
The proof is by induction on k. The base case k = 0 is trivial. Let k > 0, and let us assume that the above statement holds for every non-negative integer k < k (induction hypothesis).

Let G be a graph such that v-pack H (G) = k. A separation of G of order p ∈ N is a pair (A, B) of subsets of V (G) such that G has no edge with the one endpoint in A \ B and the other one in B \ A, and |A ∩ B| = p. We will rely on the following claim.

Claim 3.6. There is a separation (A, B) of order at most tw(G)

+ 1 of G such that v-pack H (G[A \ B]) ≤ 2k/3 and v-pack H (G[B \ A]) ≤ 2k/3.
Proof. We consider a special type of tree decomposition called nice tree decomposition. A triple (T, r, {X t } t∈V (T ) ) is said to be a nice tree decomposition of a graph G if (T, {X t } t∈V (T ) ) is a tree-decomposition where the following holds:

1. every vertex of T has degree at most 3; 2. (T, r) is a rooted tree and the bag of the root r is empty (X r = ∅);

every vertex t of T is

• either a base node, i.e. a leaf of T whose bag is empty (X t = ∅) and different from the root;

• or an introduce node, i.e. a vertex with only one child t such that X t = X t ∪ {u} for some u ∈ V (G);

• or a forget node, i.e. a vertex with only one child t such that X t = X t \ {u} for some u ∈ X t ;

• or a join node, i.e. a vertex with two children t 1 and t 2 such that X t = X t 1 = X t 2 .

It is known that every graph G has a nice tree decomposition with width tw(G) [START_REF] Kloks | Computations and Approximations[END_REF]. We therefore can assume that (T, r, (X t ) t∈V (T ) ) is a nice tree decomposition of G of optimal width. For each t ∈ V (T ), we define

G t = G   s∈desc (T,r) (t) X s   and G - t = G t \ X t .
Let t be a vertex of T at minimal distance from a leaf subject to the requirement v-pack

H (G - t ) > 2k/3. Such a vertex exists, as v-pack H (G - r ) = v-pack H (G r ) = k.
Observe that t is either a forget node, or a join node. Indeed, for every base node u we have v-pack H (G - u ) = 0. Moreover, every introduce node u with child v satisfies v-pack

H (G - u ) = v-pack H (G - v ), since G - u = G - v . First case: t is a forget node with child u. We set A = V (G u ) and B = V (G) \ V (G - u )
. Observe that (A, B) is a separation and that we have A ∩ B = X u , therefore the order of (A, B) is at most tw

(G) + 1. If k = 1, then v-pack H (G[A \ B]) = v-pack H (G - u ) = 0 (by definition of t), whereas the fact that v-pack H (G[A]) = v-pack H (G) implies v-pack H (G[B \ A]) = 0 ≤ 2k/3. When k ≥ 2, we have the following inequalities: v-pack H (G[A \ B]) = v-pack H (G - u ) ≥ v-pack H (G - t ) -1 (as t is a forget node) > 2k 3 -1 ≥ k 3 .
When k = 2, the last inequality follows from the fact that v-pack H (G[A \ B]) is an integer. Notice that we always have

v-pack H (G[A \ B]) + v-pack H (G[B \ A]) ≤ k.
Together with the above inequality, this implies that v-pack

H (G[B \ A]) ≤ 2k/3, wheras it follows from the definition of t that v-pack H (G[A \ B]) ≤ 2k/3. Second case: t is a join node with children u 1 , u 2 . We set A = V (G u i ) and B = V (G) \ V (G - u i ), where u i is a child of t such that v-pack H (G - u i ) ≥ k/3. Such child exists because v-pack H (G - t ) = v-pack H (G - u 1 ) + v-pack H (G - u 2 ) (as t is a join node) and v-pack H (G - t ) > 2k/3
, by definition of t. Here again, (A, B) is a separation and its order is at most tw

(G) + 1 given that A ∩ B = X u i . The inequality v-pack H (G[A \ B]) ≤ 2k/3 follows from the definition of t and the choice of i ensures that v-pack H (G[A \ B]) ≥ k/3, hence v-pack H (G[B \ A]) ≤ 2k/3, as above. Observe that tw(G) ≤ f (k), by definition of f. According to Claim 3.6, there is a separation (A, B) of order at most tw(G) + 1 in G such that k A , k B ≤ 2k/3 , where k A = v-pack H (G[A \ B]) and k B = v-pack H (G[B \ A]). Moreover, since (A, B) is a separation, there is no connected graph of G \ (A ∩ B) that have vertices in both G[A \ B] and G[B \ A]. Therefore, given that every graph of H is connected, we can construct a v-H-cover of G \ (A ∩ B) by taking the union of a v-H-cover of G[A \ B] and of one of G[B \ A]. In other words, we have v-cover H (G) ≤ v-cover H (G[A \ B]) + v-cover H (G[B \ A]) + |A ∩ B| ≤ v-cover H (G[A \ B]) + v-cover H (G[B \ A]) + f (k) + 1 ≤ 6f (k A ) log(k A + 1) + 6f (k B ) log(k B + 1) + f (k) + 1.

The last inequality above is obtained by applying the induction hypothesis on both

G[A \ B] and G[B \ A]. Notice that in the case where k = 1, we get k A = k B = 0 and we have v-cover H (G) ≤ f (k) ≤ 6 • f (k) log(k + 1
). Therefore we now assume k ≥ 2. We can then deduce that 2k

3 + 1 ≤ 7 9 (k + 1). We then have:

v-cover H (G) ≤ 6 • (f (k A ) + f (k B )) log 2k 3 + 1 + f (k) + 1 ≤ 6 • f (k) log 7(k + 1) 9 + f (k) + 1 (superadditivity of f ) ≤ 6 • f (k) log(k + 1) -6 • log(9/7)f (k) + 2f (k) ≤ 6 • f (k) log(k + 1).
The second inequality also requires that f is monotone, which is the case because it is superadditive and it never takes negative values.

From the fact that the function of Corollary 3.4 is superadditive, we get the following consequence of Lemma 3.5.

Corollary 3.7 (see also [START_REF] Chekuri | Large-treewidth graph decompositions and applications[END_REF] and [START_REF] Chekuri | Polynomial Bounds for the Grid-Minor Theorem[END_REF]). There is a function

f h (k) = h O(1) •k polylog(k)
such that, for every connected planar graph H with h edges, the class M(H) has the Erdős-Pósa property with gap f h . Notice that the above proof strongly relies on the fact that H is connected. The nonconnected case requires some more ideas that are originating from [START_REF] Robertson | Graph Minors. V. Excluding a planar graph[END_REF] (also used for forests in [START_REF] Fiorini | Excluded forest minors and the Erdős-Pósa property[END_REF]). We expose them hereafter. We will need the two next lemmas.

Lemma 3.8 ( [RS86]

). Let q, k be two positive integers, let T be a tree and let A 1 , . . . , A q be families of subtrees of T. Assume that for every i ∈ {1, . . . , q}, there are kq elements of A i that are pairwise vertex-disjoint. Then for every i ∈ {1, . . . , q}, there are

k elements T i 1 , . . . , T i k of A i such that T 1 1 , . . . T 1 k , T 2 1 , . . . T 2 k , . . . , T q 1 , . . . T q k are all pairwise vertex-disjoint.
The next lemma is the Erdős-Pósa property of subtrees of a tree. It can be obtained from the fact that subtrees of a tree have the Helly property. Lemma 3.9 (see [START_REF] Gyárfás | A Helly-type problem in trees[END_REF]). Let T be a tree and let A be a collection of subtrees of T. For every positive integer k, either T has (at least) k vertex disjoint subtrees that belong to A, or T has a subset X of less than k vertices such that no subtree of T \ X belongs to A.

We are now ready to deal with disconnected patterns.

Lemma 3.10 ( [RS86]

). Let w be a positive integer and let H be a graph on q connected components. M(H) has the v-Erdős-Pósa property on the class of graphs of treewidth at most w with gap k → (w -1)(kq -1).

Proof. Let k be a positive integer. We want to show that either v-pack M(H) (G) ≥ k or v-cover M(H) (G) ≤ (w -1)(kq -1). Let H 1 , . . . , H q be the connected components of H. Let (T, X ) be a tree-decomposition of G of width w. For every subgraph F of G, we denote by T (F ) the subgraph of T induced by the bags containing vertices of F. Notice that T (F ) is connected if F is connected.

For every i ∈ {1, . . . , q}, we let H i be the class of subgraphs of G that are isomorphic to a graph in M(H i ) and we consider the class

T i = {T (F ), F ∈ H i }.
If for every i ∈ {1, . . . , q}, T i contains kq vertex-disjoint trees, then according to Lemma 3.8 there is a collection {T j i } i∈{1,...,q}, j∈{1,...,k} of pairwise vertex-disjoint trees, with T j i ∈ T i for every i ∈ {1, . . . , q} and every j ∈ {1, . . . , k}. Observe that for every two subgraphs F, F of G, if T (F ) and T (F ) are vertex-disjoint, then so are F and F . Therefore G has a collection {F j i } i∈{1,...,q}, j∈{1,...,k} of pairwise vertex-disjoint subgraphs such that F j i is isomorphic to an element of H i , for every i ∈ {1, . . . , q} and j ∈ {1, . . . , k} . Consequently, for every j ∈ {1, . . . , k}, q i=1 F j i is a subgraph of G containing a graph isomorphic to a member of M(H), and these subgraphs are vertex-disjoint for distinct values of j. This proves that in this case, v-pack M(H) (G) ≥ k.

We therefore now assume that the above condition does not hold, namely there is an index i ∈ {1, . . . , q} such that T i contains less than kq vertex-disjoint trees. Lemma 3.9 implies the existence of a subset X with |X| ≤ kq -1 such that T \ X is free from subtrees isomorphic to a member of T i . Let Y denote the union of the bags indexed by vertices in X.

Observe that |Y | ≤ (w -1)|X| ≤ (w -1)(kq -1). The choice of Y ensures that G \ Y has no subgraph isomorphic to a member of H i . Hence v-cover M(H i ) ≤ (w -1)(kq -1). We deduce v-cover M(H) ≤ (w -1)(kq -1).
Corollary 3.11. For every planar graph H with h edges and q connected components, the class M(H) has the Erdős-Pósa property with gap

k → q • h O(1) • k 2 • polylog(k).

Edge version and tree partitions

The technique presented in the previous section to deal with hosts of bounded treewidth cannot be straighforwardly translated to the setting of the edge-Erdős-Pósa property. Indeed, in general, knowing that two vertex sets are separated by a small number of vertices does not give any information on the minimum number of edges separating these sets. For this reason, we consider alternative of treewidth that guarantees that small edge-separators can be found. However, to the best of our knowledge, it is not known whether the edge-Erdős-Pósa property always holds when the host graphs have bounded treewidth.

One possible edge-analogue of treewidth is tree partition width. Recall that θ t is the graph with two vertices and t edges, for every t ∈ N. The following uses [DO96, Theorem 1.2]. Lemma 3.12. For every t ∈ N, there exists a ceiling for the triple (tpw, M(θ t ), e).

Proof. According to [DO96, Theorem 1.2], there is a function f : N → N such that for every p ∈ N, every simple graph G satisfying tpw(G) ≥ f (p) contains as a subgraph either a p-wall, or a p-path, or a p-star, or a p-fan. We omit the definition of these graphs here, but we note that each of them contains a e-M(θ t )-packing of size k as soon as kt < p/2.

Let G be a graph such that tpw(G) ≥ f (2kt) • kt. If G has a multiedge e of multiplicity ≥ kt, then it clearly contains an e-M(θ t )-packing of size k. Therefore we now assume that all edges of G have multiplicity less than kt. Observe that, if we denote by G the underlying simple graph of G, we have tpw(G) ≥ tpw(G) kt . Hence tpw(G) ≥ f (2kt) and, by definition of f and the remark above, G contains a e-M(θ t )-packing of size k. As G is a subgraph of G, the aforementioned packing also belong to G, which proves the lemma.

Let H be a class of graphs. We define H as the set of all the subgraph-minimal elements of H, i.e., H = {H, H ∈ H and none of the subgraphs of H belongs to H}.

We define ∆(H) as the maximum number of edges incident to a vertex in a graph of H (counting multiple edges). We also set ∆(H) = ∆( H). Lemma 3.13. For every graph H of h edges, it holds that ∆(M(H)) ≤ h, ∆(T (H)) ≤ h, ∆(I(H)) ≤ 2h.

Lemma 3.14. Let H be a class of connected non-trivial graphs where ∆(H) ≤ d. Then for every r ∈ N, H has the e-Erdős-Pósa property on G tpw≤r with gap g r (k) = k • r • (dr + 1).

Proof. Let r ∈ N. We will show the following for every k ∈ N:

for every graph G ∈ G tpw≤r , if e-pack H (G) = k then e-cover H (G) ≤ g r (k).
We proceed by induction. The base case k = 0 is trivial. We thus assume that k > 0 and that the above statement holds for every positive integer k < k (induction hypothesis).

Let G ∈ G tpw≤r be a graph such that e-pack H (G) = k. We assume that G is connected, as otherwise we can treat each connected component separately.

Let ({X t } t∈V (T ) , T, s) be an optimal tree partition decomposition of G. We define

G t = G u∈desc (T,s) (t) X u .
For every edge {u, v} of T we denote by E {u,v} the edges of G with the one endpoint in X u and the other one in X v . Let t be a vertex of T of minimum distance from a leaf, subject to e-pack H (G t ) > 0.

Let M be a subgraph-minimal subgraph of G t isomorphic to some member of H and let t 1 , . . . , t p be the children of t such that V (G t i ) ∩ V (M ) = ∅ for every i ∈ {1, . . . , p}. By minimality of M , it has no vertex with more than ∆(H) ≤ d incident edges. As |X t | ≤ r, we deduce that p ≤ rd.

Let C = E(X t ) ∪ p i=1 E {t,t i } . Notice that |C| ≤ r + dr 2 . Let us consider then graph G = G \ C. Let M be a subgraph of G that is isomorphic to some member of H. By minimality of t, e-pack H (G t i ) = 0, for every i ∈ {1, . . . , p} . Therefore, if M contained an edge e ∈ E(G t i ) (for some i ∈ {1, . . . , p}), it would also contain an edge of E(G) \ E(G t i ). Since every graph of H is connected, M would also need to contain some edge of E {t,u i } in order to be connected to edges of E(G) \ E(G t i ). However E(G ) ∩ E {t,u i } = ∅. We deduce that for every subgraph M of G that is isomorphic to some member of H, we have E(M ) ∩ E(M ) = ∅. It follows that every e-H-packing in G is edge-disjoint with M.

Hence e-pack H (G ) < k, as otherwise a packing of size k in G would, together with M , yield a packing of size k + 1 in G whereas e-pack H (G) = k. By applying the induction hypothesis on G , there is a subset D ⊆ E(G ) such that e-pack H (G \D) = 0 and moreover |D| ≤ g r (k -1). It is easy to see that C∪D is an e-H-cover of G. Furthermore |C∪D| ≤ r(dr+1)+g r (k-1) = g r (k), as required.

An application of Lemma 3.14 is the following result, which also relies on Theorem 3.1 and Lemma 3.12.

Corollary 3.15 (see also [START_REF] Chatzidimitriou | (log OP T )-approximation for covering and packing minor models of θ r[END_REF]). For every r ∈ N ≥1 , M(θ r ) has the e-Erdős-Pósa property.

However, according to the results in [START_REF] Ding | On tree-partitions of graphs[END_REF], the class of graphs H such that there is a ceiling for (tpw, M(H), e) is rather limited. An alternative counterpart to treewidth might be the tree-cut width. We do not provide the definition here, but we refer the reader to the article where this parameter has been introduced [START_REF] Wollan | The structure of graphs not admitting a fixed immersion[END_REF] (see also [GPT + 16] for an alternative definition). The next result appeared in [START_REF] Giannopoulou | Packing and covering immersion models of planar subcubic graphs[END_REF] and is strongly based on the results of [START_REF] Wollan | The structure of graphs not admitting a fixed immersion[END_REF].

Theorem 3.16. For every planar subcubic graph H with h edges, there exists a ceiling for the triple (tcw, I(H), e).

The next Lemma is the counterpart of Lemma 3.14, especially for the case of immersion models for graphs of bounded tree-cut width.

Lemma 3.17 [START_REF] Giannopoulou | Packing and covering immersion models of planar subcubic graphs[END_REF]). Let t be a positive integer and let H be a connected non-trivial planar subcubic graph of h edges. Then I(H) has the e-Erdős-Pósa property on G tcw≤t with gap k → t 2 hk.

Using Theorem 3.1, Lemma 3.17, and Theorem 3.16 we can also derive the following.

Corollary 3.18 ([GKRT16a]

). Let H be a connected non-trivial planar subcubic graph of h edges. Then I(H) has the e-Erdős-Pósa property with gap k → (hk) O(1) .

The Erdős-Pósa property from girth

In this section, we give another proof of the Erdős-Pósa Theorem that highlights a technique for proving more general Erdős-Pósa-type results. The technique can be informally summarized as follow. We prove that either G contains a small cycle or that it can be reduced to a smaller graph with the same packing and cover number. We then apply induction on either the graph where a small cycle has been deleted (in the first case), or on the reduced graph (in the second case). This technique has been successfully applied in [START_REF] Fiorini | Excluded forest minors and the Erdős-Pósa property[END_REF][START_REF] Chatzidimitriou | (log OP T )-approximation for covering and packing minor models of θ r[END_REF], for instance.

The girth of a graph is the minimum length of a cycle in this graph. Let us first recall the following result.

Lemma 4.1 ( [START_REF] Thomassen | Girth in graphs[END_REF], see also [START_REF] Diestel | Graph Theory[END_REF]Theorem 7.4.2]). There is a constant c ∈ R, such that for every q ∈ N ≥1 , every graph of minimum degree at least 3 and girth at least c log q contains K q as a minor.

A direct consequence of this result is the following trichotomy.

Corollary 4.2. For every graph G and every integer q > 1, one of the following holds:

(i) G has a cycle on at most c log q vertices;

(ii) G has a vertex of degree at most 2;

(iii) G contains K q as a minor, where c is the constant of Lemma 4.1.

We now prove the lemma that implies the classic Erdős-Pósa Theorem both for the vertex and its edge version. Recall that A x (G) denotes V (G) or E(G), depending if x = v or x = e. Lemma 4.3. For every q ∈ N + and every x ∈ {v, e}, the class M(θ 2 ) has the x-Erdős-Pósa property for the class of graphs excluding K q as a minor with gap O(k • log q). Proof. We will prove that for every non-negative integer k and every K q -minor-free graph G, either G has k x-disjoint cycles, or G has a subset X ⊆ A x (G) of size at most ck log q such that G \ X is a forest, where c is the constant of Lemma 4.1. We proceed by induction on the pair (k, G), with the well-founded order defined by (k , G )

≤ (k, G) ⇐⇒ (k ≤ k and |A x (G )| ≤ |A x (G)|)
, for all graphs G, G and non-negative integers k, k .

The base cases corresponding to k = 0 or |A x (G)| = 0 are trivial. Let us now assume that k ≥ 1, |A x (G)| ≥ 1, and that the lemma holds for every pair (k , G ) such that (k , G ) ≤ (k, G).

According to Corollary 4.2, either G has a cycle C on at most c log q vertices, or it has a vertex v of degree at most two, or it contains K q as a minor. The last case is not possible, as we require G to be K q -minor-free.

Whenever the first case applies, we set G = G \ A x (C) and we consider the pair (k -1, G ). If G contains k -1 x-disjoint cycles, then G contains k x-disjoint cycles obtained by adding C to those of G and we are done. Otherwise, the induction hypothesis implies the existence of a subset X ⊆ A x (G ) with |X | ≤ c(k -1) log q such that G \ X is a forest. Then by definition of C, X = X ∪ A x (C) has size at most c log q and G \ X is a forest, as required.

In the second case, we delete v if it is isolated and we contract an edge e incident with it otherwise. Notice that since we cannot apply the first case, this contraction does not decrease the maximum number of x-disjoint cycles in G. Also, we can assume without loss of generality that v (respectively e) is not part of a minimum x-cover of cycles in G, as any vertex adjacent to v (respectively edge incident with e) covers all the cycles covered by v (respectively e). Therefore the obtained graph

G satisfies x-pack M(θ 2 ) (G ) = x-pack M(θ 2 ) (G ) and x-cover M(θ 2 ) (G ) = x-cover M(θ 2 ) (G). It is not hard to see that |A x (G )| < |A x (G)|.
Therefore we can apply the induction hypothesis on G and obtain the desired result on G , that immediately translates to G by the above remarks.

By setting q = 3k and observing that every graph containing K 3k as a minor also contains k vertex-disjoint cycles (hence also edge-disjoint), Lemma 4.3 yields the vertex and edge versions of the classic Erdős-Pósa Theorem as a corollary.

The technique presented in this section has been used to show the following results.

Theorem 4.4 ( [FJW13]

). For every forest H, M(H) has the v-Erdős-Pósa property with gap O(k).

Theorem 4.5 ([CRST15a], see also [START_REF] Fiorini | Optimal Erdős-Pósa property for pumpkins[END_REF] for the vertex case). For every positive integer r and every x ∈ {v, e}, M(θ r ) has the x-Erdős-Pósa property with gap O(k log k).

Actually, the ideas in [START_REF] Chatzidimitriou | (log OP T )-approximation for covering and packing minor models of θ r[END_REF] permit us to replace M(θ 2 ) by M(θ r ), r ≥ 2 in Lemma 4.3.

To extend the idea of Lemma 4.3 in order to prove that some graph class H has the x-Erdős-Pósa property with gap f : N → N, one should show that for every positive integer k and every graph G with x-pack H (G) ≤ k,

• either there is a graph G with x-pack H (G) = x-pack H (G ) and x-cover

H (G) = x-cover H (G )
and such that |G | + G < |G| + G (reduction case);

• or G has a subgraph isomorphic to a member of H on at most f (k)/k vertices/edges (progress case).

In both proofs of Theorem 4.4 and Theorem 4.5, the reduction case is done using the graph theoretic notion of a protrusion introduced in [BFL + 09a, BFL + 09b] (or variants of it).

Roughly speaking, the idea is to identify large parts of the graph that have constant treewidth (or constant tree partition width, in case of Theorem 4.5) and a small interface towards the rest of the graph and then prove that they can be replaced by smaller ones without changing the packing or the cover number.

Results in terms of containment relations

For every partial order on graphs, and for every graph H, let

G (H) = {G | H G}.
For every x ∈ {v, e}, we define

EP x = {H | G (H) has the x-Erdős-Pósa property}
A general question on the Erdős-Pósa property is to characterize EP x for several containment relations. In this section we mainly provide some negative results about this problem. We start with the following easy observation. Proof. Let H and G be two graphs and let k = x-pack G (H) (G). Let M 1 , . . . , M k be a v-G (H)-packing (respectively e-G (H)-packing) of size k with the minimal number of vertices (respectively edges). Observe that in this case,

|M i | = |H| (respectively M i = H ) for every i ∈ {1, . . . , k} . Let X = k i=1 V (M i ) (respectively X = k i=1 E(M i )).
As the packing we consider is of size k, the graph G \ X does not have any subgraph isomorphic to a member of G (H). Hence X is an v-G (H)-cover (respectively e-G (H)-cover), and besides we have

|X| = k • |H| (respectively |X| = k • H ).
Notice that in case x = v, it is not necessary to demand that H is non-trivial in the statement of Lemma 5.1.

Some negative results

Let us now state several negative results on the Erdős-Pósa property of classes related to topological minors.

In the proofs below, we use the notion of Euler genus of a graph G. The Euler genus of a non-orientable surface Σ is equal to the non-orientable genus g(Σ) (or the crosscap number). The Euler genus of an orientable surface Σ is 2g(Σ), where g(Σ) is the orientable genus of Σ. We refer to the book of Mohar and Thomassen [START_REF] Mohar | Graphs on surfaces[END_REF] for more details on graph embeddings. The Euler genus γ(G) of a graph G is the minimum Euler genus of a surface where G can be embedded.

Lemma 5.2. Let H be a non-planar graph. Then T (H) does not have the v-Erdős-Pósa property.

Proof. Informally, we will construct, for every positive integer k, a graph G k by "thickening" the vertices and edges of H. From the non-planarity of H and the way this graph is constructed, we will deduce that v-pack T (H) (G k ) = 1. On the other hand, the connectivity provided by the thickening of H will ensure that the removal of any k -1 vertices will leave at least one subdivision of H unaltered.

For every integers k > 0 and d, we denote by Γ d,k the graph obtained from a grid of width dk and height d+k-1 by adding k vertices a 1 , . . . , a k (that we call apices) and connecting a 1 to the d first vertices on the first row of the grid (starting from the left), a 2 to the d next vertices, and so on. For every i ∈ {0, . . . , d -1}, the set of vertices at indices {ik +j, j ∈ {0, . . . , k -1}} on the last row of Γ d,k is called the i-th port of Γ d,k . We will refer to the vertex at index ik + j of the last row as the j-th vertex of the i-th port. See Figure 1 for a drawing of Γ 4,3 . On this drawing, the ports are U 0 , . . . , U 3 . Let k be a positive integer. For every vertex v of H, we arbitrarily choose an ordering of its neighbors and we denote by σ v (u) the rank of u in this ordering (ranging from 0 to deg(v) -1), for every neighbor u of v. We also let F v be a copy of the graph Γ deg(v),k .

U 0 U 1 U 2 U 3 a 1 a 2 a 3
The graph G k can be constructed from the disjoint union of the graphs of {F v , v ∈ V (H)} by adding, for every pair u, v of adjacent vertices, the edge connecting the i-th vertex of the σ v (u)-th port of F v to the i-th vertex of the σ u (v)-th port of F u , for every i ∈ {0, . . . , k -1} . Informally, we connect the vertices of the σ v (u)-th port of F v to the vertices of the σ u (v)-th port of F u using "parallel" edges. Figure 2 depicts the graph G k when G = K 5 and k = 3. This graph contains a subdivision of K 5 but not two vertex-disjoint ones, and the removal of any two vertices leaves one subdivision of K 5 unaltered. It can be easily checked that the Euler genus of G k and H are equal. As H is not planar, the Euler genus of the disjoint union of two copies of H is larger than the one of H (see [START_REF] Battle | Additivity of the genus of a graph[END_REF]) and we get that v-pack T (H) (G) < 2. On the other hand, our construction ensures that v-pack T (H) (G) ≥ 1.

Let us now show that for every subset X ⊆ V (G k ) with |X| < k we have v-pack T (H) (G \ X) ≥ 1. This would complete the proof, since {G k , k ∈ N ≥1 } would be an infinite family of graphs that have no v-T (H)-packings of size 2 but where a minimum v-T (H)-cover can be arbitrarily large.

Let u and v be two adjacent vertices of H, and let d = deg(v). For every i ∈ {0, . . . , k -1}, let C i denote the vertices that are

• either in the same column of F u as the i-th vertex of the σ u (v)-th port of F u ;

• or in the same column of F v as the i-th vertex of the σ v (u)-th port of F v .

The family {C i , i ∈ {1, . . . , k}} contains k vertex disjoint elements, therefore at least one of them does not contain any vertex from X (as |X| < k). Therefore, for every edge {u, v} of H there is an edge f ({u, v}) between a vertex x of the σ u (v)-th port of F u and a vertex y of the σ v (u)-th port of F v such that no vertex of the same column as x in F u (respectively y in F v ) belong to X. Using the same argument we can show that for every vertex v ∈ V (H) there is an apex a such that the columns of F v adjacent to a are free of vertices of X. Also we know that at least d rows do not contain vertices from X, as the grid of F v has height d + k -1. Therefore F v contains as a subgraph a grid S v such that:

1. some apex a is adjacent to d vertices of the first row of S v ; 2. for every edge {u, v} ∈ E(H), the edge f ({u, v}) of G k shares one vertex of the last row of S v ;

3. no vertex of the last row of S v belongs to two edges f ({u, v}) and f ({u , v}) for some distinct neighbors u, u of v;

4. S v has height and width at least d;

5. S v does not contain any vertex of X.

We deduce that F v \ X contains d paths P v 0 , . . . , P d-1 that have only the apex a as common vertex and such that P i connects a to an endpoint of f ({v, u i }), where u i is the neighbor of v of rank i, for every i ∈ {0, . . . , d -1} . It is now easy to see that the graph

G k   v∈V (H) deg H (v)-1 i=0 V (P v i )  
contains a subdivision of H that does not contain any vertex of X. This concludes the proof.

The proof of Lemma 5.2 can be adapted to the setting of the edge-Erdős-Pósa property under the additional requirement that the pattern is subcubic.

Lemma 5.3. Let H be a subcubic non-planar graph. Then T (H) does not have the e-Erdős-Pósa property.

Proof. Let k be a positive integer. We use the same construction of G k as in the proof of Lemma 5.2 with the following modifications: each vertex v of degree d ≥ 4 of G k is replaced by a subcubic tree, the leaves of which are the neighbors of v. Let us call G k the graph we obtain. It is not hard to see that the genus of G k and G k are equal. Moreover, as G k is subcubic, every e-T (H)-packing is also an v-T (H)-packing. We then obtain as previously that e-pack T (H) (G k ) = 1. The argument to show that e-cover T (H) (G k ) ≥ k is identical to that used in the proof of Lemma 5.2.

In fact, Lemma 5.2 and Lemma 5.3 can be used to prove that more general classes do not have the Erdős-Pósa property, as follows. As we will see in Corollary 5.5 and Corollary 5.6, the conditions of Lemma 5.4 already encompass several well-studied classes.

Lemma 5.4. Let x ∈ {v, e}, let H be a non-planar graph and let H be a class of graphs such that:

(i) T (H) ⊆ H; and
(ii) H is graph of minimum Euler genus in H;

(iii) if x = e, then H is subcubic.
Then H does not have the x-Erdős-Pósa property.

Proof. Let k be a positive integer. We again consider the graphs G k and G k constructed from H as in the proofs of Lemma 5.2 and Lemma 5.

3. Let J k be G k if x = v and J k = G k if x = e. Let us show that v-pack H (J k ) = 1.
For this, let us assume that there is an x-H-packing F 1 , . . . , F p , for some p ∈ N ≥2 in J k . It is crucial to note that in both the cases x = v and x = e, the subgraphs F 1 , . . . , F p are vertex-disjoint. In fact, when x = v, this follows from the definition of a v-H-packing, and if x = e it is because G k is subcubic. Recall that γ(G) denotes the Euler genus of G, i.e. the minimum Euler genus of a surface where G can be embedded, and that our construction ensures that γ(J k ) = γ(H) (see the proofs of Lemma 5.2 and Lemma 5.3). Then we have:

γ(J k ) ≥ γ(F 1 ∪ • • • ∪ F p ) = p i=1 γ(F i ) (see [BHK62]) ≥ p • γ(H) (see below) γ(J k ) > γ(H) (as p ≥ 2).
The inequality γ(J k ) ≥ p • γ(H) come from the requirements (i)-(ii), which imply γ(F i ) ≥ γ(H) for every i ∈ {1, . . . , p}. The last inequality contradicts the fact that γ(

J k ) = γ(H). Therefore v-pack H (J k ) = 1. On the other hand, v-cover H (J k ) ≥ v-cover T (H) (J k ) ≥ k.
The last inequality can be found in the proof of Lemma 5.2 or Lemma 5.3 (depending if x = v or x = e). This concludes the proof.

Corollary 5.5. For every non-planar graph H, none of I(H) and M(H) have the v-Erdős-Pósa property.

Corollary 5.6. For every subcubic non-planar graph H, none of I(H) and M(H) have the e-Erdős-Pósa property.

Corollary 5.6 can be strengthened by dropping the degree condition on H when considering minor models of H, as follows.

Lemma 5.7. For every non-planar graph H, M(H) does not have the e-Erdős-Pósa property.

Proof. Let k be a positive integer. Again we use the graph G k constructed as in Lemma 5.3. We modify it by replacing every apex a by a subcubic tree, the leaves of which are the neighbors of a. Let G k denote the graph that we obtain. Observe that G k is subcubic. Therefore, using the same argument as in the proof of Lemma 5.3 we can show that e-pack M(H) (G) = 1. In the sequel we use the terminology of the proof of Lemma 5.2. Let F v denote the graph obtained from F v by replacing every vertex u of degree at least 4 by a subcubic tree, the leaves of which are the neighbors of u, for every v ∈ V (H). The proof that e-cover M(H) (G) ≥ k goes as in the proof of Lemma 5.2, except that we obtain, for every v ∈ V (H), that F v \ X contains a tree, the leaves of which are endpoints of f ({v, u i }) for i ∈ {0, . . . , d -1} (instead of paths connecting an apex to endpoints of f ({v, u i })). Fortunately this is enough to guarantee that G k \ X contains H as a minor, and we are done.

Let us now summarize results related to the most common containment relations.

Subgraphs and induced subgraphs: EP x is the class of all graphs, both for being the subgraph and induced subgraph relation, for every x ∈ {v, e} (Lemma 5.1).

Minors: EP v

≤m is the class of planar graphs [START_REF] Robertson | Graph Minors. V. Excluding a planar graph[END_REF]. Recently, an extension of this characterization, for strongly connected directed graphs, appeared in [START_REF] Saeed Akhoondian Amiri | The Erdős-Pósa property for directed graphs[END_REF]. About the edge version, the authors of [START_REF] Raymond | An edge variant of the Erdős-Pósa property[END_REF] proved that EP e ≤m includes the class {θ r } r∈N ≥1 , and we show in Lemma 5.7 that EP e ≤m is a subclass of planar graphs (see also [START_REF] Chatzidimitriou | (log OP T )-approximation for covering and packing minor models of θ r[END_REF]).

Topological Minors: EP v ≤tm has been characterized in [START_REF] Liu | Erdős-Pósa property for the topological minors[END_REF]. There are trees that do not belong to EP v ≤tm [START_REF] Thomassen | On the presence of disjoint subgraphs of a specified type[END_REF]. The class EP v ≤tm does not contain any non-planar graph (Lemma 5.2) and EP e ≤tm does not contain any non-planar subcubic graph (Lemma 5.3). Analogous characterizations for the case of strongly connected digraphs have recently appeared in [START_REF] Saeed Akhoondian Amiri | The Erdős-Pósa property for directed graphs[END_REF].

Immersions: As proved in [GKRT16a], EP v
≤ imm contains all planar subcubic graphs and EP e

≤ imm contains all non-trivial, connected, planar subcubic graphs. Moreover, EP v ≤ imm does not contain any non-planar graph (Corollary 5.5) and EP e ≤ imm does not contain any subcubic non-planar graph (Corollary 5.6). On the other hand there is a 3-connected planar graph of maximum degree 4 that belongs to none of EP v ≤ imm and EP v ≤ imm [START_REF] Giannopoulou | Packing and covering immersion models of planar subcubic graphs[END_REF].

Summary of results

In the following sections we list positive and negative results on the Erdős-Pósa property, and open problems.

Let us define the notation used in all the tables of Subsection 6.1 and Subsection 6.2. The fourth column of the tables gives the type of the packings/covers the current line is about. The character v (respectively e) refers to vertex-disjoint (respectively edge-disjoint) packings and vertex (respectively edge) covers. We write v/e when the mentioned result holds for both the vertex and the edge version. The symbol v 1/p (resp. e 1/p ) for some p ∈ N indicates that the packing is allowed to use at most p times each vertex (resp. each edge) and that the cover contains vertices (resp. edges). Finally, w stands for vertex covers and packings where every vertex v of the host graph can be used at most w(v) times by every packing, where w is a function mapping reals to the vertices of the host graph. The more specific definitions are given in the corresponding sections.

Positive results

We provide a series of tables presenting known results on the Erdős-Pósa property of some graph classes, sorted depending on the pattern. Results related to other structures (matroids, hypergraphs, geometry) and to fractional versions are not mentioned here.

A dash in the "gap" column means that the authors did not explicitly provided a gap function, even though one might be computable from the proof. The fourth column refers to the type of packing/cover, as defined above.

Acyclic patterns

Let G be a graph. For every S, T ⊆ V (G), an (S, T )-path of G is a path with the one endpoint in S and the other one in T . An S-path is a path with both endpoints (which are distinct) in S. If S is a collection of subsets of V (G), an S-path is a path that has endpoints in two different elements of S. A generalization of these settings have been introduced in [START_REF] Marx | An exact characterization of tractable demand patterns for maximum disjoint path problems[END_REF], where the pairs of vertices that can be connected by a path are specified by an auxilliary graph. If S ⊆ V (G) and H (demand graph) is a graph with vertex set S, a path of G is said to be H-valid if its endpoints are adjacent vertices of H.

Ref.

Guest c, d} together with the edges {b, c} and {a, d}. We denote by G 1 the class of graphs with no induced subdivision of the following: K 2,3 , a wheel, or an odd ring. We denote by G 2 the class of graphs with no induced subdivision of the following: K 3,3 , a wheel, or an odd ring.

The results on directed cycles also need few more definitions. A digraph is strongly planar if it has a planar drawing such that for every vertex v, the edges with head v form an interval in the cyclic ordering of edges incident with v (definition from [START_REF] Guenin | Packing directed circuits exactly[END_REF]). An odd double circuit is a digraph obtained from an undirected circuit of odd length more than 2 by replacing each edge by a pair of directed edges, one in each direction. F 7 is the digraph obtained from the directed cycle on vertices v 1 , . . . , v 7 , v 1 , by adding the edges creating the directed cycle v 1 , v 3 , v 5 , v 7 , v 2 , v 4 , v 6 , v 1 . We denote by F the class of digraphs with no butterfly minor isomorphic to an odd double circuit, or F 7 (for the definition of butterfly minors of digraphs see [START_REF] Guenin | Packing directed circuits exactly[END_REF][START_REF] Johnson | Directed tree-width[END_REF][START_REF] Saeed Akhoondian Amiri | The Erdős-Pósa property for directed graphs[END_REF]).

Results related to cycles with length constraints, with prescribed vertices, or to extensions of cycles are presented in the forthcoming tables.

Ref.

Guest class H

Host class G T.

Up

I(H), H connected non-trivial {G, tpw(G) ≤ t} e H • t 2 • k {G, tcw(G) ≤ t} [Liu15]
I 1/2 (H) any e 1/2 -

Patterns with prescribed vertices

Let us first present the two settings of Erdős-Pósa problems with prescribed vertices that we want to deal with here. The first type is when the guest class consists of fixed subgraphs of the host graph. For instance, one can consider a family F of (non necessarily disjoint) subtrees of a tree T , and compare the maximum number of disjoint elements in F with the minimum number of vertices/edges of T meeting all elements of F. We will refer to these guest classes by words indicating that we are dealing with substructures (like "subtrees"). We stress that in this setting, the host class is allowed to contain one subgraph F of the host graph, but not one other subgraph F even if F and F are isomorphic. For every positive integer t, a t-path is a disjoint union of t paths, and a t-subpath of a t-path G is a subgraph that has a connected intersection with every connected component of G. The concept of t-forests and t-subforests is defined similarly. In order to introduce the second type of problem, we need the following definition. Let x ∈ {v, e}. If H is a class of graphs, G is a graph and S ⊆ A x (G), then a S-H-subgraph of G is a subgraph of G isomorphic to some member of H and that contain one edge/vertex of S. We are now interested in comparing, for every graph G and every S ⊆ A x (G), the maximum number of S-H-subgraph of G with the minimum number of elements of A x (G) that meet all S-H-subgraphs of G. We refer to these problems by prefixing the guest class with an "S" (like in "S-cycles"). The authors of [START_REF] Huynh | A unified Erdős-Pósa theorem for constrained cycles[END_REF] consider (S 1 , S 2 )-cycles for S 1 , S 2 ⊆ V (G): such cycles must meet both of S 1 and S 2 . A generalization of this type of problem has been introduced in [KM15]: instead of one set S, one considers three subsets S 1 , S 2 , S 3 of V (G) and a (S 1 , S 2 , S 3 )-subgraph is required to intersect at least two sets of S 1 , S 2 and S 3 . Note that some results on patterns with prescribed vertices have been stated in the table on acyclic patterns. Recall that cc(G) denotes the number of connected components of the graph G.

Ref.

Guest

Some questions and conjectures

Clearly, the most general question on the Erdős-Pósa property is to characterize the class EP x (defined in Section 5) for various instantiations of x and and optimize the corresponding gap.

In what follows we sample some related conjectures and questions that have appeared in the bibliography.

Question 6.1 ( [START_REF] Thomassen | On the presence of disjoint subgraphs of a specified type[END_REF]). Is it true that for every class H of graphs, either H has the v-Erdős-Pósa property or there is no integer q such for every graph G with v-pack H (G) ≤ 1 it holds that v-cover H (G) ≤ q. In particular, it is true when H consists of connected graphs and is closed under topological minors? Conjecture 6.2 (Tuza's conjecture [START_REF] Tuza | A conjecture on triangles of graphs[END_REF]). For every graph G it holds that e-cover {K 3 } (G) ≤ 2 • e-pack {K 3 } (G).

Conjecture 6.3 ([BBR07]

). Let l ≥ 6 be an integer. Let G be a graph containing no v-C ≥lpacking of size 2. Then there exists a v-C ≥l -cover of G of size at most l.

Conjecture 6.4 (Jones' conjecture [START_REF] Ton Kloks | New algorithms for k-face cover, k-feedback vertex set, and k-disjoint cycles on plane and planar graphs[END_REF]). Let C denote the class of all cycles. For every planar graph G, it holds that

v-cover C (G) ≤ 2 • v-pack C (G).
A hole is an induced cycle of lenght at least 4.

Question 6.5 ( [START_REF] Bart | Approximation and kernelization for chordal vertex deletion[END_REF]). Is there a function f : N → N such that for every graph G and every k ∈ N, the following holds:

• G has k vertex-disjoint holes; or

• there is a set X ⊆ V (G) such that G \ X has no hole?

  Lemma 5.1. If is the subgraph or the induced subgraph relation, x ∈ {v, e}, and H is a non-trivial graph, then G (H) has the x-Erdős-Pósa property, with gap f : k → k • |A x (H)|. In other words, EP x is the set of all graphs.

Figure 1 :

 1 Figure 1: The gadget Γ 4,3 used in Lemma 5.2.

Figure 2 :

 2 Figure 2: The "thickening" of K 5 for k = 3. Edges with dashed ends are connected to the aligned edges at the opposite side of the figure.

  The statement of the results in[START_REF] Ding | Packing cycles in graphs[END_REF][START_REF] Ding | Packing cycles in graphs, II[END_REF] requires additional definition. An odd ring is a graph obtained from an odd cycle by replacing every edge {u, v} by either a triangle containing {u, v}, or by two triangles on vertices {u, a, b} and {v,

	Ref.	Guest class H	Host class G			T.	Up.-bound on the gap
			planar graphs			e	2k
	[Tuz90]	triangles	G with ||G||	≥	e	2k
			7|G| 2 /16
			tripartite graphs		e	7k/3
	[Kri95]	triangles	T (K 3,3 )-free graphs	e	2k
	[HK88]	triangles	tripartite graphs		e	1.956k
	[Hax99]	triangles	any			e	(3 -3 23 )k
	[ALBT11]	triangles	odd-wheel-free graphs		e	2k
			4-colorable graphs
	[HKT11]	triangles	K 4 -free graphs	planar	e	3k/2
			K 4 -free flat graphs
	6.1.3 Cycles
		class H	Host class G			T.	Up.-bound on the gap
	[Kőn31]	K 2	bipartite			v	k
	[LY78] [Lov76]	directed cuts	any digraph			e	k
	[Men27]	(S, T )-paths	any			v/e k
	[Grü38]	directed (S, T )-paths any digraph			v/e k
	[Gal64]	S-paths	any			v	2k
	[Mad78b]	S-paths	any			v	see [Sch01]
	[Mad78a]	S-paths	any			e	see [SS04]
	[CGG + 06] non-zero directed S-	edge-group-labeled		v	2k -2
		paths	digraphs
	[MW15]	H-valid paths, H	any			v	2 2 O(k+t)
		with no matching of
		size t
	[FJW13], Th. 4.4	M(H), H forest	any			v	O H (k)
	6.1.2 Triangles
	A graph is flat if every edge belongs to at most two triangles.

  is a half-integral immersion of a graph G is H is an immersion of the graph obtained by G after duplicating the multiplicity of all its edges. We denote by I 1/2 (H) the class of all graphs containing H as a half-integral immersion. See above the definition of I(G).

	Ref. Ref.	Guest class H Guest class H	Host class G Host class G	T. T.	.-bound on the gap Up.-bound on the gap Up.-bound on the gap
	[EP65] [Ree99] [Tho88]	cycles odd cycles T (0 mod t) (H), H pla-	any planar graphs any	v v v	O(k log k) superexponential -
	[Sim67] [FHRV05]	cycles odd cycles nar subcubic	any planar graphs	v v	(4 + o(1)) k log k 10k
	[Vos68] [Tho01] [LPW14]	cycles odd cycles T (H), H ∈ L	any 2 3 9k -connected any	v v v	(2 + o(1)) k log k 2k -2 -
	[Die05] [AKKW16] T (H), H ∈ W cycles	any graphs any digraph	e v	(2 + o(1))k log k -
	[DZ02] [RR01]	cycles odd cycles and H strongly-	G 1 , weighted 576k-connected	w v	k 2k -2
	[DXZ03]	cycles connected	G 2 graphs	v	k
	[KLL02] [KR09] 6.1.8 Immersion expansions odd cycles cycles	planar graphs 24k-connected outerplanar graphs graphs	v v v	5k 2k -2 2k
	[MYZ13] [RRST96] [RS96] [GT11] [Ree99] [KN07] A graph H Ref. [BR00] [Liu15]	cycles directed cycles directed cycles directed cycles odd cycles odd cycles Guest class H odd cycles I(H)	planar graphs any digraph planar digraphs strongly planar di-graphs k-near bipartite graphs embeddable in an orientable surface of Euler genus t Host class G any 4-edge-connected	v e v v v v v/e -3k 4k -1 -O(k log(k) log log k) -T. Up.-bound on the gap k e -e -
	[LY78] [Sey96] [KV04] [FHRV05] [KK16] Cor. 3.18 Lemma 3.17 [GKRT16a],	directed cycles directed cycles odd cycles odd cycles trivial cubic connected non-I(H), H planar	F planar digraphs eulerian digraphs with a linkless em-planar graphs 4-edge-connected graphs any	e e e e e	k k 2k 2 2 O(k log k) ( H • k) O(1)
	[Ree99]	odd cycles	bedding in 3-space any	v 1/2 -
	[HJW16] [NL]	cycles non homo-even cycles	embedded graphs any	v 1/2 -v -
	[Tho88]	loguous to zero cycles of length 0	any	v	-
		mod t
	6.1.4 Cycles with length constraints [KW06] non-zero cycles (15k/2)-connected	v	2k -2
			group-labeled graphs
	[Wol11]	non-zero cycles	group-labeled graphs, c.f. [Wol11]	v	c k c for some c, c
		cycles of non-zero	any
		length mod 2t + 1
	[HJW16]	doubly non-zero cy-cles, c.f. [HJW16]	doubly labeled graphs group-	v 1/2 -
		odd cycles non ho-	embedded graphs
		mologuous to zero
	[NL]	C ≥t	any	v	-
	[BBR07]	C ≥t	any	v	(13 + o t (1))tk 2
	[FH14]	C ≥t	any	v	(6t + 4 + o t (1))k log k
	[MN ŠW16]	C ≥t	any	v	6kt + (10 + o(1))k log k
	[HM13]	C ≥3	any digraph	v	-
	6.1.5 Extensions of cycles
	A dumb-bell is a graph obtained by connecting two cycles by a (non-trivial) path.

The class of cycles (resp. directed cycles) of length at least t is referred to as C ≥t (resp. C ≥t ). For every positive integer k with, we say that a graph is k-near bipartite if every set X of vertices contains a stable set of size at least |X|/2 -k.

  The next table presents lower bounds on the gap for several graph classes, as well as graph classes that do not have the Erdős-Pósa property. It indicates to which extend the results of the table of Subsection 6.1 are best possible. The notation used here are the same as in the previous section, where they are defined.

	6.2.1 Cycles and paths 6.2.2 Patterns related to containment relations
	Ref. Ref.	Guest class H Guest class H	Host class G Host class G	T.	Gap T.	Gap
	class H triangles from [EP65] M(H), H has a cycle [Tuz90]	Host class G all graphs all graphs	T. e	Up.-bound on the gap ≥ 2k v Ω(k log k)
	[HS58] [EP65] [RS86]	subpaths cycles M(H), H non-planar	paths all graphs all graphs	v v	k Ω(k log k) v arbitrary
	[GL69] [GL69] [Kai97] [Alo98] [Alo02] [KKM11] [PW12] [BJS14] [Joo14] [Sim67] Lemma 5.7 M(H), H non-planar t-subpaths subgraphs H with cc(H) ≤ t t-subforests subtrees of a tree t-subpaths t-subpaths subgraphs H with cc(H) ≤ t subgraphs H with cc(H) ≤ t S-cycles S-cycles S-cycles ∩ C ≥t odd S-cycles cycles [Vos68] cycles Lemma 5.2 T (H), H non-planar [KLL02] cycles [Tho88] T (p mod t) (H), H planar sub-t-paths paths t-forests trees t-paths t-paths trees {G, tw(G) ≤ w} any any any 50k-connected all graphs all graphs all graphs all graphs planar graphs all graphs [MYZ13] cycles planar graphs cubic, p ∈ {1, . . . , t -1} [Tho88] T (H), for infinitely many planar graphs [DNL87] odd cycles all graphs trees H with ∆(H) = 4 [Ree99] odd cycles all graphs Lemma 5.3 T (H), H non-planar subcubic all graphs [Tho01] odd cycles planar graphs copying I(H), for infinitely many planar graphs [KV04] odd cycles planar graphs [Tho88] trees H with ∆(H) = 4 [DNL87] cycles of length 2 p q mod 2 r s all graphs Cor. 5.5 I(H), H non-planar all graphs Cor. 5.6 I(H), H non-planar subcubic all graphs with [GKRT16a] I(H), for some 3-connected H planar graphs p, q, r, s ∈ N ≥1 , q, s with ∆(H) = 4 odd and p < r [DNL87] directed cycles of all digraphs [Liu15] I(H), for every H 3-edge-connected v v v v v v v v v/e O(k log k) O(k t! ) --k (t 2 -t + 1)k 2t 2 k 2t 2 k 2(w + 1)t 2 k O(k 2 log k) v O(tk log k) v O(k) v > 1 e arbitrary 2 + o(1) k log k v ≥ 1 v arbitrary 8 + o(1) k log k v v arbitrary ≥ 2k e ≥ 4k -c, e arbitrary c ∈ N v arbitrary e e arbitrary arbitrary v e arbitrary ≥ 2k -2 e ≥ 2k v v arbitrary arbitrary e arbitrary e arbitrary e e arbitrary arbitrary graphs length 2 p q mod 2 r s graphs [KK13] odd S-cycles any v 1/2 -as above [DNL87] directed odd cycles all digraphs e arbitrary [AKKW16] M (H), H ∈ P an H strongly-connected all digraphs v arbitrary
	[KK12] [PW12]	directed S-cycles S-cycles	all digraphs all graphs	v 1/5 -v Ω(k log k)
	[KKKK13] odd directed S-[KK13] odd S-cycles	any digraph all graphs	v 1/2 -v arbitrary
	[HJW16] [KK12] [KM15] [KKKK13]	cycles (S 1 , S 2 )-cycles directed S-cycles (S 1 , S 2 , S 3 )-M(H), S-cycles odd directed	any all diraphs any all digraphs	v/e arbitrary v --v v arbitrary
		H planar			Ω(k log k),
	[FH14]	C ≥t	all graphs	v	t fixed
	6.1.10 Classes with bounded parameters		Ω(t), k fixed
	Ref. [Tho88] [MN ŠW16] C ≥t Guest class H any family of con-[Sim67] dumb-bells nected graphs [FJW13] {H, pw(H) ≥ t} [MW15] H-valid paths, [CRST15a] any finite family of connected graphs matching of size t H with no	Host class G {G, tw(G) ≤ t} all graphs all graphs any all graphs {G, tpw(G) ≤ t}	T. v v v v v v/e O t (k) Up.-bound on the gap ≥ (k -1)t ≥ (k-1) log k 8 k(t + 1) > (1 + o(1))k log k unavoidable depen-O t (k) dency in t
	6.2 Negative results

T (H), H ∈ W and H strongly-connected

Acknowledgements

The authors wish to thank Dimitris Chatzidimitriou, Fedor V. Fomin, Gwenaël Joret, Daniel Lokshtanov, Ignasi Sau, and Saket Saurabh for sharing their ideas and viewpoints on the Erdős-Pósa property, as well as the anonymous referees for their useful comments.

‡ Supported by the grant PRELUDIUM 2013/11/N/ST6/02706 of the Polish National Science Center (NCN).

Ref.

Guest class H

Host class G T.

Up.-bound on the gap [START_REF] Simonovits | A new proof and generalizations of a theorem of erdős and pósa on graphs without k + 1 independent circuits[END_REF] dumb We also denote by M (D) (respectively T (G)) the class of all digraphs that contain D as a butterfly-minor (respectively as a butterfly topological minor). P (respectively W) is the class of all graphs that are butterfly minors of a cylindrical directed grid (respectively butterfly topological minors of a cylindrical directed wall). See for instance [START_REF] Saeed Akhoondian Amiri | The Erdős-Pósa property for directed graphs[END_REF] for a definition of the cyclindrical directed grid and wall and [JRST01, AKKW16] for a definition of butterfly (topological) minors.

For every s ∈ N, a digraph is said to be s-semicomplete if for every vertex v there are at most s vertices that are not connected to v by an arc (in either direction). A semicomplete digraph is a 0-semicomplete digraph.

Ref.

Guest class H Host class G T.

Up.-bound on the gap

simple graphs e -[AKKW16] M (H), H ∈ P and H stronglyconnected any digraph v -

Subdivisions

For every t ∈ N, T (0 mod t) (H) denotes the class of subdivisions of H where every edge is subdivided 0 mod t times. L is a graph class defined in the (unpublished) manuscript [START_REF] Liu | Erdős-Pósa property for the topological minors[END_REF]. See the previous section for the definition of T (G) and W.


Kouilily Fatiha
email: kouililyfatiha@gmail.com

Aboulkhouatem Fatima-Ezzahra

Yousfi Noura

El Khasmi

Achtaich Naceur

Mathematical model of hearing loss caused by viral infection

Keywords: viral infection, ordinary differential equations, stability

Hearing loss may be caused by a number of factors, including: genetics, ageing, exposure to noise, some infections, birth complications, trauma to the ear, and certain medications or toxins. In this study, we propose a new mathematical model of hearing loss resulting from the infectious disease using the ordinary differential equations with the objective to analyze the local and global stability of the model. In addition, we present some numerical simulations in order to validate our theoretical results

Introduction

Hearing loss may result from genetic causes, complications at birth, certain infectious diseases, chronic ear infections, the use of particular drugs, exposure to excessive noise, and aging, which is represent a major global health problem. According to the World Health Organization (WHO), about 360 million people worldwide have disabling hearing loss, and 32 million of these are children [START_REF]Deafness and hearing loss[END_REF].

The are many infections and contagious diseases related to hearing loss such as mumps. Mumps is an enveloped, single-stranded RNA virus belonging to the family paramyxoviridae, and causes an acute infectious disease mainly in children and young adults [START_REF] Gupta | Mumps and the UK epidemic[END_REF]. Mumps is transmitted through infected respiratory secretions and is highly contagious [START_REF] Cohen | Viral causes of hearing loss: a review for hearing health professionals[END_REF]. The most common clinical manifestations of infection include a flu-like illness and bilateral swelling of the parotid glands.

Mumps infection occasionally induces the potential for complications such as pancreatitis, orchitis, oophoritis, aseptic meningitis, encephalitis and sensorineural hearing loss. Hearing loss due to mumps is thought to be unilateral and profound with rapid onset [START_REF] Morita | The clinical features and prognosis of mumps-associated hearing loss: a retrospective, multi-institutional investigation in Japan[END_REF].

To better understand the dynamics of hearing loss, we introduce a new mathematical model by using ordinary differential equations (ODEs). In this paper, we consider the hearing loss model caused by mumps(contagion factor).

This model is described by the following system of ODEs:

dH dt = Λ -µH -βLH dL dt = βLH -(µ + γ)L dR dt = γL -µR (1)
The population is divided into three epidemiological classes that are : H(t) is the number of susceptible individuals (normal hearing), L(t) is the number of infected individuals (loss of hearing), and R(t) is the number of removed individuals at time t (recovered hearing). Where Λ is the recruitment rate of the population, µ is the natural death rate of the population, β is the transmission rate due to social contagion of hearing loss (Mumps),γ is the recovery rate of the infective individuals. The first two equations in system (1) do not depend on the third equation, and therefore this equation can be omitted without loss of generality. System (1) can be rewritten as;

dH dt = Λ -µH -βLH dL dt = βLH -(µ + γ)L (2)
The paper is organized as follows. In the next section, Positivity and boundedness of solutions are studied. In Section 3, the basic reproduction number is derived, also the local and the global asymptotic stability of the equilibrium point are analyzed. The numerical result is obtained in Section 4. Lastly, we give a conclusion of our results in Section 5.

Positivity and boundedness of solutions

In this section, we will establish the positivity and boundedness of solutions of model [START_REF]Deafness and hearing loss[END_REF], which imply that our model is well posed. Proposition 2.1 All solutions starting from non-negative initial conditions exist for all t > 0 and remain bounded and non-negative.

Proof.

For the positivity, we show that any solution starting in non-negative orthant

R 3 + = {(H,L,R) ∈ R 3 + : H ≥ 0, L ≥ 0, R ≥ 0}.
In fact (H(t),L(t),R(t)) ∈ R 3 + and we have;

dH dt | H=0 = Λ 0 dL dt | L=0 = 0 0 dR dt | R=0 = γL 0 (3)
This proves the positivity of solutions. Now, we prove that the solutions are bounded. We define T(t)=H(t)+L(t). By non-negativity of the solution, it follows that;

dT (t) dt = Λ -µH -(µ + γ)L dT (t) dt Λ -µ(H + L)
We deduce that;

T (t) Λ µ + (H(0) + L(0))e -µt Λ µ
Hence, H(t) and L(t) are bounded. Next, we show the boundedness of R(t).

dR dt = γL -µR dR dt γΛ µ -µR Then, R(t) Λγ µ 2
Finally, all the solutions are bounded.

Stability analysis for Hearing loss

Notice that the system (1) has a basic reproductive number of R 0 = βΛ µ(µ + γ) R 0 represents the average number of secondary infections caused by an infective individual introduced into a group of susceptible. By equalizing to zero the rights members of the system (1), we find two equilibrium points that exists for above model: 1. Disease-free Equilibrium Point E f = ( Λ µ , 0, 0).

2. Endemic equilibrium point E * = (H * , L * , R * ) where;

H * = (µ + γ) β L * = µ(β Λ µ -µ -γ) β(µ + γ) R * = γ(β Λ µ -µ -γ) β(µ + γ)
The endemic equilibrium point exist only when β Λ µ > γ + µ i.e the infection rate must be greater than the death rate of the infected individuals or R 0 > 1.

Local stability of equilibria

The following theorems discusses the local stability of the equilibrium point.

Theorem 3.1 1. If R 0 < 1, then the disease-free equilibrium, E f is locally asymptotically stable. 2. If R 0 > 1, E f is unstable.
Proof.

The Jacobian matrix evaluated in the disease-free equilibrium E f = ( Λ µ , 0, 0) is given by

J(E f ) =      -µ -β Λ µ 0 0 β Λ µ -(γ + µ) 0 0 γ -µ      (4)
whose eigenvalues are λ 1 = -Λ and

λ 2 = β Λ µ -γ -µ λ 1 = -µ < 0 and λ 2 = β Λ µ -γ -µ < 0 then R 0 < 1 and therefore E f is locally asymptotically stable. The disease-free equilibrium point is unstable if β Λ µ -γ -µ > 0 which translate into R 0 > 1 .
Now, we focus on local stability of the endemic infection equilibrium E * .

Theorem 3.2 1. If R 0 > 1, E * is locally asymptotically stable.

2. If R 0 < 1, then the endemic equilibrium E * does not exist.

Proof. By substituting the endemic equilibrium E * = (H * , L * , R * ) in the Jacobien matrix of the system (8)

J(E * ) =           -µ( β Λ µ -γ -µ γ + µ + 1) -(γ + µ) 0 µ( β Λ µ -γ -µ γ + µ ) 0 0 0 γ -µ           (5)
The characteristic equation of the endemic equilibria point is given by

(-µ -λ)(λ 2 + βλ γ + µ + µ(βN -γ -µ)) = 0 (6)
The disease persists when L * > 0 then R 0 > 1

Clearly when R 0 > 1, both

µβ Λ µ µ + γ > 0 and µ(β Λ µ -γ -µ) > 0,
then all roots of the characteristic equation have negative real parts. Consequently E * is locally asymptotically stable.

Global stability of equilibria

The following theorem discusses the global stability of the endemic equilibrium.

Theorem 3.3 The endemic equilibrium E * of the system (1) is globally asymptotically stable E * .

Proof. Consider the following Lyapunov functional;

W (t) = H * ε (t)φ( H(t) H * ε (t) ) + L * ε (t)φ( L(t) L * ε (t) ) (7)
Where φ(t) = x -1 -ln(x) x ∈ R + . Obviously, φ : R + → R + attains its global minimum at x = 1 and φ(1) = 0. To simplify the presentation, we shall use the following notation: H = H(t) and L=L(t).

W (t) = H * ( H(t) H * ε -1 -ln( H(t) H * ε )) + L * ε ( L(t) L * ε -1 -ln( L(t) L * ε )) = Ḣ(1 - H * ε H ) + L(1 - L * ε L ) = (Λ -µH -βLH)(1 - H * H ) + (1 - L * L )([βLH -(γ + µ)L) Note that Λ = µH * + (µ + γ)L * and (βL * H * = (µ + γ)L * Hence, Ẇ (t) = (1 - H * ε H )(µH * + (µ + γ)L * -µH -βLH + (1 - I * I )(βLH -(µ + γ)L) Ẇ (t) = µ(1 - H * H )(H * -H) + (µ + γ)L * (1 - H * H ) -(1 - L * L )βLH + (1 - L * L )βLH -(µ + γ)L(1 - L * L ) = µ(H * -H)(1 - H * H ) + (µ + γ)L * (1 - H * H + β H * L (µ + γ)L * ) + (µ + γ)L * (1 - L L * - βLH (µ + γ)L ) = µ(H * -H)(1 - H * H ) + (µ + γ)L * (-1 - L L * + (µ + γ)L βH * L + βH * L (µ + γ)L * ) -(µ + γ)(φ( H * H ) + ln( H * H ) + φ( (µ + γ)L H * (βL + ε) + ln( (µ + γ)L βH * L + φ( βLH (µ + γ)L ) + ln( βLH (µ + γ)L )
Then, we obtain the following equation:

Ẇ (t) = µ(H * -H)(1 - H * H ) + (µ + γ)L * (-1 - L L * + (µ + γ)L βH * L + βH * L (µ + γ)L * ) -(µ + γ)L * [φ( H * H ) + φ( (µ + γ)L βH * L + φ( βLH (µ + γ)L )] -1 + L L * + (µ + γ)L βH * L + βH * L (µ + γ)L * (8)
From (7), we have: )] 0

-1 + L L * + (µ + γ)L βH * L + βH * L (µ + γ)L * = -1 - L L * + f (H, L * ) f (H, L) + L L * f (H, L) f (H, L * ) Where f (H, L) = βH = -1 - L L * βHL * βHL + βHL βHL * = -1 + L L * [-1 + (βHL * ) 2 L + L * ( βHL) 2 L(βHL)(βHL * )] = -1 + L * (βL) 2 + L(βL * ) 2 -(βL)(βL * βL * LβL * = -(L + L * )βLβL * + L * (βL) 2 + (βL * ) 2 L L * βLβL * = 0 Since,              µ(H * -H)(1 - H * H ) 0 (µ + γ)L * (-
We have Ẇ (t) 0. Thus, E * is stable, and Ẇ = 0 if and only if H = H * and L = L * . From LaSalle invariance principle [START_REF] Lasalle | The stability of dynamical systems[END_REF], we conclude that E * is globally asymptotically stable.

Numerical simulations

In this section we show the numerical simulations and the graphs of system (1) to illustrate the different result obtained for each of the two cases ε > 0 and ε = 0 previously analyzed.

Figure 1 :

 1 Figure 1: Normal hearing and loss of hearing individuals as function of time in the case of R 0 < 1.

Figure 2 :

 2 Figure 2: Normal hearing and loss of hearing individuals as function of time in the case of R 0 > 1.

We choose the following data set of system (1) as follows: Λ = 0.5, µ = 0.1, and γ = 1 17 .

By calculation, we have β=0.1433 for R 0 > 1 already defined for Mumps disease [START_REF] Edmunds | The pre-vaccination epidemiology of measles, mumps and rubella in Europe: implications for modelling studies[END_REF]. Therefore, according to Theorem 3.2 has a unique endemic equilibrium, the solution of system (1) is persistent in mean, this result is illustrated in Figure 1 In this case, the system (8) has a disease free equilibrium E f = (5.0) which is globally asymptotically stable when R 0 < 1. We have R 0 = 4.4 > 1 which satisfy Theorem 3.6, then the endemic E * = (1.1364, 2.4327) is globally asymptotically stable (see Figure 2).

Conclusion

In this paper, we have presented a mathematical model of hearing loss based on a nonlinear system of differential equations. We analysis the hearing loss resulting from contagious factor due to Mumps disease.

By analysis the model, we have proved the existence, positivity and the boundedness of solutions of the problem, which implies that the model is well posed. We have shown in the case of that the disease free equilibrium is globally asymptotically stable if the basic reproductive number R 0 < 1 and the endemic point is globally asymptotically stable when R 0 > 1, which means that the disease persists in the population. The next stage of our research project is to analysis the model in the case of the hearing loss model caused by mumps(contagion factor) and noise exposure (social factor).

Conflict of Interests

The authors declares that there is no conflict of interest regarding the publication of this paper.