✦ LIBER ✦

Clutters and matroids

✍ Scribed by Raul Cordovil; Komei Fukuda; Maria Leonor Moreira

Book ID: 103058271
Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 738 KB
Volume: 89
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90364-8

No coin nor oath required. For personal study only.

✦ Synopsis

A map on clutters (collections of incomparable sets of a given set) is a function defined from the class of all clutters to itself, that sends a clutter on a ground set E to a clutter on the same set.

Here we study two maps on clutters, the blocker map and the complementary map. Our main results include simple characterizations of these maps, which essentially say: the blocker map (the complementary map) is the only nontrivial map interchanging contraction and deletion operations.

We also give new forbidden minor characterizations of matroids.

On the other hand, the blocker map and the complementary map are natural maps on clutters whenever we think of them as a generalization of circuits and bases of a matroid, respectively.

Using the convenient notion of clutter minor we *Partially supported by C.N.R.S.

📜 SIMILAR VOLUMES

Clutters and Circuits

✍ Lorenzo Traldi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 199 KB

We introduce a way to associate a family of circuits to an arbitrary clutter, suggested by a theorem of Lehman. Several characterizations of matroid ports using their circuits are presented. ᮊ 1997 Academic Press 0 0 0 Ž . component of M that contains e , then P M, e is completely unaffected 0 0 by

Monotone clutters

✍ Guoli Ding 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 700 KB

A clutter is k-monotone, completely monotone or threshold if the corresponding Boolean function is k-monotone, completely monotone or threshold, respectively. A characterization of k-monotone clutters in terms ofexcluded minors is presented here. This result is used to derive a characterization of 2

Clutters and circuits III

✍ Lorenzo Traldi 📂 Article 📅 2003 🏛 Springer 🌐 English ⚖ 134 KB

Clutters and Circuits, II

✍ Lorenzo Traldi 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 285 KB

We continue to study ways of defining circuits associated with clutters, and we give several new characterizations of matroid ports using their circuits. We also discuss the use of these circuits to analyze redundancies among elements appearing in nonmatroidal reliability problems.

On interval clutters

✍ Guoli Ding 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 157 KB

Clutters with τ2=2τ

✍ Guoli Ding 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 757 KB

## Motivated by Lehman's characterization of the minor-minimal clutters without the MFMC property, we propose a conjecture about the minor-minimal clutters with tlr< kq where k>2 is a fixed integer. We prove, without using Lehman's theorem, this conjecture for the case k=2. We introduce diadic clu