Many 2-Level Polytopes from Matroids

Abstract

The family of 2-level matroids, that is, matroids whose base polytope is 2-level, has been recently studied and characterized by means of combinatorial properties. 2-Level matroids generalize series-parallel graphs, which have been already successfully analyzed from the enumerative perspective. We bring to light some structural properties of 2-level matroids and exploit them for enumerative purposes. Moreover, the counting results are used to show that the number of combinatorially non-equivalent $(n-1)$-dimensional 2-level polytopes is bounded from below by $c \cdot n^{-5/2} \cdot \rho ^{-n}$, where $c\approx 0.03791727$ and $\rho ^{-1} \approx 4.88052854$.

1 Introduction

A hyperplane H is facet-defining for a polytope P if it is supporting for P and $\dim (P\cap H)=\dim (P)-1$. A 2-level polytope is a polytope P such that for each facet-defining hyperplane H, there exists a hyperplane $H'$ parallel to H that contains all the vertices of P not in H. The family of 2-level polytopes appeared in the literature in different areas under different names: in [5] they are called compressed polytopes and also show up in statistics (see [23]). In the context of combinatorial optimization [13, 18], 2-level polytopes are related to the so-called exact point configurations: the interest in these configurations is due to the fact that some techniques from polynomial optimization, namely semidefinite programming relaxations, are very efficient for these configurations. Furthermore 2-level polytopes play a role in the study of extremal centrally-symmetric polytopes [21].

Two polytopes are combinatorially equivalent if their face lattices are isomorphic. It is known that all 2-level n-dimensional polytopes are affinely equivalent to 0 / 1-polytopes (polytopes with all vertices in $\{ 0,1 \}^n$) and the number of combinatorially non-equivalent 0 / 1-polytopes is doubly-exponential in the dimension (see [26]). Among the finite number of 0 / 1-polytopes of fixed dimension, it is natural to ask how many are 2-level, up to combinatorial equivalence.

Though 2-level polytopes are endowed with a very restrictive geometric property, this class is not well-understood and an exact enumeration seems to be complicated. It is easy to see that the 2-levelness is preserved for some polytopal constructions: pyramid, prism, and Cartesian product. Moreover some subfamilies of 2-level polytopes are known: two of them are explored in [11], the so-called Hansen polytopes [17] and Hanner polytopes [16], while a third one arises from stable sets of perfect graphs as explained in [15, Chap. 9]. Note that the construction of twisted prism over this last family yields the family of Hansen polytopes. Order polytopes of finite posets [22] are also 2-level. Very recently, a new subfamily of 2-level polytopes arising from matroid theory has been characterized in [14]. More precisely, this subfamily is associated with the base polytopes of 2-level matroids.

A complete classification of the 0 / 1-equivalence classes of 0 / 1-polytopes is only available for dimension 3, 4, 5, (and 6 for polytopes up to 12 vertices). Moreover two polytopes that are 0 / 1-equivalent are also combinatorially equivalent, but the converse is not true. The difficulties in providing a complete list already in dimension 6 suggest that a computational approach to the problem could be unsuccessful. The lack of an exact enumeration in dimension $\ge 6$ leads to a second natural question, namely the existence of asymptotic bounds for the number of 2-level polytopes.

By means of the polytopal constructions we mentioned above (pyramid, prism, and Cartesian product) exponentially many combinatorially non-equivalent 2-level polytopes can be constructed. In this paper we compute an explicit exponential lower bound for the number of 2-level polytopes via 2-level matroids. More precisely, we prove the following theorem.

Theorem 1.1

The number of combinatorially non-equivalent $(n{-}1)$-dimensional 2-level polytopes is bounded from below by

$$\begin{aligned} c \cdot n^{-5/2} \cdot \rho ^{-n}, \end{aligned}$$

where $c\approx 0.03791727$ and $\rho ^{-1}$ is a computable constant whose value is approximately equal to 4.88052854.

The interest in the subfamily of 2-level matroids is motivated by the fact that it contains more complicated polytopes, namely not obtained by means of elementary polytopal constructions. Moreover it allows to determine a large basis for the exponential lower bound.

New combinatorial aspects of 2-level matroids are introduced in Sect. 3 and give the possibility to increase the control on the enumerative formulas. It is noteworthy that this matroid family generalizes the family of series-parallel graphs, which appears in various areas and has several interesting properties that are likely to have counterparts for 2-level matroids. In particular, series-parallel graphs have been already successfully studied from an enumerative point of view in [2, 8]. To approach the enumeration of 2-level matroids we investigate the matroid tree decomposition associated to these matroids. We analyze the features of the decomposition and we get one of the main results of the paper: we observe that there is an interesting interpretation in terms of acyclic structures. More precisely, we reveal a bijection between 2-level matroids and a family of trees, that we call $\mathsf {UMR}$ -trees, whose vertices are labelled by uniform matroids and satisfy some adjacency restrictions. This last discovery makes 2-level matroids particularly suitable for enumeration. Indeed the family of $\mathsf {UMR}$-trees is exploited in Sect. 4 to encode all the enumerative information in terms of generating functions and relations (equations) among them by means of the symbolic method in enumerative combinatorics. Finally, powerful analytic techniques are applied to the equations in order to get an asymptotic estimate for the coefficients of the generating functions.

The paper is structured in the following way: in Sect. 2 the basics on matroid theory and enumerative combinatorics are stated. In Sect.  3 we study how to decompose 2-level matroids in terms of tree-like structures ($\mathsf {UMR}$-trees). The structural properties of the $\mathsf {UMR}$-trees are exploited later in Sect. 4 in order to get counting formulas which can be analyzed by means of analytic techniques, producing the estimate stated in Theorem 1.1.

2 Preliminaries

In this section we introduce the basic notions needed in the rest of the paper. In Sect. 2.1 we focus on definitions and concepts related to matroid theory. In Sect. 2.2 we fix our notation concerning enumeration by means of generating functions and finally in Sect. 2.3 we state the results needed in order to get asymptotic estimates for the coefficients of the generating functions under consideration.

2.1 Matroids

The basic definition is the following:

Definition 1

A matroid of rank k is an ordered pair $\mathcal {M}= (E,\mathcal {B})$ consisting of a finite set E (ground set) and a collection of bases $\emptyset \ne \mathcal {B}\subseteq \left( {\begin{array}{c}E\\ k\end{array}}\right)$ satisfying the Basis Exchange Axiom: for $B_1,B_2 \in \mathcal {B}$ and $x \in B_1 \setminus B_2$ there exists $y\in B_2\setminus B_1$ such that $(B_1 \setminus x)\cup y \in \mathcal {B}$.

Matroids are combinatorial objects that generalize graphs and linear dependence: the family of graphic matroids is particularly interesting and useful to visualize examples of matroids. The matroid associated to a graph $G=(V,E)$ is such that the ground set is given by the set of edges and the collection of bases is given by the set of spanning forests. The rank of a connected graph is clearly $|V|-1$. However, it could sometimes be misleading to think in terms of the graph structure, since some information, like the vertex structure, is not retained at matroid level.

A matroid has many equivalent definitions (see [20] for more details): we presented the one using the collection of bases. Nevertheless we want to introduce two further collections of sets that can define a matroid. The first one is the collection of independent sets, that is all the sets $X \subseteq E$ such that $X \subseteq B$, for some $B\in \mathcal {B}$. The rank of $X\subseteq E$, denoted by ${\text {rank}}_{\mathcal {M}}(X)$, is the cardinality of the largest independent subset contained in X. The second one is the collection of circuits $\mathcal {C}(\mathcal {M})$. Circuits are minimal dependent sets of $\mathcal {M}$. An element e such that $\{e\}$ is a circuit is called a loop.

Two matroids $\mathcal {M}$ and $\mathcal {N}$ are isomorphic if their collection of circuits are the same up to relabelling of the ground sets $E(\mathcal {M})$ and $E(\mathcal {N})$. More formally $\mathcal {M}\cong \mathcal {N}$ if there is a bijection $\varphi : E(\mathcal {M}) \rightarrow E(\mathcal {N})$ such that, for all $X\subseteq E(\mathcal {M})$, $\varphi (X)\in \mathcal {C}(\mathcal {N})$ if and only if $X\in \mathcal {C}(\mathcal {M})$.

Let us consider a fairly simple family of matroids that is of great importance in the rest of the paper, namely uniform matroids. The uniform matroid $U_{n,k}$ for $0\le k\le n$ consists of the ground set $[n]:=\{1,\ldots , n \}$ and the collection of bases $\left( {\begin{array}{c}[n]\\ k\end{array}}\right)$. The uniform matroids which are also graphic matroids are of the form: $U_{n,0}$, $U_{n,1}$, $U_{n,n{-}1}$, and $U_{n,n}$. See Fig. 1.

Fig. 1

From left to right, graphical representations of the matroids $U_{n,0}$, $U_{n,1}$, $U_{n,n{-}1}$, and $U_{n,n}$

Observe that for $U_{n,0}$ and $U_{n,n}$ we illustrated one among many possible graphical representations. Namely, Whitney’s 2-Isomorphism Theorem [20, Thm. 5.3.1] implies that every graph formed by n loops corresponds to $U_{n,0}$ regardless of the vertex structure, while any tree with n edges corresponds to the matroid $U_{n,n}$.

For counting purposes we do not consider the uniform matroids $U_{n,0}$ and $U_{n,n}$, while among the other uniform matroids we need to distinguish the graphic ones from the non-graphic ones. More precisely we write $\mathsf {M}_n$ to denote the matroid $U_{n,1}$ (it stands for multiedge) and $\mathsf {R}_n$ to denote the matroid $U_{n,n{-}1}$ (it stands for ring).

The dual matroid $\mathcal {M}^*$ of a matroid $\mathcal {M}=(E,\mathcal {B})$ is the matroid defined by the pair $(E,\mathcal {B}^*)$ where $\mathcal {B}^*=\{E\setminus B \; : \; B\in \mathcal {B}\}$. For uniform matroids we have $U_{n,k}^*=U_{n,n-k}$ and in particular $\mathsf {R}_n^*=\mathsf {M}_n$. An element e is called a coloop of $\mathcal {M}$ if it is a loop of $\mathcal {M}^*$. A matroid $\mathcal {M}$ is self-dual if $\mathcal {M}\cong \mathcal {M}^*$. For instance, all uniform matroids of type $U_{2n,n}$ are self-dual.

Definition 2

Let $\mathcal {M}= (E,\mathcal {B})$ be a matroid. The base polytope of $\mathcal {M}$ is the polytope

