Guest post by June Huh

I will write about a common algebraic structure hidden behind seemingly distant objects: convex polytopes, Kähler manifolds, projective varieties, and lastly, matroids. Let $n$ be a positive integer.

1. Polytopes

1.1

A polytope in $\mathbb{R}^n$ is the convex hull of a finite subset of $\mathbb{R}^n$. Let’s write $\Pi$ for the abelian group with generators $[P]$, one for each polytope $P \subseteq \mathbb{R}^n$, which satisfy the following relations:

1. $[P_1 \cup P_2]+[P_1 \cap P_2]=[P_1]+[P_2]$ whenever $P_1 \cup P_2$ is a polytope,
2. $[P+t]=[P]$ for every point $t$ in $\mathbb{R}^n$, and
3. $[\varnothing]=0$.

This is the polytope algebra of McMullen [McM89]. The multiplication in $\Pi$ is defined by the Minkowski sum
\[
[P_1] \cdot [P_2]=[P_1+P_2],
\]
and this makes $\Pi$ a commutative ring with $1=[\text{point}]$ and $0=[\varnothing]$.

The structure of $\Pi$ can be glimpsed through some familiar translation invariant measures on the set of polytopes. For example, the Euler characteristic shows that there is a surjective ring homomorphism
\[
\chi:\Pi \longrightarrow \mathbb{Z}, \qquad [P] \longmapsto \chi(P),
\]
and the Lebesgue measure on $\mathbb{R}^n$ shows that there is a surjective group homomorphism
\[
\text{Vol}:\Pi \longrightarrow \mathbb{R}, \qquad [P] \longmapsto \text{Vol}(P).
\]
A fundamental observation is that some power of $[P]-1$ is zero in $\Pi$ for every nonempty polytope $P$. Since every polytope can be triangulated, it is enough to check this when the polytope is a simplex. In this case, a picture drawing for $n=0,1,2,$ and if necessary $3$, will convince the reader that
\[
([P]-1)^{n+1}=0.
\]
The kernel of the Euler characteristic $\chi$ turns out to be torsion free and divisible. Thus we may speak about the logarithm of a polytope in $\Pi$ which satisfies the usual rule
\[
\text{log}[P_1+P_2]=\text{log}[P_1]
+\text{log}[P_2].
\]
The notion of logarithm leads to a remarkable identity concerning volumes of convex polytopes.

Theorem
Writing $\texttt{p}$ for the logarithm of $[P]$, we have
\[
\text{Vol}(P)=\frac{1}{n!}\text{Vol} (\texttt{p}^n).
\]

This shows that, more generally, Minkowski’s mixed volume of polytopes $P_1,\ldots,P_n$ can be expressed in terms of the product of the corresponding logarithms $\texttt{p}_1,\ldots,\texttt{p}_n$:
\[
\text{Vol}(P_1,\ldots,P_n)=\frac{1}{n!} \text{Vol}(\texttt{p}_1 \cdots \texttt{p}_n).
\]

1.2

Let’s write $P_1 \preceq P_2$ to mean that $P_1$ is a Minkowski summand of some positive multiple of $P_2$. This relation is clearly transitive. We way that $P_1$ and $P_2$ are equivalent when
\[
P_1 \preceq P_2 \preceq P_1.
\]
Let $\mathscr{K}(P)$ be the set of all polytopes equivalent to a given polytope $P$. The collection $\mathscr{K}(P)$ is a convex cone in the sense that
\[
P_1, P_2 \in \mathscr{K}(P) \Longrightarrow \lambda_1 P_1 + \lambda_2 P_2 \in \mathscr{K}(P) \ \ \text{for positive real numbers $\lambda_1, \lambda_2$.}
\]
We will meet an analogue of this convex cone in each of the following sections.

Definition
For each positive integer $q$, let $\Pi^q(P) \subseteq \Pi$ be the subgroup generated by all elements of the form
\[
\texttt{p}_1\texttt{p}_2 \cdots \texttt{p}_q,
\]
where $\texttt{p}_i$ is the logarithm of a polytope in $\mathscr{K}(P)$.

Note that any two equivalent polytopes define the same set of subgroups of $\Pi$. These subgroups are related to each other in a surprising way when $P$ is an $n$-dimensional simple polytope; this means that every vertex of the polytope is contained in exactly $n$ edges.

Theorem [McM93]
Let $\texttt{p}$ be the logarithm of a simple polytope in $\mathscr{K}(P)$, and let $1 \le q \le \frac{n}{2}$.

1. Hard Lefschetz theorem: The multiplication by $\texttt{p}^{n-2q}$ defines an isomorphism
   \[
   \Pi^{q}(P) \longrightarrow \Pi^{n-q}(P), \quad x \longmapsto \texttt{p}^{n-2q} x.
   \]
2. Hodge-Riemann relations: The multiplication by $\texttt{p}^{n-2q}$ defines a symmetric bilinear form
   \[
   \Pi^{q}(P) \times \Pi^{q}(P) \longrightarrow \mathbb{R}, \quad (x_1,x_2) \longmapsto (-1)^q \ \text{Vol}\big(\texttt{p}^{n-2q} x_1 x_2\big)
   \]
   that is positive definite when restricted to the kernel of the multiplication by $\texttt{p}^{n-2q+1}$.

In fact, the group $\Pi^q(P)$ can be equipped with the structure of a finite dimensional real vector space in a certain natural way, and the isomorphism between groups in the first part of the theorem turns out to be an isomorphism between vector spaces.

I will mention two concrete implications of geometric-combinatorial nature, one for each of the above two statements.

