{"id":1228,"date":"2015-03-23T00:01:47","date_gmt":"2015-03-23T04:01:47","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1228"},"modified":"2015-03-23T12:31:06","modified_gmt":"2015-03-23T16:31:06","slug":"hilbert-bases-of-cuts-and-cocircuits","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1228","title":{"rendered":"Hilbert Bases of Cuts and Cocircuits"},"content":{"rendered":"

Let $X$ be a set of vectors in $\\mathbb{R}^d$. \u00a0Three important objects related to\u00a0$X$ are the\u00a0cone, lattice,\u00a0<\/em>and\u00a0integer cone<\/em> generated by $X$. \u00a0These are (respectively), the set of all real non-negative combinations, the set of all integer combinations, and the set of all non-negative integer combinations of vectors in $X$. \u00a0Clearly, the integer cone is contained in the intersection of the cone and the lattice. \u00a0If the integer cone is equal<\/em> to the intersection of the cone and the lattice, we say that $X$ is a\u00a0Hilbert basis.<\/em><\/p>\n

Hilbert bases were introduced by Giles and Pulleyblank [1] as a tool to study total dual integrality. They are often nicer to work with than arbitrary sets of vectors. \u00a0For example, from the computational perspective, membership testing can be much easier for the cone and lattice than for the integer cone.<\/p>\n

Given a graph $G$ (or matroid), we may regard subsets of $E(G)$\u00a0as characteristic $(0,1)$-vectors. In this way, we can ask whether a family\u00a0$\\mathcal{S}$ of subgraphs of $G$ is a Hilbert basis. In the case that\u00a0$\\mathcal{S}$ is the set of circuits of $G$, there is the\u00a0following nice theorem of Alspach, Goddyn and Zhang [2].<\/p>\n

Theorem 1 [Alspach, Goddyn, Zhang]. \u00a0<\/strong>The set of circuits of a graph $G$ is a Hilbert basis if and only if $G$ does not contain the Peterson graph as a minor.<\/p>\n

From the matroidal perspective, the difference between circuits and cuts is superficial, so it is very natural to ask the following question.<\/p>\n

Question 2.<\/strong> \u00a0For which graphs $G$ is the set of cuts\u00a0of $G$ a Hilbert basis?<\/p>\n

Let us define\u00a0a graph to be\u00a0cut- (respectively circuit-) Hilbert<\/em> if its set of cuts (respectively circuits) is a Hilbert basis. \u00a0Let $K_{5}^{\\perp}$ be the unique 3-connected uncontraction of $K_5$.<\/p>\n

\"$K_5^{\\perp}$\"<\/a>

The graph $K_5^{\\perp}$ with a distinguished edge $e$.<\/p><\/div>\n

Laurent [3] had previously shown that\u00a0$K_{5}^{\\perp}$ is cut-Hilbert.<\/p>\n

In a recent paper<\/a> of Deshpande, Goddyn and myself [4], we prove that all graphs without a $K_{5}^{\\perp}$-minor are cut-Hilbert.<\/p>\n

Theorem 3 [Deshpande, Goddyn, H].<\/strong>\u00a0 Every graph\u00a0without a $K_{5}^{\\perp}$-minor is cut-Hilbert.<\/p>\n

However, somewhat curiously, we also prove that the class of cut-Hilbert graphs is not as well-behaved as the class of circuit-Hilbert graphs.<\/p>\n

Theorem 4 [Deshpande, Goddyn, H].<\/strong> \u00a0The class of cut-Hilbert graphs is not closed under edge-deletion, edge-subdivision, nor\u00a02-sums.<\/p>\n

Note that Theorem 4 is in stark contrast to Theorem 1, where there is\u00a0an exact excluded-minor characterization for the class of circuit-Hilbert graphs.<\/p>\n

I will now give\u00a0the examples that establish Theorem 4.<\/p>\n

It will be important to\u00a0clarify what we mean by a 2-sum. \u00a0A\u00a02-sum<\/em>\u00a0of two graphs is obtained by gluing them together along a common edge, and then deleting that edge. A\u00a02-clique-sum<\/em> of two graphs is obtained by gluing them together along a common edge, but keeping that edge. In contrast to 2-sums, Laurent [3] also proved that the family of cut-Hilbert graphs is closed under 2-clique-sums.<\/p>\n

\"\"<\/a>

Three different weightings of a non-cut-Hilbert graph $H_1$. Black edges all have weight 1.<\/p><\/div>\n

Consider the three edge-weightings of the above graph $H_1$. \u00a0For a simple graph $G$, it is easy to show that a\u00a0vector $x \\in \\mathbb{Z}^{E(G)}$ is in the lattice of cuts of $G$ if and only if $x(C)$ is even for every circuit $C$ of $G$. \u00a0One easily checks that this condition holds for each of the above three edge-weightings. \u00a0Furthermore, one can also write (but for the benefit of the reader we will not) each of these vectors as real non-negative combinations of cuts of $H_1$. On the other hand, none of these vectors is in the integer cone of cuts of $H_1$ (this is just a (large) finite case check). \u00a0This last claim\u00a0was verified by our silent robot partner\u00a0Normaliz<\/a>\u00a0<\/em>[5], but can also be checked by humans\u00a0(as we do in the paper). Therefore, $H_1$ is not cut-Hilbert.<\/p>\n

\"\"<\/a>

Three different weightings of a\u00a0non-cut-Hilbert graph $H_2$. Black edges all have weight 1.<\/p><\/div>\n

Similarly, each of the three edge-weightings of the above graph $H_2$ show that $H_2$ is not cut-Hilbert. Now let $H_3$ be the 2-clique-sum of two copies of $K_{5}^{\\perp}$ along the distinguished edge $e$. Since\u00a0$H_3$ is a 2-clique-sum of cut-Hilbert graphs, $H_3$ is also cut-Hilbert. However, note that $H_1$ is obtained from $H_3$ by deleting an edge and $H_2$ is obtained from $H_3$ by subdividing an edge. This establishes Theorem 4, as promised.<\/p>\n

I will finish by discussing the matroid analogue of Question 2.<\/p>\n

Question 5.<\/strong> \u00a0For which matroids $M$ is the set of cocircuits of $M$ a Hilbert basis?<\/p>\n

Luis Goddyn and Marko Mitrovic (an NSERC undergraduate research student of Luis in 2013) made some interesting progress which I will briefly report here. Using\u00a0Normaliz,\u00a0<\/em>the\u00a0matroid\u00a0Sage<\/a>\u00a0package,<\/em>\u00a0and\u00a0<\/em>the catalogue<\/a>\u00a0of all matroids up to 9 elements,\u00a0they were able to determine all the non-cocircuit-Hilbert matroids up to 8 elements. \u00a0It turns out that there are\u00a0lots<\/em> of them. \u00a0In particular, of the 2198 matroids with up to 8 elements, 1305 are non-cocircuit-Hilbert. \u00a0Below is an image of the three smallest non-cocircuit-Hilbert matroids.<\/p>\n

\"threeSmallestNonH\"<\/a><\/p>\n

If one restricts to binary matroids, then the situation is more manageable. There are only two binary non-cocircuit-Hilbert matroids up to 8 elements, and interestingly, both of them are coextensions of the Fano matroid. \u00a0Therefore, the following problem may be doable.<\/p>\n

Problem 6.<\/strong> \u00a0Characterize the binary matroids whose set of cocircuits is a Hilbert basis.<\/p>\n

Note that Problem 6 is open even for graphs. \u00a0By Theorem 4, the set of cut-Hilbert graphs is not closed\u00a0under taking minors, so it does not have an excluded-minor characterization. However, perhaps there is an alternate nice\u00a0characterization.<\/p>\n

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

[1] F. R. Giles and W. R. Pulleyblank. \u00a0Total dual integrality and integer polyhedra. \u00a0Linear Algebra Appl.,\u00a0<\/em>25:191-196, 1979.<\/p>\n

[2] Brian Alspach, Luis Goddyn, and Cun Quan Zhang. \u00a0Graphs with the circuit cover property. Trans. Amer. Math. Soc.,\u00a0<\/em>344(1):131-154, 1994.<\/p>\n

[3] Monique Laurent. \u00a0Hilbert bases of cuts. \u00a0Discrete Math.,\u00a0<\/em>150(1-3):257-279, 1996.<\/p>\n

[4] Tanmay Deshpande, Luis Goddyn, and Tony Huynh. \u00a0On Hilbert bases of cuts.\u00a0arXiv<\/a>.<\/em><\/p>\n

[5] Winfred Bruns and Bogdan Ichim. \u00a0Normaliz: algorithms for affine monoids and rational cones. \u00a0J. Algebra,\u00a0<\/em>324(5):1098-1113, 2010.<\/p>\n","protected":false},"excerpt":{"rendered":"

Let $X$ be a set of vectors in $\\mathbb{R}^d$. \u00a0Three important objects related to\u00a0$X$ are the\u00a0cone, lattice,\u00a0and\u00a0integer cone generated by $X$. \u00a0These are (respectively), the set of all real non-negative combinations, the set of all integer combinations, and the set … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1228","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1228","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\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1228"}],"version-history":[{"count":59,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1228\/revisions"}],"predecessor-version":[{"id":1297,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1228\/revisions\/1297"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}