$$\begin{aligned} P_{\mathcal {M}} := {{\mathrm{\mathrm {conv}}}}(\{ \mathbf {1}_{B} : B \in \mathcal {B}\} ). \end{aligned}$$

It was proven in [12] that all the edges of a base polytope are parallel to some difference $e_i-e_j$ of two unit vectors.

The base polytopes $P_{\mathsf {R}_{n}}$ and $P_{\mathsf {M}_{n}}$ are n-simplices, while the polytopes $P_{U_{n,k}}$ for $2\le k \le n{-}2$, are called hypersimplices and denoted by $\Delta _{n,k}$. For more background about this family of polytopes we refer to [27].

A 2-level matroid is a matroid such that the corresponding base polytope is 2-level. In [14] an excluded minor characterization for the family of 2-level matroids is provided. The four excluded minors are the following rank 3 matroids on 6 elements: $\mathcal {M}(K_4)$, $\mathcal {W}^3$, $Q_6$, $P_6$. The first excluded minor of the list is nothing but the graphic matroid of the complete graph on 4 vertices; for more details about these matroids we refer to Oxley’s book [20] or to the paper where they are used to describe the 2-level matroids [14]. Since $P_6=([6],\mathcal {B})$ appears in Example 3, we list here its collection of circuits

$$\begin{aligned} \mathcal {C}(P_6)=\{123, 1245,1246, 1256, 1345,1346,1356, 1456,2345,2346,2356,2456,3456 \}. \end{aligned}$$

It is important to notice that there is only one circuit with 3 elements. In [14], together with the excluded minor characterization of 2-level matroids, a synthetic description of this class is also provided. Before presenting it, we need to introduce two matroid operations. Let $\mathcal {M}_1$ and $\mathcal {M}_2$ be matroids with disjoint ground sets $E_1$ and $E_2$. The collection

$$\begin{aligned} \mathcal {B}\ := \ \{ B_1\cup B_2 : B_1\in \mathcal {B}(\mathcal {M}_1), B_2\in \mathcal {B}(\mathcal {M}_2)\} \end{aligned}$$

is the set of bases of a matroid on $E_1 \cup E_2$, called the direct sum of $\mathcal {M}_1$ and $\mathcal {M}_2$ and denoted by $\mathcal {M}_1 \oplus \mathcal {M}_2$. On the other hand, if we choose $e_1 \in E_1$ and $e_2\in E_2$ such that they are neither a loop nor a coloop of the respective matroids and define the collection

$$\begin{aligned} \mathcal {B}\ := \ \{ B_1\cup B_2{\setminus } \{e_1,e_2\} : B_1\in \mathcal {B}(\mathcal {M}_1), B_2\in \mathcal {B}(\mathcal {M}_2), |(B_1 \cup B_2) \cap \{e_1,e_2\}|=1 \}, \end{aligned}$$

then the pair $(E_1 \cup E_2 \setminus \{ e_1, e_2 \} ,\mathcal {B})$ defines a matroid called 2-sum of $\mathcal {M}_1$ and $\mathcal {M}_2$ with base points $e_1$ and $e_2$. We denote it by $(\mathcal {M}_1,e_1) \oplus _2 (\mathcal {M}_2,e_2)$. Observe that this notation is slightly different from the one used in [20], but it turns out to be more efficient for the constructive part.

Theorem 2.1

([14]) Every 2-level matroid can be obtained as a sequence of direct sums and 2-sums of uniform matroids. Moreover every combination of uniform matroids yields a 2-level matroid.

The direct sum and the 2-sum of matroids are closely related to the connectedness of a matroid: a matroid $\mathcal {M}$ is 2-connected (or also connected) if it cannot be written as a proper direct sum of two matroids, and $\mathcal {M}$ is 3-connected if it cannot be written as 2-sum of two matroids each with fewer elements than $\mathcal {M}$.

A separator of a matroid $\mathcal {M}$ is a set $T\subseteq E$ such that ${\text {rank}}_{\mathcal {M}}(T)+{\text {rank}}_{\mathcal {M}}(E\setminus T)={\text {rank}}_{\mathcal {M}}(\mathcal {M})$. A matroid $\mathcal {M}$ is 2-connected if and only if there is no separator T, with T being a proper subset of E. The base polytope $P_{\mathcal {M}}$ of a matroid $\mathcal {M}=(E,\mathcal {B})$ has dimension $|E|-c(\mathcal {M})$ where $c(\mathcal {M})$ is the number of 2-connected components of $\mathcal {M}$. In particular, if $\mathcal {M}$ is 2-connected, then $\dim (P_{\mathcal {M}})=|E|{-}1$.

If we try to look at matroid operations from the point of view of base polytopes we have:

• $P_{\mathcal {M}^*}=\mathbf {1}- P_{\mathcal {M}}$. This means that the base polytope of the dual matroid $P_{\mathcal {M}^*}$ is congruent to the base polytope $P_{\mathcal {M}}$;

• $P_{\mathcal {M}_1\oplus \mathcal {M}_2}=P_{\mathcal {M}_1}\times P_{\mathcal {M}_2}$, where $\times$ denotes the Cartesian product of polytopes;

• $P_{(\mathcal {M}_1,e_1)\oplus _2 (\mathcal {M}_2,e_2)}$ can be described using the subdirect product construction introduced in [19] as shown in [14].

To keep the counting as easy as possible we first deal with 2-connected matroids. This corresponds to considering only sequences of 2-sums of uniform matroids. As a consequence, the polytopes we count cannot be obtained as a Cartesian product of two polytopes (for example no prism is in this family). At the end of Sect. 4 we show that, asymptotically, the restriction to 2-connected matroids does not alter the exponential growth.

The basis graph of a matroid $\mathcal {M}$ is the undirected graph with vertex set the collection of all bases of $\mathcal {M}$ such that a basis $B_1$ is connected to another basis $B_2$ whenever the symmetric difference $B_1 \Delta B_2$ has cardinality exactly 2. Equivalently, it is the 1-skeleton of the base polytope $P_\mathcal {M}$.

Let us conclude this section with some results for base polytopes that are used in Sect. 4 to complete the asymptotic enumeration of 2-level matroids. The first one appears as part of Exercise 4.9 in [25, Chap. 4].

Proposition 2.2

Let $\mathcal {M}$ and $\mathcal {N}$ be 2-connected matroids. The basis graphs of $\mathcal {M}$ and $\mathcal {N}$ are isomorphic if and only if $\mathcal {M}\cong \mathcal {N}$ or $\mathcal {M}\cong \mathcal {N}^*$.

Since two congruent polytopes have the same 1-skeleton we easily obtain the following corollary, which also appears as an exercise in [3, Chap. 1, Ex. 18].

Corollary 2.3

Let $\mathcal {M}$ and $\mathcal {N}$ be 2-connected matroids. The base polytopes $P_{\mathcal {M}}$ and $P_{\mathcal {N}}$ are congruent if and only if $\mathcal {M}\cong \mathcal {N}$ or $\mathcal {M}\cong \mathcal {N}^*$.

It is known that “congruent” $\Rightarrow$ “combinatorially equivalent”. The converse is in general not true, not even for 0 / 1-polytopes: for instance we can find full-dimensional 0 / 1-simplices with different volumes [26]. Nevertheless, for the class of base polytopes, we get the following corollary of Proposition 2.2.

Corollary 2.4

Let $\mathcal {M}$ and $\mathcal {N}$ be 2-connected matroids. The polytope $P_{\mathcal {M}}$ is congruent to $P_{\mathcal {N}}$ if and only if $P_{\mathcal {M}}$ is combinatorially equivalent to $P_{\mathcal {N}}$.

Proof

We only need to prove one direction. If $P_{\mathcal {M}}$ is combinatorially equivalent to $P_{\mathcal {N}}$, then they have isomorphic face lattices and, in particular, isomorphic 1-skeletons. By Proposition 2.2, $\mathcal {M}\cong \mathcal {N}$ or $\mathcal {M}\cong \mathcal {N}^*$ and therefore $P_{\mathcal {M}}$ is congruent to $P_{\mathcal {N}}$ by Corollary 2.3. $\square$

This last corollary allows us to investigate the number of non-congruent 2-level base polytopes, instead of looking at combinatorial equivalence of such polytopes.

2.2 The Symbolic Method in Enumerative Combinatorics. Tree-like Structures

The reader is referred to  [10, Chap. 1] to see all the terminology and notation in full detail. Let $(\mathcal {A},|\cdot |)$ be an admissible combinatorial class, namely a set $\mathcal {A}$ endowed with a size function $|\cdot |$ such that the number of elements in $\mathcal {A}$ of any given size is finite. Then the generating function (GF for short) associated to $\mathcal {A}$ is the formal power series $A(x)=\sum _{a\in \mathcal {A}} x^{|a|}=\sum _{n\ge 0}a_n x^n$. In particular, $a_n$ is the number of elements in $\mathcal {A}$ of size n and we write $[x^n]A(x)=a_n$. We assume that every combinatorial class contains no object of size 0, thus $a_0 = 0$. Given two generating functions A(x) and B(x), we write $A(x) \le B(x)$ if for each n, $[x^n]A(x) \le [x^n] B(x)$.

The symbolic method in enumerative combinatorics (see [10, Chap. 1]) gives a direct way to translate combinatorial operations among combinatorial classes into operations involving their generating functions. Besides the disjoint union and Cartesian product of combinatorial families, which translate into sums and products of GFs, respectively, we introduce the multiset construction: given a combinatorial class $(\mathcal {A},|\cdot |)$ with GF A(x), the multiset of $\mathcal {A}$ is the combinatorial family obtained by taking all multisets of elements in $\mathcal {A}$. The corresponding GF is equal to

$$\begin{aligned} {{\mathrm{\mathrm{Mul}}}}(A(x))=\exp \bigg (\sum _{r=1}^\infty \frac{1}{r}A(x^r)\bigg ). \end{aligned}$$

Finally, we also need restricted multiset constructions. Let $\Lambda$ be a subset of positive integers. The multiset operator restricted to $\Lambda$ of $\mathcal {A}$ is the combinatorial family obtained by taking multisets of elements in $\mathcal {A}$ with the restriction that the number of components lies in $\Lambda$. We write this as ${{\mathrm{\mathrm{Mul}}}}_{\Lambda }(A(x))$. In particular,

$$\begin{aligned} {{\mathrm{\mathrm{Mul}}}}_{0}(A(x))=1, \; \; \; {{\mathrm{\mathrm{Mul}}}}_{1}(A(x))=A(x),\;\; \; {{\mathrm{\mathrm{Mul}}}}_{2}(A(x))=\tfrac{1}{2}(A(x)^2+A(x^2)). \end{aligned}$$

