Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Statement

Conjecture (p. 65, unnumbered), as posed: "Let FF be a family of subsets of a finite set SS such that X∈FX\in F, Y⊂X⇒Y∈FY\subset X\Rightarrow Y\in F. Then there is a t∈St\in S such that every intersecting subfamily GG of FF satisfies ∣G∣≤∣{X∈F:t∈X}∣|G|\le|\{X\in F: t\in X\}|."

Here a family is intersecting when any two of its members, not necessarily distinct, meet (p. 62). The hypothesis is closure under taking subsets, and the finite ground set SS is part of it. The paper introduces the conjecture as a possible "strengthening of our theorem" (p. 65): the Theorem (p. 62) gives the conclusion with t=1t=1 under the stronger hypothesis of closure under the left-shift order on S={1,…,n}S=\{1,\dots,n\}.

Source. V. Chvátal, Intersecting families of edges in hypergraphs having the hereditary property, in: Hypergraph Seminar (Ohio State Univ., Columbus, 1972), Lecture Notes in Math. 411, Springer, Berlin, 1974, pp. 61--66; the Conjecture on p. 65. The edition is identified on the source card.

Read depth. Claims checked: the statement was read clause by clause on the page image, and the quotation matches the print. A conjecture has no proof to check.

Proof pointer

None; the paper poses the statement as a conjecture and proves only the case of the Theorem (p. 62).

Dependencies

None.

Bears on

  • Problem 701: this Conjecture is the problem's corrected Statement, which restores the finite ground set SS that the site's wording omits. The paper records no proof of it; the claims about it are recorded on the problem page.