<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
The Lattice of Cyclic Flats of a Matroid
Joseph E. Bonin1 and Anna de Mier2
1Department of Mathematics, The George Washington University, Washington, D.C. 20052, USA
jbonin@gwu.edu
2Mathematical Institute, University of Oxford, 24--29 St Giles', Oxford OX1 3LB, United Kingdom
ademier@gmail.com
Annals of Combinatorics 12 (2) p.155-170 June, 2008
AMS Subject Classification: 05B35
Abstract:
A flat of a matroid is cyclic if it is a union of circuits. The cyclic flats of a matroid form a lattice under inclusion. We study these lattices and explore matroids from the perspective of cyclic flats. In particular, we show that every lattice is isomorphic to the lattice of cyclic flats of a matroid. We give a necessary and sufficient condition for a lattice $\mc{Z}$ of sets and a function $r\colon\mc{Z}\rightarrow \mathbb{Z}$ to be the lattice of cyclic flats of a matroid and the restriction of the corresponding rank function to $\mc{Z}$. We apply this perspective to give an alternative view of the free product of matroids and we show how to compute the Tutte polynomial of the free product in terms of the Tutte polynomials of the constituent matroids. We define cyclic width and show that this concept gives rise to minor-closed, dual-closed classes of matroids, two of which contain only transversal matroids.
Keywords: matroid, cyclic flat, Dilworth's embedding theorem, nested matroid, free product,Tutte polynomial

References:

1. D. Acketa, On the essential chains and squares, In: Finite and Innite Sets, Vol. I, II, A. Hajnal, L. Lov´asz, and V.T. S´os, Eds., North-Holland, Amsterdam, (1984) pp. 2–-33.

2. J. Bonin and A. de Mier, Lattice path matroids: structural properties, Europ. J. Combin. 27 (5) (2006) 701–-738.

3. J. Bonin, A. de Mier, and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, J. Combin. Theory Ser. A 104 (1) (2003) 6-–94.

4. T.H. Brylawski, An afne representation for transversal geometries, Studies in Appl. Math. 54 (1975) 143-–160.

5. H.H. Crapo and W. Schmitt, The free product of matroids, Europ. J. Combin. 26 (2005) 1060-–1065.

6. H.H. Crapo andW. Schmitt, A unique factorization theorem for matroids, J. Combin. Theory Ser. A 112 (2005) 222-–249.

7. P. Crawley and R.P. Dilworth, Algebraic Theory of Lattices, Prentice Hall, Englewood Cliffs, N.J., 1973.

8. B.A. Davey and H.A. Priestley, Introduction to Lattices and Order, 2nd Ed., Cambridge Univ. Press, New York, 2002.

9. R. Diestel, Graph Theory, 2nd Ed., Springer Verlag, New York, 2000.

10. A.M.H. Gerards, private communication.

11. O. Gim´enez, private communication.

12. G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc. 2 (1952) 326-–336.

13. A.W. Ingleton, Transversal matroids and related structures, In: Higher Combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), Reidel, Dordrecht, (1977) pp. 117-–131.

14. J.G. Oxley, A characterization of the ternary matroids with no M(K4)-minor, J. Combin. Theory Ser. B 42 (1987) 212-–249.

15. J.G. Oxley, Matroid Theory, Oxford University Press, Oxford, 1992.

16. J.G. Oxley, K. Prendergast, and D. Row, Matroids whose ground sets are domains of functions, J. Austral. Math. Soc. Ser A 32 (1982) 380-–387.

17. J.A. Sims, Some problems in matroid theory, Ph.D. Dissertation, Linacre College, Oxford University, Oxford, 1980.

18. J.A. Sims, An extension of Dilworth's theorem, J. London Math. Soc. 16 (1977) 393-–396.

19. C. Thomassen, Embeddings and minors, In: Handbook of Combinatorics, R.L. Graham, M. Gr¨otschel, and L. Lov´asz, Eds., Elsevier, Amsterdam, (1995) pp. 301-349.