Peter Hudák

František Kardoš

Tomáš Madaras

Michaela Vrbjarová

František Košice

Kardoš

Tomáš Bordeaux

Madaras

On improper interval edge colourings

Keywords: Interval colorings edge colouring, interval colouring, improper colouring MSC 2010: 05C15

In this paper, we study improper interval edge colourings, defined by the requirement that edge colours around each vertex form an integer interval. For the corresponding chromatic invariant (being the maximum number of colours in such a colouring), we present upper and lower bounds and discuss their qualities; also, we determine its values and estimates for graphs of various families, like wheels, prisms or complete graphs. The study of this parameter was inspired by interval colouring, introduced by A.S. Asratian, R.R.

Introduction

Throughout this paper, we consider simple connected graphs without loops or multiple edges; we use standard graph terminology from the book [START_REF] Diestel | Graph theory[END_REF].

A proper edge colouring c : V (G) → {1, . . . , k} of a graph G which uses each colour from {1, . . . , k} at least once is called an interval colouring if, for each vertex x of G, the set of colours of edges incident with x (the palette of x) forms an integer interval; we say that the graph G is an interval k-colourable. For an interval colourable graph This work was supported in part by French national agency for the promotion of higher education, international student services, and international mobility under the bilateral contract No. 31777QK, by Slovak Science and Technology Assistance Agency under the bilateral Slovak-French contract No. APVV-SK-FR-2013-0028, VVGS-PF-2014-447, VVGS-2014-179 and VVGS-PF-2015-484. Also, this study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the "Investments for the future" Programme IdEx Bordeaux -CPU (ANR-10-IDEX-03-02).

G, let t(G) denote the maximum number of colours used in any interval colouring of G. The notion of interval colouring was introduced by Asratian and Kamalian in [START_REF] Asratian | Investigation of interval edge-colorings of graphs[END_REF] in the connection with specialized scheduling problems and, since then, it was further investigated in many papers, see, for example [START_REF] Axenovich | On interval colorings of planar graphs[END_REF][START_REF] Giaro | The complexity of consecutive ∆-coloring of bipartite graphs: 4 is easy, 5 is hard[END_REF][START_REF] Giaro | lafiejski: On the deficiency of bipartite graphs[END_REF][START_REF] Giaro | Ma lafiejski: Consecutive colorings of the edges of general graphs[END_REF][START_REF] Janczewski | lafiejski: Interval incidence graph coloring[END_REF][START_REF] Khachatrian | Interval edge-colorings of complete graphs[END_REF][START_REF] Petrosyan | Interval edge-colorings of complete graphs and n-dimensional cubes[END_REF]. Not all graphs are proper interval colourable (this concerns, for example, graphs of Class 2); in fact, the problem of determining whether a graph has an interval colouring is NP-complete, even for bipartite graphs, see [START_REF] Asratian | Interval colorings of edges of a multigraph[END_REF] and [START_REF] Sevast | janov: Interval colorability of the edges of a bipartite graph[END_REF].

In our paper, we relax the requirement of the above defined colouring to be proper and introduce the parameter t(G) being the maximum number of colours in an improper interval colouring of G. Note that t(G) is defined for every graph (which is in sharp contrast with t(G), see [START_REF] Axenovich | On interval colorings of planar graphs[END_REF]) and is at least 3 for all graphs of order at least 3 different from K 3 . Also, for a graph G which is interval colourable, t(G) ≤ t(G) holds. Compared to the range of results for interval colourings, it seems that improper interval colourings have not been studied yet. Our aim is to contribute to this topic by determining the exact values of t(G) or their estimates for graphs of several classic families (this concerns also many graphs which do not possess proper interval colourings), and to establish upper and lower bounds on t(G) in terms of graph diameter and maximum degree.

Properties and results

In the analysis of improper interval colourings, the following observations (which are easy to see) will be useful:

Proposition 2.1. If a graph G is improperly interval k-colourable with k ≥ 3,
then it is also improperly interval k-colourable in such a way that the colours 1 and k are used exactly once.

Proposition 2.2. A graph G is improperly interval ℓ-colourable for each 1 ≤ ℓ ≤ t(G).
First, we present an upper bound on t(G) in terms of maximum degree and diameter:

Lemma 2.3. For any connected graph G with maximum degree ∆ = ∆(G), t(G) ≤ 1 + (∆ -1)(diam(G) + 1).
Proof. Let uv and xy be edges coloured by 1 and k, respectively, in an improper interval colouring of G using t(G) colours. Observe that, in each such a colouring, the colours of each two adjacent edges differ by at most ∆ -1. Now, take the shortest path P between the vertex sets {u, v} and {x, y}. Then P has length at most diam(G); note, however, that the edges uv and xy need not belong to P .

It follows that the number of colour changes from uv to xy along P is at most diam(G) + 1 which implies the result.