1. The first statement is the main ingredient in the proof of the $g$-conjecture for simple polytopes [Stan80]. This gives a numerical characterization of sequences of the form
   \[
   f_0(P),f_1(P),\ldots,f_n(P),
   \]
   where $f_i(P)$ is the number of $i$-dimensional faces of an $n$-dimensional simple polytope $P$.
2. The second statement, in the special case $q=1$, is essentially equivalent to the Aleksandrov-Fenchel inequality on mixed volumes of convex bodies:
   \[
   \text{Vol}(\texttt{p}_1\texttt{p}_1 \texttt{p}_3 \cdots \texttt{p}_n) \text{Vol}(\texttt{p}_2\texttt{p}_2 \texttt{p}_3 \cdots \texttt{p}_n) \le \text{Vol}(\texttt{p}_1\texttt{p}_2 \texttt{p}_3 \cdots \texttt{p}_n)^2.
   \]
   The inequality played a central role in the proof of the van der Waerden conjecture that the permanent of any doubly stochastic $n \times n$ nonnegative matrix is at least $n!/n^n$. An interesting account on the formulation and the solution of the conjecture can be found in [vLin82].

With suitable modifications, the hard Lefschetz theorem and the Hodge-Riemann relations can be extended to polytopes that are not necessarily simple [Karu04].

2. Kähler manifolds

2.1

Let $\omega$ be a Kähler form on an $n$-dimensional compact complex manifold $M$. This means that $\omega$ is a smooth differential $2$-form on $M$ that can be written locally in coordinate charts as
\[
i \partial \overline{\partial} f
\]
for some smooth real functions $f$ whose complex Hessian matrix $\Big[\frac{\partial^2 f}{\partial z_i\partial \overline{z}_j}\Big]$ is positive definite; here $z_1,\ldots,z_n$ are holomorphic coordinates and $\partial$, $\overline{\partial}$ are the differential operators
\[
\partial=\sum_{k=1}^n \frac{\partial}{\partial z_k} dz_k, \qquad \overline{\partial}=\sum_{k=1}^n \frac{\partial}{\partial \overline{z}_k} d\overline{z}_k.
\]
Like all other good definitions, the Kähler condition has many other equivalent characterizations, and we have chosen the one that emphasizes the analogy with the notion of convexity.

To a Kähler form $\omega$ on $M$, we can associate a Riemannian metric $g$ on $M$ by setting
\[
g(u,v)=w(u,Iv),
\]
where $I$ is the operator on tangent vectors of $M$ that corresponds to the multiplication by $i$. Thus we may speak of the length, area, etc., on $M$ with respect to $\omega$.

Theorem
The volume of $M$ is given by the integral
\[
\text{Vol}(M)=\frac{1}{n!} \int_M w^n.
\]
More generally, the volume of a $d$-dimensional complex submanifold $N \subseteq M$ is given by
\[
\text{Vol}(N)=\frac{1}{d!} \int_N w^d.
\]

Compare the corresponding statement of the previous section that $\text{Vol}(P)=\frac{1}{n!}\text{Vol} (\texttt{p}^n)$.

2.2

Let $\mathscr{K}(M)$ be the set of all Kähler forms on $M$. The collection $\mathscr{K}(M)$ is a convex cone in the sense that
\[
\omega_1, \omega_2 \in \mathscr{K}(M) \Longrightarrow \lambda_1 \omega_1 + \lambda_2 \omega_2 \in \mathscr{K}(M) \ \ \text{for positive real numbers $\lambda_1, \lambda_2$.}
\]
This follows from the fact that the sum of two positive definite matrices is positive definite.

Definition
For each nonnegative integer $q$, let $H^{q,q}(M) \subseteq H^{2q}(M,\mathbb{C})$ be the subset of all the cohomology classes of closed differential forms that can be written in local coordinate charts as
\[
\sum f_{k_1,\ldots,k_q,l_1,\ldots,l_q} dz_{k_1} \wedge \cdots \wedge dz_{k_q} \wedge d\overline{z}_{l_1} \wedge \cdots \wedge d\overline{z}_{l_q}.
\]

Note that the cohomology class of a Kähler form $\omega$ is in $H^{1,1}(M)$, and that
\[
[\varphi] \in H^{q,q}(M) \Longrightarrow [\omega \wedge \varphi] \in H^{q+1,q+1}(M).
\]

Theorem (Classical)
Let $\omega$ be an element of $\mathscr{K}(M)$, and let $q$ be a nonnegative integer $\le \frac{n}{2}$.

1. Hard Lefschetz theorem: The wedge product with $\omega^{n-2q}$ defines an isomorphism
   \[
   H^{q,q}(M) \longrightarrow H^{n-q,n-q}(M), \quad [\varphi] \longmapsto [\omega^{n-2q} \wedge \varphi].
   \]
2. Hodge-Riemann relations: The wedge product with $\omega^{n-2q}$ defines a Hermitian form
   \[
   H^{q,q}(M) \times H^{q,q}(M) \longrightarrow \mathbb{C}, \quad (\varphi_1,\varphi_2) \longmapsto (-1)^q \int_M \omega^{n-2q} \wedge \varphi_1 \wedge \overline{\varphi_2}
   \]
   that is positive definite when restricted to the kernel of the wedge product with $\omega^{n-2q+1}$.

Analogous statements hold for $H^{q_1,q_2}(M)$ with $q_1 \neq q_2$, and these provide a way to show that certain compact complex manifolds cannot admit any Kähler form. For deeper applications, see [Voi10].

3. Projective varieties

3.1

