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