The main tool Tom uses is an abstract notion of duality, based on the formula for dual rank in a matroid. Then, as with matroids, we have f(G*;t,z)=f(G;z,t), where G* is the dual of G. I'll give some examples, showing how to define deletion, contraction and duality. This also gives a characterization of the class of matroids as the intersection of the classes of greedoids and dual greedoids.
It is known that the number of partitions Π of
{1, 2,... , n + 1} such that no block
of Π contains a pair of consecutive integers, equals the number of unrestricted partitions
of
{1, 2, ..., n}. In our context, this may be expressed as the equality B(Pn+1) = B(En),
Pn+1 being the path graph. We give two generalizations.
We will also give examples of one-parameter families of graphs whose Bell numbers
form a quasigeometric sequence such as the Fibonacci sequence or the Lucas sequence.
These examples lead naturally to an interesting conjecture.
Finally, in the parlance of matroid theory, B(G) is an example of a Tutte group
invariant that is not a Tutte ring invariant. The deletion-contraction identity B(G) =
B(G − e) − B(G/e) holds, but B(G ∪ H) = B(G) ⋅ B(H) (disjoint union) must be replaced
by B(G join H) = B(G)
⋅ B(H). (G join H has a new edge joining every vertex of G to
every vertex of H.) We discuss some theoretical consequences of these facts. This work grew out of an independent study course that I conducted for Bryce Duncan
when he was an undergraduate. I gave a talk with the same title as this one at the Ohio
State Zassenhaus conference honoring Professor Dowling in 2006. The present talk contains
a fair amount of new material.
Does this happen in any other context?
B. Lindström (A theorem on families of sets, J. of Combinatorial Theory (A) 13 (1972), 274--277) proved an analogue of Radon's
Theorem for families of sets. In this context, "convex" means
closed under unions. Tverberg (On equal unions of sets, in Studies in Pure Mathematics, edited by L. Mirsky, Academic Press, London, 1971, 249--250) deduced
Lindström's result from the Euclidean case. It turns out that the minimal Radon partitionable 2-sets of an n-set again form the circuits of one of Simões-Pereira's
(On matroids on edge sets of graphs with connected subgraphs as circuits, II Discrete Math. 12 (1975), 55-78) family of graph matroids.
This is joint work with Neil Calkin, Clemson.
Some Problems about the Tutte Polynomial and its Specialisations
Dominic Welsh, Oxford University
Abstract
Two of the earliest papers of Tom Brylawski were hugely
influential in the development of the theory of the Tutte
polynomial.
In this talk I shall discuss some more recent problems arising
from some of its many specialisations and applications.
The matroids that are binary or ternary
James Oxley, LSU
Abstract In his chapter on constructions in Neil White's book
"Theory of Matroids", Tom Brylawski raised as a research problem
exploring the set of excluded minors for the union of two
minor-closed classes of matroids. This talk will present the solution
to this problem for the union of the classes of binary and ternary
matroids. This is joint work with Dillon Mayhew, Bogdan Oporowski,
and Geoff Whittle.
Brylawski's lost notes: Generalized duality and deletion-contraction
Gary Gordon, Lafayette College
Abstract My office was painted this summer. Upon unpacking when the painters left, I came across 3 pages of notes Tom Brylawski gave me around 20 years ago. Tom was interested in generalizations of the Tutte polynomial to finite sets having an arbitrary rank function. His (unpublished) notes sketch how to define a corank-nullity polynomial that satisfies a natural deletion-contraction recursion in this general setting.
Fixing and distinguishing numbers for matroids
Jennifer McNulty, University of Montana
Abstract There are many ways to study the symmetry of matroids. We are interested in two matroid invariants that can be interpreted as modifying a given matroid so as to force the resulting matroid to have no non-trivial automorphisms. To study this idea, we borrow two concepts from graph theory, the distinguishing and fixing numbers. The distinguishing number of a graph is defined as the minimum number of colors needed to color the vertices of the graph in such a way that the resulting graph has no non-trivial color-preserving automorphisms. A related symmetry-measure is the fixing number. A set of vertices of a graph is a fixing set if the only automorphism that fixes this set is the identity. The fixing number of the graph is the minimum size of a fixing set. In this preliminary report, we define the fixing and distinguishing numbers for matroids and give several examples and properties. This is joint work woth Gary Gordon.
Radon Partitions in Families of Sets
Robert E. Jamison, Clemson University
Abstract A set is Radon partitionable iff it has two disjoint subsets A and B with conv(A) ∩ conv(B) ≠ ∅. Radon (Mengen konvexer Körper, die einer gemeinsamen Punkt enthalten, Math. Ann. 83 (1921), 113--115) showed
that any d + 2 points in Rd are Radon partitionable. Brylawski (A combinatorial perspective on the Radon convexity theorem,
Geometriae Dedicata 5 (1976), no. 4, 459-466) used
matroid techniques to study the number of Radon partitions of a set in Euclidean space.
A key to this and Radon's Theorem is the fact that a subset of Rd
is Radon partitionable iff it is affinely dependent.
That is, the minimally Radon partitionable sets form the circuits of a matroid.
Binary matroid minors
James Geelen, University of Waterloo
Abstract In joint work with Bert Gerards and Geoff Whittle, we are trying to extend the
graph minors project, of Neil Robertson and Paul Seymour, to matroids represented
over a fixed finite field. I will report on recent progress for the binary field.
Tutte functions
Thomas Zaslavsky, Binghamton University (SUNY)
Abstract A function defined on an arbitrary minor-closed class of matroids is a
"Tutte function" if it satisfies the parametrized deletion-contraction
law
F(M) = de F(M\e) + ce F(M/e)
whenever e is a point of M that is neither a loop nor a coloop. F
need not have any other Tutte-style properties like multiplicativity.
Here de and ce are constants associated with e,
independent of M but depending on the point e. Joanna Ellis-Monaghan
and I are studying the algebraic structures underlying the class of
Tutte functions.
The double majorization order
Curtis Greene, Haverford College
Abstract The double-majorization order is a partial order extending the classical majorization (=dominance) order on partitions. We will discuss some of its properties, as well as applications to the theory of symmetric functions. This is joint work with Allison Cuttler and Mark Skandera.
Evolutionary stability and population dynamics for symmetric games
Douglas G. Kelly, University of North Carolina
Abstract
We review, for symmetric two-person games (e.g. the Iterated Prisoner's Dilemma), the connections between the static, game-theoretic properties of Nash equilibrium and evolutionary stability, and the dynamic stability properties of evolving populations of individuals playing various strategies. We then discuss some of the problems arising from attempts to extend these properties to multi-player symmetric games (e.g., the Iterated Public Goods Game).
Sudoku: Strategy versus structure
J. Scott Provan, University of North Carolina
Abstract
Sudoku puzzles have become wildly popular in just the last few years, and quite a school has developed around classifying solution strategies for Sudoku puzzles. We give a simply-described set of strategies that solves about 90% of all Sudoku puzzles. This strategy class has two interesting properties: one associated with the formulation of these puzzles as a set of interlocking assignment problems and the other with their representation as the unique nonnegative solution to the associated set of assignment equations. We end by indicating some interesting research problems in the area.
Clones and Minors in Matroids
Carla Cotwright, Hampton University
Abstract We consider matroid structure problems relating clones, lines, minors, and representability of matroids. This is joint work with James Reid and Jakayla Robbins.
Equivariant classes of matroid realization spaces
Richard Rimanyi, University of North Carolina
Organizing Fundamental Combinatorial Counts
Robert A. Proctor, University of North Carolina
Abstract Imagine a discrete manifold which contains one point for each of the 144,000+ sequences in the On-Line Encyclopedia of Integer Sequences. At times it may be useful to introduce some local coordinate charts which organize small subsets of the manifold with tabular structures. Rota's 3 x 4 Twelvefold Way table was nearly of this nature. (At face value, it organized two-parameter families of counts, not one-parameter families.) Brylawki's and Bogart's follow-on contributions to Rota's viewpoint may be viewed as additional columns and rows. These are incorporated into the 6 x 5 more-comprehensive table presented here. Then a second 6 x 7 table of sequences of counts is presented; it is a chart of the kind first mentioned.