Let $k$ be an algebraically closed field, and let $\mathbb{P}^m$ be the $m$-dimensional projective space over $k$. A projective variety over $k$ is a subset of the form
\[
X=\{h_1=h_2=\ldots=h_k=0\} \subseteq \mathbb{P}^m,
\]
where $h_i$ are homogeneous polynomials in $m+1$ variables. One can define the dimension, connectedness, and smoothness of projective varieties in a way that is compatible with our intuition when $k=\mathbb{C}$. One can also define what it means for a map between two projective varieties, each living in two possibly different ambient projective spaces, to be algebraic.

Let $K$ be another field, not necessarily algebraically closed but of characteristic zero. A Weil cohomology theory with coefficients in $K$ is an assignment
\[
X \longmapsto H^*(X)=\bigoplus_k H^k(X),
\]
where $X$ is a smooth and connected projective variety over $k$ and $H^*(X)$ is a graded-commutative algebra over $K$. This assignment is required to satisfy certain rules similar to those satisfied by the singular cohomology of compact complex manifolds, such as functoriality, finite dimensionality, Poincar&eacute duality, K&uumlnneth formula, etc. For this reason the product of two elements in $H^*(X)$ will be written
\[
\xi_1 \cup \xi_2 \in H^*(X).
\]
For algebraic geometers, the most important of the rules is that to every codimension $q$ subvariety $Y \subseteq X$ there be a corresponding cohomology class
\[
\text{cl}(Y) \in H^{2q}(X).
\]
These classes should have the property that, for example,
\[
\text{cl}(Y_1 \cap Y_2)=\text{cl}(Y_1) \cup \text{cl}(Y_2)
\]
whenever $Y_1$ and $Y_2$ are subvarieties intersecting transversely, and that
\[
\text{cl}(H_1)=\text{cl}(H_2)
\]
whenever $H_1$ and $H_2$ are two hyperplane sections of $X \subseteq \mathbb{P}^m$. Though not easy, it is possible to construct a Weil cohomology theory for any $k$ for some $K$. For example, when both $k$ and $K$ are the field of complex numbers, one can take the de Rham cohomology of smooth differential forms.

Definition
For each nonnegative integer $q$, let $A^q(X) \subseteq H^{2q}(X)$ be the set of rational linear combinations of cohomology classes of codimension $q$ subvarieties of $X$.

One of the rules for $H^*(X)$ implies that, if $n$ is the dimension of $X$, there is an isomorphism
\[
\text{deg}: A^n(X) \longrightarrow \mathbb{Q}
\]
determined by the property that
\[
\text{deg}(\text{cl}(\text{p}))=1 \ \ \text{for every} \ \ \text{p} \in X.
\]
Writing $h$ for the class in $A^1(X)$ of any hyperplane section of $X \subseteq \mathbb{P}^m$, the degree of $X \subseteq \mathbb{P}^m$ satisfies the formula
\[
\text{deg}(X \subseteq \mathbb{P}^m)=\text{deg}(h^n),
\]
the number of points in the intersection of $X$ with a sufficiently general subspace $\mathbb{P}^{m-n} \subseteq \mathbb{P}^m$. Compare the corresponding statements of the previous sections
\[
\text{Vol}(P)=\frac{1}{n!}\text{Vol} (\texttt{p}^n) \quad \text{and} \quad \text{Vol}(M)=\frac{1}{n!} \int_M w^n.
\]

3.2

Let $\mathscr{K}(X)$ be the set of cohomology classes of hyperplane sections of $X$ under all possible embeddings of $X$ into projective spaces. Classical projective geometers knew that $\mathscr{K}(X)$ is a convex cone in a certain sense; if you are curious, read about the Segre embedding and the Veronese embedding.

Conjecture (Grothendieck)
Let $h$ be an element in $\mathscr{K}(X)$, and let $q$ be a nonnegative integer $\le n/2$.

1. Lefschetz standard: The multiplication by $h^{n-2q}$ defines an isomorphism
   \[
   A^q(X) \longrightarrow A^{n-q}(X), \quad \xi \longmapsto h^{n-2q} \cup \xi.
   \]
2. Hodge standard: The multiplication by $h^{n-2q}$ defines a symmetric bilinear form
   \[
   A^q(X) \times A^q(X) \longrightarrow \mathbb{Q}, \quad (\xi_1,\xi_2) \longmapsto (-1)^q \text{deg}\big(h^{n-2q} \cup \xi_1 \cup \xi_2\big),
   \]
   that is positive definite when restricted to the kernel of the cup product with $h^{n-2q+1}$.

The above statements are at the core of Grothendieck’s approach to Weil’s conjecture on zeta functions and other important problems in algebraic geometry [Gro69].

4. Matroids

4.1

As we know, a matroid $\mathrm{M}$ is given by a closure operator defined on all subsets of a finite set $E$ satisfying the Steinitz-MacLane exchange property:

For every subset $I$ of $E$ and every element $a$ not in the closure of $I$, if $a$ is in the closure of ${I \cup\{ b\}}$, then $b$ is in the closure of $I \cup \{a\}$.

It is remarkable that this single sentence leads to an intricate algebraic structure of the kind we have seen above. This structure reveals certain properties of matroids that are not easy to see by other means.

Let’s write $S_\mathrm{M}$ for the polynomial ring with real coefficients and variables $x_F$, one for each nonempty proper flat $F$ of $\mathrm{M}$.

Definition
The Chow ring of a loopless matroid $\mathrm{M}$ is defined to be the quotient
\[
A^*(\mathrm{M}):=S_\mathrm{M}/(I_\mathrm{M}+J_\mathrm{M}),
\]
where $I_\mathrm{M}$ is the ideal generated by the quadratic monomials
\[
x_{F_1}x_{F_2}, \ \ \text{$F_1$ and $F_2$ are two incomparable nonempty proper flats of $\mathrm{M}$,}
\]
and $J_\mathrm{M}$ is the ideal generated by the linear forms
\[
\sum_{i_1 \in F} x_F – \sum_{i_2 \in F} x_F, \ \ \text{$i_1$ and $i_2$ are distinct elements of the ground set $E$.}
\]
We write $A^q(\mathrm{M}) \subseteq A^*(\mathrm{M})$ for the subspace spanned by all degree $q$ monomials.

