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
Youtube

(Part 1 is on Youtube as well)

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.

 

 

Online talk: Tony Huynh

Mon, August 31, 3pm ET (8pm BST, 7am Tue NZST)
Tony Huynh, Monash University
Subgraph densities in a surface
Youtube

Abstract:
We consider the following problem at the intersection of extremal and structural graph theory. Given a fixed graph $H$ and surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph that embeds in $\Sigma$? Here a copy means a subgraph isomorphic to $H$. Exact answers are known for some $H$ when $\Sigma$ is the sphere. Our main result answers the question for all $H$ and $\Sigma$ (up to a constant factor). We show that the answer is $\Theta(n^{f(H)})$ where $f(H)$ is a graph invariant called the flap number of $H$, which is independent of the surface $\Sigma$.

This is joint work with Gwenaël Joret and David Wood.

Online talk: Ahmad Abdi

Mon, August 24, 3pm ET (8pm BST, 7am Tue NZST)
Ahmad Abdi, London School of Economics
Ideal clutters and dyadic fractional packings
Youtube

Abstract:
A clutter is a finite family of finite sets where no set contains another one. Clutters form a very broad class of objects generalizing graphs and matroids in more than one way, and are also accompanied by notions of duality (more specifically, the blocking relation) and minor theory.

Most questions about clutters can be traced back to the study of three key parameters: the covering number, the fractional packing number, and the packing number, ordered from largest to smallest. The first two parameters are known to be equal, and efficiently computable, for the class of ideal clutters, an important class of clutters rooted in Combinatorial Optimization and Polyhedral Combinatorics.

In 1975, Seymour conjectured that for every ideal clutter, the fractional packing number can be attained not just by a fractional vector, but by a vector whose entries are dyadic rational numbers. As a first step, we prove this conjecture in the case when the fractional packing number is equal to 2; we also provide a quasi-polynomial time algorithm for finding the dyadic vector. Our proof techniques rely on the key insight that ideal clutters are so-called clean, i.e. they forbid two infinite classes of clutters as a minor, one coming from projective planes, and another coming from odd holes.

In this self-contained talk, after contextualizing Seymour’s conjecture, I shall motivate clean clutters and survey two important subclasses other than ideal clutters, namely, binary clutters (coming from binary matroids), and clutters without an intersecting family as a minor.

Based on joint work with Gérard Cornuéjols, Bertrand Guenin, and Levent Tunçel.

 

P.S. Upcoming speakers for the next month are now listed at the talks page.