Online talk: Alexey Pokrovskiy (non-standard day & time!)

We’re really excited to have Alexey Pokrovskiy speak on his fantastic recent result on Rota’s Basis Conjecture this upcoming week. This talk has been moved to be a part of the Tutte Colloquium at Waterloo and so will be held at a different day and time than usual. Here are the full details.

Friday, September 25, 1pm ET (6pm BST, 5am Tue NZST)
Alexey Pokrovskiy, Birkbeck, University of London
Rota’s Basis Conjecture holds asymptotically
Zoom
[Type the first ten characters of the usual password. Email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]

 

Abstract:
Rota’s Basis Conjecture is a well known problem, that states that for any collection of $n$ bases in a rank $n$ matroid, it is possible to decompose all the elements into $n$ disjoint rainbow bases. Here an asymptotic version of this is will be discussed – that it is possible to find $n – o(n)$ disjoint rainbow independent sets of size $n – o(n)$.

The World of Clean Clutters, I: Ideal Clutters

Guest post by Ahmad Abdi

You may have heard of Paul Seymour’s f-Flowing Conjecture on binary matroids, perhaps as alluded to in these detailed posts (I, II, III) by Dillon Mayhew, or in connection with weakly bipartite graphs, or directly from the source. 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.

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, where I’ll be able to talk about ideal clutters and binary 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.

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

The world of clean clutters
labelclass nameconjecture
1Ideal CluttersEvery clutter in this class has bounded chromatic number.
2Binary CluttersThe f-Flowing Conjecture
3Clutters without an Intersecting MinorThe $\tau=2$ Conjecture
The classes of clutters surveyed in this series of posts

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.

This post focuses on the class of Ideal Clutters.

1.

Clutters form the framework for my post. I’m grateful that Dillon has already laid the basics in these posts: I, II, III, 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.

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

A cover 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 if it does not contain another cover.

By design, the family of minimal covers of $\mathcal{C}$ forms another clutter over the same ground set. This clutter is called the blocker 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}$.

Our choice of terminology for “clutter” and “blocker” follows the convention set forth by Jack Edmonds and Ray Fulkerson in this 1970 paper. 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 and 1965 papers lay some of the foundational concepts in the study of clutters, predating the Edmonds-Fulkerson paper.

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 of $\mathcal{C}$ obtained after deleting $I$ and contracting $J$. This notion was coined in 1971 by Ray Fulkerson

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. 

Photo by Bill Cook

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 refers to this clutter as a port of $M$. He has shown that,

  • $b(\mathrm{port}(M,f)) = \mathrm{port}(M^\star,f)$ (Dillon proved this in his first post on clutters),
  • $\mathrm{port}(M,f)\setminus I/J = \mathrm{port}(M\setminus I/J,f)$ for disjoint $I,J\subseteq E-\{f\}$.

Thus, the two clutter notions are indeed extensions of matroid duality and matroid minors. One may have reached this conclusion alternatively by taking the clutter of bases, or circuits, of a matroid.

2.

Now that we’re done with the basics of Clutter Theory, we can move on to the main topic of this post: Ideal Clutters.

$\mathcal{C}$ is an ideal clutter if any of the following equivalent conditions are satisfied:

  1. Every vertex of the polyhedron $Q(\mathcal{C}):=\{x\in \mathbb{R}^E_+: x(C)\geq 1 ~ \forall C\in \mathcal{C}\}$ is integral. 
  2. For all cost vectors $c\in \mathbb{R}^E$, the linear program $$\text{minimize } c^\top x \text{ subject to } x\in Q(\mathcal{C})$$ if finite has an integral optimal solution.
  3. For all lengths $\ell\in \mathbb{R}^E_+$ and widths $w\in \mathbb{R}^E_+$, the width-length inequality holds: $$\min\{\ell(C):C\in \mathcal{C}\}\cdot \min\{w(B):B\in b(\mathcal{C})\}\leq \ell^\top w.$$

Here, $x(C)$ is short-hand notation for $\sum_{e\in C}x_e$.

The term ideal was coined in 1994 by Gérard Cornuéjols and Beth Novick, who used #1 as the main definition. This concept has been dubbed in the literature as the weak max-flow min-cut property, the max-flow min-cut property, the width-length property, or even the Fulkersonian property, all of which only speaks to the rich and tangled history of the concept, hinted at by the following table, displaying various classes of ideal clutters in the literature.

