{"id":1830,"date":"2016-06-07T16:25:24","date_gmt":"2016-06-07T20:25:24","guid":{"rendered":"http:\/\/matroidunion.org\/?page_id=1830"},"modified":"2016-07-23T05:18:31","modified_gmt":"2016-07-23T09:18:31","slug":"2016-workshop-abstracts","status":"publish","type":"page","link":"https:\/\/matroidunion.org\/?page_id=1830","title":{"rendered":"2016 Workshop – Abstracts"},"content":{"rendered":"

Look here<\/a> for the schedule.<\/p>\n

<\/a>Is $P_8^{=}$ a gammoid?<\/strong><\/p>\n

Immanuel Albrecht<\/em><\/p>\n

Abstract: <\/em>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.<\/p>\n

\n

<\/a>Algebraic matroids and Frobenius flocks<\/strong><\/p>\n

Guus Bollen<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

\n

<\/a>A New Perspective on the $\\mathcal{G}$-Invariant of a Matroid
\n<\/strong><\/p>\n

Joseph E. Bonin<\/em><\/p>\n

Abstract:\u00a0<\/em>The $\\mathcal{G}$-invariant of a matroid was introduced by Derksen\u00a0(2009), who showed that it properly generalizes the Tutte polynomial.\u00a0Akin to the recipe theorem, which says that the Tutte polynomial is\u00a0universal among invariants that satisfy deletion-contraction rules,\u00a0Derksen and Fink (2010) showed that the $\\mathcal{G}$-invariant is\u00a0universal among invariants that satisfy an inclusion\/exclusion-like\u00a0property on matroid base polytopes.<\/p>\n

In this joint work with Joseph Kung, we give a new view of this\u00a0invariant and explore its implications. We show that the\u00a0$\\mathcal{G}$-invariant of a matroid $M$ of rank $r$ is equivalent to\u00a0having, for each sequence $a_0,a_1,\\ldots,a_r$, the number of flags of\u00a0flats $X_0\\subset X_1\\subset\\cdots\\subset X_r$ of $M$ with $|X_0|=a_0$\u00a0and $|X_i-X_{i-1}|=a_i$ for $i>0$. With this view, we can determine\u00a0the effect of some matroid constructions, such as taking $q$-cones, on\u00a0the $\\mathcal{G}$-invariant, and we can identify some of the\u00a0information that the $\\mathcal{G}$-invariant picks up that the Tutte\u00a0polynomial does not, such as the number of circuits and cocircuits of\u00a0any given size, and the number of cyclic flats of any given rank and\u00a0size. Also, the $\\mathcal{G}$-invariant of a matroid can be\u00a0reconstructed from the multi-set of $\\mathcal{G}$-invariants of the\u00a0restrictions to hyperplanes. Still, strengthening what J. Eberhardt\u00a0proved for the Tutte polynomial, the $\\mathcal{G}$-invariant is\u00a0determined by relatively little information, namely, by just the\u00a0isomorphism type of the lattice of cyclic flats along with the rank\u00a0and size of each cyclic flat.<\/p>\n

\n

<\/a>Infinite regular matroids<\/strong><\/p>\n

Nathan Bowler<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

\n

<\/a>The Structure of Graphs Without Even Holes or Odd Pans<\/strong><\/p>\n

Kathie\u00a0Cameron<\/em><\/p>\n

Abstract:\u00a0<\/em>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. \u00a0Minty’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\u00e4dt, Lozin and Mosca (2010) to pan-free graphs. We show that pan-free even-hole-free \u00a0graphs 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. \u00a0Our 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.<\/p>\n

Joint work with Steven Chaplick, Ch\u00ednh T. H\u00f2ang.<\/p>\n

\n

<\/a>Dense PG(t-1,2)-free binary matroids<\/strong><\/p>\n

Rutger Campbell<\/em><\/p>\n

Abstract:\u00a0<\/em>Turan’s theorem says that, for a positive\u00a0integer $t$, the densest $K_t$-free graphs are $(t-1)$-colourable. We\u00a0discuss what we know about the structure of a $K_t$-free graph\u00a0that has\u00a0density<\/span>\u00a0close to the maximum. We present the analogous\u00a0problem for\u00a0binary<\/span>\u00a0matroids<\/span>\u00a0and give similar results.<\/p>\n

\n

<\/a>Delta-matroids overview<\/strong><\/p>\n

Carolyn Chun<\/em><\/p>\n

Abstract: <\/em>We give a brief discussion of some objects that give rise to delta-matroids.<\/p>\n

\n

<\/a>Relaxations of quaternary matroids<\/strong><\/p>\n

Ben Clark<\/em><\/p>\n

Abstract:\u00a0<\/em>We describe the structure of\u00a0the\u00a0quaternary matroids with a circuit-hyperplane whose relaxation is a quaternary matroid. This is joint work with James Oxley and Stefan van Zwam.<\/p>\n

\n

<\/a>Properties of almost all sparse\u00a0paving matroids<\/strong><\/p>\n

Will Critchlow<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

\n

<\/a>Tw-fragility and some related questions<\/strong><\/p>\n

Zdenek Dvorak<\/em><\/p>\n

Abstract:\u00a0<\/em>Tw-fragility is a property of graph classes inspired by design of approximation\u00a0algorithms, as well as structural considerations (“distance” to bounded\u00a0tree-width). \u00a0A class C of graphs is tw-fragile if for every positive integer\u00a0k, there exists an integer r as follows: for every graph G from C, there exist\u00a0k disjoint subsets of its vertices, such that removing any of them from G\u00a0decreases its treewidth to at most r. \u00a0As an example, all proper minor-closed\u00a0classes of graphs are known to have this property.<\/p>\n

Characterizing tw-fragile classes is a tough problem, in particular due to\u00a0existence of classes (such as 3-dimensional grids) whose non-tw-fragility is\u00a0only established using surprisingly involved arguments. \u00a0However, a fractional\u00a0version of the property seems easier to handle. \u00a0We consider the question\u00a0whether all hereditary classes with strongly sublinear separators are\u00a0fractionally tw-fragile, and present some results supporting this conjecture.<\/p>\n

\n

<\/a>Structural properties of laminar matroids<\/strong><\/p>\n

Tara Fife<\/em><\/p>\n

Abstract:\u00a0<\/em>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}$.\u00a0It 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.<\/p>\n

\n

<\/a>Almost balanced biased graphical representations of 4-connected frame matroids are essentially unique<\/strong><\/p>\n

Daryl Funk<\/em><\/p>\n

Abstract:\u00a0<\/em>Let M be a frame matroid, with biased graphical representation (G,B).\u00a0 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.\u00a0 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.<\/p>\n

\n

<\/a>Fragility for binary matroids<\/strong><\/p>\n

Jim Geelen<\/em><\/p>\n

Abstract:\u00a0<\/em>A matroid $M$ is $N$-fragile<\/em> if $N$ is a minor of $M$ and\u00a0there is no element $e$ of $M$ such that $N$ is a minor of both $M\\backslash e$ and\u00a0and $M\/ e$. We prove that binary $N$-fragile matroids have bounded path-width.\u00a0The proof is short and self-contained. This is joint work with Bert Gerards and Geoff Whittle.<\/p>\n

\n

<\/a>Templates for minor-closed classes of binary matroids<\/strong><\/p>\n

Kevin Grace<\/em><\/p>\n

Abstract:\u00a0<\/em>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\u00a0applications 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.<\/p>\n

\n

<\/a>A graph result looking for a matroid generalization<\/strong><\/p>\n

Gary Gordon<\/em><\/p>\n

Abstract: <\/em>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.<\/p>\n

\n

<\/a>Chromatic polynomial for the spike matroids<\/strong><\/p>\n

Rhiannon Hall<\/em><\/p>\n

Abstract:\u00a0<\/em>For $n\\geq 3$, an $n$-spike<\/em> is a matroid whose groundset can be partitioned into $n$ pairs called\u00a0legs<\/em>, 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<\/em>\u00a0and\/or coextended by an element called a cotip<\/em>\u00a0such that the union of the tip with each leg forms a triangle, and the union of the cotip with each leg forms a triad.
\nSpikes have arisen in many areas of matroid theory, sometimes notoriously, such as when Oxley, Vertigan & Whittle\u00a0used 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)$.<\/p>\n

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$.<\/p>\n