Note that this lemma generalizes the result of [START_REF] Asratian | Investigation of interval edge-colorings of graphs[END_REF] where the right side of the above inequality estimated t(G) from above. Using the same arguments, we can prove an analogous inequality with respect to the diameter of the line graph L(G): Lemma 2.4. For any connected graph G with maximum degree ∆ = ∆(G), t(G) ≤ 1 + (∆ -1)(diam(L(G)); the bound is sharp.

We also present strengthenings of two theorems from [START_REF] Asratian | Investigation of interval edge-colorings of graphs[END_REF]: Theorem 2.5. For each triangle-free graph G on n vertices, t(G) ≤ n -1; the bound is sharp.

Proof. We follow the same reasoning as in the proof of Theorem 1 from [START_REF] Asratian | Investigation of interval edge-colorings of graphs[END_REF]; the difference is only in the estimate of the number of elements of the set A(i) (see original proof, page 38): we obtain that, for improper interval t-colouring of G, the inequality

|A(i)| ≥ f (e i ) -f (e i+1 ) -1, i = 1, . . . , k -1, holds (instead of equality).
Then the last argument of the original proof rephrases as

n ≥ k + 1 + k-1 i=1 |A(i)| ≥ k + 1 + k-1 i=1 (f (e i ) -f (e i+1 ) -1) = = k + 1 + t -1 -(k -1) = 1 + t, implying t ≤ n -1.
To show the sharpness of the bound, consider the graph of path on n vertices P n , n ≥ 2. It is easy to see that t(P n ) = n -1.

Since the original proof of the Proposition 4 of [START_REF] Asratian | Investigation of interval edge-colorings of graphs[END_REF], page 39 does not involve a considered interval colourings to be proper, we obtain Theorem 2.6. For each graph G on n vertices, t(G) ≤ 2n -1.

For the lower bound on t(G), we have the following estimate: Theorem 2.7. For each graph G, t(G) ≥ 1 + diam(L(G)); the bound is sharp.

Proof. Consider the line graph L(G) of G and let x be a vertex of maximum eccentricity in L(G). Then colour x with the colour 1 and each vertex y ∈ V (L(G)), y = x with the colour equal to 1 + dist L(G) (x, y). This vertex colouring of L(G) induces an edge colouring of G. The way the colouring of vertices of L(G) was constructed gives that, in G, the palette of each vertex consists either of two consecutive colours or of a single colour; thus, it is an improper interval colouring of G having the highest colour equal to diam(L(G)) + 1. To show the sharpness of the lower bound, consider, for an integer k ≥ 6 the graph DB k obtained from a k-vertex path x 1 x 2 . . . x k by adding new edges x 1 x 3 and

x k-2 x k . Then it is easy to check that t(DB k ) = k -1 and diam(L(DB k )) = k -2.
The difference between t(G) and t(G) can be arbitrarily large. This can be seen on the graph SN k formed from a chain of k copies of the graph K - 4 where both chain ends are closed with a different triangle, see Figure 1. It is easy to see that the graph SN k has proper interval colouring; observe that, in each proper interval colouring of SN k , the difference of colours of two consecutive bridges incident with the same copy of K - 4 is 0 or 3 while it is possible to construct an improper colouring of SN k such that the colour difference on consecutive bridges is 4. Thus, we obtain that t(SN k )t(SN k ) ≥ k. A similar construction can be used also for triangle-free graphs, where instead of copies of K - 4 , the 5-cycle with pendant edges incident with two nonadjacent vertices is used: the difference of colours on bridges in a proper interval colouring is at most 3 whereas it is possible to assign the colours to obtain the difference 4 in an improper interval colouring, see Figure 2.

The construction generalizes to classes of graphs of arbitrarily large girth. Moreover, one can consider several other suitable configurations to show that the colour difference on two selected edges can be greater in improper version of the colouring rather than in the proper one, and these configurations may be used to form other graphs (for example, 2-connected) with arbitrarily large difference of t(G) and t(G).

There is no known significant upper bound on difference t(G)t(G) in terms of number of vertices of G.

In the following, we establish the exact values and estimates of t(G) of graphs from several standard graph families. Theorem 2.8. For an n-wheel W n ,

t(W n ) = 4, if n = 3; n, if n ≥ 4.
Proof. Suppose first that n = 3. If t(W 3 ) ≥ 5, then the unique edge of W 3 which is not adjacent to the edge of maximum colour would have a colour at least 2, so colour 1 is not used, a contradiction; on the other hand, an improper interval 4-colouring of W 3 is easy to find. Now, let n ≥ 4. An improper interval n-colouring of W n can be constructed as follows: if x is the centre of W n and x 1 , . . . , x n are its neighbours in counter clockwise order, assign to each edge x i x i+1 , 1 ≤ i ≤ n 2 the colour 2i -1, to each edge x i x i+1 , n 2 < i ≤ n (indices taken modulo n) the colour 2n+ 4 -2i, and to each edge xx i , i ∈ {1, n 2 + 1} the colour equal to the arithmetic mean of colours of edges x i-1 x i , x i x i+1 whereas the edge xx 1 receives colour 1 and the edge xx ⌈ n 2 ⌉+1 receives the colour n. It is easy to check that, in this colour assignment, the palettes of all vertices form integer intervals (note that the palette of x 1 is [START_REF] Asratian | Interval colorings of edges of a multigraph[END_REF][START_REF] Asratian | Investigation of interval edge-colorings of graphs[END_REF] and the palette of

x ⌈ n 2 ⌉+1 is [n -1, n]
). See Figure 3 for illustration. Assume now that, for some n, t(W n ) ≥ n+1. Consider first the case when n is odd. Then at least one of colours 1 and n + 1 is used at a rim edge of W n (otherwise the palette of the central vertex of W n does not form an integer interval). Since replacing each colour c with the colour n+2-c yields also an improper interval (n+1)-colouring of W n , we can suppose, without loss of generality, that the colour 1 is used on a rim edge uv. Note that colours of two adjacent rim edges can differ by at most 2; this gives that two edges yw, wz which are -taking into account the bidirectional distance on the rim -most distant from uv have colour at most 1 + 2 • n-1 2 = n. Thus, the colour n + 1 has to appear at a spoke edge of W n and, repeating the above colour difference argument, we obtain that this spoke edge is incident with the vertex w.

Due to the fact that, in the considered improper interval colouring, the colour 1 is unique, the edge uv is adjacent with at least two edges coloured by 2 and at least one of them -say, vq -is a rim edge (otherwise again, the palette of the central vertex is not an integer interval). Then the colour sequence of the rim path P from uv through vq ending in one of rim edges incident to w, is 1, 2, 4, . . . , 2i, 2(i + 1), . . . , n -1; this gives that one of yw and wz has colour n -1 and the other one has the colour n. Now, if we take the rim path P ′ starting at uv, but with the opposite direction as P , we get that its colour sequence is 1, 3, 5, . . . , 2i -1, 2i + 1, . . . , n. But then the colour n does not appear at a spoke edge, hence, the palette of the central vertex is not an integer interval, a contradiction. Consider now the case when n is Rephrasing the above arguments, we can suppose that the colour 1 is used on a rim edge uv. According to the possible position of the colour n + 1, we distinguish two cases:

Case 1: The colour n + 1 is on a rim edge. Then the colour sequences of both rim paths starting at uv are 1, 3, 5, . . . , 2i -1, 2i + 1, . . . , n + 1, which gives that colours of all spoke edges are even numbers, a contradiction.

Case 2:

The colour n + 1 is on a spoke edge xw. Let yw and wz be rim edges adjacent to xw; without loss of generality, let yw be closer to uv than wz to uv. Then the colour sequence of a rim path starting at uv and ending at yw is 1, 3, . . . , 2i -1, 2i + 1, . . . , n -1, which gives that wz has colour n. By the same argument as for n odd, the colour 2 has to be used on a rim edge incident with uv, hence, the colour sequence of the rim path between uv and wz is 2, 4, . . . , 2i, 2(i + 1), . . . , n. But then again, the colour n is missing at spoke edges, a contradiction.

Note that, by [START_REF] Axenovich | On interval colorings of planar graphs[END_REF], only three wheels are proper interval colourable, namely W 3 , W 6 and W 9 .

Next, we present exact value for a graph Y n = C n K 2 , the graph of an n-sided prism.

Theorem 2.9. For an n-prism graph

Y n with n ≥ 3, t(Y n ) = n + 2. Proof. Let Y n = C n K 2 .
In a plane drawing of Y n , there are two n-gonal faces x 1 , x 2 , . . . , x n and y 1 , y 2 , . . . , y n interconnected by the edges x i y i , i = 1, . . . , n (the side edges); the edges of type x i x i+1 or y i y i+1 (i = 1, . . . , n indices are modulo n) will be called base edges in the sequel.

First we show that there exists an improper interval colouring of graph Y n by n+ 2 colours. It can be constructed as follows: Assign the edge x 1 y 1 colour 1, the edges x 1 x 2 , y 1 y 2 colour 2, the edges x 1 x n , y 1 y n colour 3 and the edge x ⌈ n 2 ⌉+1 y ⌈ n 2 ⌉+1 assign colour n + 2. Now, assign edges x i y i colour 2i -1 for i = 2, . . . , ⌈ n 2 ⌉. Remaining side edges x i y i assign colour 2(ni) + 4 for i = n, . . . , ⌈ n 2 ⌉ + 2. The colours of remaining base edges are now determined unambiguously, see Figure 4 for illustration. Now we prove that the colouring is optimal. Observe that diam(L(Y

n )) = ⌊ n 2 ⌋ + 1, hence Lemma 2.4 gives an upper bound t(Y n ) ≤ 2 • ⌊ n 2 ⌋ + 3.
For n odd this meets the lower bound.

Suppose that n is even and there is an interval edge colouring of Y n with n + 3 colours. From the proof of Lemma 2.4 we know that for any pair of edges in G coloured 1 and n + 3 the corresponding vertices in L(G) are at distance diam(L(G)). It is possible either for a pair of side edges x i y i and x j y j with |i -j| = n 2 , or for a pair of base edges x i x i+1 and y j y j+1 with |i -j| = n 2 . In both cases all edges incident with the edge assigned colour 1 lie on some path of optimal length between edges assigned 1 and n + 3, so all these edges have to be assigned colour 3, which is a contradiction, since there is no colour 2 in the palettes of vertices incident with the edge assigned colour 1.

Finally, we discuss improper interval colourings of complete graphs which is of particular interest due to the ongoing intensive research in [START_REF] Khachatrian | Interval edge-colorings of complete graphs[END_REF], [START_REF] Petrosyan | Interval edge-colorings of complete graphs and n-dimensional cubes[END_REF].

Theorem 2.10. For a complete graph K n with n ≥ 5, t(K n ) ≤ 2n -5.

Proof. By contradiction. Assume that there exists a positive integer n ≥ 5 such that K n is improperly interval (2n -4)-colourable. Let xy and uv be edges coloured by 1 and 2n -4, respectively; note that xy and uv are not adjacent. Then the colour of xu (xv, yu or yv) is either n -2 or n -1. We claim that both palettes of x and y contain each of the colours 1, . . . , n -1 exactly once; similarly, both palettes of u and v contain each of the colours n -2, . . . , 2n -4 exactly once: If both xu and xv had colour n -2, then the palettes of u and v would contain each of the colours n -2, . . . , 2n -4 exactly once, hence, yu and yv would have colour n -1, which is impossible.

Let z be a vertex of K n such that zx has colour 2. Then the colour of the edge zu is at least n (because of u); note, however, that the difference of the highest and the lowest colour (which is the colour 2) in the palette of z is at most n -2 which gives that the highest colour in the palette of z is at most n. Therefore, the colour of zu is equal to n. The same argument can be used for the edge zv, obtaining that its colour is also n. But then the palette of z is not an integer interval, a contradiction. Theorem 2.11. For each n, t(K n ) < t(K n+1 ).

Proof. Let c be an improper interval t-colouring of K n with t = t(G), and let w 1 , . . . , w n be ordering of vertices of K n such that w 1 is incident with an edge of colour t. Now, add to K n a new vertex u and, for each 1 < i ≤ n, add new edge uw i coloured with the colour c(w 1 w i )+1; the edge uw 1 will be then coloured with t + 1. Theorem 2.12. For each n, t(K n+2 )t(K n ) ≥ 3.

Proof. Let c be an improper interval t-colouring of K n with t = t(G), and let w 1 , . . . , w n be ordering of vertices of K n such that w 1 and w 2 are endvertices of an edge of colour t. Now, add to K n two new vertices x, y and, for each 3 ≤ i ≤ n, add new edges xw i and yw i coloured with the colour c(w i w 1 ) + 1 and new edges xw 1 and yw 2 coloured with t + 1. In addition, add new edges yw 1 and xw 2 coloured with t + 2 and the new edge xy coloured with t + 3. 4j 4j + 1 4j + 2 4j + 3 4i 3i + 4j 3i + 4j + 1 3i + 4j + 2 3i + 4j + 3 4i + 1 3i + 4j + 1 3i + 4j 3i + 4j + 3 3i + 4j + 2 4i + 2 3i + 4j + 2 3i + 4j + 3 3i + 4j + 1 3i + 4j + 4 4i + 3 3i + 4j + 3 3i + 4j + 2 3i + 4j + 4 3i + 4j + 1 Table 1. Colouring of a complete graph on n = 4k vertices: the colour of an edge joining vertices 4i+r and 4j +s with 0 ≤ i < j ≤ k and r, s ∈ {0, 1, 2, 3}. 4i 4i + 1 4i + 2 4i + 3 4i 7i + 1 7i + 2 7i + 3 4i + 1 7i + 3 7i + 2 4i + 2 7i + 4 4i + 3 Table 2. Colouring of a complete graph on n = 4k vertices: the colour of an edge joining vertices 4i + r and 4i + s with 0 ≤ i ≤ k and 0 ≤ r < s ≤ 3.

Theorem 2.13. For each n, t(K n ) ≥ 7n-17 4 .

Proof. We prove first that t(K 4k ) ≥ 7k -3 for every k ≥ 1. The general bound is then implied by Theorems 2.11 and 2.12.

Let n = 4k for k ≥ 1, let G = K n , and let V (G) = {0, 1, . . . , n -1}. We define a colouring of the edges of G in the following manner: The colour of an edge joining vertices 4i + r and 4j + s with 0 ≤ i < j ≤ k and r, s ∈ {0, 1, 2, 3} is given in Table 1, the colour of an edge joining vertices 4i + r and 4i + s with 0 ≤ i ≤ k and 0 ≤ r < s ≤ 3 is given in Table 2. It is easy to observe that it is an (improper) interval colouring of G.

Note that, for proper interval colourings, it is not known whether the sequence {t(K n )} ∞ n=1 is monotone; also, any value of n for which t(K n-1 ) > t(K n ) yields that t(K n ) ≥ t(K n ) + 2.

To conclude this part, we list exact values of t(K n ) for some small values of n, see Table 3

Figure 1 .

 1 Figure 1. The graph SN k and its proper and improper interval colourings.

Figure 2 .

 2 Figure 2. An analogous construction for triangle-free graphs.

Figure 3 .

 3 Figure 3. Improper interval n-colouring of a wheel W n for n = 7 and n = 8.

Figure 4 .

 4 Figure 4. Improper interval (n + 2)-colouring of a prism Y n for n = 7 and n = 8.

Table 3 .

 3 . Bound and exact values of t(K n ) for small values of n.

	n 2 3 4 5 6 7 8 9 10 11 12
	lower bound from Theorem 2.13	4 5 7 8 11 12 14 15 18
	t(K n ) 1 2 4 5 7 8 11 12 14 16 18
	upper bound from Theorem 2.10	5 7 9 11 13 15 17 19


František Kardoš
email: frantisek.kardos@labri.fr.

Daniel Král'

Anita Liebenau
email: anita.liebenau@monash.edu

Lukáš Mach
email: lukas.mach@gmail.com.

First order convergence of matroids *

The model theory based notion of the first order convergence unifies the notions of the left-convergence for dense structures and the Benjamini-Schramm convergence for sparse structures. It is known that every first order convergent sequence of graphs with bounded tree-depth can be represented by an analytic limit object called a limit modeling. We establish the matroid counterpart of this result: every first order convergent sequence of matroids with bounded branch-depth representable over a fixed finite field has a limit modeling, i.e., there exists an infinite matroid with the elements forming a probability space that has asymptotically the same first order properties. We show that neither of the bounded branch-depth assumption nor the representability assumption can be removed.

Introduction

The theory of combinatorial limits keeps attracting a growing amount of attention. Combinatorial limits have sparked many exciting developments in extremal combinatorics, in theoretical computer science, and other areas. Their significance is also evidenced by a recent monograph of Lovász [START_REF] Lovász | Large networks and graph limits[END_REF]. The better understood case of convergence of dense structures originated in the series of papers by Borgs, Chayes, Lovász, Sós, Szegedy, and Vesztergombi [6-8, 26, 27] on the dense graph convergence, and the notion was applied in various settings including hypergraphs, partial orders, permutations, and tournaments [START_REF] Elek | A measure-theoretic approach to the theory of dense hypergraphs[END_REF][START_REF] Hladký | Pikhurko: Poset limits can be totally ordered[END_REF][START_REF] Hoppen | Limits of permutation sequences[END_REF][START_REF] Hoppen | Limits of permutation sequences through permutation regularity[END_REF][START_REF] Janson | Poset limits and exchangeable random posets[END_REF][START_REF] Král | Pikhurko: Quasirandom permutations are characterized by 4point densities[END_REF]. The convergence of sparse structures (such as graphs with bounded maximum degree) referred to as the Benjamini-Schramm convergence [START_REF] Aldous | Processes on unimodular random networks[END_REF][START_REF] Benjamni | Recurrence of distributional limits of finite planar graphs[END_REF][START_REF] Elek | On limits of finite graphs[END_REF][START_REF] Hatami | Limits of locally-globally convergent graph sequences[END_REF] is less understood despite having links to many problems of high importance. For example, the conjecture of Aldous and Lyons [START_REF] Aldous | Processes on unimodular random networks[END_REF] on Benjamini-Schramm convergent sequences of graphs is essentially equivalent to Gromov's question of whether all countable discrete groups are sofic. Other notions of convergence of sparse graphs were also proposed and studied [3-5, 11, 14].

In the light of many results on the convergence of graphs, one can ask whether a reasonable theory of matroid convergence can be developed. The first obstacle to building such a theory comes from the fact that matroids when viewed as hypergraphs (e.g. with edges being the bases) can be too sparse for the classical dense convergence approach to be directly applied, and too dense for the sparse convergence approach at the same time. For example, the number of bases of the graphic matroid of K n is n n-2 , an exponentially small fraction of all (n-1)-element subsets of the edge set of K n and an even tinier fraction of all subsets of the edge set, which rules out the dense convergence approach. On the other hand, each element of this matroid is contained in a non-constant number of bases, and it is impossible to follow the sparse convergence approach. We overcome this obstacle by adapting the notion of the first order convergence to matroids.

The notion of the first order convergence was introduced by Nešetřil and Ossona de Mendez [START_REF] Nešetřil | A model theory approach to structural limits[END_REF][START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF] as an attempt to unify the convergence notions in the dense and sparse settings: a sequence of structures of a fixed type (e.g., graphs) is first order convergent if the probability that a random k-tuple of its elements has a first order property ϕ, converges for every choice of ϕ (a formal definition can be found in Subsection 2.4). It holds that every first order convergent sequence of dense structures is convergent in the dense sense and every first order convergent sequence of sparse structures is convergent in the Benjamini-Schramm sense.

In the analogy to graphons in the setting of dense graphs and graphings in the setting of sparse graphs, an analytic limit object called a limit modeling was proposed in [START_REF] Nešetřil | A model theory approach to structural limits[END_REF][START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF] to represent asymptotic properties of first order convergent sequences. Unlike in the dense and sparse graph settings, it is not true that every first order convergent sequence of graphs has a limit modeling. For example, the sequence of Erdős-Rényi random graphs G n,p for p ∈ (0, 1) is first order convergent with probability one but it has no limit modeling [29, Lemma 18]. In the same paper, Nešetřil and Ossona de Mendez showed the following.

Theorem 1.1. Every first order convergent sequence of graphs with bounded treedepth has a limit modeling.

This result was extended to first convergent sequences of trees and graphs of bounded path-width [START_REF] Gajarský | First order limits of sparse graphs: Plane trees and pathwidth, to appear in Random[END_REF][START_REF] Nešetřil | Modeling limits in hereditary classes: reduction and application to trees[END_REF]. Nešetřil and Ossona de Mendez [START_REF] Nešetřil | Existence of modeling limits for sequences of sparse structures[END_REF] have recently shown that every first order convergent sequence of graphs from a nowhere-dense class of graphs has a limit modeling, which is the most general result possible for monotone classes of graphs [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF]Theorem 25].