The notation ${{\mathrm{\mathrm{Mul}}}}_{\ge k}$ refers to the multiset operator restricted to $\Lambda =\{k,k+1,\ldots \}$.

The Dissymmetry Theorem for trees The Dissymmetry Theorem for trees (see [1]) provides a general methodology to relate a combinatorial class of unrooted trees with given properties to the corresponding classes of rooted trees. More precisely, let $\mathcal {T}$ be a class of unrooted trees. We define the following families of rooted trees: $\mathcal {T}_{\circ }$ is built from $\mathcal {T}$ by rooting a vertex, $\mathcal {T}_{\circ -\circ }$ is the class of trees where an edge of $\mathcal {T}$ is rooted and $\mathcal {T}_{\circ \rightarrow \circ }$ is the class of trees obtained from $\mathcal {T}$ by rooting and orienting an edge. The Dissymmetry Theorem for trees asserts that

$$\begin{aligned} \mathcal {T} \cup \mathcal {T}_{\circ \rightarrow \circ } \simeq \mathcal {T}_{\circ -\circ }\cup \mathcal {T}_{\circ }, \end{aligned}$$

(1)

where “$\simeq$” means that there a bijection between the two combinatorial classes which translates directly into equalities of the corresponding generating functions.

2.3 Asymptotic Estimates and Analytic Combinatorics

By means of analytic methods we can obtain asymptotic estimates for $[x^n]A(x)$ in terms of the singularities of A(x) with minimum complex modulus. Such singularities are called dominant. Whenever A(x) has non-negative coefficients, one of its dominant singularities (if there is any) is a positive real number by Pringsheim’s Theorem, see [10, Thm. IV.6].

With this language, we obtain the asymptotic expansion of $[x^n]A(x)$ by transferring the behaviour of A(x) around its dominant singularity from a simpler function B(x) for which we know the asymptotic behaviour of the coefficients. The first result in this direction is the Transfer Theorem for singularity analysis [9, 10]. For our purposes we present a version of the theorem that covers the case when there is a unique dominant singularity $\rho$.

Theorem 2.5

(Transfer Theorem for a unique dominant singularity [9], simplified version) Assume that the generating function A(x) is analytic in a dented domain $\Delta (\phi ,R)$ at $\rho \in \mathbb {C}$, defined as the set

$$\begin{aligned} \{x\in \mathbb {C}: x \ne \rho ,\, |x|<R,\, |\mathrm {Arg}(x-\rho )|>\phi \} \end{aligned}$$

for $|\rho |<R\in \mathbb {R}$ and $0<\phi <\pi /2$. If A(x) admits an expansion of the form

$$\begin{aligned} A(x) = C\big (1 - \frac{x}{\rho } \big )^{-\alpha }+ O\big (\big (1-\frac{x}{\rho }\big )^{-\alpha +1}\big ) \end{aligned}$$

for $x\rightarrow \rho$ in the dented domain $\Delta (\phi , R)$ at $\rho$, and $\alpha \notin \{0,-1,-2,\dots \}$ then

$$\begin{aligned}{}[x^n]A(x) = C\frac{1}{\Gamma (\alpha )} \cdot n^{\alpha -1} \cdot \rho ^{-n} \, (1+o(1)), \end{aligned}$$

where $\Gamma (s) = \int _0^\infty t^{s-1} e^{-t} dt$ denotes the classical Gamma function.

In the next sections we also have to analyze systems of functional equations. The main reference for this topic is the paper [6]. For convenience, we rephrase it here in a simplified version (the interested reader could find the more general result in [7, Sect. 2.2.5]).

Let $y_1(x),\dots , y_k(x)$ be generating functions satisfying a system of functional equations. We define the vector $\varvec{y}(x):=(y_1(x),\dots , y_k(x))$, and a system $\varvec{y}=\mathbf F (x; \varvec{y})$ satisfied by $\varvec{y}(x)$. Notice that $\mathbf F (x,\varvec{y})=(F_1(x,\varvec{y}),\dots , F_k(x,\varvec{y}))$. We assume that each $y_i(x)$ is analytic at $x=0$, and that $y_i(0)=0$. We also assume that all $F_i(x,\varvec{y})$ are analytic around $(0,\varvec{0})$ and have nonnegative Taylor coefficients around $(0,\varvec{0})$ (this condition assures the uniqueness of the solution).

The dependency graph $G=(V,\mathcal {D})$ associated to the system $\varvec{y}=\mathbf F (x; \varvec{y})$ is the oriented graph whose vertex set is $V=\{y_1,\dots , y_k\}$ and the arc $\overrightarrow{y_{i}y_{j}}\in \mathcal {D}$ if and only if $\frac{\partial F_i(x,\varvec{y})}{\partial y_j}\ne 0$ (this indicates that $F_i(x,\varvec{y})$ really depends on $y_j$). A dependency graph is called strongly connected if every pair of vertices is connected by a directed path. With this terminology we have the following result:

Theorem 2.6

(Singularity analysis of systems of functional equations [6], simplified version) Let $\varvec{y}(x)=\mathbf F (x; \varvec{y}(x))$ be a system of functional equations satisfying the conditions described above. Additionally, assume that the related dependency graph is strongly connected. Denote by $\mathbf I _{k}$ the $k \times k$ identity matrix and by $\mathrm {Jac}(\mathbf F )$ the $k\times k$ Jacobian matrix associated to $\mathbf F (x,\varvec{y})$. If the system

