|
Organizers |
Matroids applied to coding theory
by
Thomas Britz
University of New South Wales
Coauthors: Keisuke Shiromoto
One of the most attractive features of matroid theory is that it generalises objects and results from other fields, such as linear algebra, graph theory, and matching theory, to name three prominent examples. By applying matroid theory to the generalized objects, it is often possible to achieve good results regarding the original objects.
This talk presents several ways in which matroid theory may be applied to coding theory. The results thereby obtained include a new and unexpected dual relationship between bond and cycle cardinalities in graphs, and an efficient method to calculate higher weight enumerators of linear codes.
Date received: October 10, 2007
Even pairs in Berge graphs
by
Maria Chudnovsky
Columbia/CMI
Coauthors: Paul Seymour
An even pair in a graph is a pair of non-adjacent vertices so that every induced path between them has even length. A graph is called Berge if no induced subgraph of it is a cycle of odd length at least five or the complement of one. In my talk I will discuss two results, obtained in joint work with Paul Seymour, about even pairs in Berge graphs.
The first result is a a simplification of the proof of the Strong Perfect Graph Theorem (which we proved a few years ago in joint work with Neil Robertson, Paul Seymour and Robin Thomas). We were able to replace the last 55 pages of the proof (which are the least intuitive part of it) with a much shorter and simpler argument. This simplification is based on an approach by Maffray and Trotignon that allowed us to find even pairs in certain classes of Berge graphs.
The second result is a description of all K4-free Berge graph that do not have even pairs. This is a special case of a conejcture of Thomas, attempting to describe all Berge graphs with no even pair. In particular, our result implies a new combinatorial coloring algorithm for K4 free Berge graphs.
Date received: October 30, 2007
Unavoidable Minors of Loosely c-Connected Infinite Graphs
by
Carolyn Chun
Louisiana State University
Coauthors: Guoli Ding
An infinite graph G is called loosely c-connected if there exists a number d depending on the graph such that the deletion of fewer than c vertices from G results in a graph containing one infinite component and a collection of components containing d vertices altogether. This talk builds on Konig's Infinity Lemma, and describes the complete set of unavoidable minors, topological minors, and parallel minors for loosely c-connected infinite graphs.
Date received: October 27, 2007
Simplicial Maps, and the Generic Rigidity Matroid
by
Henry Crapo
CAMS/EHESS, Paris
Coauthors: Emanuela Ughi (Perugia) and Tiong Seng Tay (Singapore)
The generic rigidity matroid of a graph G (in dimension d) has as bases all subgraphs of G that are isostatic, that is, that are minimal sets of edges forming subgraphs that are rigid in general position in d-dimensional space.
Everything there is to be known about 2-isostatic graphs has been known for decades, but 3-isostatic graphs have no known combinatorial characterization.
We endeavor to shed some light on this subject by investigating simplicial maps from graphs to the simplex K4. The existence of a single such map that is shellable (in the sense that vertices mapped to the same vertex of K4 can be gradually separated) suffices to establish that a graph is isostatic. The converse problem involves a detailed analysis of obstacles to shellability.
Date received: October 30, 2007
Binary matroid minors
by
Jim Geelen
University of Waterloo
Coauthors: Bert Gerards and Geoff Whittle
I will discuss recent progress towards extending the graph minors project of Neil Robertson and Paul Seymour to the binary matroids.
Date received: October 29, 2007
Some Links Between Combinatorial Optimization Properties of Clutters and Algebraic Properties of Monomial Ideals
by
Isidoro Gitler
CINVESTAV-IPN Mexico
Coauthors: Enrique Reyes and Rafael Villarreal
Some combinatorial properties of clutters, such as the max-flow min-cut property or the packing property, will be expressed in terms of algebraic properties of square-free monomial ideals. We present some new families of Mengerian hypergraphs, some algebraic criteria for perfect graphs and a general setup for some combinatorial problems in the relatively new field of combinatorial commutative algebra.
Date received: October 29, 2007
Automorphisms of matroids associated with root systems
by
Gary Gordon
Lafayette College
Given a collection of vectors in Euclidean space, we consider the associated matroid, represented over the reals. We compute the automorphism group of this matroid for two collections of vectors: the root systems associated to the icosahedron and the F4 lattice. We give geometric interpretations to the matroid automorphisms, comparing the automorphism group of the matroids (combinatorial symmetry) to the Coxeter groups (geometric symmetry).
Date received: October 23, 2007
Chain-type and splitter-type theorems for cocircuits and hyperplanes in 3-connected matroids
by
Rhiannon Hall
Brunel University
Coauthors: Dillon Mayhew
There has been much interest for many years in the ability to
remove elements from 3-connected matroids and remain (almost)
3-connected. Theorems of this nature are generally known as
"chain-type" theorems. Theorems in which you remove elements
while remaining (almost) 3-connected and retaining a specific
minor, are known as "splitter-type" theorems. I will discuss a
chain-type theorem where we wish to contract elements from a
specific hyperplane, and I will discuss a splitter-type theorem
where we wish to contract elements from a specific cocircuit.
Key words: chain theorem, splitter theorem, 3-connected matroid, cocircuit, hyperplane.
Date received: October 24, 2007
Finding Branch-decompositions and Rank-decompositions
by
Petr Hlineny
TU Ostrava + Masaryk University Brno, CZ
Coauthors: Sang-Il Oum
We present a new algorithm that can output the rank-decomposition of width at most k of a graph if such exists. For that we use an algorithm that, for an input matroid represented over a fixed finite field, outputs its branch-decomposition of width at most k if such exists. This algorithm works also for partitioned matroids. Both these algorithms are fixed-parameter tractable, that is, they run in time O(n3) for each fixed value of k where n is the number of vertices / elements of the input.
Date received: September 18, 2007
A basis exchange property for matroids
by
Peter Humphries
University of Canterbury
Coauthors: Jim Geelen
Rota conjectured that the set of elements from n disjoint bases of a rank-n matroid M can be repartitioned into n transversal sets that are also bases of M. We present a stronger result for the class of paving matroids, and explain why the technique used in the proof fail when trying to prove the conjecture directly.
Date received: October 30, 2007
The Tutte polynomial turned upside down
by
Joseph P. Kung
University of North Texas
This talk is about possible new directions for research on the Tutte polynomial. The talk will begin with a generalization of flows and tensions for graphs to matroids represented over partial fields. We will show how results of Goodall and Matiaseyich can be extended in an elementary way to such matroids. We will also discuss whether it is possible to count flows over the dyadic partial field (which is not finite, but "profinite"). We will end by discussing the question of defining an "upside-down" Tutte polynomial based on a natural recursion for the the Eulerian function of a matroid.
Date received: August 29, 2007
Minimal non-bipartite join covered graphs
by
Charles Little
Massey University
Coauthors: Marcelo de Carvalho
A weight function on a graph G assigns a weight of 1 or -1 to each edge of G. It is said to be conservative if the sum of the weights around any circuit is non-negative. A pair (G,w) is called a conservative graph if G is a graph with a conservative weight function w. A conservative graph is defined to be join covered if for every edge e there is a circuit through e around which the sum of the weights is 0. Join covered graphs are a natural generalisation of matching covered graphs. We characterise minimal non-bipartite join covered graphs.
Date received: August 29, 2007
The excluded minors for the class of matroids that are either binary or ternary.
by
Dillon Mayhew
Victoria University of Wellington
Coauthors: Bogdan Oporowski, James Oxley, Geoff Whittle.
The excluded-minor characterisations for matroids that are representable over GF(2) and GF(3) respectively are classic results in matroid theory. The first of these characterisations is due to Tutte, and the second was proved independently by Reid, Bixby, and Seymour. There is a single excluded minor for the class of matroids representable over GF(2), and four for the class of matroids representable over GF(3).
The union of these two classes of matroids is minor-closed, and it is natural to ask for an excluded-minor characterisation of this family. In this talk we present such a characterisation. There are exactly eight excluded minors for the class of matroids that are representable over GF(2) or GF(3).
The proof relies upon Truemper's structural results for his class of almost-regular matroids.
Date received: October 29, 2007
Binary matroids with no K3, 3 minor
by
Gordon Royle
University of Western Australia
Coauthors: Dillon Mayhew, Geoff Whittle
We have recently completed the classification of the internally 4-connected binary matroids with no K3, 3 minor. Rather than describe the proof of this result (which has been reported previously), this talk will focus on its consequences by considering a number of questions about this class of matroids that can now be answered with the help of the classification.
These results include classifying the largest simple binary matroids in this class, determining the critical exponent of the matroids in this class and the existence of a polynomial time recognition algorithm for matroids in this class. If time permits, I will speculate on the analogous questions for the class of binary matroids excluding K5 for which we do not (yet) have a suitable classification theorem to use.
Date received: October 22, 2007
Forcing a K2, t minor
by
Paul Seymour
Princeton University
Coauthors: Maria Chudnovsky, Bruce Reed
Let t ≥ 2 be an integer, and G be a simple graph with n ≥ t+2 vertices, with no K2, t minor. What is the maximum number of edges G can have? It is known from general results of Mader that this function is asymptotically linear in n (for fixed t). At the time of writing we seem to be close to a proof that in fact G can have at most (t+1)(n-1)/2 edges, which would be best possible for infinitely many values of n.
We report progress on this conjecture and related questions.
Date received: October 30, 2007