Let $n+1$ be the rank of $\mathrm{M}$. An important step is to identify the map analogous to the volume in section $1$, the integral in section $2$, and the degree in section $3$.

Theorem
There is an isomorphism $\text{deg}: A^n(\mathrm{M}) \longrightarrow \mathbb{R}$ uniquely determined by the property
\[
\text{deg}(x_{F_1}x_{F_2}\cdots x_{F_n})=1 \ \ \text{for every flag of nonempty proper flats} \ \ F_1 \subsetneq F_2 \subsetneq \cdots \subsetneq F_n.
\]

In particular, any two monomials corresponding to a complete flag of nonempty proper flats are equal in the Chow ring of a loopless matroid.

4.2

What should be the convex cone $\mathscr{K}(\mathrm{M})$? In fact, there is a certain piecewise linear space associated to $\mathrm{M}$, the tropical linear space of $\mathrm{M}$, and one takes $\mathscr{K}(\mathrm{M})$ to be the set of all strictly convex piecewise linear functions on the tropical linear space. For known applications, the following more restrictive definition is sufficient.

Definition
A function $c$ on the set of nonempty proper subsets of $E$ is said to be strictly submodular if
\[
c_{I_1}+c_{I_2} > c_{I_1 \cap I_2} +c_{I_1 \cup I_2} \ \ \text{for any two incomparable subsets $I_1,I_2 \subseteq E$,}
\]
where we replace $c_\varnothing$ and $c_E$ by zero whenever they appear in the above inequality.

A strictly submodular function $c$ defines an element
\[
\ell(c):= \sum_F c_F x_F\in A^1(\mathrm{M}),
\]
where the sum is over all nonempty proper flats of $\mathrm{M}$; the set of all such is a convex cone in the obvious sense. Note that the rank function of any matroid on $E$ can be obtained as a limit of strictly submodular functions.

Theorem [AHK]
Let $\ell$ be an element of $A^1(\mathrm{M})$ associated to a strictly submodular function, and let $q$ be a nonnegative integer $\le \frac{n}{2}$.

1. Hard Lefschetz theorem: The multiplication by $\ell^{n-2q}$ defines an isomorphism
   \[
   A^q(\mathrm{M}) \longrightarrow A^{n-q}(\mathrm{M}), \qquad a \longmapsto \ell^{n-2q} \ a.
   \]
2. Hodge-Riemann relations: The multiplication by $\ell^{n-2q}$ defines a symmetric bilinear form
   \[
   A^q(\mathrm{M}) \times A^q(\mathrm{M}) \longrightarrow \mathbb{R}, \qquad (a_1,a_2) \longmapsto (-1)^q \ \text{deg}(\ell^{n-2q}\ a_1 a_2)
   \]
   that is positive definite when restricted to the kernel of the multiplication by
   $\ell^{n-2q+1}$.

In fact, the theorem applies more generally to elements $\ell$ in the cone $\mathscr{K}(\mathrm{M})$ mentioned above. Below are two applications presented in [AHK], which use the Hodge-Riemann relations in the special case when $q=1$.

1. Let $w_k$ be the absolute value of the coefficient of $\lambda^{n-k+1}$ in the characteristic polynomial of $\mathrm{M}$. Then the sequence $w_k$ is log-concave:
   \[
   w_{k-1} w_{k+1} \le w_k^2 \ \ \text{for all $1 \le k\le n$.}
   \]
   In particular, the sequence $w_k$ is unimodal:
   \[
   w_0 \le w_1 \le \cdots \le w_l \ge \cdots \ge w_n \ge w_{n+1} \ \ \text{for some index $l$.}
   \]
   This verifies a conjecture of Heron, Rota, and Welsh.
2. Let $f_k$ be the number of independent subsets of $E$ with cardinality $k$. Then the sequence $f_k$ is log-concave:
   \[
   f_{k-1} f_{k+1} \le f_k^2 \ \ \text{for all $1 \le k \le n$.}
   \]
   In particular, the sequence $f_k$ is unimodal:
   \[
   f_0 \le f_1 \le \cdots \le f_l \ge \cdots \ge f_n \ge f_{n+1} \ \ \text{for some index $l$.}
   \]
   This verifies a conjecture of Mason and Welsh.

These applications only use the Hodge-Riemann relations for $q=1$ and for one carefully chosen $\ell$. The general Hodge-Riemann relations for all $\ell$ in $\mathscr{K}(\mathrm{M})$ may contain more interesting information on $\mathrm{M}$.

References

[AHK] Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, arXiv:1511.02888.

[Gro69] Alexander Grothendieck, Standard conjectures on algebraic cycles, 1969 Algebraic Geometry, 193-199, Oxford University Press.

[Karu04] Kalle Karu, Hard Lefschetz theorem for nonrational polytopes, Inventiones Mathematicae 157 (2004), 419-447.

[McM89] Peter McMullen, The polytope algebra, Advances in Mathematics 78 (1989), 76-130.

[McM93] Peter McMullen, On simple polytopes, Inventiones Mathematicae 113 (1993), 419-444.

[Stan80] Richard Stanley, The number of faces of a simplicial convex polytope, Advances in Mathematics 35 (1980), 236-238.

[vLin82] Jack van Lint, The van der Waerden conjecture: two proofs in one year, The Mathematical Intelligencer 4 (1982), 72-77.