$$\begin{aligned} {\left\{ \begin{array}{ll} \varvec{y}&{}=\mathbf F (x; \varvec{y}) \\ 0&{}= \det \big (\mathbf I _{k}-\mathrm {Jac}(\mathbf F )\big ) \end{array}\right. } \end{aligned}$$

(2)

has a unique positive real solution $(x_0,\varvec{y}_0)$ in the region of analyticity of each component of $\mathbf F (x,\varvec{y})$, then there is a unique solution $\varvec{y}(x)$ to the system of functional equations. Moreover, the functions $y_i(x)$ have nonnegative coefficients and a square-root expansion in a domain dented at $x_0$.

3 Matroid Decomposition

This section is devoted to the analysis of the structure of 2-level matroids. Every 2-connected matroid has a tree decomposition which relies on the 2-sum and we refer to [20, Sect. 8.3] for a complete overview on this topic. We state here the results which are relevant for the paper and we explore further features of tree decomposition that are specific for the class of 2-level matroids. First let us make precise what we mean by a decomposition.

Definition 3

A matroid-labelled tree is a tree T with vertex set $\{ \mathcal {N}_1,\ldots , \mathcal {N}_s\}$ for some positive integer s such that

• (i) the $\mathcal {N}_i$’s are matroids with pairwise disjoint ground sets;

• (ii) an edge joining $\mathcal {N}_i$ and $\mathcal {N}_j$ is labelled by a set $\{e_i,e_j\}$ such that $e_i\in E(\mathcal {N}_i)$, $e_j\in E(\mathcal {N}_j)$, and $e_i$, $e_j$ are neither loops nor coloops;

• (iii) the labels of the edges of T are pairwise disjoint.

We call $\mathcal {N}_1,\ldots , \mathcal {N}_s$ the vertex labels of T.

Example 1

Let us consider the matroid-labelled tree in the picture whose vertex labels are all graphic matroids. In particular they are rings and multiedges. Each vertex label must be provided with its ground set and its collection of bases. For instance the ring $R_4$ has ground set $E(R_4)=\{ 1,2,3,4\}$ and collection of bases $\left( {\begin{array}{c}[4]\\ 3\end{array}}\right)$. For a complete description of the vertex labels we refer to Example 2.

For a matroid-labelled tree T, we can contract an edge t labelled by $\{e_i,e_j\}$ connecting two vertex labels $\mathcal {N}_{i}$ and $\mathcal {N}_{j}$. The result is a matroid-labelled tree T / t with the same edges and vertex labels, except that the vertex labels $\mathcal {N}_{i}$ and $\mathcal {N}_{j}$ have been gathered into a unique vertex label, namely ${(\mathcal {N}_{i},e_{i})\oplus _2 (\mathcal {N}_{j},e_{j})}$, and the edge t has been contracted (Figs. 2, 3).

Example 2

The vertex labels of the matroid-labelled tree introduced in Example 1 are all graphic matroids. Thus, we can represent it as a sequence of 2-sums of graphs. In the picture we specify the ground set for each of the graphs.

Contracting an edge in the matroid-labelled tree corresponds to computing the 2-sum of two graphs. If we contract all the edges we get the graph on the right which happens to be a series-parallel graph. Definition 4 shows that the matroid-labelled tree we are considering is a tree decomposition for the matroid associated to this series-parallel graph.

Fig. 2

Matroid-labelled tree with vertex labels of type ring and multiedge

Fig. 3

Graph obtained after contraction of all edges of the matroid-labelled tree

Definition 4

A tree decomposition of a 2-connected matroid $\mathcal {M}$ is a matroid-labelled tree T such that if $V(T)=\{\mathcal {N}_1,\ldots , \mathcal {N}_s \}$ and $E(T)=\{t_1,\ldots , t_{s-1}\}$, then

• $E(\mathcal {M})=(E(\mathcal {N}_1)\cup E(\mathcal {N}_2) \cup \ldots \cup E(\mathcal {N}_s))\setminus (t_1 \cup t_2 \cup \ldots \cup t_{s-1} )$;

• $|E(\mathcal {N}_i)|\ge 3$ for all i, unless $|E(\mathcal {M})|< 3$, in which case $s=1$ and $\mathcal {N}_1=\mathcal {M}$;

• $\mathcal {M}$ is the matroid that labels the single vertex of $T/\{t_1,t_2,\ldots , t_{s-1}\}$.

We now report a theorem from [20, Thm. 8.3.10] which first appeared in [4]. According to our definitions, we replace the words “circuit” and “cocircuit” with “ring” and “multiedge”, respectively.

Theorem 3.1

Let $\mathcal {M}$ be a 2-connected matroid. Then $\mathcal {M}$ has a tree decomposition $T_\mathcal {M}$ in which every vertex label is 3-connected, a ring, or a multiedge, and there are no two adjacent vertices that are both labelled by rings or are both labelled by multiedges. Moreover, $T_\mathcal {M}$ is unique up to relabelling of its edges.

In order to obtain the uniqueness, it is necessary to require that there are no two adjacent vertex labels that are both rings or multiedges, otherwise adjacent rings (or multiedges) could make possible to keep the same tree structure while changing the vertex labels. These additional requirements to get uniqueness justify why we consider separately the labels of type $\mathsf {U}$, $\mathsf {M}$, and $\mathsf {R}$ in Sect. 4.

The theorem allows us to uniquely represent every matroid by a matroid-labelled tree whose vertex labels are 3-connected matroids (except rings and multiedges). In this paper we want to tackle the problem from a different perspective: instead of starting with a matroid and finding its tree decomposition, the goal is to count how many non-isomorphic matroid-labelled trees can be constructed from a given set of possible vertex labels. In this constructive process, every time that we establish the adjacency of two vertices, we have to decide one element for each ground set of the two vertex labels to be the base points of the 2-sum.

As shown in Example 3, the choice of the elements affects the result of the 2-sum: there exist two non-isomorphic matroids whose tree decompositions have the same tree structure and the same vertex labels, but different labels for the edges of the tree.

Before presenting the example, let us give an explicit description of the collection of circuits of the matroid $(\mathcal {M}_1,e_1)\oplus _2 (\mathcal {M}_2,e_2)$, namely

$$\begin{aligned} \mathcal {C}(\mathcal {M}_1\setminus e_1)\cup \mathcal {C}(\mathcal {M}_2 \setminus e_2)\cup \big \{(C_1-\{e_1\})\cup (C_2- \{e_2 \}){:}e_1\in C_1 \in \mathcal {C}(\mathcal {M}_1) \text { and }e_2\in C_2 \in \mathcal {C}(\mathcal {M}_2)\big \}. \end{aligned}$$

(3)

Example 3

Consider the 3-connected matroid $P_6$ described in Sect. 2.1. Construct a matroid-labelled tree with two adjacent vertex labels, both equal to $P_6$ (see Fig. 4). Let us label the ground set of the first copy of $P_6$ from 1 to 6 and the ground set of the second copy from 7 to 12. Each of the two copies has one circuit of length 3 (we assume $\{1,2,3\}$ and $\{7,8,9\})$ and all the other circuits are of length 4.

Fig. 4

Non-isomorphic matroids obtained as 2-sum of two matroids of type $P_6$

Consider the matroid $(P_6,1)\oplus _2 (P_6,7)$. It has circuits of length 4, 5, 6. On the other hand, the matroid $(P_6,4)\oplus _2 (P_6,10)$ has circuits of length 3, 4, 6. Thus, the two matroids are not isomorphic.

Nevertheless if we focus on 2-level matroids, the vertex labels are chosen among uniform matroids that we divide in the following three categories:

• (i) $\mathsf {M}$-vertices: correspond to multiedges of size at least 3;

• (ii) $\mathsf {R}$-vertices: correspond to rings of size at least 3;

• (iii) $\mathsf {U}$-vertices: correspond to uniform matroids $U_{n,k}$ such that $n\ge 4$ and $2\le k \le n-2$.

We define a new class of trees as follows.

Definition 5

Let T be a tree whose vertex labels are of type $\mathsf {U}$, $\mathsf {M}$, and $\mathsf {R}$ and such that no two $\mathsf {M}$-vertices and no two $\mathsf {R}$-vertices are adjacent. The tree T is a $\mathsf {UMR}$-tree if $\deg (\mathcal {N}_i)\le |E(\mathcal {N}_i)|$ for every vertex label $\mathcal {N}_i$.

For this particular class, the tree structure and the vertex labels are enough to determine the matroid uniquely up to matroid isomorphism. The proof of this fact is provided by Lemmas 3.3 and 3.4. The main result of this section is the following theorem, which is required for the enumeration in Sect. 4.

Theorem 3.2

The family of 2-connected 2-level matroids is in bijection with the family of $\mathsf {UMR}$-trees.

Before presenting the proof of the theorem, we introduce some further definitions. For each vertex label $\mathcal {N}_i$ of the tree decomposition of a matroid $\mathcal {M}$, we partition the ground set $E(\mathcal {N}_i)=\{e_1,\ldots , e_{s_i}\}$ into two sets: the set $W(\mathcal {N}_i)$ of elements which are base points for the 2-sum with a vertex label adjacent to $\mathcal {N}_i$ and the set $F(\mathcal {N}_i)=E(\mathcal {N}_i)\setminus W(\mathcal {N}_i)$. We call $W(\mathcal {N}_i)$ the set of ideal elements (generalizing the notion of ideal edge in [24, Sect. IV.3]) and $F(\mathcal {N}_i)$ the set of free elements. Note that the ideal elements do not belong to the ground set of $\mathcal {M}$, while we have $E(\mathcal {M})=\cup _{i} F(\mathcal {N}_i)$.

For a matroid $\mathcal {M}$ let us consider the set of its circuits $\mathcal {C}$. We say that $\mathcal {M}$ is transposition invariant with respect to the pair of elements $\{e_1,e_2\}\subset E(\mathcal {M})$ if we have that $\pi (\mathcal {C})=\mathcal {C}$, where $\pi$ is the transposition $(e_1 , e_2)$ and

$$\begin{aligned} \pi (\mathcal {C})=\{\pi (C){:}C\in \mathcal {C} \}. \end{aligned}$$

The notation $\pi (C)$ means that we apply the permutation of the ground set $\pi : E(\mathcal {M})\rightarrow E(\mathcal {M})$ to the circuit C of $\mathcal {M}$. A matroid is permutation invariant if it is transposition invariant with respect to every pair of elements in the ground set.

Example 4

Every uniform matroid $U_{n,k}$ is permutation invariant, since for every choice of $e_1,e_2\in [n]=E(U_{n,k})$, $\pi (\cdot )$ is a bijection from the set of $(k+1)$-subsets of [n] to itself. Moreover if a matroid $\mathcal {M}=([n],\mathcal {B})$ is permutation invariant, then it is a uniform matroid. Indeed let C be the circuit with the least number s of elements, then all the other subsets $\left( {\begin{array}{c}[n]\\ s\end{array}}\right)$ have to be circuits (by transposition invariance). It also follows that there cannot be other circuits. Thus $\mathcal {M}=U_{n,s-1}$.

We say that $\mathcal {M}$ is $\mathcal {N}_i$-transposition invariant, for $\mathcal {N}_i$ vertex label of the tree decomposition if it is transposition invariant with respect to every pair of elements in $F(\mathcal {N}_i)$. We say that $\mathcal {M}$ is node-invariant if it is $\mathcal {N}_i$-transposition invariant for every vertex label $\mathcal {N}_i$ of the tree decomposition.

Lemma 3.3

Let $\mathcal {M}$ be a $\mathcal {N}_i$-transposition invariant 2-connected matroid and $\mathcal {U}$ a uniform matroid. For any choice of $f\in F(\mathcal {N}_i)$ and $u\in E(\mathcal {U})$, the 2-sum $(\mathcal {M},f) \oplus _2 (\mathcal {U},u)$ yields the same matroid up to isomorphism.

Proof

The uniform matroid $\mathcal {U}$ is permutation invariant and thus the choice of $u \in E(\mathcal {U})$ does not affect the result of the 2-sum. Consider any two elements $f_1,f_2\in F(\mathcal {N}_i)$. We want to show that

$$\begin{aligned} S_{f_1}:=(\mathcal {M},f_1) \oplus _2 (\mathcal {U},u)\cong (\mathcal {M},f_2) \oplus _2 (\mathcal {U},u)=:S_{f_2}. \end{aligned}$$

Notice that $E(S_{f_2})=E(S_{f_1})- \{ f_2 \} \cup \{ f_1 \}$. We claim that the bijection ${\varphi \ : E(S_{f_1}) \rightarrow E(S_{f_2})}$ such that

$$\begin{aligned} \varphi (e)={\left\{ \begin{array}{ll} f_1 &{}\mathrm{{if}}\quad e= f_2, \\ e &{} \mathrm{{otherwise}} \end{array}\right. } \end{aligned}$$

yields the matroid isomorphism. We need to show that for every $X\subset E(S_{f_1})$, $X\in \mathcal {C}(S_{f_1})$ if and only if $\varphi (X)\in \mathcal {C}(S_{f_2})$.

As we have seen in  (3) a circuit C of $S_{f_1}$ can be of 3 different types:

• $C\in \mathcal {C}(\mathcal {U}\setminus u)$. In this case $\varphi (C)=C$ and clearly $C\in \mathcal {C}(S_{f_2})$.

• $C\in \mathcal {C}(\mathcal {M}\setminus f_1)$. This implies that C is a circuit of $\mathcal {M}$, $f_1\notin C$. Since $\mathcal {M}$ is $\mathcal {N}_i$-transposition invariant, we have that $\pi (C)\in \mathcal {C}(\mathcal {M})$ for $\pi =(f_1 , f_2)$. Moreover, $f_1\notin C$ implies $f_2\notin \pi (C)$, that is $\pi (C)\in \mathcal {C}(\mathcal {M}\setminus f_2)$. Finally, $\varphi (C)=\pi (C)\in \mathcal {C}(\mathcal {M}\setminus f_2)$ and thus $\varphi (C)\in \mathcal {C}(S_{f_2})$.

• $C=(C_1-\{f_1\})\cup (C_2-\{ u \})$, $f_1\in C_1 \in \mathcal {C}(\mathcal {M})$ and $u\in C_2 \in \mathcal {C}(\mathcal {U})$. Since $\mathcal {M}$ is $\mathcal {N}_i$-transposition invariant, for $\pi =(f_1 , f_2)$ we have $\pi (C_1) \in \mathcal {C}(\mathcal {M})$ and $f_2\in \pi (C_1)$. Moreover, $\varphi (C)=(\pi (C_1)-\{ f_2\})\cup (C_2-\{ u \})$, $f_2\in \pi (C_1) \in \mathcal {C}(\mathcal {M})$ and $u\in C_2 \in \mathcal {C}(\mathcal {U})$ and thus $\varphi (C)\in \mathcal {C}(S_{f_2})$.

The same argument applies to check that all circuits of $S_{f_2}$ are circuits of $S_{f_1}$ under the map $\varphi ^{-1}$. This concludes the proof. $\square$

Lemma 3.4

Let $\mathcal {M}$ be a node-invariant 2-connected matroid and $\mathcal {U}$ a uniform matroid. The 2-sum $(\mathcal {M},f) \oplus _2 (\mathcal {U},u)$ is a node-invariant matroid for any choice of $f\in E(\mathcal {M})$ and $u\in E(\mathcal {U})$.

Proof

Choose a vertex label $\mathcal {N}_i$ of the unique tree decomposition $T_\mathcal {M}$ of $\mathcal {M}$. Without loss of generality, let us assume $f\in F(\mathcal {N}_i)$. To prove that $S_f:=(\mathcal {M},f)\oplus _2 (\mathcal {U},u)$ is node-invariant, we need to check the transposition invariance for each vertex label. For any vertex label $\mathcal {N}_j$ and $f_1,f_2\in F(\mathcal {N}_j)$, $f_1,f_2\ne f$, we have that the set $\mathcal {C}(S_f)$ is invariant under $\pi =(f_1 , f_2)$. Indeed $\mathcal {C}(\mathcal {M}\setminus f)$ and $\mathcal {C}(\mathcal {U}\setminus u)$ are invariant under $\pi$ because $\mathcal {M}$ is node-invariant and $\mathcal {U}$ is permutation invariant. The same holds true for the circuits of the third type, since

$$\begin{aligned} \pi ((C_1- \{f\}) \cup (C_2 -\{ u\}))=(\pi (C_1)-\{ f\}) \cup (C_2 -\{ u\}) \end{aligned}$$

and $f\in \pi (C_1) \in \mathcal {C}(\mathcal {M})$ by node-invariance of $\mathcal {M}$.

The tree decomposition of $S_f$ has one new node, labelled by the uniform matroid $\mathcal {U}$. We still have to check that $S_f$ is $\mathcal {U}$-transposition invariant. The same argument used above applies to $\mathcal {U}$, since it is a permutation invariant matroid. $\square$

Proof of Theorem 3.2

Let us start with a uniform matroid $\mathcal {N}_1$. Since $\mathcal {N}_1$ is permutation invariant, it is also node-invariant. The 2-sum of $\mathcal {N}_1$ with a second uniform matroid $\mathcal {N}_2$ yields a node-invariant matroid by Lemma 3.4. We can iteratively add by 2-sum new uniform matroids $\mathcal {N}_3,\,\mathcal {N}_4,\,\ldots ,\, \mathcal {N}_s$. The matroid we get at every step is clearly node-invariant. Moreover, at the j-th iteration we have to select which vertex label $\mathcal {N}_i$, $i<j$ of $\mathcal {M}$ is adjacent to $\mathcal {N}_j$. Once we fix $\mathcal {N}_i$, the resulting matroid $(\mathcal {M},f)\oplus _2(\mathcal {N}_j,e)$ does not depend (up to isomorphism) on the choice of $f\in F(\mathcal {N}_i)$ by Lemma 3.3. We can conclude that the structure of the tree decomposition and the vertex labels are enough to determine uniquely the 2-level matroid. Vice versa Theorem 3.1 together with Theorem 2.1 proves that a 2-connected 2-level matroid uniquely identifies a tree structure with vertex labels chosen among the uniform matroids. $\square$

We close the section with a proposition from [20, Prop. 7.1.22] which is needed to deal with self-duality in Sect. 4.4.

Proposition 3.5

Let $\mathcal {M}_1$ and $\mathcal {M}_2$ be two matroids and $e_i\in E(\mathcal {M}_i)$. Then

$$\begin{aligned} ((\mathcal {M}_1,e_1)\oplus _2 (\mathcal {M}_2,e_2))^*=(\mathcal {M}_1^*,e_1) \oplus _2 (\mathcal {M}_2^*,e_2). \end{aligned}$$

4 Counting $\mathsf {UMR}$-Trees

In this section we apply the results in Sect. 3 to get enumerative formulas for the number of 2-level matroids of fixed size. By means of Theorem 3.2, this is equivalent to the enumeration of $\mathsf {UMR}$-trees. To the set of $\mathsf {U}$-vertices, $\mathsf {M}$-vertices, and $\mathsf {R}$-vertices, we add an additional type of vertices that we call legs. Legs always have degree 1, and are graphically represented by small red disks. For each free element of a vertex label $\mathcal {N}_i$ we draw a leg connected to $\mathcal {N}_i$. Observe that legs represent all the leaves of the tree. Hence, we develop enumerative formulas in terms of the number of legs in our tree mode and we translate them into counting results in the matroid setting. The combinatorial restrictions we consider in our trees (which naturally arise from the obstructions inherited from the matroid setting) are the following:

• (1) The edges are unlabelled;

• (2) No two $\mathsf {R}$-vertices and no two $\mathsf {M}$-vertices are adjacent;

• (3) The degree of the $\mathsf {R}$-vertices and $\mathsf {M}$-vertices is greater or equal than 3, and the degree of the $\mathsf {U}$-vertices is greater or equal than 4.

In principle, our goal is to get enumerative formulas for $\mathsf {UMR}$-trees, but in order to apply the Dissymmetry Theorem for trees (Sect. 2) we need to encode rooted families. For this reason we introduce the following technical definition: a $\mathsf {UMR}$-tree is said to be pointed if it has a special leaf of size 0 (namely, it does not contribute to the total amount of legs) that we call virtual leg. Roughly speaking, the virtual leg pinpoints its adjacent vertex which we call the pointed vertex of the $\mathsf {UMR}$-tree. We use a red triangle to graphically represent the virtual leg. See Fig. 5 for an example of a pointed $\mathsf {UMR}$-tree.

Fig. 5

A pointed tree with 18 legs, 1 virtual leg, and a pointed $\mathsf {R}$-vertex

If a vertex is incident with the virtual leg, its restricted degree is the total degree minus 1. Notice that $\mathsf {U}$-vertices have multiplicity due to the rank of the associated matroid. In other words, once the total degree of a $\mathsf {U}$-vertex is fixed (call it d), then the possible rank could take any value in $\{2,3,4,\ldots , d-2\}$. This yields $d-3$ possible different uniform matroids for this $\mathsf {U}$-vertex.

In the next subsections we use ordinary generating functions to enumerate $\mathsf {UMR}$-trees. We first analyze the rooted case and then the unrooted case; in both cases the variable x encodes non-virtual legs.

4.1 Counting Pointed $\mathsf {UMR}$-Trees

We denote by $A_{\mathsf {R}}(x),\, A_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)$ the generating functions for pointed trees where the virtual leg is adjacent to a $\mathsf {R}$-vertex, a $\mathsf {M}$-vertex, and a $\mathsf {U}$-vertex, respectively. Additionally, we write $A_l(x)$ for the generating function of the elementary tree pointed at a leg. Clearly, $A_l(x)=x$. Observe that the first non-zero coefficients in the generating functions of pointed $\mathsf {UMR}$-trees are $[x^2]A_{\mathsf {R}}(x)=[x^2]A_{\mathsf {M}}(x)=1,$ and $[x^3]A_{\mathsf {U}}(x)=1$.

We start getting relations between these generating functions by decomposing the trees at the pointed vertex. Let us start with $A_{\mathsf {R}}(x)$. Observe that such a tree can be described as a $\mathsf {R}$-vertex (the pointed one) followed by a multiset of size greater or equal than 2 of (the disjoint union of) trees rooted at either an $\mathsf {M}$-vertex or at an $\mathsf {U}$-vertex as shown in the following figure (Fig. 6).

Fig. 6

Decomposition of a pointed $\mathsf {UMR}$-tree

The combinatorial description gives us that $A_{\mathsf {R}}(x)= {{\mathrm{\mathrm{Mul}}}}_{\ge 2} (A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x)).$ This equation can be made explicit by means of the multiset operator:

$$\begin{aligned} A_{\mathsf {R}}(x)=&\exp \big (\sum _{r=1}^{\infty } \frac{1}{r} \big (A_{\mathsf {M}}(x^r)+A_{\mathsf {U}}(x^r)+A_l(x^r)\big )\big )\nonumber \\&- 1-\big (A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x)\big ). \end{aligned}$$

(4)

A similar argument holds changing the pointed $\mathsf {R}$-vertex by a $\mathsf {M}$-vertex. This gives an analogous equation for $A_{\mathsf {M}}(x)$:

$$\begin{aligned} A_{\mathsf {M}}(x)=\exp \big (\sum _{r=1}^{\infty } \frac{1}{r} \big (A_{\mathsf {R}}(x^r)+A_{\mathsf {U}}(x^r)+A_l(x^r)\big )\big ) - 1-\big (A_{\mathsf {R}}(x)+A_{\mathsf {U}}(x)+A_l(x)\big ). \end{aligned}$$

(5)

Observe that  (4) and (5) give that $A_{\mathsf {R}}(x)=A_{\mathsf {M}}(x)$. Indeed, by subtracting (4) from (5) we obtain that

$$\begin{aligned} \sum _{r\ge 1}\frac{1}{r}A_{\mathsf {R}}(x^r)=\sum _{r\ge 1}\frac{1}{r}A_{\mathsf {M}}(x^r). \end{aligned}$$

These two formal power series have the same coefficients. In particular, for each choice of n, $[x^n]\sum _{r\ge 1}\frac{1}{r}A_{\mathsf {R}}(x^r)= [x^n]\sum _{r\le n}\frac{1}{r}A_{\mathsf {R}}(x^r)$. Now, applying an easy induction argument we can conclude that for each n, $[x^n]A_{\mathsf {R}}(x)=[x^n]A_{\mathsf {M}}(x)$.

Getting formulas for $A_{\mathsf {U}}(x)$ is slightly more involved: if the pointed $\mathsf {U}$-vertex has total degree d, then it has multiplicity $d-3$. This fact must be encoded in the counting formulas. Let us use an auxiliary variable u which marks the restricted degree of the pointed $\mathsf {U}$-vertex (namely, the total degree d minus 1). Here we emphasize that we do not consider the contribution of the virtual leg to the total number of legs n. This is due to technical reasons that are going to be clear while proceeding with the counting. However, the multiplicity of the pointed $\mathsf {U}$-vertex must be considered with respect to the total degree of the vertex (thus including the virtual leg) and not with respect to the restricted degree. Indeed, for a pointed $\mathsf {U}$-vertex of degree d, its restricted degree is equal to $r=d-1$, and its multiplicity is equal to $d-3=r-2$.

We write $a_{n,r}$ for the number of pointed trees with n non-virtual legs whose virtual leg is adjacent to a $\mathsf {U}$-vertex of restricted degree r. The notation $a_{\mathsf {U}}(x,u):=\sum _{n,\,r\ge 3}a_{n,r}x^n u^r$ refers to the corresponding generating function. Then we have

$$\begin{aligned} A_{\mathsf {U}}(x)= \sum _{n,r\ge 3}(r-2) a_{n,r}x^n u^r|_{u=1}=\frac{\partial }{\partial u}a_{\mathsf {U}}(x,u)|_{u=1}- 2a_{\mathsf {U}}(x,1). \end{aligned}$$

(6)

Observe now that $a_{\mathsf {U}}(x,u)$ satisfies the equation $a_{\mathsf {U}}(x,u)={{\mathrm{\mathrm{Mul}}}}_{\ge 3} (u(A_{\mathsf {M}}(x)+A_{\mathsf {R}}(x)+A_{\mathsf {U}}(x)+A_l(x)))$, which arises from the fact that the pointed $\mathsf {U}$-vertex has restricted degree $\ge 3$ (or equivalently, degree $\ge 4$). Hence we have that

