Clutters with τ2=2τ

✍ Scribed by Guoli Ding

• Book ID: 103057784
• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 757 KB
• Volume: 115
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90484-b

✦ Synopsis

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 clutters, which are defined as clutters H with the property that 1 An BJ <2 for all edges A of H and B of b(H). For diadic clutters, we present explicitly all of the minor-minimal clutters with z2 < 2~.

Q(H) = max {r: there exists a list of r edges of H, with repetition allowed, such that no vertex of H is contained in more than k members of this list} r,(H)=min(r:

there exists a list of r vertices of H, with repetition allowed, such that no edge of H contains fewer than k members of this list}