[Voi10] Claire Voisin, On the cohomology of algebraic varieties, Proceedings of the International Congress of Mathematicians I, 476-503, New Delhi, 2010.

Guest post by Sandra Kingan

Growth rates are a popular topic on Matroid Union. Peter Nelson has written five posts on it: Growth Rates I, II, III, IV, V.  Irene Pivotto has also written a post on it.

Following James Oxley’s book [Oxley, 2012] , the growth rate function of a minor-closed class $\mathcal M$, denoted by $h_{\mathcal M}(r)$, is defined as the maximum number of elements in a simple rank-$r$ matroid in $\mathcal M$ if the number is finite and infinity otherwise (p. 570). A simple matroid is extremal in a minor-closed class $\mu$ of matroid if $M\in \mu$, but $\mu$ contains no simple single-element extension of $M$ that has the same rank as $M$ (p. 572).

For example, if $\mathcal M$ is the class of graphs, then the complete graph of rank-$r$ denoted by $K_{r+1}$, for $r\ge 1$ is the rank-$r$ extremal matroid. The growth rate function is the size of $K_{r+1}$ which is $\frac {r(r+1)}{2}$.  On the other hand if $\mathcal M$ is the subclass of planar graphs, then we don’t know precisely the extremal planar graphs, but we do know the growth rate function. A straightforward graph theoretic argument (found in any graph theory textbook) shows that the number of edges of a “maximal” planar graph is $3r-3$. (In graph theory a maximal planar graph is defined as one to which if you add one more edge it becomes non-planar.)

Similarly, if $\mathcal M$ is the class of binary matroids, then the rank-$r$ projective geometry $PG(r-1, 2)$, for $r\ge 2$, is the rank-$r$ extremal matroid. The growth rate function is the size of $PG(r-1, 2)$ which is $2^r-1$.

Within the class of binary matroids lies the class of cographic matroids (matroids whose duals are graphic). Again we don’t know precisely the extremal cographic matroids, but we can prove that the growth rate function is $3r-3$ (as shown by Joseph Kung and further explained further in Pivotto’s post). Also in her post is the growth rate of series-parallel networks. Series-parallel networks are formed by starting with a single edge or loop and repeatedly adding edges in parallel or edges in series (turning one edge into two edges by putting a vertex on the edge). The growth rate of series parallel networks is $2r+1$. See [Oxley Section 5.4] and [Oxley 1987, Section 3] for the explanation.

The first extremal result is generally attributed to Paul Turán. The class he considered was the class of graphs with no $K_{s+1}$-subgraph. (Mantel proved the $K_3$ case earlier.) Turán proved that the rank $r$ extremal graph is a specific type of complete s-partite graph (see Wikipedia). The growth rate function is $\frac{(s-1)(r+1)^2}{2s}$ [Turan, 1941].

With respect to the growth rate function we are keen on knowing if it is linear or a higher order polynomial like quadratic or exponential. See Nelson’s posts for detailed explanations on this.

In 1963 G. A. Dirac determined the graphs without two vertex disjoint cycles [Dirac, 1963]. Excluding two vertex-disjoint cycles in a 3-connected graph is equivalent to excluding the prism graph $(K_5\backslash e)^*$ as a minor. So essentially Dirac determined the 3-connected graphs with no prism minor. He found that the 3-connected members of this class are $K_5$, $K_5 \backslash e$, the infinite family of wheel graphs $W_r$, for $r\ge 4$, and $K_{3,p}$, $K’_{3,p} $, $K”_{3,p} $ or $K”’_{3,p}$, for some $p\ge 3$.

Theorem 1.  A simple $3$-connected graph has no minor isomorphic to $(K_5\backslash e)^*$ if and only if it is isomorphic to $W_r$ for some $r\ge 3$, $K_5$, $K_5 \backslash e$, $K_{3,p}$, $K’_{3,p} $, $K”_{3,p} $ or $K”’_{3,p}$, for some $p\ge 3$.

Observe that there are two very distinct 3-connected infinite families here: $W_r$ and $K_{3, p}”’$. The size of $W_r$ is $2r+1$ for $r\ge 3$ and the size of $K_{3, r-2}”’$ is $3r-3$ for $r\ge 5$. Both of these 3-connected infinite families are growing linearly. I’ve heard the word “monarchs” used to describe $W_r$ and $K_{3, p}”’$; I think Jack Edmonds used this term. Monarchs is a good word to describe them.

Matroids that are not 3-connected may be pieced together from 3-connected matroids using direct-sums and 2-sums [Oxley, 2012, 8.3.1]. This result was first proven by Bixby in 1972. This is a terrific decomposition result that allows us to focus on just the 3-connected matroids in the family. Thus if we know the 3-connected matroids we can build the 2-connected ones via the operation of two sums.

Now extremal matroid is defined as the simple rank-$r$ matroid of maximum size. So 2-sums and even direct sums are allowed. But when the class contains $W_r$ and $K_{3, r-2}”’$ with $W_r$ growing at rate $2r$ and $K_{3, r-2}”’$ growing at rate $3r-3$, the latter dominates any rank-$r$ graph that can be constructed from direct sum or 2-sum. The proof is straightforward case-checking. Thus the growth rate of the class of graphs with no prism minor is $3r-3$ and the rank-$r$ extremal matroid is $K_{3, r-2}”’$. Even if we were not able to say precisely what the growth rate is, once the 3-connected families are found, and found to be growing linearly, piecing together using direct sum and 2-sum will still give a linear growth rate.