As a test that the approach to the matroid convergence based on the first order convergence is meaningful, it seems natural to prove the analogue of Theorem 1.1, which is actually one of our results (Theorem 1.2). On the way towards Theorem 1.2, we need to find a matroid parameter that can play the role of the graph tree-depth. We do so by introducing a parameter called branch-depth in Section 3. We believe that this matroid parameter is the right analogue of the graph tree-depth because it has the following properties, which we establish in this paper. We refer the reader to [START_REF] Nešetřil | Sparsity: graphs, structures, and algorithms[END_REF]Chapter 6] for a thorough discussion of the graph tree-depth.

• The branch-depth of a matroid corresponding to a graph G is at most the tree-depth of G.

• The branch-depth of a matroid corresponding to a graph G with tree-depth d is at least 1 2 log 2 d if G is 2-connected. • The branch-depth is a minor monotone parameter (the same holds for graph tree-depth).

• The branch-depth of a matroid is at most the square of the length of its longest circuit (recall that the tree-depth of a graph G is at most the length of its longest path).

• The branch-depth of a matroid is at least the binary logarithm of the length of its longest circuit (recall that the tree-depth of a graph G is at least the binary logarithm of the length of its longest path).

In addition, there exists an efficient algorithm that given an integer d and an oraclerepresented input matroid either outputs its decomposition of bounded depth or it determines that the branch-depth of the input matroid exceeds d.

Equipped with the notion of branch-depth, we prove the following theorem in Section 4.

Theorem 1.2. Every first order convergent sequence of matroids with bounded branch-depth that is representable over a fixed finite field has a limit matroid modeling.

Note that matroids representable over finite fields have a structure more similar to graphs than general matroids and it is not surprising that Theorem 1.2 includes this assumption. In fact, we show in Section 5 that neither the assumption on the bounded branch-depth nor the assumption on the representability over a fixed finite field can be dropped. In particular, we construct a first order convergent sequence of binary matroids that has no limit modeling, and a first order convergent sequence of rank three matroids representable over rationals that has no limit modeling.

Notation

In this section, we introduce the notation used throughout the paper.

Finite matroids

We start by introducing concepts related to finite matroids. We refer to the monograph by Oxley [START_REF] Oxley | Matroid Theory[END_REF] for a more detailed treatment. In Subsection 2.3, we extend the terminology to infinite matroids. A matroid M is a pair (E, I) where E is a finite set, called the ground set, and I ⊆ 2 E is a collection of its subsets referred to as independent sets. The set I is required to be nonempty, to be hereditary (i.e., for every F ∈ I, I must contain every subset of F ), and to satisfy the augmentation axiom: if F and F ′ are independent sets with |F | < |F ′ |, then there exists x ∈ F ′ \ F such that F ∪ {x} ∈ I. We abuse the notation and we often denote by M the ground set of the matroid M.

A subset F ⊆ M is called dependent if F ∈ I, and a minimal dependent set is a circuit. The number of elements of a circuit is referred to as its length. It is well-known that the collection C of circuits of a matroid M satisfies the following properties.

(C1) ∅ ∈ C. (C2) If C 1 , C 2 ∈ C and C 1 ⊆ C 2 , then C 1 = C 2 . (C3) If C 1 , C 2 ∈ C with e ∈ C 1 ∩ C 2 and f ∈ C 1 \ C 2 , then there exists a circuit C 3 ∈ C such that f ∈ C 3 ⊆ (C 1 ∪ C 2 ) \ {e}.
Furthermore, (C1)-(C3) form an alternative set of axioms to define matroids. More precisely, a collection C of subsets of M is the collection of circuits of a matroid if and only if it satisfies (C1)-(C3). The rank r M (F ) of a set F ⊆ M is the size of the largest independent subset of F . The rank of a matroid r M (M) is the rank of the ground set of M. It is well-known that the rank function of a matroid M is submodular, i.e., for any two subsets

F 1 , F 2 ⊆ M it holds that r M (F 1 ∪ F 2 ) + r M (F 1 ∩ F 2 ) ≤ r M (F 1 ) + r M (F 2 )
. When there is no danger of confusion, we omit the subscript, i.e., we just use r(F ) instead of r M (F ). There are two particular important examples of matroids. A graphic matroid M(G) is obtained from a graph G in the following way: the elements of M(G) are the edges of G, and a set of edges is independent if it is acyclic. Vector matroids have a set of vectors of a vector space as their ground set, and a set of elements is independent if they are linearly independent.

A matroid M is called representable over a field F if there exists a function f that maps the elements of M to vectors over F such that F ⊆ M is independent in M if and only if f (F ) is linearly independent. A matroid is binary iff it is representable over the binary field F 2 .

A loop is an element e of M with r({e}) = 0, and a bridge is an element such that r(M\e) = r(M) -1. Two elements e and e ′ are parallel if neither of them is a loop and r({e, e

′ }) = 1. If F is a subset of elements of M, the closure of F is defined as cl(F ) := x : r(F ∪ {x}) = r(F ) . Clearly, r(cl(F )) = r(F ).
If F is a subset of the elements of M, then M\F is the matroid obtained from M by deleting the elements of F , i.e., the elements of M\F are those not contained in F , and a set F ′ is independent in M\F iff it is independent in M. The matroid M/F is obtained by contracting F : the elements of M/F are those not contained in F , and a subset F ′ of such elements is independent in M/F iff F ′ is independent in M and r(F ∪ F ′ ) = r(F ) + r(F ′ ). When F = {e} is a single element, we write M\e and M/e instead of M\{e} and M/{e}. The restriction M|F of a matroid M to F is the matroid M \ F , where F denotes the complement of F in M. Finally, a minor of a matroid M is a matroid obtained by a sequence of deleting and contracting some of its elements. It is not hard to show that if a graph G ′ is a minor of a graph G, then the matroid M(G ′ ) is a minor of the matroid M(G).

A matroid M is connected if the only two subsets F ⊆ M satisfying r(F ) + r(F ) = r(M) are the empty set and the whole ground set. A component of M is a set F that is an inclusion-wise maximal subset such that M|F is connected. The components of M are equivalence classes given by the binary relation that represents that two elements of M are contained in a common circuit. Hence, any two components of a matroid M are disjoint. If M is a matroid and M 1 , . . . , M k are its components, then r

M (X) = r M 1 (X ∩ M 1 ) + • • • + r M k (X ∩ M k ).

Matroid algorithms

Algorithms for matroids have been studied extensively, and we want to review selected important facts here. It is common (see, e.g., [START_REF] Gavenčiak | Deciding first order logic properties of matroids[END_REF][START_REF] Robinson | The computational complexity of matroid properties[END_REF][START_REF] Seymour | Recognizing graphic matroids[END_REF]) to assume that the input matroid is presented by means of an independence oracle. That is, we assume that we can determine whether any subset of the elements of the given matroid is independent using a black-box function in unit time. The complexity of algorithms for matroids is measured in terms of the number of elements of the input matroid.