$$\begin{aligned} a_{\mathsf {U}}(x,u)=&\exp \big (\sum _{r=1}^{\infty } \frac{u^r}{r} \big (A_{\mathsf {R}}(x^r)+A_{\mathsf {M}}(x^r)+A_{\mathsf {U}}(x^r)+A_l(x^r)\big )\big )\\&- 1-u\big (A_{\mathsf {R}}(x)+A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x)\big )\\&-{{\mathrm{\mathrm{Mul}}}}_{ 2} (u(A_{\mathsf {M}}(x)+A_{\mathsf {R}}(x)+A_{\mathsf {U}}(x)+A_l(x))). \end{aligned}$$

Now by using (6) we can write $A_{\mathsf {U}}(x)$ in terms of $a_{\mathsf {U}}(x,1)$ and its derivative at $u=1$:

$$\begin{aligned} A_{\mathsf {U}}(x)&=\exp \big (\sum _{r=1}^{\infty } \frac{1}{r} \big (A_{\mathsf {R}}(x^r)+A_{\mathsf {M}}(x^r)+A_{\mathsf {U}}(x^r)+x^r\big )\big )\nonumber \\&\quad \times \, \big (\sum _{r=1}^{\infty } (A_{\mathsf {R}}(x^r)+A_{\mathsf {M}}(x^r)+A_{\mathsf {U}}(x^r)+x^r)\big )\nonumber \\&\quad -(A_{\mathsf {R}}(x)+A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+x)-2{{\mathrm{\mathrm{Mul}}}}_{ 2}(A_{\mathsf {M}}(x)+A_{\mathsf {R}}(x)+A_{\mathsf {U}}(x)+x)\nonumber \\&\quad -2\exp \big (\sum _{r=1}^{\infty } \frac{1}{r} \big (A_{\mathsf {R}}(x^r)+A_{\mathsf {M}}(x^r)+A_{\mathsf {U}}(x^r)+x^r\big )\big )+\nonumber \\&\quad +2+2(A_{\mathsf {R}}(x)+A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+x)+2{{\mathrm{\mathrm{Mul}}}}_{ 2}(A_{\mathsf {M}}(x)+A_{\mathsf {R}}(x)+A_{\mathsf {U}}(x)+x). \end{aligned}$$

(7)

Hence, we have three equations relating $A_{\mathsf {R}}(x)$, $A_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)$.

4.2 Application of the Dissymmetry Theorem

We now proceed by applying the Dissymmetry Theorem for trees (see Sect. 2.2) in order to express $\mathsf {UMR}$-trees in terms of rooted ones. Let T(x) be the generating function of $\mathsf {UMR}$-trees, where x marks legs. Write $T_{v}(x)$, $T_e(x)$, and $T_d(x)$ the generating functions associated to families of $\mathsf {UMR}$-trees with a rooted vertex, a rooted edge and a rooted and oriented edge, respectively. By the Dissymmetry Theorem for trees stated in (1), we have that

$$\begin{aligned} T(x)=T_{v}(x)+T_e(x)-T_d(x). \end{aligned}$$

(8)

Let us compute each generating function in terms of the pointed families obtained in Sect. 4.1. Let us start with $T_e(x)$. This can be written as

$$\begin{aligned} T_e(x)=T_{\mathsf {M}-\mathsf {R}}(x)+T_{\mathsf {M}-\mathsf {U}}(x)+T_{\mathsf {M}-\bullet }(x)+T_{\mathsf {R}-\mathsf {U}}(x)+T_{\mathsf {R}-\bullet }(x)+T_{\mathsf {U}-\mathsf {U}}(x)+T_{\mathsf {U}-\bullet }(x), \end{aligned}$$

where the index of each term shows the type of the end vertices of the rooted edge (for instance, the first term $\mathsf {R}{-}\mathsf {M}$ means that the rooted edge has as end vertices a $\mathsf {R}$-vertex and a $\mathsf {M}$-vertex). By cutting the rooted edge and pasting two virtual legs on the ends (see Fig. 7), each term in the sum (with the exception of $T_{\mathsf {U}-\mathsf {U}}(x)$, which has an additional symmetry) is the product of the corresponding generating functions of pointed families.

Fig. 7

A $\mathsf {UMR}$-tree rooted at an edge (colored red), and its decomposition in terms of pointed trees

The single situation where symmetry exists is in $T_{\mathsf {U}-\mathsf {U}}(x)$, and in this case we have a multiset of size 2 of trees pointed at a $\mathsf {U}$-vertex. We conclude that

$$\begin{aligned} T_e(x)= & {} A_{\mathsf {M}}(x)(A_{\mathsf {R}}(x)+A_{\mathsf {U}}(x)+A_l(x))+A_{\mathsf {R}}(x)(A_{\mathsf {U}}(x)+A_l(x))\nonumber \\&+{{\mathrm{\mathrm{Mul}}}}_2(A_{\mathsf {U}}(x))+A_l(x)A_{\mathsf {U}}(x). \end{aligned}$$

(9)

A decomposition similar to the one of  (9) applies for $T_d(x)$. Indeed this generating function can be written as

$$\begin{aligned} T_d(x)= & {} T_{\mathsf {M}\rightarrow \mathsf {R}}(x)+T_{\mathsf {M}\rightarrow \mathsf {U}}(x)+T_{\mathsf {M}\rightarrow \bullet }(x)\\&+\,T_{\mathsf {R}\rightarrow \mathsf {M}}(x)+T_{\mathsf {R}\rightarrow \mathsf {U}}(x)+T_{\mathsf {R}\rightarrow \bullet }(x)\\&+\,T_{\mathsf {U}\rightarrow \mathsf {M}}(x)+T_{\mathsf {U}\rightarrow \mathsf {R}}(x)+T_{\mathsf {U}\rightarrow \mathsf {U}}(x)+T_{\mathsf {U}\rightarrow \bullet }(x)\\&+\,T_{\bullet \rightarrow \mathsf {M}}(x)+T_{\bullet \rightarrow \mathsf {R}}(x)+T_{\bullet \rightarrow \mathsf {U}}(x), \end{aligned}$$

where the index of each term shows the type of the end vertices for the rooted directed edge. In this situation the computations are similar and even easier, because there is no extra symmetry when dealing with an edge linking two $\mathsf {U}$-vertices:

$$\begin{aligned} T_d(x)= & {} A_{M}(x)(A_{R}(x)+A_{U}(x)+A_l(x))\nonumber \\&+\, A_{R}(x)(A_{M}(x)+A_{U}(x)+A_l(x))\nonumber \\&+\,A_{U}(x)(A_{M}(x)+A_{R}(x)+A_{U}(x)+A_l(x))\nonumber \\&+\,A_l(x)(A_{R}(x)+A_{M}(x)+A_{U}(x)). \end{aligned}$$

(10)

The last generating function we want to get is $T_v(x).$ Observe that $T_v(x)$ is not the sum of the generating functions obtained in Sect. 4.1, because now we do not have to consider the virtual leg. We write

$$\begin{aligned} T_v(x)=T_\mathsf {R}(x)+T_\mathsf {M}(x)+T_\mathsf {U}(x)+T_{\bullet }(x), \end{aligned}$$

(11)

where the index of each term indicates the type of the rooted vertex. We want to express now each term by means of the previous pointed families. It is obvious that

$$\begin{aligned} T_{\bullet }(x)=A_l(x)(A_\mathsf {R}(x)+A_\mathsf {M}(x)+A_\mathsf {U}(x)) \end{aligned}$$

(12)

because a rooted leg induces canonically a rooted edge. Let us consider the other situations: observe that $T_\mathsf {R}(x)={{\mathrm{\mathrm{Mul}}}}_{\ge 3} (A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x))$, which is obtained by cutting the edges incident with the rooted $\mathsf {R}$-vertex, and pasting a virtual leg to each resulting subtree. In particular

$$\begin{aligned} T_\mathsf {R}(x)&={{\mathrm{\mathrm{Mul}}}}_{\ge 3} (A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x))\nonumber \\&={{\mathrm{\mathrm{Mul}}}}_{\ge 2} (A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x))-{{\mathrm{\mathrm{Mul}}}}_{2} (A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x))\nonumber \\&=A_{\mathsf {R}}(x)-{{\mathrm{\mathrm{Mul}}}}_{2} (A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x)) \end{aligned}$$

(13)

and, mutatis mutandis, an analogous expression holds for $T_\mathsf {M}(x)$. At last, let us study $T_\mathsf {U}(x)$: let $t_{\mathsf {U}}(x,u)$ be the generating function of trees with a rooted $\mathsf {U}$-vertex, where the multiplicity of the rooted vertex is not encoded yet and u encodes the degree of the rooted $\mathsf {U}$-vertex. Then, $t_{\mathsf {U}}(x,u)= {{\mathrm{\mathrm{Mul}}}}_{\ge 4}(u(A_{\mathsf {R}}(x)+A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x)))$ and

$$\begin{aligned} t_{\mathsf {U}}(x,u)=\sum _{n,d\ge 4}t_{n,d}x^n u^d \quad \Longrightarrow \quad T_{\mathsf {U}}(x)&= \sum _{n,d\ge 4}(d-3) t_{n,d}x^n u^d|_{u=1}\\&=\frac{\partial }{\partial u}t_{\mathsf {U}}(x,u)|_{u=1}- 3t_{\mathsf {U}}(x,1). \end{aligned}$$

Applying the same trick we used for $a_{\mathsf {U}}(x,u)$ in Sect. 4.1, we get that

$$\begin{aligned} T_{\mathsf {U}}(x)&= \frac{\partial }{\partial u}t_{\mathsf {U}}(x,u)|_{u=1}- 3t_{\mathsf {U}}(x,1)\nonumber \\&= \big (\frac{\partial }{\partial u}-3\big ) (a_{\mathsf {U}}(x,u)-u^3 {{\mathrm{\mathrm{Mul}}}}_{3}(A_{\mathsf {R}}(x)+A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x)))|_{u=1}\nonumber \\&= A_{\mathsf {U}}(x)-a_{\mathsf {U}}(x,1)+(3-3){{\mathrm{\mathrm{Mul}}}}_{3}(A_{\mathsf {R}}(x)+A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x)))\nonumber \\&=A_{\mathsf {U}}(x)-{{\mathrm{\mathrm{Mul}}}}_{\ge 3}(A_{\mathsf {R}}(x)+A_{\mathsf {M}}(x)+A_{\mathsf {U}}(x)+A_l(x))). \end{aligned}$$

(14)