Moving on let’s take a look at Oxley’s 1987 result where he determined the 3-connected matroids with no 4-wheel minor [Oxley, 1987]. The main theorem of that paper is Theorem 2.1 and the key component of the main theorem is Theorem 2.2 which is stated below. Let $Z_r$ denote the $(2r+1)$-element rank-$r$ binary spikes. They are non-regular matroids represented by the binary matrix $[I_r| D]$ where $D$ has $r+1$ columns labeled $b_1, \dots b_r, c_r$. The first $r$ columns in $D$ have zeros along the diagonal and ones elsewhere. The last column is all ones.

Theorem 2. A 3-connected binary non-regular matroid has no minor isomorphic to $P_9$ or ${P_9}^*$ if and only if it is isomorphic to $F_7$, ${F_7}^*$, $Z_r$, ${Z_r}^*$, $Z_r \backslash b_r$, or $Z_r \backslash b_r$, for some $\ge 4$.

Observe that the 3-connected infinite family $Z_r$ is growing at the rate of $2r+1$ elements. In Section 3 of his paper Oxley states without proof (details are straightforward) that the growth rate of the class of binary matroids with no 4-wheel minor is $3r-2$ if $r$ is odd and $3r-3$ if $r$ is even (Theorem 3.1). Why the difference: $2r+1$ versus $3r-2$? The answer is given in the second part of the statement of the theorem, you can 2-sum $F_7$ with itself or $F_7$ with $Z_4$ or $F_7$ with $U_{2,3}$ and get slightly larger rank-$r$ matroids as compared to $Z_r$.

This is why it is sufficient to know the 3-connected members of a class, and for all practical purposes the definition of extremal matroid really should have had 3-connected in it. The definition of extremal matroid made in the 1950s did not forsee Bixby’s result. There’s probably no point changing any definition, but it must be understood clearly that if the 3-connected members of a class are known, then so is the growth rate.

This raises the question: What if we don’t know the 3-connected members, but we have a decomposition result? The first and most well-known such result in Matroid Theory is Paul Seymour’s regular matroid decomposition. He proved that if $M$ is a 3-connected matroid in $EX(F_7, F_7^*)$, then $M$ can be constructed by piecing together graphic and cographic matroids and $R_{10}$, which is a special 10-element matroid [Seymour, 1980].  The  3-connected regular matroids are not known precisely. However, in 1957 Heller showed that the growth rate of the class of regular matroids is $\frac {r(r+1)}{2}$. His proof predates Seymour’s decomposition theorem. I have not seen a proof of growth rate of regular matroids based on the Seymour’s decomposition theorem. Perhaps if someone has, a reference could be mentioned in the comments.