There is an efficient algorithm [START_REF] Tutte | An algorithm for determining whether a given binary matroid is graphic[END_REF] to test whether a given binary matroid is graphic, and if so to find a suitable graph. However, in general, deciding if an oracle-given matroid is binary cannot be solved in subexponential time [START_REF] Seymour | Recognizing graphic matroids[END_REF]. In the same paper [START_REF] Seymour | Recognizing graphic matroids[END_REF], Seymour presents a polynomial-time algorithm to decide whether an oracle-given matroid is graphic.

A lot of decision problems for matroids involve the structural matroid parameter branch-width. Rather than giving the exact definition here, let us just say that matroid branch-width is the analogue of graph tree-width. Oum and Seymour [START_REF] Oum | Testing branch-width[END_REF] showed, improving [START_REF] Hliněný | A parametrized algorithm for matroid branch-width[END_REF], that for every fixed k ≥ 1, it can be decided in polynomial time whether the branch-width of an oracle-given matroid is at most k, and that an optimal branch-decomposition can be constructed (for such matroids).

If M is a class of matroids that are representable over a fixed finite field and that have branch-width bounded by a constant, then properties expressible in monadic second order over M can be decided in cubic time [START_REF] Hliněný | Branch-width, parse trees and monadic second-order logic for matroids[END_REF]. In [START_REF] Gavenčiak | Deciding first order logic properties of matroids[END_REF], Gavenčiak, Oum, and the second author introduce the notion of locally bounded branch-width and present a fixed parameter algorithm to decide first order properties on the class of regular matroids with locally bounded branch-width.

Hliněný [START_REF] Hliněný | On matroid representability and minor problems[END_REF] also showed that for every field F of order at least four, it is NP-hard to decide whether a matroid given by its rational representation is Frepresentable. The result still holds when restricting the input to matroids of branch-width at most three. On the other hand, for every k ≥ 1 and any two finite fields F and F ′ , there is a polynomial-time algorithm that decides whether a given F-representable matroid of branch-width at most k is also F ′ -representable [START_REF] Král | Computing representations of matroids of bounded branch-width[END_REF].

Similarly to the relation between the tree-depth and tree-width, the branchwidth of a matroid M is upper bounded by the branch-depth of M up to an additive constant. It is natural to ask whether Theorem 1.2 can be extended to sequences of matroids representable over finite fields that have bounded branchwidth; we believe that this is likely to be the case but it might be challenging to prove since the analogous statement for sequences of graphs has been proven only very recently [START_REF] Nešetřil | Existence of modeling limits for sequences of sparse structures[END_REF].

Infinite matroids

One of the ways to define the notion of infinite matroids is to require the augmentation axiom to hold for finite subsets and to additionally require that an infinite set F ⊆ E is independent if and only if all of its finite subsets are independent. Such matroids are called finitary. The drawback of this definition is that finitary matroids can have only finite circuits.

A robust notion of infinite matroids was proposed by Bruhn et al. [START_REF] Bruhn | Axioms for infinite matroids[END_REF]. They developed five equivalent axiom systems that characterize (infinite) matroids through independent sets, bases, the closure operator, circuits, and their rank function. We present the characterization through circuits here. Let M be a set, and let C ⊆ 2 M be a collection of subsets. Further, let I = I(C) denote the C-independent sets, that is the collection of sets I ⊆ M such that C I for all C ∈ C. A family C is the collection of circuits of a matroid if it satisfies (C1), (C2), and the following two conditions. (C3') Whenever X ⊆ C ∈ C and {C e | e ∈ X} is a family of elements of C such that e ∈ C f ⇔ e = f for all e, f ∈ X, then for every

f ∈ C \ e∈X C e there exists C ′ ∈ C such that f ∈ C ′ ⊆ C ∪ e∈X C e \ X.
(CM) Whenever I ⊆ F ⊆ E and I ∈ I, the set {I ′ ∈ I : I ⊆ I ′ ⊆ F } has a maximal element.

If |X| = 1, the axiom (C3') becomes the usual strong circuit elimination axiom (C3). We remark that all finitary matroids are matroids in the sense just defined.

First order convergence

For a set λ of relational symbols, let FO(λ) denote the set of first order formulas using symbols from λ, and let FO k (λ) ⊆ FO(λ) denote the set of all such formulas ϕ with k free variables. A λ-modeling (or just a modeling if λ is clear from the context) A is a (finite or infinite) λ-structure whose domain is a standard Borel space equipped with a probability measure ν such that the following holds: for every ϕ ∈ FO k (λ), the subset A ϕ ⊆ A k formed by all k-tuples of the elements of A satisfying ϕ is measurable with respect to the product measure ν k . For a formula ϕ ∈ FO k (λ) and a modeling A, the Stone pairing ϕ, A is ν k (A ϕ ), i.e., the Stone pairing is the probability that a randomly chosen k-tuple of the elements of A satisfies ϕ. When a finite λ-structure A with |A| elements is viewed as a modeling with a uniform discrete probability measure, it holds that

ϕ, A = A ϕ |A| k = {(v 1 , . . . , v k ) ∈ A k : A |= ϕ[v 1 , . . . , v k ]} |A| k . A sequence (A n ) n∈N of finite λ-structures is first order convergent if the sequence ϕ, A n converges for every first order formula ϕ ∈ FO(λ). A λ-modeling A is a limit modeling of a first order convergent sequence (A n ) n∈N if ϕ, A = lim n→∞ ϕ, A n
for every formula ϕ ∈ FO(λ).

In Sections 3 and 4, we work with rooted trees, rooted forests and their modelings, which were studied in [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF]Part 3]. A rooted tree is a tree with a distinguished vertex referred to as the root, and a rooted forest is a graph such that each of its component is a rooted tree. The depth of a rooted tree is the length of the longest path from the root to a leaf, and the depth of a rooted forest is the maximum depth of a rooted tree contained in it. Rooted forests can be described by a language with a single binary relation representing the parent-child relation. In addition, we also consider rooted forests with vertices colored with one of a bounded number of colors. The vertex coloring of a rooted forest that uses k colors can be described by extending the language with k unary relations, each representing one of the colors. We use the following [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF]Theorem 34] to prove one of our main results.

Theorem 2.1. Let k and d be fixed integers. Every first order convergent sequence (F n ) n∈N of rooted forests with depth at most d and with vertices colored with at most k colors has a limit modeling.

Theorem 2.1 is proven in [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF] for rooted forests described by a language with a single symmetric binary relation representing edges and a single unary relation distinguishing roots of trees in the forest. Since there is a basic interpretation scheme translating the description of rooted forests from this language to the language that we consider here and there is also a basic interpretation scheme in the other direction (see the next subsection for a definition if needed), Theorem 34 from [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF] and Theorem 2.1 are equivalent by [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF]Propositions 3 and 4].

Our paper concerns matroids and their modelings; we now introduce the notation related to the first order convergence matroids and matroid modelings. Let λ M be the countable language containing a k-ary relation I k for every positive integer k. The relation I k is formed by all k-tuples of elements that are independent in the matroid. Finite matroids can be axiomatized in the first order language by a countable set of λ M -formulas. However, in general, the axioms (C1), (C2), (C3') and (CM) cannot be replaced by a countable set of first order axioms.

Let (M n ) n∈N be a sequence of finite matroids, equipped with the uniform measure on its element sets. We define (M n ) n∈N to be first order convergent if the sequence of the Stone pairings ϕ, M n converges for every first order λ M -formula

ϕ. A λ M -modeling M is a limit modeling of (M n ) n∈N if it is an infinite matroid and ϕ, M = lim n→∞ ϕ, M n
for every first order λ M -formula ϕ. Note that this definition is stronger than that of a limit modeling because we require additionally that the limit modeling is an infinite matroid. Note that if there exists an integer K such that every circuit of M n has length at most K, then every circuit of the limit modeling M has length at most K. In particular, M is finitary.

Interpretation schemes

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

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

• each formula θ i is compatible with θ E , in the sense that for every 0 ≤ i ≤ q it holds

1≤j≤r i θ E (x j , y j ) ⊢ θ i (x 1 , . . . , x r i ) ↔ θ i (y 1 , . . . , y r i ),
where r 0 = 1, x j and y j represent k-tuples of free variables, and

θ i (x 1 , . . . , x r i ) stands for θ i (x 1,1 , . . . , x 1,k , . . . , x r i ,1 , . . . , x r i ,k ).
For a κ-structure A, we denote by I(A) the λ-structure B defined as follows:

• the domain of B is the subset of the θ E -equivalence classes [x] ⊆ A k of the tuples x = (x 1 , . . . , x k ) such that A |= θ 0 (x); • for each 1 ≤ i ≤ q and every v 1 , . . . , v r i ∈ A r i ×k such that A |= θ 0 (v j ) for every 1 ≤ j ≤ r i it holds B |= R i ([v 1 ], . . . , [v r i ]) ⇐⇒ A |= θ i (v 1 , . . . , v r i ).
If θ 0 is a tautology and θ E is the equality on k-tuples, then the interpretation scheme is said to be basic.

The following is a standard result.

Proposition 2.2. Let I be an interpretation scheme of λ-structures in κ-structures.

Then there is a mapping Ĩ : FO(λ) → FO(κ) (defined by means of the formulas θ E , θ 0 , . . . , θ q above) such that for every ϕ ∈ FO p (λ), and every κ-structure A, the following property holds. For every

[v 1 ], . . . , [v p ] ∈ I(A) p (where v i = (v i,1 , . . . , v i,k ) ∈ A k ) it holds I(A) |= ϕ([v 1 ], . . . , [v p ]) ⇐⇒ A |= Ĩ(ϕ)(v 1 , . . . , v p ).
We need the following generalization of Propositions 3 and 4 from [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF].

Lemma 2.3. Let I be an interpretation scheme of λ-structures in κ-structures, let Ĩ be the mapping from Proposition 2.2, and let (A n ) n∈N be a sequence of finite κ-structures such that

(1) lim n→∞ θ 0 , A n = 1, and

(2)

lim n→∞ ϕ, I(A n ) = lim n→∞ Ĩ(ϕ), A n for every ϕ ∈ FO(λ).
If the sequence (A n ) n∈N is first order convergent, then the sequence (I(A n )) n∈N is also first order convergent. Moreover, if A is a limit modeling of (A n ) n∈N , then I(A) is a limit modeling of (I(A n )) n∈N .

Proof. The sequence (I(A n )) n∈N is first order convergent by [START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF]Proposition 3]. Let Σ A be the underlying σ-algebra of the probability space of A. We define the σ-algebra on B := I(A) as follows:

X ∈ Σ B if and only if x∈X [x] ∈ Σ A .
The probability measure ν B on B is defined as

