---

Statement

Setting (p. 2). The Kneser graph $KG(\mathcal F)$ of a family $\mathcal F$ has vertex set $\mathcal F$, two members being joined when they are disjoint.

Theorem 4 (Berge, p. 2). Let $\mathcal B$ be a down-set. Then one of the following holds:

• (i) $|\mathcal B|$ is even and $KG(\mathcal B)$ has a perfect matching;
• (ii) $|\mathcal B|$ is odd and $KG(\mathcal B\setminus\{\emptyset\})$ has a perfect matching.

The paper attributes Theorem 4 to an unpublished 1980 manuscript of Berge (its reference [1]) and proves it at the end of Section 3, restated as Theorem 13 (p. 7): a down-set $\mathcal A\subset2^{[n]}$ "can be matched to itself", meaning that $\mathcal A$ or $\mathcal A\setminus\{\emptyset\}$ can be partitioned into pairs of disjoint sets.

Theorem 3 (p. 2). If $\mathcal B\subset2^{[n]}$ is a down-set and $\mathcal F\subset\mathcal B$ is intersecting, then

$$|\mathcal F|\le|\mathcal B|/2. \tag{4}$$

The paper proves (4) from the non-uniform Erdős–Ko–Rado bound $|\mathcal F|\le2^{n-1}$ for intersecting $\mathcal F\subset2^{[n]}$ (its Theorem 1, p. 1) and the Harris–Kleitman inequality (its Theorem 2, p. 2), calls it a weaker result than Chvátal's conjecture, and notes that Berge's Theorem 4 implies it. The reason, an observation of this page: an intersecting family takes at most one set from each disjoint pair and never the empty set.

Proof pointer

Theorem 3, p. 2: the up-set $\mathcal A=\mathcal F^\uparrow$ generated by $\mathcal F$ is intersecting, so $|\mathcal A|\le2^{n-1}$, and Harris–Kleitman applied to $\mathcal A\cap\mathcal B\supset\mathcal F$ gives (4).

Theorem 13, pp. 7--8, by induction on $n$. Split $\mathcal A$ into the traces $\mathcal A(n)\subset\mathcal A(\bar n)\subset2^{[n-1]}$ of its members containing and avoiding $n$, both down-sets, and match each to itself by induction. Observation 1 (p. 7): the union of two matchings is a bipartite graph, so the pairs of the first matching can be oriented so that their first members form an independent set $\mathcal I$ in the union. Adding $n$ to the second member of each first-matching pair and to the members of second-matching pairs that lie in $\mathcal I$ gives disjoint pairs covering nearly all of $\mathcal A$; the parity cases of $|\mathcal A(n)|$ and $|\mathcal A(\bar n)|$ are closed by pairing $\{n\}$ with $\emptyset$ or with a maximal set of $\mathcal A(\bar n)\setminus\mathcal A(n)$ (p. 8).

Read depth

Claims checked: Theorems 3, 4 and 13 and the paper's remark that Theorem 4 implies (4) were read clause by clause on the print; the proof of Theorem 3 was followed, and the proof of Theorem 13 was followed for its structure and not checked line by line. Theorems 1 and 2 are cited by the paper, not proved there. Nothing here is independently reviewed.

Dependencies

None in the corpus. External inputs named by the paper for Theorem 3: the non-uniform Erdős–Ko–Rado theorem (Erdős, Ko and Rado, Quart. J. Math. Oxford 12 (1961)) and the Harris–Kleitman inequality (Harris, Proc. Cambridge Phil. Soc. 56 (1960); Kleitman, J. Combin. Theory 1 (1966)).

Source. P. Frankl and A. Kupavskii, Perfect matchings in down-sets, Discrete Math. 346 (2023), Paper No. 113323, DOI 10.1016/j.disc.2023.113323; read in arXiv:2201.03865v1, Theorems 3 and 4 on p. 2, Theorem 13 and its proof on pp. 7--8. The edition is identified on the source card.

Bears on

• Problem 701: Theorem 3, which Theorem 4 also implies, bounds every intersecting subfamily of a down-set $\mathcal B$ by $|\mathcal B|/2$. The paper calls this weaker than Chvátal's conjecture (the problem's corrected Statement), whose bound is the largest degree $\Delta(\mathcal B)$; for a down-set $\Delta(\mathcal B)\le|\mathcal B|/2$, since removing $x$ maps the members containing $x$ injectively to members avoiding it (an observation of this page).