\n

<\/a>Q[x]-representable Excluded Minors for Q-Representable Matroids of Rank Three<\/strong><\/p>\n

Hidefumi Hiraishi<\/em><\/p>\n

Abstract:\u00a0<\/em>While any minor-closed class of graphs is characterized by a \ffinite 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\ffinite field is well-known to have an in\ffinite number of excluded minors. In this talk, we show that, for any algebraic element x over the rational \ffield Q whose minimal polynomial is degree 2, the class of matroids representable over Q also has in\ffinitely 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.<\/p>\n

\n

<\/a>Sticky matroids and Kantor’s conjecture<\/strong><\/p>\n

Winfried Hochst\u00e4ttler<\/em><\/p>\n

Abstract:\u00a0<\/em>A matroid is sticky if for any two of its extensions there exists an\u00a0amalgam. The sticky matroid conjecture (Polyak, Turzik 1982)\u00a0asserts that a matroid is sticky if and only if it is modular.<\/p>\n

Kantor conjectured 1974 that a finite rank 4 matroid where any two\u00a0hyperplanes intersect in a line does not possess the Vamos-matroid as a\u00a0restriction, and presented a counterexample for the infinite case.<\/p>\n

Let us say that a matroid has a non-trivial extension, if it has an\u00a0extension which decreases the modular defect of a non-modular\u00a0pair. Bachem and Kern 1987 gave a (flawed) proof that a matroid which\u00a0has a non-trivial extension decreasing the modular defect of a line\u00a0and a hyperplane is not sticky. The flaw was pointed out and fixed by\u00a0Bonin in 2011.<\/p>\n