ν B (X) := ν A ( x∈X [x]) for X ∈ Σ B ,
where ν A is the probability measure on A. The condition (1) implies that ν B is indeed a probability measure, i.e., ν B (B) = 1. We now argue that I(A) is a limit modeling of the sequence (

I(A n )) n∈N . Let ϕ ∈ FO k (λ). Proposition 2.2 yields that (x 1 , . . . , x k ) ∈ I(A) ϕ iff ([x 1 ], . . . , [x k ]) ∈ A Ĩ(ϕ) . It follows from the definition of the σ-algebra Σ B that I(A) ϕ is measurable. The definition of ν B yields that that ϕ, I(A) = Ĩ(ϕ), A ,
which combines with the condition (2) to the following:

ϕ, I(A) = Ĩ(ϕ), A = lim n→∞ Ĩ(ϕ), A n = lim n→∞ ϕ, I(A n ) .
Hence, I(A) is a limit modeling of the sequence (I(A n )) n∈N .

Matroid branch-depth

In this section, we introduce a matroid parameter analogous to the graph treedepth. We also present an algorithm that efficiently computes an approximate value of the parameter of an input matroid together with the certifying depthdecomposition.

Definition and basic properties

The branch-depth of a matroid is equal to the optimal height of a certain kind of a decomposition tree. In the definition below and in the proofs of subsequent claims, we use T to denote the number of edges of a tree T . Definition 3.1. Let M be a finite matroid. A depth-decomposition of M is a pair (T, f ), where T is a rooted tree and f : M → V (T ) is a mapping such that (1) r(M) = T , and

(2) r(X) ≤ T * (X) for every X ⊆ M, where T * (X) is the union of paths from the root to all the vertices in f (X). The branch-depth of a matroid M, denoted by bd(M), is the smallest depth of its depth-decomposition, i.e., the smallest depth of a rooted tree T such that (T, f ) is a depth-decomposition of M.

For any matroid M there is a trivial decomposition where the tree is a path of length r(M) with one of its end vertices being the root and all the elements of M mapped to the other end vertex. The following lemma gives us a way to modify a depth-decomposition.

Lemma 3.2. Let M be a finite matroid. If (T, f ) is a depth-decomposition of M, then there is a depth-decomposition (T, f ′ ) such that f ′ (e) is a leaf of T for every element e of M.
Proof. Let (T, f ) be a depth-decomposition of M. For every inner vertex v of T , let ℓ(v) be a leaf of T that is a descendant of v. For every e ∈ M, define f ′ as follows.

f ′ (e) := f (e) if f (e) is a leaf of T , and ℓ(f (e)) otherwise.

We now verify that (T, f ′ ) is a depth-decomposition of M. The part (1) of Definition 3.1 holds since we have not changed the tree T . To check part (2), observe that for any subset X of the elements of M, the subtree T * (X) with respect to f is contained in the subtree T * (X) with respect to f ′ . Hence, (T, f ′ ) is a depthdecomposition of M.

As the notion of graph tree-depth [START_REF] Nešetřil | Sparsity: graphs, structures, and algorithms[END_REF], the parameter of matroid branch-depth is also minor monotone.

Proposition 3.3. If M ′ is a minor of M, then bd(M ′ ) ≤ bd(M).
Proof. Since a minor of a matroid is obtained by a sequence of contractions and deletions of some of its elements, it is enough to show that if M is a matroid and e is an element of M, then the branch-depth of both M/e and M \ e is at most bd(M). Fix a matroid M and e ∈ M. Let (T, f ) be a depth-decomposition of M of depth bd(M). By Lemma 3.2, we can assume that f (e) is a leaf of T for every e ∈ M.

If e is a loop in M then M 0 := M \ e = M/e. It is easy to see that for every X ⊆ M 0 we have r M 0 (X) = r M (X). Hence, (T, f | M 0 ) is a depth-decomposition of M 0 .

We now assume that e is not a loop. Let M 1 := M/e, let u be the leaf f (e), and let v be the parent of u. Set T 1 = T \ u and define f 1 : M 1 → V (T 1 ) as follows:

f 1 (x) = v if f (x) = u, and f (x) otherwise.
We now show that (T 1 , f 1 ) is a depth-decomposition of M 1 . Since e is not a loop, we have r(M 1 ) = r(M)-1. Thus,

T 1 = r(M 1 ). Now, consider a subset X ⊆ M 1 . Recall that r M 1 (X) = r M (X ∪ {e}) -1. If u ∈ f (X)
, we employ the bound on the rank function provided by the depth-decomposition of M:

T * 1 (X) = T * (X ∪ {e}) -1 ≥ r M (X ∪ {e}) -1 = r M 1 (X).
Otherwise, we have

T * 1 (X) = T * (X) ≥ r M (X) ≥ r M 1 (X).
Let M 2 = M \e. If e is a bridge then M \e = M/e. Hence, we may assume that e is not a bridge in M. In this case, we claim that (T, f | M 2 ) is a depth-decomposition of M 2 . Since the rank of M 2 equals the rank of M, we have r(M 2 ) = T , and it also holds that

T * (X) ≥ r M (X) = r M 2 (X) for every X ⊆ M 2 .
If a graph G has a path with n vertices, its tree-depth (see Definition 3.5 if needed) is at least ⌈log 2 n + 1⌉ -1, see e.g. [START_REF] Nešetřil | Sparsity: graphs, structures, and algorithms[END_REF]Chapter 6]. The next proposition relates the length of circuits in a matroid to its branch-depth, in the analogy to the relation between the graph tree-depth and the existence of long paths. Let w be the root of T . We first prove that the degree of w is one. Suppose not. Let W be vertices of one of the subtrees of w, and let T 1 be the subtree induced by W ∪ {w} and T 2 the subtree induced by the vertices not contained in W . Observe that

T i ≥ r(f -1 (V (T i ))) = |f -1 (V (T i ))| for i ∈ {1, 2}. It follows that r(C d ) = T = T 1 + T 2 ≥ |f -1 (V (T 1 ))|+|f -1 (V (T 2 ))| = |C d | = r(C d )+1, which is impossible.
Let v be a vertex of T of degree larger than two that is as close to the root w as possible. If there is no such vertex, T is a path and it has depth d -1 ≥ log 2 (d).

Let P be a path from w to v, ℓ its length, and W vertices of one of the subtrees of v. Let T 1 be the subtree induced by W ∪ {v} and T 2 the subtree induced by v and the vertices not contained in W or in P . Further, let m i = T i and n i = |f -1 (V (T i ))| for i ∈ {1, 2}. Observe that both n 1 and n 2 are non-zero, and that

m 1 + m 2 + ℓ = r(C d ) = d -1 and n 1 + n 2 = |C d | = d. (1)
Since f -1 (V (T i )) is a proper subset of C d , it is independent and we get that

n i ≤ m i + ℓ for i ∈ {1, 2}. This yields that m i ≤ n i -1; otherwise, n 3-i > m 3-i + ℓ
by [START_REF] Aldous | Processes on unimodular random networks[END_REF]. By symmetry, we may assume that n 1 ≤ n 2 , which gives

n 1 ≤ d 2 . Let M ′ := C d /f -1 (V (T 1 )). Observe that M ′ is isomorphic to C n 2 .
Let T ′ be the tree obtained by considering a path of length of m 1 + ℓn 1 ≥ 0, identifying one of its end vertices with the root of the tree T 2 and rooting the resulting tree at the other end vertex of the path. Observe that T ′ = r(M ′ ) since the number of its edges is smaller by r(V (T 1 )) compared to M, and that the tree

T ′ with f | M ′ is a depth-decomposition of M ′ . By induction, the depth of T ′ is at least log 2 d 2 . Since m 1 + ℓ -n 1 = ℓ -(n 1 -m 1 ) ≤ ℓ -1, it follows that the depth of T is at least log 2 d 2 + 1 = log 2 d.
We now recall the notion of graph tree-depth. We use cl(T ) to denote the transitive closure of a rooted tree T , i.e., the graph with vertex set V (T ) and an edge connecting each pair of vertices u and v such that u is an ancestor of v in T . Definition 3.5. The tree-depth td(G) of a graph G is the smallest possible depth of a rooted tree T with the same vertex set as G such that G ⊆ cl(T ). Such a tree T is called an optimal tree-depth decomposition of G.

We next relate the branch-depth of a graphic matroid to the tree-depth of the underlying graph.

Proposition 3.6. The branch-depth of a graphic matroid M(G) is at most td(G).

Proof. Let G be a graph on n vertices and let M := M(G) be the corresponding graphic matroid. We proceed by induction on n. If n = 1 or n = 2, the claim holds. If G is not 2-connected, let G 1 , . . . , G k be its 2-connected components (blocks). Since the tree-depth is a minor monotone parameter, each G i has treedepth at most td(G) and the matroid M(G i ) has a depth-decomposition with depth at most td(G) by induction. Since the matroid M is the disjoint union of the matroids M(G 1 ), . . . , M(G k ), a depth-decomposition of M can be obtained by identifying the roots of depth-decompositions of M(G 1 ), . . . , M(G k ). The depth of such a depth-decomposition is at most td(G) and the claim follows. So, we assume that G is 2-connected in the rest of the proof.

Let T be an optimal tree-depth decomposition of G. We construct a depthdecomposition (T, f ) of M as follows. The function f maps an element e ∈ M to the end vertex of e that is farther from the root of T . We verify the two conditions from Definition 3.1. Since G is connected, we indeed have r(M) = n -1 = |V (T )| -1 as required by the condition (1). Consider a subset X ⊆ M. We show that r(X) ≤ T * (X) to establish the condition (2). We may assume that X has no circuit: if X contained a circuit, removing an element from a circuit of X would not change r(X) and it could not increase T * (X) . So, we assume that X is independent and r(X) = |X|.

Let X 1 , . . . , X k be the edge sets of the connected components of the graph (V (G), X), and let U 1 , . . . , U k be the their vertex sets. Further, let U ′ i be the set f -1 (X i ). Note that the sets U 1 , . . . , U k are disjoint and U ′ i is a subset of U i . Since (U i , X i ) is connected, the set U i contains a unique vertex closest to the root, and U ′ i is equal to U i with the vertex closest to the root removed. Since the subtree T * (X) contains an edge from each vertex of U ′ i to its parent, and the sets U 1 , . . . , U k are disjoint (and so are the sets U

′ 1 , . . . , U ′ k ), T * (X) is at least |U ′ 1 | + • • • + |U ′ k | ≥ |U 1 | + • • • + |U k | -k.
Since the rank of X is equal to the sum of ranks of the sets X i and r(

X i ) = |X i | = |U i | -1, it follows that r(X) = |U 1 | + • • • + |U k | -k.
This finishes the proof of the lemma.

Note that the converse of Proposition 3.6 does not hold. The graphic matroids of an (n + 1)-vertex star K 1,n and an (n + 1)-vertex path P n+1 are isomorphic and both have branch-depth one despite of the tree-depth of K 1,n being one and the tree-depth of P n+1 being ⌈log 2 n + 1⌉ -1. Nevertheless, the following inequality holds for 2-connected graphs.

