{"id":1063,"date":"2015-02-10T03:28:37","date_gmt":"2015-02-10T08:28:37","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1063"},"modified":"2015-02-10T14:42:00","modified_gmt":"2015-02-10T19:42:00","slug":"non-unimodality-of-2-polymatroids","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1063","title":{"rendered":"Non-unimodality of 2-polymatroids"},"content":{"rendered":"<p><em>Guest post by Thomas Savitsky<\/em><\/p>\n<p>A $k$-polymatroid is a generalization of a matroid in which the rank of an element is allowed to exceed one, but cannot exceed $k$.<\/p>\n<p><strong>Definition 1.<\/strong><br \/>\nLet $S$ be a finite set. Suppose $\\rho : 2^S \\to \\mathbb{N}$ satisfies the following four conditions:<\/p>\n<ul>\n<li>if $X, Y \\subseteq S$, then $\\rho(X \\cap Y) + \\rho(X \\cup Y) \\le \\rho(X) + \\rho(Y)$<br \/>\n(submodular);<\/li>\n<li>if $X \\subseteq Y \\subseteq S$, then $\\rho(X) \\le \\rho(Y)$ (monotone);<\/li>\n<li>$\\rho(\\varnothing) = 0$ (normalized); and<\/li>\n<li>$\\rho(\\{x\\}) \\le k$ for all $x \\in S$.<\/li>\n<\/ul>\n<p>Then $(\\rho, S)$ is a <em>$k$-polymatroid<\/em> with <em>rank function<\/em> $\\rho$ and <em>ground set<\/em> $S$.<\/p>\n<p>So a matroid is a $1$-polymatroid. Here are a few examples of $2$-polymatroids.<\/p>\n<ul>\n<li>If $(r_1, S)$, and $(r_2, S)$ are matroids, then $(r_1+r_2, S)$ is a $2$-polymatroid.<\/li>\n<li>If $G = (V, E)$ is a graph, one may define a $2$-polymatroid $(\\rho, E)$, where<br \/>\n$\\rho(X)$ equals the number of vertices incident to $X$.<\/li>\n<li>Given an $m \\times 2n$ matrix with entries in a field, one may define a <em>representable<\/em> $2$-polymatroid on $n$ elements by pairing up the columns in a obvious manner.<\/li>\n<\/ul>\n<p>We became interested in $k$-polymatroids and thought it would be practical to have a catalog of the small ones at our disposal. We successfully adapted the canonical deletion<br \/>\napproach used by Mayhew and Royle (see [MR08]) to catalog matroids on nine elements to $2$-polymatroids. This first required developing a theory of single-element extensions of $k$-polymatroids. We then wrote code in the C programming language and interfaced with Brendan McKay&#8217;s <a href=\"http:\/\/cs.anu.edu.au\/~bdm\/nauty\/\">nauty<\/a> program and the <a href=\"http:\/\/igraph.org\">igraph<\/a> graph library. After a few days of execution time on a desktop computer, our program produced a catalog of all $2$-polymatroids, up to isomorphism, on at most seven elements.<\/p>\n<p>By consulting our catalog, we produced Table 1, which lists the number of unlabeled $2$-polymatroids on the ground set $\\{1, \\ldots, n\\}$ by rank.<\/p>\n<table style=\"width: 100%;border: 1px solid black\">\n<caption>Table 1: The number of unlabeled $2$-polymatroids.<\/caption>\n<tbody>\n<tr>\n<th style=\"text-align: center;border: 1px solid black;color: brown\">rank $\\backslash$ $n$<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">0<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">1<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">2<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">3<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">4<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">5<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">6<\/th>\n<th style=\"text-align: left;border: 1px solid black;color: brown\">7<\/th>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">0<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">1<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">2<\/td>\n<td style=\"border: 1px solid black\">3<\/td>\n<td style=\"border: 1px solid black\">4<\/td>\n<td style=\"border: 1px solid black\">5<\/td>\n<td style=\"border: 1px solid black\">6<\/td>\n<td style=\"border: 1px solid black\">7<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">2<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">4<\/td>\n<td style=\"border: 1px solid black\">10<\/td>\n<td style=\"border: 1px solid black\">21<\/td>\n<td style=\"border: 1px solid black\">39<\/td>\n<td style=\"border: 1px solid black\">68<\/td>\n<td style=\"border: 1px solid black\">112<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">3<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">2<\/td>\n<td style=\"border: 1px solid black\">12<\/td>\n<td style=\"border: 1px solid black\">49<\/td>\n<td style=\"border: 1px solid black\">172<\/td>\n<td style=\"border: 1px solid black\">573<\/td>\n<td style=\"border: 1px solid black\">1890<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">4<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">10<\/td>\n<td style=\"border: 1px solid black\">78<\/td>\n<td style=\"border: 1px solid black\">584<\/td>\n<td style=\"border: 1px solid black\">5236<\/td>\n<td style=\"border: 1px solid black\">72205<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">5<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">3<\/td>\n<td style=\"border: 1px solid black\">49<\/td>\n<td style=\"border: 1px solid black\">778<\/td>\n<td style=\"border: 1px solid black\">18033<\/td>\n<td style=\"border: 1px solid black\">971573<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">6<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">21<\/td>\n<td style=\"border: 1px solid black\">584<\/td>\n<td style=\"border: 1px solid black\">46661<\/td>\n<td style=\"border: 1px solid black;color: green\">149636721<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">7<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">4<\/td>\n<td style=\"border: 1px solid black\">172<\/td>\n<td style=\"border: 1px solid black\">18033<\/td>\n<td style=\"border: 1px solid black;color: green\">19498369<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">8<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">39<\/td>\n<td style=\"border: 1px solid black\">5236<\/td>\n<td style=\"border: 1px solid black;color: green\">149636721<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">9<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">5<\/td>\n<td style=\"border: 1px solid black\">573<\/td>\n<td style=\"border: 1px solid black\">971573<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">10<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">68<\/td>\n<td style=\"border: 1px solid black\">72205<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">11<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">6<\/td>\n<td style=\"border: 1px solid black\">1890<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">12<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<td style=\"border: 1px solid black\">112<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">13<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">7<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: brown\">14<\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\"><\/td>\n<td style=\"border: 1px solid black\">1<\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;border: 1px solid black;color: blue\">total<\/td>\n<td style=\"border: 1px solid black;color: blue\">1<\/td>\n<td style=\"border: 1px solid black;color: blue\">3<\/td>\n<td style=\"border: 1px solid black;color: blue\">10<\/td>\n<td style=\"border: 1px solid black;color: blue\">40<\/td>\n<td style=\"border: 1px solid black;color: blue\">228<\/td>\n<td style=\"border: 1px solid black;color: blue\">2380<\/td>\n<td style=\"border: 1px solid black;color: blue\">94495<\/td>\n<td style=\"border: 1px solid black;color: blue\">320863387<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>&nbsp;<\/p>\n<p>Surprisingly, the number of $2$-polymatroids on seven elements is not unimodal in rank. In contrast, matroids are conjectured to be unimodal in rank, and the catalog of matroids with nine elements supports this. By the way, the symmetry in the columns in Table 1 is accounted for by a notion of duality for $2$-polymatroids.<\/p>\n<p>Note that one can obtain the analogue of Table 1 for <em>labeled<\/em> $2$-polymatroids by computing the automorphism group of each $2$-polymatroid and then using the Orbit-Stabilizer relation. This allowed us to confirm the results of our enumeration through another means. By interpreting a $2$-polymatroid as a solution to a certain integer programming program, the number of labeled $2$-polymatroids can theoretically be computed by integer programming software. Fortunately, the software package SCIP was up to the task when $n \\le 7$.<\/p>\n<p>See [Sa14] for more details on all of the above.<\/p>\n<p>Now recall that a matroid $M$ is <em>paving<\/em> if it contains no circuit of size less than $r(M)$. If both $M$ and $M^{*}$ are paving, then $M$ is <em>sparse-paving<\/em>. If $M$ is sparse-paving, then one can show that that every set of size less than $r(M)$ is independent and that the dependent $r(M)$-subsets are circuit-hyperplanes; furthermore, the symmetric difference of any two circuit-hyperplanes must be at least $4$. In fact, sparse-paving matroids are characterized by these properties.<\/p>\n<p>It is conjectured that almost all matroids are sparse-paving.<\/p>\n<p>The ideas in the remainder of this post were communicated to me by<br \/>\nRudi Pendavingh.<\/p>\n<p>We first mention the following background item. Let $S = \\{e_1, e_2, \\dots, e_n\\} \\cup \\{f_1, f_2, \\dots, f_n\\}$ be a set of size $2n$. Suppose $(r, S)$ is a matroid. We will pair up the elements of $S$ to define a $2$-polymatroid as follows. Define $S&#8217; = \\big\\{\\{e_1, f_1\\}, \\{e_2, f_2\\}, \\dots, \\{e_n, f_n\\}\\big\\}$, and define $\\rho : S&#8217; \\to \\mathbb{N}$ by<br \/>\n$$\\rho\\big(\\big\\{\\{e_{i_1}, f_{i_1}\\}, \\{e_{i_2}, f_{i_2}\\}, \\dots, \\{e_{i_m}, f_{i_m}\\}\\big\\}\\big) = r(\\{e_{i_1}, f_{i_1}, e_{i_2}, f_{i_2},\\dots, e_{i_m}, f_{i_m}\\}).$$<br \/>\nThen $(\\rho, S&#8217;)$ is a $2$-polymatroid on $n$ elements with $\\rho(S&#8217;) = r(S)$. Furthermore, <em>every<\/em> $2$-polymatroid on $n$ elements may be obtained in this manner from a matroid on $2n$ elements. See Section 44.6b of Schrijver&#8217;s <em>Combinatorial Optimization<\/em> or Theorem 11.1.9 of Oxley&#8217;s <em>Matroid Theory<\/em> for details.<\/p>\n<p>Now assume that $r$ is a sparse-paving matroid. If $r(S)$ is odd, then $\\rho$ does not detect any of the circuit-hyperplanes of $r$; namely,<br \/>\n\\begin{equation*}<br \/>\n\\rho(X) =<br \/>\n\\begin{cases}<br \/>\n2|X| &#038; \\text{if} \\ 2|X| < r(S),\\\\\nr(S) &#038; \\text{if} \\ 2|X| > r(S).\\\\<br \/>\n\\end{cases}<br \/>\n\\end{equation*}<br \/>\nTo illustrate, all the rank-$7$ sparse-paving matroids on 14 elements map, in this manner, to a single rank-$7$ $2$-polymatroid on seven elements. However, if $r(S)$ is even, then the circuit-hyperplanes of $r$ are picked up by $\\rho$. Perhaps this observation, combined with the conjecture that almost all matroids are sparse-paving, makes the non-unimodality of $2$-polymatroids appear more reasonable.<\/p>\n<h1>References<\/h1>\n<p>[MR08] Dillon Mayhew and Gordon F. Royle.<br \/>\n<em>Matroids with nine elements.<\/em><br \/>\nJ. Combin. Theory Ser. B, 98(2):415&#8211;431, 2008.<br \/>\n<a href=\"http:\/\/dx.doi.org\/10.1016\/j.jctb.2007.07.005\">doi<\/a><\/p>\n<p>[Sa14] Thomas J. Savitsky.<br \/>\n<em>Enumeration of 2-polymatroids on up to seven elements.<\/em><br \/>\nSIAM J. Discrete Math., 28(4):1641&#8211;1650, 2014.<br \/>\n<a href=\"http:\/\/dx.doi.org\/10.1137\/140955094\">doi<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Guest post by Thomas Savitsky A $k$-polymatroid is a generalization of a matroid in which the rank of an element is allowed to exceed one, but cannot exceed $k$. Definition 1. Let $S$ be a finite set. Suppose $\\rho : &hellip; <a href=\"https:\/\/matroidunion.org\/?p=1063\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1063","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1063","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=1063"}],"version-history":[{"count":7,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1063\/revisions"}],"predecessor-version":[{"id":1167,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1063\/revisions\/1167"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1063"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1063"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1063"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}