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.

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.

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.

Mon, August 17, 3pm ET (8pm BST, 7am Tue NZST)
Sophie Spirkl, University of Waterloo
A graph-based introduction to the chromatic symmetric function
Youtube

Abstract:
The chromatic symmetric function is a generalization of the chromatic polynomial, and has been studied extensively, mostly in algebraic combinatorics. I’ll give an introduction to the chromatic symmetric function from a graph theory point of view, including some results and open questions.

Joint work with Logan Crew.