Matroid 4-Connectivity: A Deletion–Contraction Theorem

✍ Scribed by James Geelen; Geoff Whittle

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 223 KB
• Volume: 83
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.2001.2032

✦ Synopsis

A 3-separation (A, B), in a matroid M, is called sequential if the elements of A can be ordered (a 1 , ..., a k ) such that, for i=3, ..., k, ([a 1 , ..., a i ], [a i+1 , ..., a k ] _ B) is a 3-separation. A matroid M is sequentially 4-connected if M is 3-connected and, for every 3-separation (A, B) of M, either (A, B) or (B, A) is sequential. We prove that, if M is a sequentially 4-connected matroid that is neither a wheel nor a whirl, then there exists an element x of M such that either M "x or MÂx is sequentially 4-connected.

2001 Academic Press

Theorem 1.1 (Wheels and Whirls Theorem). If M is a 3-connected matroid that is neither a wheel nor a whirl, then M has an element x such that either M"x or MÂx is 3-connected.

While there is general agreement on an appropriate definition for matroid 3-connectivity, for higher connectivity the situation is more problematic. Recall Tutte's definition of connectivity [10]. Let M be a