Conversely, we prove that a rank 4 matroid which does not admit a\u00a0non-trivial extension is sticky. As a consequence we get that the\u00a0sticky matroid conjecture and Kantor’s conjecture are\u00a0equivalent. Moreover, we derive an example showing that the sticky\u00a0matroid conjecture fails in the infinite case.<\/p>\n

joint work with Michael Wilhelmi<\/p>\n

\n

<\/a>The matroid secretary problem for minor-closed classes and random matroids<\/strong><\/p>\n

Tony Huynh<\/em><\/p>\n

Abstract:\u00a0<\/em>We prove that for every proper minor-closed class of matroids representable over a prime field, there exists a constant-competitive matroid secretary algorithm.\u00a0 This result relies on the extremely powerful matroid minor structure theory developed by Geelen, Gerards and Whittle.<\/p>\n

<\/div>\n
We also prove that for asymptotically almost all matroids, the matroid secretary algorithm that selects a random basis, ignoring weights, is (2+o(1))-competitive.\u00a0 In fact, assuming the conjecture that almost all matroids are paving, there is a (1+o(1))-competitive algorithm for almost all matroids.<\/div>\n
<\/div>\n
This is joint work with Peter Nelson (University of Waterloo).<\/div>\n
\n
\n<\/div>\n

<\/a>Recognizing frame matroids<\/strong><\/p>\n

Benson Joeris<\/em><\/p>\n

Abstract:\u00a0<\/em>A frame<\/em>\u00a0matrix 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.<\/p>\n

\n

<\/a>Sparsity and dimension<\/strong><\/p>\n

Gwena\u00ebl Joret<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

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.<\/p>\n

\n

<\/a>Defining the q-analogue of a matroid<\/strong><\/p>\n

Relinde Jurrius<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

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!\u00a0To 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.<\/p>\n

In this talk, we will discuss the problems and possible solutions concerned with the different ways to define a q-matroid, illustrated by examples.<\/p>\n

Joint work with Ruud Pellikaan<\/p>\n

\n

<\/a>On a question of Alon and Mohar<\/strong><\/p>\n

Ross Kang<\/em><\/p>\n

Abstract:\u00a0<\/em>Alon and Mohar posed the following: among all graphs $G$ of maximum\u00a0degree at most $d$ and girth at least $g$, what is the largest\u00a0possible value of $\\chi(G^t)$, the chromatic number of the $t$th power\u00a0of $G$? With respect to this problem and related questions, we can\u00a0provide upper bounds on $\\chi(G^t)$. For instance, we show that the\u00a0chromatic number of the cube of a graph of maximum degree at most $d$\u00a0containing no cycle of length $8$ is at most $cd^3\/\\log d$ for some\u00a0fixed constant $c>0$. We also discuss to what extent these bounds are\u00a0best possible.<\/p>\n

This is based on joint work with Fran\u00e7ois Pirot (ENSL).<\/p>\n

