Look here for the schedule.
Immanuel Albrecht
Abstract: According to Oxley, the matroid $P_8^{=}$ arises from $P_8$ by relaxing its pair of disjoint circuit-hyperplanes and is a forbidden minor for GF(4)-representability, it is neither a transversal matroid nor the dual of a transversal matroid. It is not known whether $P_8^{=}$ is a gammoid and we want to try to find it out.
Algebraic matroids and Frobenius flocks
Guus Bollen
Abstract: In characteristic zero, any algebraic matroid has a linear representation. In positive characteristic, this no longer holds. As an alternative, we introduce the notion of a Frobenius flock. Each algebraic matroid can be represented by a Frobenius flock. Eventually, we want to use Frobenius flocks to help determine whether or not certain matroids are algebraic over certain fields.
A New Perspective on the $\mathcal{G}$-Invariant of a Matroid
Joseph E. Bonin
Abstract: The $\mathcal{G}$-invariant of a matroid was introduced by Derksen (2009), who showed that it properly generalizes the Tutte polynomial. Akin to the recipe theorem, which says that the Tutte polynomial is universal among invariants that satisfy deletion-contraction rules, Derksen and Fink (2010) showed that the $\mathcal{G}$-invariant is universal among invariants that satisfy an inclusion/exclusion-like property on matroid base polytopes.
In this joint work with Joseph Kung, we give a new view of this invariant and explore its implications. We show that the $\mathcal{G}$-invariant of a matroid $M$ of rank $r$ is equivalent to having, for each sequence $a_0,a_1,\ldots,a_r$, the number of flags of flats $X_0\subset X_1\subset\cdots\subset X_r$ of $M$ with $|X_0|=a_0$ and $|X_i-X_{i-1}|=a_i$ for $i>0$. With this view, we can determine the effect of some matroid constructions, such as taking $q$-cones, on the $\mathcal{G}$-invariant, and we can identify some of the information that the $\mathcal{G}$-invariant picks up that the Tutte polynomial does not, such as the number of circuits and cocircuits of any given size, and the number of cyclic flats of any given rank and size. Also, the $\mathcal{G}$-invariant of a matroid can be reconstructed from the multi-set of $\mathcal{G}$-invariants of the restrictions to hyperplanes. Still, strengthening what J. Eberhardt proved for the Tutte polynomial, the $\mathcal{G}$-invariant is determined by relatively little information, namely, by just the isomorphism type of the lattice of cyclic flats along with the rank and size of each cyclic flat.
Nathan Bowler
Abstract: I’ll explain how the familiar theory of regular matroids looks when we allow the matroids in question to be infinite. I’ll start by defining infinite regular matroids and covering their basic properties, then cover a couple of key topics in a little more depth: how the elementary submodel method can be used to extend a classical partitioning theorem of Nash Williams from infinite directed graphs to finitary regular matroids, and the open question of whether Farkas’s Lemma holds for all infinite regular matroids.
The Structure of Graphs Without Even Holes or Odd Pans
Kathie Cameron
Abstract: A hole is a chordless cycle with at least four vertices. A pan is a graph consisting of a hole with one additional vertex adjacent to one vertex of the hole. Where $G$ and $H$ are graphs, $G$ is called $H$-free if $G$ has no induced subgraph isomorphic to $H$. Pan-free graphs generalize claw-free graphs which generalize line-graphs, and thus independent sets in pan-free graphs generalize matchings and colourings of pan-free graphs generalize edge-colourings. Minty’s (1980) polytime algorithm for maximum weight independent set in claw-free graphs led to much research on claw-free graphs, including the generalization of it by Brandstädt, Lozin and Mosca (2010) to pan-free graphs. We show that pan-free even-hole-free graphs can be decomposed by clique-cutsets into joins of cliques and specially-structured unit circular-arc graphs. Finding a minimum colouring of pan-free graphs is NP-hard and the complexity of colouring even-hole-free graphs is unknown. Our structure theorem is the basis of our $O(nm)$ certifying algorithm for recognizing pan-free even-hole-free graphs and for our $O(n^3)$ algorithm for colouring them.
Joint work with Steven Chaplick, Chính T. Hòang.
Dense PG(t-1,2)-free binary matroids
Rutger Campbell
Abstract: Turan’s theorem says that, for a positive integer $t$, the densest $K_t$-free graphs are $(t-1)$-colourable. We discuss what we know about the structure of a $K_t$-free graph that has density close to the maximum. We present the analogous problem for binary matroids and give similar results.
Carolyn Chun
Abstract: We give a brief discussion of some objects that give rise to delta-matroids.
Relaxations of quaternary matroids
Ben Clark
Abstract: We describe the structure of the quaternary matroids with a circuit-hyperplane whose relaxation is a quaternary matroid. This is joint work with James Oxley and Stefan van Zwam.
Properties of almost all sparse paving matroids
Will Critchlow
Abstract: Whilst random graphs are easily and intuitively generated, we have no such simple formulation of the “random” matroid. This means that for many straightforward asymptotic results in graph theory, the analagous result for matroids is considerably harder. In this talk we shall consider the question of which minors are contained in asymptotically almost all matroids, and show that some progress can be made by restricting to a large subclass of matroids, the sparse paving matroids.
Tw-fragility and some related questions
Zdenek Dvorak
Abstract: Tw-fragility is a property of graph classes inspired by design of approximation algorithms, as well as structural considerations (“distance” to bounded tree-width). A class C of graphs is tw-fragile if for every positive integer k, there exists an integer r as follows: for every graph G from C, there exist k disjoint subsets of its vertices, such that removing any of them from G decreases its treewidth to at most r. As an example, all proper minor-closed classes of graphs are known to have this property.
Characterizing tw-fragile classes is a tough problem, in particular due to existence of classes (such as 3-dimensional grids) whose non-tw-fragility is only established using surprisingly involved arguments. However, a fractional version of the property seems easier to handle. We consider the question whether all hereditary classes with strongly sublinear separators are fractionally tw-fragile, and present some results supporting this conjecture.
Structural properties of laminar matroids
Tara Fife
Abstract: A laminar family is a collection of sets such that if two sets intersect, one is contained in the other. A laminar matroid is defined in terms of a laminar family $\mathscr{A}$ and a capacity function $c:\mathscr{A}\rightarrow \mathbb{N}$, a set $I$ being independent if $|I\cap A|\leq c(A)$ for all $A\in\mathscr{A}$. It is not hard to show that the class of laminar matroids is minor closed. This talk will describe the set of excluded minors for the class. In addition, it will present a way to construct all laminar matroids using basic operations and will compare the class of laminar matroids to other well-known classes of matroids. This is joint work with James Oxley.
Almost balanced biased graphical representations of 4-connected frame matroids are essentially unique
Daryl Funk
Abstract: Let M be a frame matroid, with biased graphical representation (G,B). If G is 3-connected and has a vertex whose deletion leaves no cycle that is not a circuit of M, then we may determine all biased graphical representations of M. Moreover, if M is 4-connected, then M has a unique frame, and all biased graphical representations of M differ from G only by the substitution of a few edges with loop-edges or vice versa.
Jim Geelen
Abstract: A matroid $M$ is $N$-fragile if $N$ is a minor of $M$ and there is no element $e$ of $M$ such that $N$ is a minor of both $M\backslash e$ and and $M/ e$. We prove that binary $N$-fragile matroids have bounded path-width. The proof is short and self-contained. This is joint work with Bert Gerards and Geoff Whittle.
Templates for minor-closed classes of binary matroids
Kevin Grace
Abstract: Matroids conforming to a binary frame template are obtained by altering a graphic matroid in a certain way. We introduce a preorder on binary frame templates and a list of minimal nontrivial templates with respect to this preorder. An application of this result is that all highly connected 1-flowing matroids of sufficient size are either graphic or cographic. Other applications can be made to growth rates of minor-closed classes of binary matroids. The classes of even-cycle matroids and even-cut matroids each have hundreds of excluded minors. Our final application is that the number of excluded minors for these classes can be drastically reduced if we consider only the highly connected matroids of sufficient size.
A graph result looking for a matroid generalization
Gary Gordon
Abstract: The proportion of spanning trees among all subtrees of $K_n$ is asymptotically $e^{-1/e} \approx 0.69.$ What is the right matroid generalization of this result? A few possibilities will be discussed.
Chromatic polynomial for the spike matroids
Rhiannon Hall
Abstract: For $n\geq 3$, an $n$-spike is a matroid whose groundset can be partitioned into $n$ pairs called legs, such that the union of any two legs is both a circuit and a cocircuit. A spike may be extended by an element called a tip and/or coextended by an element called a cotip such that the union of the tip with each leg forms a triangle, and the union of the cotip with each leg forms a triad.
Spikes have arisen in many areas of matroid theory, sometimes notoriously, such as when Oxley, Vertigan & Whittle used them to disprove Kahn’s conjecture that the number of inequivalent representations of $3$-connected matroids over any finite field $GF(q)$ would be bounded above by some value $n(q)$.
In this talk, I will present the characteristic polynomials, $\chi(M;\lambda)$, for the four categories of spikes: those with a tip; a cotip; both; or neither. I will also outline a proof that the zeros of these characteristic polynomials are bounded above by $\lambda=4$.
Q[x]-representable Excluded Minors for Q-Representable Matroids of Rank Three
Hidefumi Hiraishi
Abstract: While any minor-closed class of graphs is characterized by a finite list of excluded minors by Robertson-Seymour graph minor theorem, such a concise characterization by excluded minors does not always hold on matroids. The class of matroids representable over a given in finite field is well-known to have an in finite number of excluded minors. In this talk, we show that, for any algebraic element x over the rational field Q whose minimal polynomial is degree 2, the class of matroids representable over Q also has in finitely many Q[x]-representable excluded minors even in rank 3. This implies that the characterization of Q-representable matroids by excluded minors is difficult even within Q[x]-representable matroids. This is joint work with Sonoko Moriyama.
Sticky matroids and Kantor’s conjecture
Winfried Hochstättler
Abstract: A matroid is sticky if for any two of its extensions there exists an amalgam. The sticky matroid conjecture (Polyak, Turzik 1982) asserts that a matroid is sticky if and only if it is modular.
Kantor conjectured 1974 that a finite rank 4 matroid where any two hyperplanes intersect in a line does not possess the Vamos-matroid as a restriction, and presented a counterexample for the infinite case.
Let us say that a matroid has a non-trivial extension, if it has an extension which decreases the modular defect of a non-modular pair. Bachem and Kern 1987 gave a (flawed) proof that a matroid which has a non-trivial extension decreasing the modular defect of a line and a hyperplane is not sticky. The flaw was pointed out and fixed by Bonin in 2011.
Conversely, we prove that a rank 4 matroid which does not admit a non-trivial extension is sticky. As a consequence we get that the sticky matroid conjecture and Kantor’s conjecture are equivalent. Moreover, we derive an example showing that the sticky matroid conjecture fails in the infinite case.
joint work with Michael Wilhelmi
The matroid secretary problem for minor-closed classes and random matroids
Tony Huynh
Abstract: We prove that for every proper minor-closed class of matroids representable over a prime field, there exists a constant-competitive matroid secretary algorithm. This result relies on the extremely powerful matroid minor structure theory developed by Geelen, Gerards and Whittle.
Benson Joeris
Abstract: A frame matrix is a matrix with at most two non-zero entries in each column. We give a polynomial-time algorithm to determine whether a given matrix is row-equivalent to a frame matrix. Over the two element field, frame matrices are precisely the incidence matrices of graphs, so our algorithm recognizes whether a given binary matrix is graphic, a problem originally solved by Tutte in 1960. In this talk I will discuss motivation for this problem and give an overview of the algorithm. This is joint work with Rong Chen, Jim Geelen, and Peter Nelson.
Gwenaël Joret
Abstract: In this talk we will look at posets and their dimension through the lens of the Nesetril-Ossona de Mendez theory of sparsity for graphs. The type of questions studied here are of the following form: Given some fixed sparse class of graphs, is it true that posets whose cover graphs are in the class have dimension bounded in terms of their height? This is the case for instance for planar graphs, and more generally for graphs excluding a fixed minor.
First I will give a very brief introduction to this area (no knowledge of posets needed) and mention a result obtained jointly with Piotr Micek and Veit Wiechert that the above property holds more generally for every class with bounded expansion. Then I will try to motivate and advertise a conjecture of ours, that this property provides in fact a new characterization of classes with bounded expansion.
Defining the q-analogue of a matroid
Relinde Jurrius
Abstract: The combinatorial concept of q-analogues studies, roughly speaking, what happens if we generalize from finite sets to finite spaces. The motivation for defining the q-analogue of matroid comes from network coding. The q-analogue of a linear code is a rank metric code: a type of error-correcting codes used in network coding. Since the weight enumerator of a linear code has a q-analogue, we ask ourselves if there is also a q analogue for the link between the weight enumerator of a linear code and the Tutte polynomial of the associated matroid. We will not answer that question here, but focus on the first step: we define a q-matroid, the q-analogue of a matroid.
A strong feature of matroids is that they have several cryptomorphic definitions, such as the axiom systems for independent sets, bases, and the rank function. These definitions all have a q-analogue, however, these q-analogues are not always equivalent! To solve this problem, we first have to ask ourselves the question: what properties do we want a q matroid to have? We think a q-matroid should “behave nicely” under deletion, contraction, and duality. Also, we want the duality to coincide with duality in rank metric codes, which are our main examples of q-matroids.
In this talk, we will discuss the problems and possible solutions concerned with the different ways to define a q-matroid, illustrated by examples.
Joint work with Ruud Pellikaan
On a question of Alon and Mohar
Ross Kang
Abstract: Alon and Mohar posed the following: among all graphs $G$ of maximum degree at most $d$ and girth at least $g$, what is the largest possible value of $\chi(G^t)$, the chromatic number of the $t$th power of $G$? With respect to this problem and related questions, we can provide upper bounds on $\chi(G^t)$. For instance, we show that the chromatic number of the cube of a graph of maximum degree at most $d$ containing no cycle of length $8$ is at most $cd^3/\log d$ for some fixed constant $c>0$. We also discuss to what extent these bounds are best possible.
This is based on joint work with François Pirot (ENSL).
Sandra Kingan
Abstract: We present an approach to matroid theory that covers some of the major theorems from an algorithmic point of view. This approach leads to surprising improvements on existing results and completely new ones. For example, the Splitter Theorem establishes that (with a few exceptions) if M is a 3-connected graph with a 3-connected minor N, then we can construct M from N by a sequence of 3-connected single-element extensions and coextensions. The Strong Splitter Theorem enhances this theorem to the best possible result. It was obtained by thinking of single-element extensions and coextensions in a manner different from the prevailing notion. Likewise the Decomposition Theorem was also enhanced to best possible. This talk will focus on these two results and their applications.
A chain theorem for triangle-free 3-connected matroids
Manoel Lemos
Abstract: In 2007, Kriesell established a chain theorem for triangle-free 3-connected graphs. Any triangle-free 3-connected graph can be reduced to a double-wheel or to $K_{3,3}$ by performing a sequence of simple operations without leaving the class of triangle-free 3-connected graphs. Double-wheels define the only infinite family of graphs that are irreducible with respect to these simple operations.
In 2013, Lemos extended Kriesell’s theorem for matroids. In this case, there are four infinite families of irreducible matroids.
Recently, we improve these results by proving that one of Kriesell’s reduction operations can be avoided provided the number of families of irreducible matroids are increased by four.
A proof of the Barát-Thomassen Conjecture
Martin Merker
Abstract: Barát and Thomassen conjectured in 2006 that for every tree $T$ there exists a natural number $k(T)$ such that the following holds: If $G$ is a $k(T)$-edge-connected simple graph with size divisible by the size of $T$, then $G$ can be edge-decomposed into subgraphs isomorphic to $T$. Previously, the conjecture has been verified for certain classes of trees such as paths, stars, and a class of bistars. We can now prove the conjecture for all trees by combining recent results on the existence of modulo $k$-orientations with probabilistic methods. I will give an overview of the full proof and discuss the tools that are used.
Joint work with Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, and Stéphan Thomassé.
Matroids, graphs in surfaces, and the Tutte polynomial
Iain Moffatt
Abstract: I will describe some new ways in which matroidal objects can be associated with graphs embedded in surfaces, emphasising applications to the theory of graph polynomials. The motivation for this work comes from the theory of the Tutte polynomial, as follows.
The Tutte polynomial is one of the most important, and best studied, graph polynomials. It is important not only because it encodes a large amount of combinatorial information about a graph, but also because of its applications to areas such as statistical physics and knot theory. Because of its importance, the Tutte polynomial has been extended from graphs to other combinatorial objects. I will consider three different extensions of the Tutte polynomial from graphs to graphs in surfaces. These are due to M. Las Vergnas (1978), B. Bollobás and O. Riordan (2002), and V. Kruskal (2011).
In this talk I will present a matroidal framework for these topological graph polynomials, and will demonstrate the advantages of this framework by showing that desirable properties of the Tutte polynomial that do not hold for topological Tutte polynomials do hold for their matroidal analogues. As an added bonus, we’ll see that the matroidal framework explains why there are three different extensions of the Tutte polynomial to embedded graphs rather than just one.
This is joint work with Ben Smith.
Almost all matroids are non-representable
Peter Nelson
Abstract: We give an upper bound on the number of representable matroids that proves that almost all matroids on n elements are non-representable. We also discuss lower bounds in the same vein.
Mike Newman
Abstract: Consider a separation $(A,B)$ of $M$. Two subsets $X_1$ and $X_2$ on one side are said to be equivalent if $\Pi(X_1,Y)=\Pi(X_2,Y)$ for every $Y$ on the other side. A class $\mathcal{M}$ is \emph{pigeonhole} if it has the property that there if a function $f(k)$ such that for $M \in \mathcal{M}$ of branch-width $k$, every displayed $k$-separation has at most $f(k)$ equivalence classes.
Consider a branch decomposition of $M$ of width $k$. A tree automaton assigns states (from a finite alphabet that depends on $k$) to the leaves of the underlying tree and propagates states inwards towards a root using a transition function. Depending on the final state of the root the tree automaton accepts or rejects. If an automaton accepts exactly those matroids that satisfy a monadic second order sentence $\psi$ then we say that the automaton decides $\psi$. A class $\mathcal{M}$ is \emph{automatic} is for every $k$, every monadic second order $\psi$ is decidable for $M \in \mathcal{M}$ of branch-width $k$.
Both pigeonhole classes and automatic classes can be thought of as permitting only a bounded amount of “information” across (displayed) separations. It turns out that these two conditions are equivalent.
(Joint work with Daryl Funk, Dillon Mayhew, Geoff Whittle.)
Minimum Area of Rectangle Visibility Graphs
Nancy Neudauer
Abstract: A graph $G$ is a rectangle visibility graph if the vertices can be represented by rectangles in the plane, parallel to the $x$ and $y$-axes, with edges in $G$ whenever two rectangles can “see” each other. Only some graphs are representable as a rectangle visibility graph. For example, it is known that
(i) If $G$ is an rvg, it has at most $6n – 20$ edges;
(ii) $G$ has thickness at most two, so chromatic number at most 12 (not sharp);
(iii) $K_{p,q}$ is not an rvg if $p>4$, where $p\leq q$.
We consider the smallest area required for a rectangle visibility graph. We also consider which graphs are possible when restrictions are put on one dimension (the smaller) of the rectangle representation area, say the height.
Recent results on delta-matroids
Steve Noble
Abstract: We present progress on extending various matroid results to delta-matroids, in particular results concerning connectivity, two-sums, modular cuts and counting the number of labelled delta-matroids.
Inductive tools for $3$-connected $2$-polymatroids
James Oxley
Abstract: Tutte’s Wheels-and-Whirls Theorem and Seymour’s Splitter Theorem are basic inductive tools for dealing with $3$-connected matroids. Every matroid is a $2$-polymatroid, and such structures model both sets of points and lines in a projective space and sets of edges in a graph. The rank definitions of deletion and contraction for matroids give corresponding operations for $2$-polymatroids. But, unless one uses some reduction operation in addition to deletion and contraction, the set of minimal $2$-polymatroids that are not representable over a fixed field ${\mathbb F}$ is infinite, irrespective of whether ${\mathbb F}$ is finite or infinite. This talk will present an analogue of the Wheels-and-Whirls Theorem for $2$-polymatroids and will discuss progress towards a Splitter Theorem. This work is joint with Charles Semple and Geoff Whittle.
Properties of almost all matroids
Rudi Pendavingh
Abstract: We show that asymptotically as $n \rightarrow \infty$, almost all matroids on $n$ elements
- have connectivity at least $\Omega(\sqrt{\log(n)})$
- have girth at least $\Omega(\log{n})$
- have $U_{k, 2k}$ as a minor, for some $k\geq \Omega(\log{n})$
- do not arise as the truncation of another matroid.
Our proof is based on a method for writing compressed descriptions of a matroid, which allows bounding the number of matroids in a class relative to the number of sparse paving matroids.
This is joint work with Jorn van der Pol. Our paper is available on http://arxiv.org/abs/1602.04763
Decomposition of signed-graphic matroids
Leonidas Pitsoulis
Abstract: In this talk we will present a decomposition for the class of signed graphic matroids which are representable in either GF(2) or GF(4). The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not solely based on k-sums such as the decomposition of regular matroids, but also on an operation called star composition. A sketch of the resulting recognition algorithms as well as an excluded minor characterization of the building blocks of the aforementioned decomposition will also be presented.
Enumerating matroids of fixed rank
Jorn van der Pol
Abstract: We give lower and upper bounds on the number of matroids of fixed rank. These bounds are asymptotically equivalent on the logarithmic level.
The upper bound relies heavily on the theory of matroid erections, developed by Crapo and Knuth, to encode each matroid as a stack of paving matroids. Our bound is obtained by relating this stack to an antichain that completely determines the matroid.
Along the way, we obtain that the essential flats of a matroid give a concise description of matroids.
Luke Postle
Abstract: The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. In a publication dating from 1998, Reed showed that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. He conjectured that 1/2 of the gap could be saved. We show for large enough maximum degree that 1/26 of the gap can be saved improving on the bound of 1/320e^6 by King and Reed. This is joint work with Marthe Bonamy (LaBRI) and Thomas Perrett (Technical University of Denmark).
Some Excluded Minors for Strongly Base-Orderable Matroids
Thomas Savitsky
Abstract: In 1975, Ingleton gave an example of a matroid that is base-orderable, but not strongly base-orderable. Using cyclic flats, we generalize his construction and exhibit infinitely many excluded minors for the class of strongly base-orderable matroids that are themselves base-orderable. This is joint work with Joe Bonin.
Structural problems in phylogenetic networks
Charles Semple
Abstract: Evolution is not necessarily a treelike process because of reticulate (non-treelike) events such as hybridisation and lateral gene transfer. The reticulate evolutionary history of a set of extant species is typically represented by a phylogenetic network (a particular type of acyclic directed graph). Although reticulation has long been recognised in evolutionary biology, mathematical investigations into understanding the structural properties of phylogenetic networks are relatively new. Originally, the questions and consequent investigations were of a certain type, but now we are seeing an ever-increasing variety of questions being asked. For example, how hard is it to decide if a given gene tree is embeddable in a given network? If one selects a network with $\ell$ leaves uniformly at random, how many reticulations (vertices of in-degree at least two) can one expect it to have when $\ell$ is sufficiently large? When is a network determined by the path-length distances between its leaves? In this talk, we discuss some of these questions and recent results.
Forbidden Induced Subgraph Characterizations
Vaidy Sivaraman
Abstract: One way to describe a class of graphs closed under taking induced subgraphs is by listing the set of all forbidden graphs, graphs that are not in the class but whose every proper induced subgraph is in the class. Such characterizations are known for some important classes. The class of perfect graphs is a prime example. I will mention such a theorem that we discovered recently for a generalization of threshold graphs. Our main focus will be on the following question: For a hereditary class of graphs, let $f_i$ be the number of forbidden graphs with $i$ vertices. We call this sequence the forbidden sequence of this class. Which integer sequences can occur as the forbidden sequence of some hereditary class? This is joint work with Richard Behr and Thomas Zaslavsky.
Coloring square-free Berge graphs
Kristina Vušković
Abstract: We consider the class of graphs that does not contain as induced subgraphs chordless cycles of odd length greater than 3, their complements and chordless cycles of length 4 (square-free Berge graphs). We present a purely-graph theoretical algorithm that produces an optimal coloring for the graphs in this class. This is joint work with Chudnovsky, Lo, Maffray and Trotignon.
This is a subclass of perfect graphs, that have been extensively studied in the last 50 years. In 1981 Grötschel, Lovász and Schrijver showed that perfect graphs can be optimally colored in polynomial time. Their algorithm uses the ellipsoid method and is usually considered impractical. The last big open problem in the area is to find a purely combinatorial polynomial time coloring algorithm for perfect graphs.
Density of Binary Matroids with no PG(t+2,2)-minor
Zach Walsh
Abstract: The Matroid Minors Structure Theorem describes the structure of matroids in
a given minor-closed class of matroids representable over a finite field. We apply this
theorem to prove that for any non-negative integer $t$ and any sufficiently large
integer $r$, any simple rank-$r$ binary matroid with no $\text{PG}(t+2,2)$-minor has at most $2^t{r-t+1 \choose 2}+2^t-1$ elements.
The Binary Matroids Whose Only Odd Circuits are Small
Kristen Wetzler
Abstract: This talk generalizes a graph-theoretical result of Maffray to binary matroids. In particular, we prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if $M$ is affine, $M$ is $M(K_4)$ or $F_7$, or $M$ is the cycle matroid of a graph consisting of a collection of triangles all of which share a common edge. We then extend the graph-theoretical case and show similar results for binary matroids whose largest odd circuit are of size five.
Proving Rota’s Conjecture without Structure Theory
Geoff Whittle
Abstract: This is joint research with Jim Geelen and Bert Gerards. Our original proof of Rota’s Conjecture relied heavily on structure theory for members of minor-closed classes of matroids representable over a finite field. In this talk I discuss a new proof of Rota’s Conjecture that bypasses much of this structure theory.
Minor-closed classes of error-correcting codes
Stefan van Zwam
Abstract: When designing an error-correcting code, tradeoffs are inevitable. Nice codes could result in easier decoding algorithms; furthermore, the more transmission errors we try to correct, the lower the data rate of the code gets. In this talk we will prove that minor-closed classes are not the place to look for a certain type of good codes.