Technical lemmas

In this section, we establish further properties of the branch-depth, which are important to prove the correctness of the algorithm presented later. The following two claims follow directly from the definition of contracting an element of a matroid. Proof. First observe that any proper subset of

C is independent in M: indeed, if X is a proper subset of C, then r M (X) ≥ r M (X ∪ {e}) -1 = r M/e (X) = |X|. If C is not independent in M, then C is a circuit. Suppose that C is independent in M. We claim that C ∪ {e} is a circuit. First, r M (C ∪ {e}) = r M/e (C) + 1 = |C|, i.e.
, C ∪ {e} is not independent. Let X be a subset of C ∪ {e}. We have already observed that X is independent if e ∈ X. If e ∈ X, then r M (X ∪ {e}) = r M/e (X) + 1 = |X| + 1, i.e., X is independent. We conclude that C ∪ {e} is a circuit.

When encountering a circuit, the algorithm is going to proceed by contracting one of its elements. The following lemma will be crucial for the analysis. Lemma 3.10. Let M be a connected matroid, e an element of M such that M/e is disconnected, and let M 1 , . . . , M k be the components of M/e. For every circuit C of M containing e, there exists i ∈ {1, . . . , k} such that C ⊆ M i ∪ {e}.

Proof. Suppose that C contains an element from M 1 and an element from M i , i > 1. Let M ′ 2 be the union of M 2 , . . . , M k , and let D 1 = C ∩M 1 and D 2 = C ∩M ′ 2 . Hence, we get the following Lemma 3.11. Let M be a connected matroid. Let e be an element of M such that M/e is not connected and let M 1 , . . . , M k be the components of M/e. For each i = 1, . . . , k there is a circuit C i in M containing e such that C i ⊆ M i ∪ {e}. Proof. Fix i = 1, . . . , k. Since M is connected, there is a circuit containing any two elements of M, in particular, M has a circuit C i containing the element e and an element of M i . By Lemma 3.10, the circuit C i must be a subset of M i ∪{e}.

|D 1 | + |D 2 | = |C| -1 = r M (C) = r M/e (C \ e) + 1 . Since M 1 , . . . , M k are the components of M, it follows that r M/e (C \ {e}) = r M 1 (D 1 ) + r M ′ 2 (D 2 ).
The following lemma allows us to find an obstruction to a small branchdepth. We utilize this lemma to show that Algorithm 1 always returns a depthdecomposition of depth at most 4 bd(M ) . Figure 1 contains an illustration of the notation used in the lemma. Lemma 3.12. Let M be a matroid. Let e 1 , . . . , e k be distinct elements of M and C 0 , C 1 , . . . , C k subsets of M such that

|C i | ≥ 3 for i = 0, . . . , k, C i-1 ∩ C i = {e i } for i = 1, . . . , k, C i ∩ C j = ∅ for |i -j| ≥ 2.
Let e 0 ∈ C 0 \ {e 1 } and e ′ i ∈ C i-1 \ {e i-1 , e i }, i = 1, . . . , k. Further, set

M i := M for i = 0, M i-1 /(C i-1 \ {e i , e ′ i }) for i = 1, . . . , k.
If C i is a circuit in M i for i = 0, 1, . . . , k, then M contains a circuit of length at least k + 3 containing e 0 .

Proof. We prove the statement by induction on k. For k = 0 it suffices to take the circuit

C 0 itself. Let k ≥ 1. By induction, M 1 = M 0 /(C 0 \ {e 1 , e ′ 1 }) has a circuit C of length at least k + 2 that contains e 1 . Let D = C \ {e 1 }. Since C is a circuit, D is independent in M 1 and thus in M 0 . Also note |D| ≥ k + 1.
Let N = M 0 /(C 0 \ {e 0 , e 1 , e ′ 1 }). Since C 0 is a circuit in M 0 , {e 0 , e 1 , e ′ 1 } is a circuit in N by Lemma 3.8. Furthermore, it holds that M 1 = N/e 0 . If Y is a circuit in N, then there is a circuit Y ′ ⊇ Y in M by Lemma 3.9. Therefore, it suffices to find a circuit of length at least k + 3 in N.

Approximating branch-depth

We now present our polynomial-time algorithm for constructing a depth-decomposition of an oracle-given matroid M with depth at most 4 bd(M ) . The pseudocode is given as Algorithm 1 in the form of a routine taking three parameters: a connected matroid M, one of its circuits C, and a non-loop element e ∈ C. For disconnected matroids we process the components individually and glue the resulting depth-decompositions by identifying their roots. Note that every connected matroid has a circuit and a non-loop element unless |M| = 1.

If the rank of M is at most one, which can be easily determined by checking the existence of a two-element independent set, the routine returns the trivial depthdecomposition, which is either one-vertex or two-vertex rooted tree with all the matroid elements mapped to the root or the non-root leaf, respectively, depending on the rank of M. Assume r(M) ≥ 2. If |C| ≤ 2, we find another circuit containing e of size at least three. The existence of such circuit in a connected matroid with rank at least two is implied by the definition of connectivity, and it can be found in a polynomial time for example as follows. Find using the greedy algorithm a base B of M not containing any element parallel to e and remove from B all the elements f such that B ∪ {e} \ {f } is not independent. The resulting set together with e forms a circuit of length at least three.

If |C| ≥ 3, we proceed by contracting e in M and analyzing the resulting matroid. If the resulting matroid is connected, Algorithm 1 calls itself recursively (Step 3 of Algorithm 1) on the contracted matroid. Note that the connectivity of a matroid can be tested in polynomial time using the matroid intersection algorithm; this algorithm can also be used to find the connected components if the matroid is not connected. In case that the matroid is connected, the recursive call is made for the contracted matroid, the circuit C \ {e}, and an arbitrary element e 1 of C \ {e}. Note that e 1 is not a loop in the contracted matroid since |C| ≥ 3. After the call is finished, we alter the resulting decomposition by adding a new vertex that becomes the root.

If M/e is not connected, the recursive calls are performed on each component separately (Step 4 and Step 5). For the unique component containing C \ {e} (see Lemma 3.10), the call is performed with the component, the circuit C \ {e}, and an arbitrary element e 1 of C \ {e}. For other components, the call is performed for C ′ \ {e} where C ′ is an arbitrary circuit of the original matroid that contains e and an element of the component; the element of C ′ \ {e} to perform the call with is chosen arbitrary. The resulting decomposition is obtained by identifying the roots of the individual decompositions and adding a new vertex that becomes the root of the whole decomposition.

It is easily verified that Algorithm 1 finishes in time polynomial in the number of elements of the input matroid: if the recursive call in Step 2 is executed, the next execution avoids this step and performs one of the other recursive calls, which in turn lead to a decrease in the input size. If Step 3 is reached, only a single recursive call is made by the routine and the number of matroid elements is decreased by one. If Steps 4 and 5 are reached, then the number of recursive calls equals the number of connected components and the sum of the numbers of elements of the matroids passed to the calls is one less than the number of elements of the original matroid. It is easy to establish that the number of recursive calls is at most quadratic in the number n of elements of the original matroid, and a more refined analysis can yield that the number of recursive calls is at most O(n log n).

We next establish that Algorithm 1 produces a depth-decomposition of the input matroid. Lemma 3.14. Algorithm 1 returns a valid depth-decomposition of M.

Proof. Let M be the input matroid and (T, f ) the output of the Algorithm 1. Clearly, T is a tree and f a mapping from M to V (T ). Thus, we need to verify the two conditions from Definition 3.1. We start with the condition (1), and verify it by induction on the number of recursive calls. If Step 0 or 1 is reached, the tree T clearly satisfies r(M) = T . In Step 2, the algorithm is recursively evoked to a matroid of the same rank and the returned tree T has the number of edges equal to r(M) by induction. In Step 3, the routine is recursively called to a matroid with rank one smaller and the returned tree is extended by a single edge; consequently, it also holds r(M) = T . Finally, in Steps 4 and 5, the sum of the ranks of the matroids that the routine is called to is one smaller than r(M) and thus the output tree T has r(M) edges in this case, too.

We next establish the condition (2) from Definition 3.1, and we again proceed by induction on the number of recursive calls. Let X be a non-empty subset of M; our aim is to show that r(X) ≤ T * (X) . If the depth-decomposition is constructed in Step 0 or 1, then the condition (2) clearly holds. If the algorithm reached Step 2, the returned depth-decomposition is not modified and the condition (2) holds by induction. Suppose that the depth-decomposition was constructed in Step 3, i.e., the matroid M/e is connected. From the induction, we get r M/e (X \ {e}) ≤ T * (X) -1, since T * (X) includes one additional edge compared to the corresponding subtree of T ′ . It follows that

r M (X) ≤ r M (X ∪ {e}) = r M/e (X \ {e}) + 1 ≤ T * (X) .
It remains to analyze the case that the depth-decomposition is constructed in Steps 4 and 5, i.e., the case that the matroid M/e is has components M 0 , . . . , M k . By induction, we get

r M i (X ∩ M i ) ≤ T i * (X ∩ E(M i ))
, where T i is the depthdecomposition of M i returned by the recursive call for M i . Since the resulting Algorithm 1: construct(M, C, e) Input: a connected matroid M, a circuit C of M, and a non-loop element e ∈ C Output: a depth-decomposition of M if r(M) = 0 then

Step 0 return one-vertex tree with f mapping all elements to the root; else if r(M) = 1 then

Step 1

return one-edge tree with f mapping all elements to the leaf;

else if |C| = 2 then Step 2 choose a circuit C ′ satisfying |C ′ | ≥ 3 and e ∈ C ′ ; return construct(M, C ′ , e); else if M/e is connected then
Step 3

choose an element e 1 ∈ C \ {e};

(T ′ , f ′ ) := construct(M/e, C \ {e}, e 1 ); T := (V (T ′ ) ∪ {v}, E(T ′ ) ∪ {vv ′ }) where v ′ is the root of T ′ ; root T at v; f (e) := v ′ ; f (e ′ ) := f ′ (e ′
) for e ′ = e; return (T, f ); else for each component

M i of M/e disjoint from C do choose a circuit C i of M contained in M i ∪ {e} that contains e; choose e i ∈ C i \ {e}; (T i , f i ) := construct(M i , C i \ {e}, e i ); end identify all the roots v i of T i into a single root v ′ , obtaining T ′ ; T := (v(T ′ ) ∪ {v}, E(T ′ ) ∪ {vv ′ }), root T at v; f (e) := v ′ , f (e i ) := f i (e i ) for e i ∈ M i ; return (T, f ); end end end end
depth-decomposition is constructed by identifying the roots of T 1 , . . . , T k and connecting them to the new root, we get