\n

<\/a>Algorithmic matroid theory<\/strong><\/p>\n

Sandra Kingan<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

\n

<\/a>A chain theorem for triangle-free 3-connected matroids<\/strong><\/p>\n

Manoel Lemos<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

In 2013, Lemos extended Kriesell’s theorem for matroids. In this case, there are four infinite families of irreducible matroids.<\/p>\n

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.<\/p>\n

\n

<\/a>A proof of the Bar\u00e1t-Thomassen Conjecture<\/strong><\/p>\n

Martin Merker<\/em><\/p>\n

Abstract:\u00a0<\/em>Bar\u00e1t 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.
\nJoint work with Julien Bensmail, Ararat Harutyunyan, Tien-Nam Le, and St\u00e9phan Thomass\u00e9.<\/p>\n

\n

<\/a>Matroids, graphs in surfaces, and the Tutte polynomial<\/strong><\/p>\n

Iain Moffatt<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

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 \u00a0extensions of the Tutte polynomial from graphs to graphs in surfaces. These are due to M. Las Vergnas (1978), B. Bollob\u00e1s and O. Riordan (2002), and V. Kruskal (2011).<\/p>\n

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<\/em> 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.<\/p>\n

This is joint work with Ben Smith.<\/p>\n

\n

<\/a>Almost all matroids are non-representable<\/strong><\/p>\n

Peter Nelson<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

\n

<\/a>Automatic Pigeonholes<\/strong><\/p>\n

Mike Newman<\/em><\/p>\n

Abstract:\u00a0<\/em>Consider a separation $(A,B)$ of $M$. \u00a0Two 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. \u00a0A 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.<\/p>\n

Consider a branch decomposition of $M$ of width $k$. \u00a0A 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. \u00a0Depending on the final state of the root the tree automaton accepts or rejects. \u00a0If 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$.<\/p>\n

Both pigeonhole classes and automatic classes can be thought of as permitting only a bounded amount of “information” across (displayed) separations. \u00a0It turns out that these two conditions are equivalent.<\/p>\n

(Joint work with Daryl Funk, Dillon Mayhew, Geoff Whittle.)<\/p>\n

\n

<\/a>Minimum Area of Rectangle Visibility Graphs<\/strong><\/p>\n

Nancy Neudauer<\/em><\/p>\n

Abstract:\u00a0<\/em>A graph $G$ is a rectangle visibility graph<\/em>\u00a0if the vertices can be represented by\u00a0rectangles in the plane, parallel to the $x$ and $y$-axes, with edges in $G$ whenever\u00a0two rectangles can “see” each other.\u00a0Only some graphs are representable as a rectangle visibility graph.\u00a0For example, it is known that
\n(i) If $G$ is an rvg, it has at most $6n – 20$ edges;
\n(ii) $G$ has thickness at most two, so chromatic number at most 12 (not sharp);
\n(iii) $K_{p,q}$ is not an rvg if $p>4$, where $p\\leq q$.
\nWe consider the smallest area required for a rectangle visibility graph.\u00a0We also consider which graphs are possible when restrictions are put on one dimension\u00a0(the smaller) of the rectangle representation area, say the height.<\/p>\n

\n

<\/a>Recent results on delta-matroids<\/strong><\/p>\n

Steve Noble<\/em><\/p>\n

Abstract:\u00a0<\/em>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.<\/p>\n

\n

<\/a>Inductive tools for $3$-connected $2$-polymatroids<\/strong><\/p>\n

James Oxley<\/em><\/p>\n

Abstract:\u00a0<\/em>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, \u00a0and such structures model \u00a0both sets of points and lines in a projective space and sets of edges in a graph. The rank definitions of \u00a0deletion and contraction \u00a0for \u00a0matroids give corresponding operations for $2$-polymatroids. But, unless one uses some \u00a0 reduction operation in addition to \u00a0deletion and contraction, the set of minimal $2$-polymatroids that are not representable over a fixed field ${\\mathbb F}$ is infinite, irrespective of whether \u00a0${\\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.<\/p>\n

\n

<\/a>Properties of almost all matroids<\/strong><\/p>\n

Rudi Pendavingh<\/em><\/p>\n

Abstract:\u00a0<\/em>We show that asymptotically as $n \\rightarrow \\infty$, almost all matroids on $n$ elements<\/p>\n