More recently, Kung, Mayhew, Pivotto, and Royle showed the growth rate of $EX(AG(3,2)$ is $\frac {r(r+1)}{2}$. See Nelson’s fifth post on growth-rates. In that post he said:

Given this (and Irene asked a question along these lines in her post), it is natural to ask for a characterisation of exactly which classes of matroids grow like the graphic ones:

In a paper titled “Growth rates of binary matroids with no $P_9^*$-minor,” I found another class that exhibits this behavior.

Theorem 3. Let $M$ be a simple rank-$r$ binary matroid with no $P_9^*$ minor. Then, $|E(M)| \le \frac {r(r+1)}{2}$ with this bound being attained if and only if $M\cong K_{r+1}$. Moreover, the growth rate function of non-regular matroids in $EX[P_9^*]$ is $4r-5$, for $r\ge 6$.

The technique in Oxley’s 1987 paper is Seymour’s Splitter Theorem which was used to obtain the precise 3-connected members. The technique in my paper is the Strong Splitter Theorem, which was joint work with Manoel Lemos, where we built on the Splitter Theorem. Using it I was able to find the 3-connected members for $EX({P_9}^*)$. This approach is completely different from the approach Kung, Mayhew, Pivotto, and Royle adopted to find $EX(AG(3,2)$.

This post is getting quite long. In my next post I will describe the complete structure of the class $EX(P_9^*)$ and explain how I can say precisely the growth rate of the 3-connected non-regular matroids is $4r-5$. Note that $4r-5$ is the growth rate of the rank-$r$ 3-connected family, but it is large enough that it dominates any rank-$r$ 2-connected matroid pieced together from small 3-connected matroids.

The next post will appear on my blog Graphs, Matroids, etc.

References:

[Heller, 1957] I. Heller (1957), On linear systems with integral valued solutions, Pacific J. Math. 7, 1351-1364.

[Kingan, 2015] S. R. Kingan, Growth rates of binary matroids with no $P_9^*$-minor,  arXiv:1412.8169.

[Kingan and Lemos, 2014] S. R. Kingan and M. Lemos (2014), Strong Splitter Theorem , Annals of Combinatorics, Vol. 18 – 1, 111 – 116.

[Kung, Mayhew, Pivotto, Royle, 2013] J. Kung, D. Mayhew, I. Pivotto, and G. Royle, Maximum size binary matroids with no AG(3,2)-minor are graphic,  http://epubs.siam.org/doi/abs/10.1137/130918915

[Oxley, 1987] J. G. Oxley (1987). The binary matroids with no 4-wheel minor, {\it Trans. Amer. Math. Soc.} {\bf 154}, 63-75.

[Oxley, 2012] J. G. Oxley (2012). {\it Matroid Theory}, Second Edition, Oxford University Press, New York.

[Seymour, 1980] P. D. Seymour (1980) Decomposition of regular matroids, {\it J. Combin. Theory Ser. B} {\bf 28}, (1980) 305-359.

[Turán, 1941] P. Turán (1941), “On an extremal problem in graph theory”, Matematikaiés Fizikai Lapok (in Hungarian) 48: 436–452.

Guest post by Daryl Funk

This post is meant as a short postscript to Irene’s post in March, Which biased graphs are group-labelled graphs? Since Irene’s post generated a fair number of comments, there may be some interest in taking a closer look at the construction used in Theorem 1 of that post. Let us quickly remind ourselves of the context, and the theorem.

A graph $G$ together with a collection $\mathcal{B}$ of its cycles — called balanced — is a biased graph. Cycles not in $\mathcal{B}$ are unbalanced. Orienting the edges of $G$ and labelling each edge with an element of a group gives us a group-labelled graph. A group-labelled graph naturally gives rise to a biased graph, as follows. Traverse each cycle via a simple closed walk, taking the product of the group elements labelling each edge as you go, taking the inverse of the element when traversing an edge in reverse. Declare as balanced just those cycles for which such a product is the identity. Thus, group-labelled graphs provide the primary examples of biased graphs. An arbitrary biased graph $(G,\mathcal{B})$ is group-labellable if there is a group and a labelling for which this procedure yields precisely its collection of balanced cycles $\mathcal{B}$. Hence the question of our title: Which biased graphs are group-labelled? Theorem 1 provides an answer.

Theorem 1. Let $(G,\mathcal{B})$ be a biased graph. Construct a 2-cell complex $K$ from $G$ by adding a disc with boundary $C$ for each $C \in \mathcal{B}$. Then the following are equivalent:

1. $(G,\mathcal{B})$ is group-labellable.
2. $(G,\mathcal{B})$ is $\pi_1(K)$-labellable (where $\pi_1(K)$ is the fundamental group of $K$).
3. Every unbalanced cycle of $G$ is noncontractible in $K$.

Barring degenerate cases, the $\pi_1(K)$-labelling constructed by Theorem 1 is a labelling by an infinite group. In practice, we often work with graphs labelled by a finite group — probably the most studied group-labelled graphs are those labelled by the group of order two (i.e. signed graphs). Moreover, we consider only finite graphs. The following therefore is a natural question:

Question 1. If $(G,\mathcal{B})$ is group-labellable, is $(G,\mathcal{B})$ labellable by a finite group?

Could it be that there are group-labelled graphs whose collections of balanced cycles may only be realised by a labelling using an infinite group?

Given any group-labelling of a biased graph $(G,\mathcal{B})$, say using elements of the group $\Gamma$, there is a homomorphism from the fundamental group $\pi_1(K)$ of the 2-cell complex $K$ we construct in Theorem 1, to $\Gamma$. This homomorphism makes explicit the connection between the topology of $K$ and group-labellings of $(G,\mathcal{B})$. It also enables us to easily answer Question 1.

In preparation for a description of this homomorphism, let us recall some additional terminology and notation from Irene’s original post. Let $G$ be a graph and let $\Gamma$ be a group. Orient the edges of $G$, and let $\phi: E(G) \to \Gamma$ be a function. We extend $\phi$ to the set of closed walks in $G$ by defining, for closed walk $W$ with edge sequence $e_1, e_2, \ldots, e_k$,
\[ \phi(W) = \phi(e_1)^{\textrm{dir}(e_1)} \phi(e_2)^{\textrm{dir}(e_2)} \cdots \phi(e_k)^{\textrm{dir}(e_k)} \]
where $\textrm{dir}(e_i)$ is 1 if $W$ traverses edge $e_i$ in the forward direction, and is $-1$ if $W$ traverses $e_i$ in the backward direction. Let $\mathcal{B}_\phi$ be the collection of cycles $C$ for which a simple closed walk $W$ traversing $C$ has $\phi(W)=1$. With this notation, $(G,\mathcal{B})$ is group-labellable if there is a group $\Gamma$ and labelling $\phi$ such that $\mathcal{B}_\phi = \mathcal{B}$. In this case we say the labelling $\phi$ realises $\mathcal{B}$, and that $(G,\mathcal{B})$ is $\Gamma$-labellable.

As Irene described near the end of her post, there is a fourth statement equivalent to statements 1, 2, and 3 of Theorem 1. To state it, we need just two more definitions. A rerouting of a closed walk $W$ is a closed walk $W’$ obtained from $W$ by replacing a subpath $P$ of $W$, say between vertices $u$ and $v$, with another $u$-$v$ path $P’$ that is internally disjoint from $P$. If $P \cup P’$ is a balanced cycle, then this is a balanced rerouting. Statement 4 below is equivalent to Statements 1, 2, and 3 of Theorem 1:

4. No unbalanced cycle can be moved to a balanced cycle via a sequence of balanced reroutings of closed walks.

We may now describe the homomorphism $\pi_1(K) \to \Gamma$, where $K$ is the 2-cell complex constructed from $(G,\mathcal{B})$ and $(G,\mathcal{B})$ is $\Gamma$-labellable. Let $\phi : E(G) \to \Gamma$ with $\mathcal{B}_\phi = \mathcal{B}$. The fundamental group $\pi_1(K)$ of $K$ is constructed in our proof of Theorem 1 with presentation in terms of generators $g_e$, one for each edge $e$ not in a chosen spanning tree of $G$, and relations among these generators given by simple closed walks around the cycles in $\mathcal{B}$. Each edge in the spanning tree is labelled by the group identity 1, and for each cycle in $\mathcal{B}$ we add a relation corresponding to the product of the generators labelling the edges as they are traversed by a simple closed walk around the cycle (as described by Irene in her original post; of course, details may be found in our paper [DFP14]). Let us denote this $\pi_1(K)$-labelling by $\rho : E(G) \to \pi_1(K)$. For an element $g \in \pi_1(K)$ expressed as the word $g = g_{e_1}^{a_1} g_{e_2}^{a_2} \cdots g_{e_m}^{a_m}$ for some generators $g_{e_1}, g_{e_2}, \ldots, g_{e_m}$ and integers $a_1, a_2, \ldots, a_m$, define $\eta : \pi_1(K) \to \Gamma$ by
\[ \eta(g) = \eta \left( g_{e_1}^{a_1} g_{e_2}^{a_2} \cdots g_{e_m}^{a_m} \right) = \phi \left( \rho^{-1}(g_{e_1})^{a_1} \rho^{-1}(g_{e_2})^{a_2} \cdots \rho^{-1}(g_{e_m})^{a_m} \right) .\]

Theorem 2.The map $\eta:\pi_1(K) \to \Gamma$ is a group homomorphism.

Proof. Clearly $\eta$ is a homomorphism if it is well-defined. So suppose $g=$ $g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{n_m}^{a_{m_n}}$ $=$ $g_{k_1}^{a_{k_1}} g_{k_2}^{a_{k_2}} \cdots g_{k_p}^{a_{k_p}}$ are two words expressing the element $g \in \pi_1(K)$, where $g_{n_1}$, $g_{n_2}$, $\ldots$, $g_{n_m}$, $g_{k_1}$, $g_{k_2}$, $\ldots$, $g_{k_p}$ are generators and $a_{n_1}, a_{n_2}, \ldots$, $a_{n_m}, a_{k_1}, a_{k_2}, \ldots, a_{k_p}$ are integers. We show that
\[ \eta\left(g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{n_m}^{a_{m_n}} ( g_{k_1}^{a_{k_1}} g_{k_2}^{a_2} \cdots g_{k_p}^{a_{k_p}})^{-1}\right)=1,\]
and so that $\eta$ maps both words $g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{n_m}^{a_{m_n}}$ and $g_{k_1}^{a_{k_1}} g_{k_2}^{a_2} \cdots g_{k_p}^{a_{k_p}}$ to the same element of $\Gamma$. We have
\begin{multline*}
\eta \left(g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{m_n}^{a_{m_n}} ( g_{k_1}^{a_{k_1}} g_{k_2}^{a_{k_2}} \cdots g_{k_p}^{a_{k_p}} )^{-1}\right) \\
= \phi \left( \rho^{-1}(g_{n_1})^{a_{n_1}} \rho^{-1}(g_{n_2})^{a_{n_2}} \cdots \rho^{-1}(g_{n_m})^{a_{n_m}} \rho^{-1}(g_{k_p})^{-a_{k_p}} \cdots \rho^{-1}(g_{k_2})^{-a_{k_2}} \rho^{-1}(g_{k_1})^{-a_{k_1}} \right) \\
= \phi\left( \rho^{-1}(g_{n_1})\right)^{a_{n_1}} \phi\left(\rho^{-1}(g_{n_2})\right)^{a_{n_2}} \cdots \phi\left(\rho^{-1}(g_{n_m})\right)^{a_{n_m}} \phi \left(\rho^{-1}(g_{k_p})\right)^{-a_{k_p}} \cdots \\ \phi\left(\rho^{-1}(g_{k_2})\right)^{-a_{k_2}} \phi\left(\rho^{-1}(g_{k_1})\right)^{-a_{k_1}}.
\end{multline*}
In $\pi_1(K)$, $g_{n_1}^{a_{n_1}} g_{n_2}^{a_{n_2}} \cdots g_{m_n}^{a_{m_n}} g_{k_p}^{-a_{k_p}} \cdots g_{k_2}^{-a_{k_2}} g_{k_1}^{-a_{k_1}} = 1$; the relations in $\pi_1(K)$ that reduce this word to the identity correspond to a sequence of reroutings via balanced cycles. The word in $\Gamma$ given by $\eta$ has the same corresponding edge sequence. Since $\mathcal{B}_\phi = \mathcal{B}$, this word is therefore reduced to the identity by the same sequence of balanced reroutings. $\square$

Let’s now use this homomorphism to answer Question 1.

Theorem 3. There exists a group-labellable biased graph whose collection of balanced cycles is not realised by any labelling with any finite group.

Proof. Let $H$ be the Higman group
\[ H = \left< a, b, c, d \mid a^{-1} b a = b^2, b^{-1} c b = c^2, c^{-1} d c = d^2, d^{-1} a d = a^2 \right>. \]
The Higman group is infinite with no non-trivial finite quotients [H51] (the Wikipedia entry has a brief description). Construct a simplicial 2-complex $\mathcal{K}$ by identifying the points of edges marked $a$, $b$, $c$, and $d$, respectively, of five pentagons, oriented as shown in the figure.

Let $G$ be the graph consisting of the vertices and edges of the barycentric subdivision of $\mathcal{K}$ (the following figure shows the part of the graph obtained from the first pentagon above), and let $\mathcal{B}$ be the set of cycles of $G$ that are contractible in $\mathcal{K}$.

By construction, the fundamental group $\pi_1(\mathcal{K})$ is $H$. Hence the biased graph $(G,\mathcal{B})$ is $H$-labellable. Let $\Gamma$ be a group for which there is a labelling $\gamma : E(G) \to \Gamma$ realising $\mathcal{B}$. By Theorem 2, there is a homomorphism from $H$ to $\Gamma$. Since $H$ has no non-trivial finite quotient, and $(G,\mathcal{B})$ is not labellable by the trivial group, $\Gamma$ cannot be finite. $\square$

The graph $G$ constructed in the proof of Theorem 3 is pretty; it is shown below.

References

[H51] Graham Higman. A finitely generated infinite simple group. J. London Math. Soc., 26:61-64, 1951.

[DFP14] DeVos, Matthew; Funk, Daryl; and Pivotto, Irene. When does a biased graph come from a group labelling? Advances in Applied Mathematics, Vol 61 (October 2014), pp 1-18.