𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On chvátal's conjecture related to a hereditary system

✍ Scribed by Peter Stein


Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
800 KB
Volume
43
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis


It is shown that among the maximal intersecting systems, which are subsystems of a hereditary family F, there is a star, as claimed by a conjecture of ChvBtal, if it is assumed, that the number of bases of F is n, but it -1 bases of F form a simple-star.

1. Mroduction

V. Chv;ital [l] conjectured that if F={A1, AZ, . . . , A,)-is ;d system of difierent subsets of a finite set M and F has the hereditary property, i.e. F= b%, AZ,.. .y A,) = Ui=l P(Ai), where P(Ai) = (X: XC Ai}, then among the subsystems G of F, which are maximal intersecting systems, i.e. no two disjoint sets in G, and G is maximal in respect to cardinality, there is a star, i.e. a system the intersection of all of its members being nonempty.

Earlier and recent results proving the conjecture for particular systems F are cited in [2-7).

In this paper we will prove the conjecture in the case when the number of buses, i.e. of maximal members in F, in respect to inclusions, is II, but n -1 bases form a simple-star, i.e. a system the intersection of all of its members being non-empty and being equal to the intersections of any two of its members.


📜 SIMILAR VOLUMES