Substituting (12), (13) and (14) in (11) we get the expression for $T_{v}(x)$. Finally, we replace (9), (10) and this expression of $T_v(x)$ in (8). All together this brings us the generating function T(x), whose first coefficients are $2x^3+4x^4+10x^5+27x^6+78x^7+246x^8+818x^9+2871x^{10}+10446x^{11}+39358x^{12}+\cdots$

4.3 Asymptotic Analysis

Now we can apply the machinery arising from analytic combinatorics in order to get asymptotic estimates for $[x^n]T(x)$. The main point is based on studying the system of equations which defines $A_{\mathsf {R}}(x), A_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)$, which provides the position and the nature of the dominant singularity of T(x).

In particular, by means of the Drmota–Lalley–Woods methodology (see Sect. 2.3), we obtain the constant growth, which is $\rho ^{-1}\approx 4.88052854$ (whose inverse $\rho \approx 0.20489584$ gives the radius of convergence around the origin of the generating function). Possibly more important, we can show that all these generating functions have the same square-root singularity (see the details in the proof). Moreover, the generating function T(x) is an analytic expression of the previous counting formulas, hence the position of the singularity does not change. However, the type of the singularity changes due to a combinatorial cancellation arising from the Dissymmetry Theorem for trees applied to $\mathsf {UMR}$-trees. Finally, the asymptotic estimates for the coefficients of T(x) are deduced by means of the Transfer Theorem for singularity analysis (see Theorem 2.5).

Before presenting the proofs, it is worth comparing the growth constant we get with the one arising in the context of unlabelled 2-connected series-parallel graphs, which is the analogue in the graphical setting. In [8] it is proven that the number of unlabelled 2-connected series-parallel graphs with n vertices grows exponentially as $\gamma ^{-n}$, where $\gamma \approx 0.12419991$ (and $\gamma ^{-1}\approx 8.05153567$). Despite several similarities, there are few caveats that we have to keep into account:

• (i) Matroids do not have a vertex structure; instead we count them by the number of elements in the ground set, which will also pay off when relating our results to the enumeration of 2-level base polytopes

• (ii) The tree decompositions of series-parallel graphs have only $\mathsf {R}$-vertices and $\mathsf {M}$-vertices. General 2-level matroids are constructed using also the $\mathsf {U}$-vertices, that is, a much wider variety of building blocks.

• (iii) Series-parallel graphs with different graph realizations can correspond to isomorphic matroids and must be counted only once in the matroid setting.

The first result deals with the singular behaviour of $A_{\mathsf {R}}(x), A_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)$:

Proposition 4.1

The generating functions $A_{\mathsf {R}}(x), A_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)$ have a dominant singularity at $\rho \approx 0.20489584$. Additionally, this is the unique singularity in the region $\{x\in \mathbb {C}: |x|\le \rho \}$. In a domain dented at $\rho$, $A_{\mathsf {R}}(x)$, $A_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)$ have a singular expansion of the form

$$\begin{aligned} A_{\mathsf {R}}(X)=A_{\mathsf {M}}(X) =&\,\, A_0+A_1X+A_2X^2+A_3X^3+O(X^4), \\ A_{\mathsf {U}}(X) =&\,\, U_0+U_1X+U_2X^2+U_3X^3+O(X^4), \end{aligned}$$

where $X=\sqrt{1-x/\rho }$, $A_0\approx 0.13529174$, $A_1\approx -0.23137622$, $A_2\approx 0.04653888$, $A_3\approx 0.06281332$, $U_0\approx 0.06921673$, $U_1\approx -0.19340420$, $U_2\approx 0.15045323$ and $U_3\approx 0.01018058$.

Proof

As we know that $A_{\mathsf {R}}(x)=A_{\mathsf {M}}(x)$, we just need to analyze the pair of (4) and (7). Indeed if $A_{\mathsf {R}}(x)$ and $A_{\mathsf {U}}(x)$ have a unique singularity $\rho$, then the term

$$\begin{aligned} \exp \big (\sum _{r=2}^{\infty } \frac{1}{r} \big (A_{\mathsf {M}}(x^r)+A_{\mathsf {U}}(x^r)+A_l(x^r)\big )\big ). \end{aligned}$$

in  (4) is analytic at $x=\rho$ (similarly in (7)). Hence, we can approximate this term by its Taylor series (which can be computed by an iterative algorithm). As a result, we obtain a pair of functional equations in x, $A_{\mathsf {R}}(x)$, and $A_{\mathsf {U}}(x)$ satisfying the conditions of Theorem 2.6. Solving now the resulting system of 3 equations by means of Maple computations (namely, the two equations and the one associated to the jacobian matrix in (2)), we obtain the solution $x_0\approx 0.20489584$, $\widehat{A_{\mathsf {R}}}\approx 0.13529174$ and $\widehat{A_{\mathsf {U}}}\approx 0.06921673$. By Theorem 2.6 the position of the singularity of both $A_{\mathsf {R}}(x)$ and $A_{\mathsf {U}}(x)$ is located at $\rho =x_0\approx 0.20489584$, and both $A_{\mathsf {R}}(x)$ and $A_{\mathsf {U}}(x)$ have a square-root expansion in a domain dented at $\rho$ of the form

$$\begin{aligned} A_{\mathsf {R}}(X)=A_{\mathsf {M}}(X) =&\,\, A_0+A_1X+A_2X^2+A_3X^3+O(X^4), \\ A_{\mathsf {U}}(X) =&\,\, U_0+U_1X+U_2X^2+U_3X^3+O(X^4), \end{aligned}$$

where $A_i,\,U_i$, $i\in \{1,2,3,4\}$, are computable constants. In order to get approximate values of these constants, we substitute the square-root expansions of $A_{\mathsf {M}}(x)=A_{\mathsf {R}}(x)$ and $A_{\mathsf {U}}(x)$ in (4) and (7). The terms of the form $A_{\mathsf {M}}(x^r)=A_{\mathsf {R}}(x^r)$ and $A_{\mathsf {U}}(x^r)$ ($r\ge 2$) are also approximated by a truncation of the Taylor series (which can also be computed by an iterative algorithm), because these GFs are analytic at the point $x=\rho$. At this point we can get a system of equations in the $A_i$’s and the $U_i$’s by equating the coefficients with same degree of the square-root expansions. Solving this system yields the constants reported in the statement of the theorem. $\square$

More precisely, we get the following result for $[x^n]T(x)$:

Theorem 4.2

The following asymptotic estimate holds:

$$\begin{aligned}{}[x^n]T(x)=C\cdot n^{-5/2}\cdot \rho ^{-n}\,\,(1+o(1)), \end{aligned}$$

where $C\approx 0.07583455$ and $\rho \approx 0.20489584$ are computable constants.

Proof

We use the singular square-root expansions for $A_{\mathsf {R}}(x)$, $A_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)$ obtained in Lemma 4.1, together with the expressions in (8)–(14) in order to get the singular expansion of T(x):

$$\begin{aligned} T(x)=T_0+T_2 X^2+T_3 X^3 +O(X^4), \end{aligned}$$

with $T_0\approx 0.03457946$, $T_2\approx -0.18596384$ and $T_3\approx 0.17921766$. Observe that the constant multiplying X in this singular expansion is equal to 0 (due to the unrooting process in the Dissymmetry Theorem for trees). Finally we apply the Transfer Theorem for singularity analysis over this singular expansion. $\square$

4.4 Dealing with Duality. Proof of Theorem 1.1

The last part is devoted to show that the contribution of self-dual 2-level matroids is exponentially small compared to the estimates we obtained in the previous subsection. Let $\mathcal {M}$ be a matroid with tree decomposition $T_\mathcal {M}$, then Proposition 3.5 implies that the tree decomposition of $\mathcal {M}^*$ has the same tree structure of $T_\mathcal {M}$. Moreover, we replace each vertex label $\mathcal {N}_i$ with its dual matroid $\mathcal {N}_i^*$.

We are interested in self-dual 2-connected 2-level matroids. The vertex labels are chosen among uniform matroids, and the operation of duality turns labels of type $\mathsf {M}_n$ into labels of type $\mathsf {R}_n$ and vice versa, and $U_{n,k}$-labels into $U_{n,n{-}k}$-labels. It is clear that the self-dual labels are of the form $U_{2n,n}$. Moreover, for technical reasons, we consider also virtual legs and legs to be self-dual.

Our goal is to estimate the contribution of the family of self-dual $\mathsf {UMR}$-trees (namely $\mathsf {UMR}$-trees associated to self-dual matroids) to the total number of $\mathsf {UMR}$-trees. To do that we start analyzing the pointed situation: we write $A_{\mathsf {R}}(x)=S_{\mathsf {R}}(x)+N_{\mathsf {R}}(x)$, $A_{\mathsf {M}}(x)=S_{\mathsf {M}}(x)+N_{\mathsf {M}}(x)$ and $A_{\mathsf {U}}(x)=S_{\mathsf {U}}(x)+N_{\mathsf {U}}(x)$, where the generating functions $S_{\mathsf {R}}(x),\,S_{\mathsf {M}}(x)$ and $S_{\mathsf {U}}(x)$ encode self-dual trees whose pointed vertex is a $\mathsf {R}$-vertex, an $\mathsf {M}$-vertex and an $\mathsf {U}$-vertex, respectively. The generating functions $N_{\mathsf {R}}(x),\,N_{\mathsf {M}}(x)$ and $N_{\mathsf {U}}(x)$ are the ones encoding trees which are not self-dual. Observe that in particular $S_{\mathsf {R}}(x)=S_{\mathsf {M}}(x)=0$, because the dual of each $\mathsf {R}$-vertex is an $\mathsf {M}$-vertex, and consequently there are no self-dual trees pointed at either a $\mathsf {R}$-vertex or a $\mathsf {M}$-vertex.

We also use a similar notation for unrooted trees. We write $T(x)=S(x)+N(x)$, where S(x) is the generating function associated to self-dual (unrooted) trees.

The next lemma tells us that the contribution of self-dual rooted trees is exponentially small.

Lemma 4.3

The following estimate holds:

$$\begin{aligned}{}[x^n]S_{\mathsf {U}}(x)= o([x^n]A_{\mathsf {U}}(x)). \end{aligned}$$

Proof

We get and analyze equations for $S_{\mathsf {U}}(x)$. In this situation, the pointed vertex is a $\mathsf {U}$-vertex associated to a uniform matroid of the form $U_{2n,n}$. Hence, we notice that the degree of the pointed vertex determines the rank and, in particular, the multiplicity in the counting is 1. Moreover, the possible restricted degree of the vertex is clearly in the set $\Lambda =\{3,5,7,\dots \}$.