r M (X) ≤ r M (X ∪{e}) = 1+ k i=0 r M i (X ∩M i ) ≤ 1+ k i=0 T * (X ∩ M i ) = T * (X) .
We next analyze the depth of the tree returned by Algorithm 1.

Lemma 3.15. Algorithm 1 returns a depth-decomposition of M with depth at most 4 bd(M ) .

Proof. Let d be the depth of the depth-decomposition T returned by the algorithm for a matroid M. Let r = v 0 , v 1 , . . . , v d be a path in T of length d from the root to one of the leaves. It is easy to see that each vertex of T that is not a leaf is the root of some subtree of T during the execution of the algorithm. For i = 0, 1, . . . , d -1, let (M i , C i , e i ) be the matroid together with a circuit and an element of it such that the algorithm creates the subtree rooted at v i and containing v i+1 in the call with the parameters (M i , C i , e i ). Note that M 0 = M and C 0 = C. In addition,

r(M d-1 ) = 1 and |C d-1 | = 2.
For every i = 0, . . . , d -2, precisely one of the following five cases occurs depending whether the matroid M i+1 was passed to the recursive call in Step 3, 4 or 5 during the execution of the call with the parameters (M i , C i , e i ) and whether the recursive call reached Step 2.

• M i+1 = M i /e i , C i+1 = C i \ {e i } (Step 3), • M i+1 = M i /e i , |C i | = 3, |C i ∩ C i+1 | = 1 (Step 3 followed by Step 2), • M i+1 is a component of M i /e i , C i+1 = C i \ {e i } (Step 4), • M i+1 is a component of M i /e i , |C i | = 3, |C i ∩ C i+1 | = 1 (Step 4

followed by

Step 2),

• M i+1 is a component of M i /e i , C i+1 ∩ C i = ∅, but C i+1 ∪ {e i } is a circuit in M i (Step 5).
The sequence C 0 , . . . , C d-1 consists of several runs where the next set is a subset of the preceding one; the runs correspond to Steps 3 or 4. Each run except for the last one is finished either by Step 3 or 4 followed by Step 2, or by Step 5. Let j 0 , . . . , j k be the indices of the elements where the run starts, i.e., the i-th run contains the elements with indices between j i-1 and j i -1 (inclusively). Note that j 0 = 0, and set Ĉ0 := C j 0 = C 0 and ê0 := e 0 . If the i-th run is finished by Step 5, Let q be a fixed prime power, and let M be a finite matroid which is representable over a finite field F q . We identify the elements of M with the corresponding vectors. Let d = bd(M) be the branch-depth of M. Recall that by Corollary 3.17 there exists a depth-decomposition (T, f ), where T has depth at most D := 4 d , such that there is a base B of M with f | B being a bijection between B and the non-root elements of T , and where f (e) is a leaf for every e ∈ B.

We now construct a vertex-colored forest F = F (M) from (T, f ) such that each component of F is a rooted tree of depth at most D, the colors are D-tuples of elements of the finite field F q , and there is a bijection between the vertices of F and the elements of M. The construction proceeds as follows. For every non-root vertex v of T , let b v be the unique element of the base B that is mapped by f to v. Let v ∈ L(T ) be a leaf of T , say of depth t, and let P (v) = (v 0 , v 1 , v 2 , . . . , v t ) be the unique path from the root v 0 to v t = v. Every element e ∈ B that is mapped by

