{"id":2802,"date":"2020-09-16T13:36:23","date_gmt":"2020-09-16T17:36:23","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2802"},"modified":"2020-09-17T06:07:43","modified_gmt":"2020-09-17T10:07:43","slug":"the-world-of-clean-clutters-i-ideal-clutters","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2802","title":{"rendered":"The World of Clean Clutters, I: Ideal Clutters"},"content":{"rendered":"\n

Guest post by<\/em> Ahmad Abdi<\/a><\/p>\n\n\n\n

You may have heard of Paul Seymour’s f-Flowing Conjecture on binary matroids, perhaps as alluded to in these detailed posts (I<\/a>, II<\/a>, III<\/a>) by Dillon Mayhew, or in connection with weakly bipartite graphs<\/a>, or directly from the source<\/a>. If you haven’t heard of it, or have but don’t remember much, or better yet, know it well but need a new lens to view the problem, it’s your lucky day! I’m here to tell you all about it. <\/p>\n\n\n\n

For you to fully appreciate the conjecture though, I’ll have to put it in the proper context. That’ll require me to take you outside your comfort zone of matroids to the larger world of clutters<\/em>, where I’ll be able to talk about ideal<\/em> clutters and binary<\/em> clutters. I’ll then be able to present the f-Flowing Conjecture, the latest progress made towards resolving it, as well as the tools that have made that possible.<\/p>\n\n\n\n

But I won’t stop there. I’ll talk about an adjacent, intriguing class of clutters, those without an intersecting clutter <\/em>as a minor, and then move my way up to the all-encompassing class of clean clutters<\/em> (an oxymoron, I know!): a minor-closed class whose excluded minors come from degenerate projective planes<\/em> and odd holes<\/em>.<\/p>\n\n\n\n

\"\"
The world of clean clutters<\/figcaption><\/figure><\/div>\n\n\n\n
label<\/th>class name<\/th>conjecture<\/th><\/tr><\/thead>
1<\/td>Ideal Clutters<\/strong><\/td>Every clutter in this class has bounded chromatic number.<\/strong><\/td><\/tr>
2<\/td>Binary Clutters<\/td>The f-Flowing Conjecture<\/td><\/tr>
3<\/td>Clutters without an Intersecting Minor<\/td>The $\\tau=2$ Conjecture<\/td><\/tr><\/tbody><\/table>
The classes of clutters surveyed in this series of posts<\/figcaption><\/figure>\n\n\n\n

This series of posts is meant to provide a non-technical survey of the classes displayed below. I shall provide a historical account of each class, hopefully making it clear why the class is interesting, and then provide just one exciting conjecture to stimulate further research on the class.<\/p>\n\n\n\n

This post focuses on the class of Ideal Clutters<\/em>.<\/p>\n\n\n\n

1.<\/p>\n\n\n\n

Clutters<\/em> form the framework for my post. I’m grateful that Dillon has already laid the basics in these posts: I<\/a>, II<\/a>, III<\/a>, but let me recall a few definitions, as well as make some new ones; the careful reader will notice that my notation is slightly but harmlessly different from Dillon’s.<\/p>\n\n\n\n

Let E be a finite set of elements<\/em>, and let $\\mathcal{C}$ be a family of subsets of E called members<\/em>. $\\mathcal{C}$ is a clutter<\/em> over ground set<\/em> E if no member contains another one.<\/p>\n\n\n\n

A cover<\/em> of $\\mathcal{C}$ is a subset of E that intersects every member. Every superset of a cover is another cover, so not all covers are interesting from a clutter theoretic perspective, thereby leading us to the forthcoming adjective. A cover is minimal<\/em> if it does not contain another cover.<\/p>\n\n\n\n

By design, the family of minimal covers of $\\mathcal{C}$ forms another clutter over the same ground set. This clutter is called the blocker<\/em> of $\\mathcal{C}$, and is denoted $b(\\mathcal{C})$. Dillon has already proved the basic fact that the blocking relation is an involution, that is, $b(b(\\mathcal{C}))=\\mathcal{C}$.<\/p>\n\n\n\n

Our choice of terminology for “clutter” and “blocker” follows the convention set forth by Jack Edmonds and Ray Fulkerson in this 1970 paper<\/a>. The origin of the blocking relation, however, dates earlier to the theory of games, wherein the members of $\\mathcal{C}$ represent the minimal winning coalitions, while the blocker takes an adversarial position, collecting all the minimal hitting sets, meant to tear down every winning coalition. For instance, these important 1958<\/a> and 1965<\/a> papers lay some of the foundational concepts in the study of clutters, predating the Edmonds-Fulkerson paper.<\/p>\n\n\n\n

Given disjoint subsets $I,J\\subseteq E$, $\\mathcal{C}\\setminus I\/J$ denotes the clutter over ground set $E-(I\\cup J)$ whose members are the inclusionwise minimal sets of $\\{C-J: C\\in \\mathcal{C}, C\\cap I=\\emptyset\\}$. This clutter is called the minor<\/em> of $\\mathcal{C}$ obtained after deleting<\/em> $I$ and contracting<\/em> $J$. This notion was coined in 1971 by Ray Fulkerson<\/a>. <\/p>\n\n\n\n

You might find the notions of the blocker and clutter minors reminiscent of matroid duality and matroid minors, in which case you’d be happily surprised that the former two notions may in fact be viewed as extensions of the latter two. <\/p>\n\n\n\n

\"\"
Photo by Bill Cook<\/figcaption><\/figure>\n\n\n\n
\n
\n

For example, let $M$ be a matroid over ground set $E$, and take an element $f\\in E$. Denote by $\\mathrm{port}(M,f)$ the clutter over ground set $E-\\{f\\}$ whose members are $$\\{C-\\{f\\} : C \\text{ is a circuit of $M$ containing $f$}\\}.$$ Seymour<\/a> refers to this clutter as a port of $M$<\/em>. He has shown that,<\/p>\n\n\n\n