yearreferenceExamples of ideal clutters
1927
1956
1979
Menger
Ford and Fulkerson
Lehman
st-paths of a graph of a graph
1931König, Egreváryedges of a simple, bipartite graph
1938Gallai (a.k.a. Grünwald)directed st-paths of a digraph
1956Hoffman and Kruskaltotally unimodular matrices
1967Edmondsrooted arborescences of a digraph
1972Bergebalanced matrices
1973Edmonds and JohnsonT-joins of a graft
1979Lucchesi and Youngerdicuts of a digraph
1985
1994
Prodon
Goemans
Steiner cuts of a series-parallel digraph
2001Gueninodd circuits of a signed graph without an odd-K5 minor
2020Abdi, Cornuéjols, Guričanová and Leecube-ideal sets
A historical account of some classes of ideal clutters

In 1963 Alfred Lehman, inspired by Moore and Shannon’s landmark work on unreliable communication networks, studied the width-length inequality, condition #3, and proved it equivalent to #1, and also to what he called the max-flow min-cut equality, #2. In case you’re wondering what the terminology refers to, apply Strong Duality to the LP in #2.

The characterization #3 of idealness is particularly interesting due to its consequence that

the blocker of an ideal clutter is also ideal.

The blocking relation between clutters was later extended to polyhedra by Fulkerson, as documented in this RAND report. In the 1968 memorandum, he develops a geometric view of the blocking relation and gives another proof that idealness is closed under the blocking relation. Sadly, some authors fail to cite Lehman for this fact and only cite Fulkerson’s 1971 published version of the report, even though Ray himself cites Lehman for the fact. Understandably, Lehman did not put his 1963 memorandum in print until 1979!

3.

Not only is idealness closed under the blocking relation, but 

every minor of an ideal clutter is also ideal.

I leave the proof of this as an exercise for the reader; the only thing I’ll say is that there are three proofs, one corresponding to each characterization of idealness.

Given the fact above, a natural question arises:

What are the excluded minors for the class of ideal clutters?

A clutter is minimally non-ideal (mni) if it is non-ideal but every proper minor is ideal. Observe that a clutter is ideal if, and only if, it has no mni minor. In particular, the excluded minors for the class of ideal clutters are precisely the mni clutters.

Note that as idealness is closed under the blocking relation, and deletion/contraction corresponds to contraction/deletion in the blocker, the blocker of every mni clutter is another mni clutter.

In 1963, Lehman found four classes of mni minors, three of which formed infinite classes:

nameelementsmembersnotes
$\mathbb{L}_7$1,2,3,4,5,6,7{1,2,3}, {1,4,5},{1,6,7}, {2,4,7}, {2,5,6}, {3,4,6}, {3,5,7}The elements/members correspond to the points/lines of the Fano plane.

$b(\mathbb{L}_7) =\mathbb{L}_7$
$\Delta_n$, n=3,4,5,…1,2,3,…,n{1,2},{1,3},…,{1,n} and {2,3,…,n}The elements/members correspond to the points/lines of a degenerate projective plane.

$b(\Delta_n) =\Delta_n$
Odd hole of dimension n, n=5,7,9,…1,2,3,…,n{1,2},{2,3},{3,4}, …,{n-1,n},{n,1}In the literature, $\Delta_3$ is sometimes called an odd hole, too.
The blocker of an odd hole 1,2,3,…,nToo many to list.Every member has cardinality at least $\frac{n+1}{2}$.
The minimally non-ideal clutters found by Lehman in 1963

Lehman seems to have been discouraged by the multiplicity of the excluded minors:

“Whether or not this list is complete, the multiplicity of minimal matrices seems to preclude their usefulness as a W-L matrix characterization. (Cf. author’s foreword.)” 

These projective planes give rise to mni clutters.

In the foreword, which was added 17 years later in 1979 when the paper was finally published, he writes:

“More is known about minimal non-W-L matrices. U. Peled has found several additional classes of matrices which are also classically known in other contexts.”

I’m not sure what additional classes Uri Peled had found at the time but to this day, there are over 1500 small examples of mni clutters: See the paper by Cornuejols and Novick, as well as this paper by Lütolf and Margot. A new infinite class of mni clutters was also found 9 years ago (and don’t forget, the blocking clutters form another infinite class).

Odd holes, and their blockers, also give rise to mni clutters.

Lehman continues in the foreword:

“A consequence of a recent matrix theorem is apparently that the degenerate projective planes [i.e. the deltas] are the only minimal matrices requiring unequal weights.”

More specifically, the consequence of the “matrix theorem” states that for a minimally non-ideal clutter $\mathcal{C}$ different from $\Delta_4$, $\Delta_5$,…,, the width-length inequality is violated for $w=\ell={\bf 1}.$ Whereas for the mni clutters $\Delta_4$, $\Delta_5$,…, the width-length inequality is satisfied for $w=\ell={\bf 1}$.