f to v is in the closure of b v 1 , . . . , b vt since r M ({e, b v 1 , . . . , b vt }) ≤ T * ({v 1 , . . . , v t } = t.
Consequently, if matroid elements are viewed as vectors, e is contained in the linear hull of b v 1 , . . . , b vt , and it can be expressed as their linear combination, i.e., e = t i=1 α i b v i . For every such e ∈ f -1 (v t ) \ B, we attach a new leaf with its parent being v t and color it with the color (α 1 , . . . , α t , 0, . . . , 0). Each vertex of the original tree T is colored with the d-th unit vector e d , where d is its depth in T .

We next delete the root and obtain a rooted forest with subtrees T 1 , . . . , T ℓ . Each of the trees T 1 , . . . , T ℓ has height at most D. We call the resulting forest F = F (M) with coloring c M : V (F ) → F D q a forest representation of M. It follows from the construction that there is a bijection g between the elements of M and the vertices of V (F ).

A forest representation of M is not unique since there can be several different depth-decompositions of M. However, a forest representation (F, c) uniquely determines the matroid. The elements of the matroid are the vertices of F . A set of k vertices {v 1 , . . . , v k } is independent if the following holds. For 1 ≤ i ≤ k, let d i be the depth of v i in F , and let P (v i ) = (w

(i) 1 , . . . , w (i) d i +1
) be the unique path from the root of the tree containing v i to v i = w (i)

d i +1 . We associate v i with a formal sum d i j=1 α (i) j w (i)
j , where (α

(i) 1 , . . . , α (i)
d i , 0, . . . , 0) = c(v i ) is the color of v i . The set {v 1 , . . . , v k } is linearly independent if and only if there exists no non-trivial k-tuple (x 1 , . . . , x k ) ∈ F k q such that

x 1 • d 1 j=1 α (1) j w
(1) j

+ • • • + x k • d k j=1 α (k) j w (k) j = 0.
Note that whether {v 1 , . . . , v k } is independent is determined by the subforest F * = F * (v 1 , . . . , v k ), which is formed by the union of the paths P (v i ), and by the colors c(v 1 ), . . . , c(v k ).

Let λ D be the language describing rooted forests with vertices colored with F D q , i.e., λ D contains a binary relation representing the parent relation and q D unary symbols for the colors of the vertices. We now introduce an interpretation scheme I of exponent one of λ M -structures (matroids) in λ D -structures (vertex-colored rooted forests). Let Θ(x) ≡ x = x and θ E (x, y) ≡ x = y. For k ≥ 1, we define θ k ∈ FO k (λ D ) to encode the k-ary independence operator I k in the following way. Let v 1 , . . . , v k be vertices in F . For every 1 ≤ i ≤ k, let P (v i ) and c(v i ) be defined as above. Since each path P (v i ) has length at most D, and since the number of colors is at most q D , there are finitely many possibilities how F * (v 1 , . . . , v k ) can look. The subforest F * (v 1 , . . . , v k ) completely determines whether there exists a non-trivial linear combination of the formal sums t i j=1 α

(i) j w (i)
j that is zero. We set θ k (v 1 , . . . , v k ) to be the λ D -formula that says that F * (v 1 , . . . , v k ) is such that there exists no non-trivial zero linear combination; the above reasoning yields that θ k (v 1 , . . . , v k ) should say that F * (v 1 , . . . , v k ) is isomorphic to one of finitely many vertex-colored rooted forests, i.e., there exists a λ D -formula with these properties.

The next lemma follows from the construction and the definition of an interpretation.

Lemma 4.1. Let M be a finite F q -representable matroid of branch-depth at most d, and let (F, c M ) be a forest representation of M. Then I((F, c M )) ∼ = M.

We are now ready to prove our main theorem.

Proof of Theorem 1.2. Let q be a prime power, d an integer, and (M n ) n∈N a first order convergent sequence of matroids such that each matroid M n is representable over the field F q and has branch-depth bounded by d. Let (F n , c n ) n∈N be the corresponding sequence of forest representations of depth at most D := 4 d . Recall that each c n uses at most q D colors.

By compactness (see [START_REF] Nešetřil | A model theory approach to structural limits[END_REF][START_REF] Nešetřil | A unified approach to structural limits, and limits of graphs with bounded tree-depth[END_REF]), we can assume that (F n , c n ) n∈N is first order convergent (otherwise, we pick a first order convergent subsequence). By Theorem 2.1, (F n , c n ) n∈N has a limit modeling (F, c). Note that F has depth at most D and c is an F D q -coloring. We now show that the assumptions of Lemma 2.3 hold. Since F n |= θ 0 (v) for any n ∈ N and any vertex v of F n , the condition (1) of Lemma 2.3 trivially holds. Finally, the condition (2) holds by Proposition 2.2 and since there is a bijection g n between the elements of M n and the vertices of F n , for any n ∈ N.

It follows from Lemma 2.3 that M := I((F, c)) is a limit modeling for the sequence (I(F n , c n )) n∈N , and thus of the sequence (M n ) n∈N , by Lemma 4.1. It remains to prove that M is an infinite matroid. For k ∈ N, let C k be the k-element subsets {x 1 , . . . , x k } ⊆ M of M that satisfy

M |= ¬I k (x 1 , . . . , x k ) ∧ 1≤i≤k I k-1 (x 1 , . . . , x i-1 , x i+1 , . . . , x k ).
We show that C := k≥1 C k is a collection of circuits of M.

First, note that for every n ∈ N, since the branch-depth of each M n is at most d, the length of every circuit of M n is at most 2 d , by Proposition 3.4. It follows that the length of every circuit in M (i.e., the size of each element in C) is at most 2 d (since, e.g., the first order formula stating that there is no circuit of size 2 d + 1 holds in each M n and hence in M). Thus, the axioms (C1), (C2) and (C3') trivially hold since they are equivalent to a finite set of first order axioms. Finally, since all circuits of M are finite, M is finitary, and thus, as mentioned in Subsection 2.3, it is also a finitary matroid.

Non-existence of matroid limit modelings

In this section, we show that neither of the assumptions in Theorem 1.2 can be removed. In particular, we prove the following two results. Theorem 5.1. There exists a first order convergent sequence of Q-representable matroids of rank three that has no limit modeling. Theorem 5.2. There exists a first order convergent sequence of binary matroids that has no limit modeling.

Matroids with rank three

We now construct a sequence of matroids of rank three, each representable over the field of rationals, that has no limit modeling. We start with describing a procedure to convert a graph G to a Q-representable matroid of rank at most three in a way that the first order properties of G are preserved. The existence of a first-order convergent sequence of graphs without a limit modeling (e.g., a sequence of Erdős-Rényi random graphs has this property with probability one [29, Lemma 18]) allows us to deduce that there exists a first order convergent sequence of such matroids that does not have a limit modeling.

Let G be a graph on n vertices. We construct a matroid M(G, k), where k ∈ N is a parameter. We first give the construction for k = 1. The construction is illustrated in Figure 2. Let P = {p v : v ∈ V (G)} be a set of n points in the Euclidean plane R 2 in general position. For every edge uv ∈ E(G), add a new point p uv to the set P on the line through the points p u and p v such that p uv does not lie on any line passing through another pair of the points (of P and the newly added points). The ground set of the matroid M(G, 1) is P . The bases B of M(G, 1) are all triples {x, y, z} of M(G, 1) such that x, y, and z do not lie on a line. Equivalently, the circuits are all sets of size four and all triples {p u , p v , p uv } where uv ∈ E(G). The matroid M(G, 1) has rank at most 3 and it is Q-representable. Note that the matroids obtained for a different initial choice of P are isomorphic.

For k ≥ 2, M(G, k) is constructed from M(G, 1) by adding k -1 parallel elements to p v for every v ∈ V (G). This class of k parallel elements corresponding to p v is denoted by C(v), and we say that an element in C(v) represents the vertex v. We call an element of M(G, k) a vertex element if it is contained in some C(v), and an edge element otherwise.

Let k ≥ 2. To show that first order definable properties of G are preserved in M(G, k) let us define an interpretation scheme I of λ G -structures in λ M -structures of exponent one. Note first that the formula D 2 ≡ ¬I 2 ∈ FO 2 (λ M ), which captures the dependence of pairs of elements, defines an equivalence relation on the ground set of any such matroid M(G, k). Further, note that edge elements can be distinguished from vertex elements in M(G, k) since x ∈ M(G, k) is a vertex element if and only if M(G, k) |= ∃ y (x = y ∧ ¬I 2 (x, y)). We set θ E (x, y) ≡ D 2 (x, y) ≡ ¬I 2 (x, y) and θ 0 ≡ ∃ y (x = y ∧ ¬I 2 (x, y)) . Finally, we define the formula θ 1 ∈ F O 2 (λ M ) to represent the edge-relation as θ 1 (x, y) ≡ I 2 (x, y) ∧ ∃z (I 2 (x, z) ∧ I 2 (y, z) ∧ ¬I 3 (x, y, z)) .

It is clear that θ 0 and θ 1 are compatible with θ E . That is, I defined by the formulas θ E , θ 0 , and θ 1 is an interpretation scheme of exponent one. The construction and the definition of the interpretation I(M(G, k)) yield the following. We are ready to prove Theorem 5.1.

Proof of Theorem 5.1. Let (G n ) n∈N be a first order convergent sequence of graphs that does not have a limit modeling. Consider now the sequence (M n ) n∈N where M n = M(G n , |G n | 2 ). We may assume that (M n ) n∈N is first order convergent (otherwise, we consider a first order convergent subsequence, which exists by compactness). Let I be the interpretation scheme defined earlier, and let Ĩ : FO(λ G ) → FO(λ M ) be the mapping from Proposition 2.2. We claim that the conditions in Lemma 2.3 are satisfied for the sequence (M n ) n∈N . Let x ∈ M n be an element chosen uniformly at random. Then the probability that x is an edge element is So, the second condition in Lemma 2.3 also holds.

Assume now that (M n ) n∈N has a matroid limit modeling M. By Lemma 2.3, G := I(M) is a limit modeling for the sequence (I(M n )) n∈N , that is for (G n ) n∈N by Lemma 5.3, a contradiction.

Binary matroids

We describe an interpretation scheme of graphs in binary matroids. The argument is largely analogous to the one presented in Subsection 5.1.

Let G = (V, E) be a graph on n vertices, and let k ∈ N be a parameter. We define a binary matroid M ′ = M ′ (G, k) of rank |V | in the following way. The matroid M ′ contains k distinct elements represented by the unit vector e v ∈ F V 2 for every vertex v ∈ V , and M ′ contains an element represented by e u + e v for every edge uv ∈ E. Recall the interpretation scheme I of exponent one defined in Subsection 5.1, and observe that observe that the graph I(M ′ (G, k)) is isomorphic to G. Theorem 5.2 can now be proven in a way completely analogous to the proof of Theorem 5.1.

Concluding remarks

The tree-depth of graphs is important in relation to testing graph properties in a fixed parameter way. It is also important with respect to the structure of graphs in general. For example, for every d, there exists a finite set G of graphs with treedepth at most d such that each graph of tree-depth at most d is homomorphically equivalent to one of the graphs in G. Naturally, one may ask whether some of these results can be generalized to matroids using the branch-depth parameter introduced in this paper. Independently of us, Matt DeVos and Sang-il Oum (private communication) were considering another tree-depth like parameter for matroids, which was inspired by the work of Dittmann and Oporowski [START_REF] Dittmann | Unavoidable minors of graphs of large type[END_REF]. They define a contractiondepth of a matroid recursively as follows. A matroid that consists of loops and co-loops only has contraction-depth 0. For other matroids, the contraction-depth of M is the smallest k that there exists an element e such that each component of M/e has contraction-depth at most k -1. As in the case of branch-depth, the contraction-depth of a matroid is both lower and upper bounded by the length of its longest circuit. They have also been working on the variant of the parameter called deletion-depth defined similarly and on generalizations for arbitrary connectivity functions, which are of interest in relation to problems from discrete optimization.

Proposition 3 . 4 .

 34 Let M be a matroid and d the size of its largest circuit. Then bd(M) ≥ log 2 d. Proof. Let C d be the matroid that consists of exactly one circuit of size d. If M has a circuit of length d, then M contains C d as a minor. Hence, it is enough to show by Proposition 3.3 that the branch-depth of C d is at least log 2 d. We prove this statement by induction on d. Let (T, f ) be a depth-decomposition of C d such that T has depth bd(C d ) and such that f (e) is a leaf of T for every e ∈ C d . Its existence follows from Lemma 3.2.

Proposition 3 . 7 .

 37 Let G be a 2-connected graph with tree-depth d. Then, the branch-depth of a graphic matroid M(G) is at least1 2 log 2 d. Proof. Since td(G) = d, the graph G contains a cycle of length at least √ d by [32, Proposition 6.2]. Therefore, by Proposition 3.4, bd(M(G)) ≥ 1 2 log 2 d.

Lemma 3 . 8 .Lemma 3 . 9 .

 3839 Let C be a circuit in a matroid M. Let e ∈ C. If |C| > 1, then the set C \ {e} is a circuit in M/e. Proof. By the definition of contracting an element, it follows that r M/e (C \ e) = r M (C) -1 = |C| -2. On the other hand, if X is a proper subset of C, then r M/e (X) = r M (X ∪ {e}) -1 = |X|. Hence, C \ {e} is a circuit in M/e. Let M be a matroid and e an element of M. If C is a circuit of M/e, then M has a circuit C ′ such that C ′ ⊇ C.

  However, C \ {e} is a circuit in M/e by Lemma 3.8. Since D 1 and D 2 are proper subsets of C \ {e}, both D 1 and D 2 are independent in M/e. Hence, D 1 and D 2 are independent in M 1 and M ′ 2 , respectively. It follows that r M/e (C \ {e}) = |D 1 | + |D 2 |, which is impossible. Lemma 3.8 and Lemma 3.10 yield the following.

4 Figure 1 :

 41 Figure 1: The notation used in the proof of Lemma 3.12.

Step 4 for

 4 the component M 0 of M/e containing C \ e do choose an element e 0 ∈ C \ {e}; (T 0 , f 0 ) := construct(M 0 , C \ {e}, e 0 ); end Step 5

Figure 2 :

 2 Figure 2: Encoding a general graph G in a rank 3 matroid M(G, 1).

Lemma 5 . 3 .

 53 For any graph G and k ≥ 2, it holds that I(M(G, k)) ∼ = G.

  )|+|Gn| 3 ≤ 1 |Gn| . Since |G n | tends to infinity, lim n→∞ θ 0 , M n = 1 and the first condition in Lemma 2.3 holds. Now for ℓ ∈ N, consider ϕ ∈ FO ℓ (λ G ). Let (e 1 , . . . , e ℓ ) be an ℓ-tuple chosen uniformly at random from M n . Since lim n→∞ θ 0 , M n = 1, the probability that at least one e j is not a vertex element in M n tends to zero. Since in M n the equivalence classes C(v) for v ∈ V (G n ) have all the same size, it follows from Proposition 2.2 and Lemma 5.3 that ϕ, G n = ϕ, I(M n ) = Ĩ(ϕ), M n + o(1).

* Research supported by the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 259385. The work of the second author was also supported by the Engineering and Physical Sciences Research Council Standard Grant number EP/M025365/1.

We will show that D ∪ {e 0 , e ′ 1 } or D ∪ {e 0 , e 1 } is a circuit in N. Since D is independent in N/e 0 , we get that D ∪ {e 0 } is independent in M. We next show that r N (X ∪ {e i , e j }) = r N (X ∪ {e 0 , e 1 , e ′ 1 })

for any e i , e j ∈ {e 0 , e 1 , e ′ 1 }, e i = e j and for any set X ⊆ N. This follows from the following application of the submodularity of the rank function:

Hence, for any proper subset D ′ D, we have

where the last equality follows from the fact that

Thus, both D ′ ∪ {e 0 , e ′ 1 } and D ′ ∪ {e 0 , e 1 } are independent in N. On the other hand, it also holds that

where the first equality follows from (2), the second from M 1 = N/e 0 , and the last from the fact that

This can be shown using the submodularity of the rank function and (2) as follows:

The proof is now complete.

We get the following corollary.

Corollary 3.13. Let M be a matroid. If C 0 , C 1 , . . . , C k and M 0 , . . . , M k are as in Lemma 3.12, then the matroid M contains a circuit of length at least

2 , then by Lemma 3.12 there is a circuit of length at least k + 3 > √ t. On the other hand, if t > (k + 1) 2 , then there exists i ∈ {0, 1, . . . , k} such that

let Ĉi := C j i ∪ {e j i -1 }, êi := e j i -1 and ê′ i any element of C j i -1 different from e j i -1 . If the i-th run is finished by Step 3 or 4 followed by Step 2, let Ĉi := C j i , let êi be the unique element in C j i ∩ C j i +1 and let ê′ i be the element of C j i -1 different from e j i -1 and from êi .

The circuits Ĉ0 , . . . , Ĉk together with the elements ê0 , . . . , êk and the elements ê′ Proof. Apply Algorithm 1 to M and keep the notation of the proof of Lemma 3.15. Since M has a circuit of length at least

We obtain another corollary from the presented analysis of Algorithm 1.

Corollary 3.17. There is a depth-decomposition (T, f ) and a base B of M such that f | B is a bijection between B and the non-root vertices of T , and f (e) is a leaf for every e ∈ B. Furthermore, the depth of T is at most 4 bd(M ) .

Proof. We prove that the pair (T, f ) returned by Algorithm 1 satisfies the statement. The depth of T is at most 4 bd(M ) by Lemma 3.15, and we prove the existence of B by induction on the number of recursive calls. Let C and e be the parameters used to execute Algorithm 1. If the algorithm constructed (T, f ) in Step 0 or 1, then the statement is obvious. If (T, f ) is constructed in Step 2, the existence of B follows from induction. If (T, f ) is constructed in Step 3, the base from the recursive call together with e forms a base B of M. Finally, if (T, f ) is constructed in Steps 4 and 5, the bases from the recursive calls together with e form a base B of M. Observe that in the last two cases the elements of the base B are mapped by f to different non-root vertices, and all the other elements are mapped by f to leaves.

Limits of representable matroids

This section is devoted to the proof of Theorem 1.2. We first describe an encoding of first-order properties of a matroid in a rooted forest and we then employ Theorem 2.1 to find a limit modeling.