{"id":1375,"date":"2015-05-05T09:00:05","date_gmt":"2015-05-05T13:00:05","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1375"},"modified":"2015-05-05T17:13:57","modified_gmt":"2015-05-05T21:13:57","slug":"extremal-matroids-and-growth-rates","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1375","title":{"rendered":"Extremal Matroids and Growth Rates"},"content":{"rendered":"

Guest post by Sandra Kingan<\/a><\/em><\/p>\n

Growth rates are a popular topic on Matroid Union.\u00a0Peter Nelson<\/a>\u00a0has written five posts on it: Growth Rates\u00a0I<\/a>,\u00a0II<\/a>,\u00a0III<\/a>,\u00a0IV<\/a>,\u00a0V<\/a>.\u00a0 Irene Pivotto has also written a\u00a0post<\/a>\u00a0on it.<\/p>\n

Following James Oxley’s book [Oxley, 2012] , the\u00a0growth rate function<\/strong>\u00a0of 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).\u00a0A simple matroid is\u00a0extremal<\/strong>\u00a0in 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).<\/p>\n

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}$.\u00a0 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\u00a0straightforward graph theoretic argument (found in any graph theory textbook) shows\u00a0that the number of edges\u00a0of a\u00a0“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\u00a0non-planar.)<\/p>\n

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$.<\/p>\n

Within the class of binary matroids lies the class of cographic matroids (matroids whose duals are graphic).\u00a0Again we don’t know precisely the extremal cographic matroids, but we can prove that the\u00a0growth rate function is $3r-3$ (as shown\u00a0by Joseph Kung\u00a0and further\u00a0explained further in\u00a0Pivotto’s post<\/a>).\u00a0Also in her post is the growth rate of series-parallel networks.\u00a0Series-parallel networks\u00a0are formed by starting with a single edge or loop and repeatedly adding edges in parallel or edges in series (turning\u00a0one edge into two edges by putting a vertex on the\u00a0edge). The growth rate of series parallel networks is $2r+1$. See [Oxley Section 5.4] and\u00a0[Oxley 1987, Section 3<\/a>] for the explanation.<\/p>\n

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

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.<\/p>\n

In\u00a01963 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\u00a0that 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$.<\/p>\n

Theorem 1.<\/strong>\u00a0 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$.<\/p>\n

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\u00a0$K_{3, r-2}”’$ is $3r-3$ for\u00a0$r\\ge 5$. Both of these 3-connected infinite families are growing linearly. I’ve heard the word “monarchs<\/strong>” used to describe $W_r$ and\u00a0$K_{3, p}”’$; I think Jack Edmonds used this term. Monarchs is a\u00a0good word to describe them.<\/p>\n

Matroids that are not\u00a03-connected may be pieced together\u00a0from 3-connected matroids using direct-sums and 2-sums\u00a0[Oxley, 2012, 8.3.1].\u00a0This\u00a0result 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.\u00a0Thus if we know the 3-connected matroids we can build the 2-connected ones via the operation of two sums.<\/p>\n

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\u00a0that can be constructed from\u00a0direct sum or 2-sum. The proof\u00a0is straightforward case-checking.\u00a0Thus 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\u00a0say 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\u00a0will still give a linear growth rate.<\/p>\n

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.\u00a0Let $Z_r$ denote the $(2r+1)$-element rank-$r$ binary spikes.\u00a0They are non-regular matroids\u00a0represented by the binary matrix $[I_r| D]$ where $D$\u00a0has $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.<\/p>\n

Theorem 2.<\/strong>\u00a0A 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$.<\/p>\n

Observe that the\u00a03-connected infinite family $Z_r$ is growing at the rate of $2r+1$ elements. In\u00a0Section 3 of his paper\u00a0Oxley 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).\u00a0Why the difference: $2r+1$ versus $3r-2$?\u00a0The answer is given in the second part of the statement of the theorem, you can 2-sum $F_7$\u00a0with itself or $F_7$\u00a0with $Z_4$ or $F_7$ with $U_{2,3}$ and get slightly larger rank-$r$ matroids as compared to $Z_r$.<\/p>\n

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\u00a0understood clearly\u00a0that if the 3-connected members of a class are known, then so is the growth rate.<\/p>\n

This raises\u00a0the question:\u00a0What if we don’t know the 3-connected members, but we have a decomposition result?\u00a0The first and most well-known such\u00a0result in Matroid\u00a0Theory is Paul Seymour’s regular matroid decomposition. He proved that\u00a0if $M$ is a 3-connected matroid in $EX(F_7, F_7^*)$, then\u00a0$M$ can be\u00a0constructed by piecing together graphic and cographic matroids and $R_{10}$, which is a special 10-element matroid [Seymour, 1980].\u00a0\u00a0The \u00a03-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\u00a0predates\u00a0Seymour’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.<\/p>\n

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

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:<\/p><\/blockquote>\n

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

Theorem 3.<\/strong>\u00a0Let $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$.<\/p>\n

The technique in Oxley’s 1987 paper is Seymour’s\u00a0Splitter Theorem which was used to obtain the precise 3-connected members. The technique in my paper is the\u00a0Strong Splitter Theorem<\/a>, which was joint work with Manoel Lemos, where we built on\u00a0the\u00a0Splitter 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\u00a0adopted to find $EX(AG(3,2)$.<\/p>\n

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\u00a0is $4r-5$.\u00a0Note 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.<\/p>\n

The next post will appear on my\u00a0blog\u00a0Graphs, Matroids, etc.<\/a><\/p>\n

References:<\/strong><\/p>\n

[Heller, 1957] I. Heller (1957),\u00a0On linear systems with integral valued solutions,<\/em>\u00a0Pacific J. Math.\u00a07<\/strong>, 1351-1364.<\/p>\n

[Kingan, 2015] S. R. Kingan,\u00a0Growth rates of binary matroids with no $P_9^*$-minor<\/a>,<\/em>\u00a0\u00a0arXiv:1412.8169.<\/p>\n

[Kingan and Lemos, 2014] S. R. Kingan and M. Lemos (2014),\u00a0Strong Splitter Theorem\u00a0<\/a>,\u00a0Annals of Combinatorics<\/i>,\u00a0Vol. 18 \u2013 1<\/b>, 111 \u2013 116.<\/p>\n

[Kung, Mayhew, Pivotto, Royle, 2013] J. Kung, D. Mayhew, I. Pivotto, and G. Royle,\u00a0Maximum size binary matroids with no AG(3,2)-minor are graphic<\/em>,<\/em>\u00a0\u00a0http:\/\/epubs.siam.org\/doi\/abs\/10.1137\/130918915<\/a><\/p>\n

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

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

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

[Tur\u00e1n, 1941] P.\u00a0Tur\u00e1n\u00a0(1941), “On an extremal problem in graph theory”,\u00a0Matematikai\u00e9s Fizikai Lapok<\/i>\u00a0(in Hungarian)\u00a048<\/b>: 436\u2013452.<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Guest post by Sandra Kingan Growth rates are a popular topic on Matroid Union.\u00a0Peter Nelson\u00a0has written five posts on it: Growth Rates\u00a0I,\u00a0II,\u00a0III,\u00a0IV,\u00a0V.\u00a0 Irene Pivotto has also written a\u00a0post\u00a0on it. Following James Oxley’s book [Oxley, 2012] , the\u00a0growth rate function\u00a0of a … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1375","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1375","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1375"}],"version-history":[{"count":6,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1375\/revisions"}],"predecessor-version":[{"id":1381,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1375\/revisions\/1381"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}