The foreword above is the humblest of hints to one of the deepest results on ideal clutters, a result that dusted in Lehman’s desk drawer for over 10 years, until it finally appeared in 1990 at the request of Bill Cook and Paul Seymour in the first issue of DIMACS Series. A year later, Lehman won a Fulkerson prize for this “matrix theorem”. If you’re curious about the statement of this theorem, I urge you to read Chapter 9 of my notes, and in particular, Theorem 9.12.

A snapshot of Lehman’s handwritten manuscript on the special role of the deltas among minimally non-ideal clutters.

If you, like Lehman himself, are skeptical about the usefulness of his matrix theorem, the next post is bound to change your mind.

4.

Before I conclude with ideal clutters, let me leave you with a conjecture on idealness that Gérard Cornuéjols, Tony Huynh, Dabeen Lee, and I made in a paper whose extended abstract appeared in the proceedings of IPCO 2020, held online this past summer at the London School of Economics.

Suppose $\mathcal{C}$ has no member of cardinality one. A proper colouring of $\mathcal{C}$ is an assignment of colours to the elements so that there is no monochromatic member, that is, it consists of an assignment of an integer $\phi(e)$ to every element $e$ such that $\{\phi(e):e\in C\}$ has cardinality at least two. The chromatic number of $\mathcal{C}$ is the minimum number of colours used in a proper colouring.

Conjecture. There exists an integer $k\geq 4$ such that every ideal clutter without a member of cardinality one has chromatic number at most $k$.

Why $k$ should be at least four, and part of the origins of the conjecture, are explained in the paper. I hope the abrupt appearance of the conjecture is made up for by its utter simplicity.

Thank you for sticking around long enough to read this sentence. If you have any questions, feel free to ask them in the comment section below.

Ahmad Abdi, London School of Economics

Online talk: Oliver Lorscheid

Mon, September 14, 3pm ET (8pm BST, 7am Tue NZST)
Oliver Lorscheid, Instituto Nacional de Matemática Pura e Aplicada
Foundations of Matroids without Large Uniform Minors, Part 2
Zoom
[email rose.mccarty ~at~ uwaterloo ~.~ ca if you need the password]
(Part 1 is on Youtube)

Abstract:
In this talk, we take a look under the hood of last week’s talk by Matt Baker: we inspect the foundation of a matroid.

The first desired properties follow readily from its definition: the foundation represents the rescaling classes of the matroid and shows a functorial behaviour with respect to minors and dualization. It requires however deep results by Tutte, Dress-Wenzel and Gelfand-Rybnikov-Stone to gain an understanding of the foundation in terms of generators and relations.

For small matroids, this allows us to determine the foundation explicitly. This, in turn, lets us derive the structure theorem for foundations of matroids without large uniform minors, which is the central result behind the applications from last week.

In a concluding part of the talk, we turn to potential future directions and open problems.

 

 

Online talk: Matt Baker

Mon, September 7, 3pm ET (8pm BST, 7am Tue NZST)
Matt Baker, Georgia Tech
Foundations of Matroids without Large Uniform Minors, Part 1
Youtube

Abstract:
Matroid theorists are of course very interested in questions concerning representability of matroids over fields. More generally, one can ask about representability over partial fields in the sense of Semple and Whittle. Pendavingh and van Zwam introduced the universal partial field of a matroid $M$, which governs the representations of $M$ over all partial fields. Unfortunately, almost all matroids are not representable over any partial field, and in this case, the universal partial field gives no information.

Oliver Lorscheid and I have introduced a generalization of the universal partial field which we call the foundation of a matroid. The foundation of $M$ is a type of algebraic object which we call a pasture; pastures include both hyperfields and partial fields. Pastures form a natural class of field-like objects within Lorscheid’s theory of ordered blueprints, and they have desirable categorical properties (e.g., existence of products and coproducts) that make them a natural context in which to study algebraic invariants of matroids. The foundation of a matroid $M$ represents the functor taking a pasture $F$ to the set of rescaling equivalence classes of $F$-representations of $M$; in particular, $M$ is representable over a pasture $F$ if and only if there is a homomorphism from the foundation of $M$ to $F$.

As a particular application of this point of view, I will explain the classification which Lorscheid and I have recently obtained of all possible foundations for matroids having no $U(2,5)$ or $U(3,5)$ minors. The proof of this classification theorem relies crucially on Tutte’s Homotopy Theorem and the theory of cross-ratios for matroids. Among other things, our classification provides a short conceptual proof of the 1997 theorem of Lee and Scobee which says that a matroid is both ternary and orientable if and only if it is dyadic.

This is part 1 of a series of two talks. The second talk will be given the following week by Oliver Lorscheid.