Now observe that the collection of pending pointed subtrees is a multiset of pairs of pointed trees such that one is the dual of the second, followed by a multiset of odd size of self-dual pointed trees. Hence,

$$\begin{aligned} S_{\mathsf {U}}(x)&= {{\mathrm{\mathrm{Mul}}}}_{\{3,5,7,\dots \}}(S_{\mathsf {U}}(x)+A_l(x))\nonumber \\&\quad +{{\mathrm{\mathrm{Mul}}}}_{\ge 1}(A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+(A_{\mathsf {U}}(x^2)-S_{\mathsf {U}}(x^2)))\nonumber \\&\quad {{\mathrm{\mathrm{Mul}}}}_{\{1,3,5,7,\dots \}}(S_{\mathsf {U}}(x)+A_l(x)). \end{aligned}$$

(15)

Let $\eta$ be the radius of convergence of $S_U(x)$. It is obvious that $\eta \ge \rho$, because the family of self-dual pointed trees is counted in the family of $\mathsf {U}$-pointed trees. We need to show that $\eta > \rho$.

Equation (15) can be analyzed in a similar way to the one we find in the proof of Proposition 4.1. However, for our purposes it is enough to bound the coefficients of $S_{\mathsf {U}}(x)$ by means of crude estimates. Observe that ${{\mathrm{\mathrm{Mul}}}}_{\ge 3}(S_{\mathsf {U}}(x)+A_l(x)) \ge {{\mathrm{\mathrm{Mul}}}}_{\{3,5,7,\dots \}}(S_{\mathsf {U}}(x)+A_l(x))$ and

$$\begin{aligned}&{{\mathrm{\mathrm{Mul}}}}_{\ge 1}(A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+(A_{\mathsf {U}}(x^2)-S_{\mathsf {U}}(x^2))) {{\mathrm{\mathrm{Mul}}}}_{\ge 1}(S_{\mathsf {U}}(x)+A_l(x)) \\&\ge {{\mathrm{\mathrm{Mul}}}}_{\ge 1}(A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+(A_{\mathsf {U}}(x^2)-S_{\mathsf {U}}(x^2))) {{\mathrm{\mathrm{Mul}}}}_{\{1,3,5,7,\dots \}}(S_{\mathsf {U}}(x)+A_l(x)). \end{aligned}$$

Hence, if s(x) satisfies the equation

$$\begin{aligned} s(x)&= {{\mathrm{\mathrm{Mul}}}}_{\ge 3}(s(x)+A_l(x))+\,{{\mathrm{\mathrm{Mul}}}}_{\ge 1}(A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)\nonumber \\&\quad +N_{\mathsf {U}}(x^2)) {{\mathrm{\mathrm{Mul}}}}_{\ge 1}(s(x)+A_l(x)), \end{aligned}$$

(16)

then $S_{\mathsf {U}}(x) \le s(x)$. Observe also that by the combinatorial specification of $\mathsf {UMR}$-trees $s(x) \le A_{\mathsf {U}}(x)$. Let $\gamma$ be the dominant real singularity of s(x). Observe that this singularity arises either from the square-root singularity of the terms $A_{\mathsf {R}}(x^2)$, $A_{\mathsf {M}}(x^2)$, $N_{\mathsf {U}}(x^2)$ at x equals to $\sqrt{\rho } \approx 0.45265421$ or from a branch point (smaller than $\sqrt{\rho }$) of  (16).

In the second case, (16) can be written in the form $s(x)=F(x,s(x))$ after replacing all analytic terms by their truncated Taylor series. Any hypothetic branch point arises as a coalescence of the solutions $x\le \sqrt{\rho }$ of the pair of equations $s=F(x,s)$, $1=F_{s}(x,s)$. Since there is no such solution (these computations have been done with Maple by taking 30 coefficients in the Taylor series of $A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+N_{\mathsf {U}}(x^2)$), there is no branch point $\gamma$ strictly smaller than $\sqrt{\rho }$, and consequently the singularity of s(x) arises from the singularity of the term $A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+N_{\mathsf {U}}(x^2)$. To conclude, $[x^n]s(x)$ has exponential growth of order $\rho ^{-n/2}$, which is exponentially small compared with $\rho ^{-n}$. $\square$

Once we know that the number of self-dual pointed trees is exponentially small compared to the total number of pointed trees, we can prove that the number of self-dual $\mathsf {UMR}$-trees is also exponentially small compared to the total number of $\mathsf {UMR}$-trees.

Proposition 4.4

The following estimate hold:

$$\begin{aligned}{}[x^n]S(x)=o([x^n]T(x)). \end{aligned}$$

Proof

To prove the statement we obtain a generating function D(x) such that $S(x) \le D(x)$ and that $[x^n]D(x)=o([x^n]T(x))$. We split the class of self-dual trees by looking at the type of the center for each self-dual tree. The center of a connected graph is the set of vertices that minimize the maximal path-distance from other vertices in the graph. The center of a tree consists of a single vertex or two adjacent vertices (we say it is an edge).

Let us write $S(x)=S_{\circ }(x)+S_{\circ - \circ }(x)$, where $S_{\circ }(x)$ and $S_{\circ -\circ }(x)$ are the generating functions associated to self-dual trees whose center is a vertex and an edge, respectively. We analyze each case separately.

We start with self-dual trees whose center is a vertex. In this situation the center is necessarily a $\mathsf {U}$-vertex labelled by a matroid of type $U_{2n,n}$. In this case the degree of the pointed vertex determines the rank of the $\mathsf {U}$-vertex, which has to be counted with multiplicity one. Hence, we have the crude bound $S_{\circ }(x)\le {{\mathrm{\mathrm{Mul}}}}(A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+N_{\mathsf {U}}(x^2)) {{\mathrm{\mathrm{Mul}}}}(S_{\mathsf {U}}(x)+A_l(x))$, whose radius of convergence by Lemma 4.3 is strictly bigger than $\rho .$

Let us study now self-dual trees whose center is an edge. Consider the pair of pointed trees that arise when cutting the edge which plays the role of the center of the tree (and pasting a virtual leg). Two situations may happen:

• (1) Each tree is self-dual.

• (2) Each tree is non self-dual, but one is the dual of the other.

In both cases (1) and (2) we can easily find a bound and the sum of the upper bounds yields the function D(x). Namely, $S_U(x)^2$ and $A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+N_{\mathsf {U}}(x^2)$, respectively. Therefore $S_{\circ -\circ }(x)\le S_{\mathsf {U}}(x)^2+A_{\mathsf {R}}(x^2)+A_{\mathsf {M}}(x^2)+N_{\mathsf {U}}(x^2)$. Finally, again by Lemma 4.3, the radius of convergence of $S_{\circ -\circ }(x)$ is strictly bigger than $\rho$. Hence the result follows. $\square$

We can now prove that there are exponentially many 2-level polytopes coming from matroid base polytopes:

Proof of Theorem 1.1

Every 2-connected 2-level matroid $\mathcal {M}$ on n elements is, by definition, associated with a 2-level base polytope $P_{\mathcal {M}}$. The 2-connectedness implies that the dimension of the base polytope is $n{-}1$. By Theorem 2.3 there is only another matroid with congruent base polytope, namely $\mathcal {M}^*$.

Denote by $L_2(n)$ the number of 2-connected 2-level matroids and by $S_2(n)$ the number of self-dual ones. The number of non-congruent $(n{-}1)$-dimensional 2-level polytopes associated with such family is $\frac{L_2(n)+S_2(n)}{2}$. This yields a lower bound to the number of $(n{-}1)$-dimensional 2-level polytopes.

Applying the structural result of Sect. 3 and using the notation of Sect. 4.2 we easily see that $L_2(n)=[x^n]T(x)$ and $S_2(n)=[x^n]S(x)$. We do not have closed formulas for the coefficients of the generating functions, but nevertheless we are able to provide asymptotic estimates: by Theorem 4.2 the number of $\mathsf {UMR}$-trees is asymptotically equal to $C\cdot n^{-5/2}\cdot \rho ^{-n}\,\,(1+o(1)),$ where $C\approx 0.07583455$ and $\rho \approx 0.20489584$ are computable constants. Due to Proposition 4.4, the contribution of self-dual $\mathsf {UMR}$-trees to this asymptotic is exponentially small. Hence, the number of non self-dual $\mathsf {UMR}$-trees is asymptotically equal to the whole number of $\mathsf {UMR}$-trees. Finally, the number of $\mathsf {UMR}$-trees up to the duality relation is half of this value plus the number of self-dual $\mathsf {UMR}$-trees. So, Theorem 1.1 holds by dividing the previous bound by 2. $\square$

To conclude, observe that we can use the singular expansion of T(x) in order to get asymptotic estimates for the number of 2-level matroids, including the non-connected ones. This family corresponds with the multiset construction applied over $\mathsf {UMR}$-trees (namely, forests). Hence, the generating function here is ${{\mathrm{\mathrm{Mul}}}}(T(x))=\exp \big (\sum _{r=1}^{\infty }\frac{1}{r}(T(x^r))\big )$. Observe that

$$\begin{aligned} \exp \big (\sum _{r=1}^{\infty }\frac{1}{r}(T(x^r))\big )=\exp (T(x))\exp \big (\sum _{r=2}^{\infty }\frac{1}{r}(T(x^r))\big ), \end{aligned}$$

and the second term is analytic at $x=\rho$. Hence, in a domain dented at $x=\rho$ the singular expansion of ${{\mathrm{\mathrm{Mul}}}}(T(x))$ is equal to:

$$\begin{aligned} {{\mathrm{\mathrm{Mul}}}}(T(x))=\exp (T_0+T_2 X^2+T_3 X^3+ O(X^4)) \exp \big (\sum _{r=2}^{\infty }\frac{1}{r}(T(\rho ^r))\big ), \end{aligned}$$

(see the singular expansion of T(x) in the proof of Theorem 4.2) which has the expression

$$\begin{aligned} {{\mathrm{\mathrm{Mul}}}}(T(x))=F_0+F_2 X^2+F_3X^3+O(X^4), \end{aligned}$$

with $F_0 \approx 1.03526853$, $F_2 \approx -0.19252251$, $F_3 \approx 0.18553841$. Applying now Theorem 2.5 we conclude that

$$\begin{aligned}{}[x^n]{{\mathrm{\mathrm{Mul}}}}(T(x)) = C' \cdot n^{-5/2} \cdot \rho ^{-n} (1+o(1)), \end{aligned}$$

with $C' \approx 0.07850913$. Observe that the constant $C'$ is slightly bigger than the constant obtained in the asymptotic estimate for $\mathsf {UMR}$-trees.