Discussiones Mathematicae Graph Theory 33(3) (2013) 599-602
doi: 10.7151/dmgt.1689

[BIBTex] [PDF] [PS]

Broken Circuits in Matroids---Dohmen's Inductive Proof

Wojciech Kordecki

University of Business in Wrocław
Department of Management
ul. Ostrowskiego 22, 53-238 Wrocław, Poland

Anna Łyczkowska-Hanćkowiak

Poznań University of Economics
Faculty of Informatics and Electronic Economy
Department of Operations Research
al. Niepodległości 10, 61-875 Poznań, Poland


Dohmen [4] gives a simple inductive proof of Whitney's famous broken circuits theorem. We generalise his inductive proof to the case of matroids.

Keywords: matroids, broken circuits, induction

2010 Mathematics Subject Classification: 05C15, 05B35.


[1]T. Brylawski, The broken circuit complex, Trans. Amer. Math. Soc. 234 (1977) 417--433, doi: 10.1090/S0002-9947-1977-0468931-6 .
[2]T. Brylawski and J. Oxley, The Tutte polynomials and its applications, in: Matroid Applications, ed(s), N. White Cambridge University Press, 1992) 121--225.
[3]K. Dohmen, Some remarks on the sieve formula, the Tutte polynomial and Crapo's beta invariant, Aequationes Math. 60 (2000) 108--115, doi: 10.1007/s000100050139.
[4]K. Dohmen, An inductive proof of Whitney?s broken circuit theorem, Disscus. Math. Graph Theory 31 (2011) 509--515, doi: 10.7151/dmgt.1561.
[5]A.P. Heron, Matroid polynomials, in: Combinatorics, ed(s), D.J.A. Welsh and D.R. Woodall The Institute of Combinatorics and Its Applications, Southend-On-Sea, 1972) 164--202.
[6]J.G. Oxley, Matroid Theory (Oxford University Press, Oxford, 1992).

Received 18 October 2011
Revised 12 July 2012
Accepted 8 November 2012