Wiki
Wiki

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

Updated


Claim. Theorem 7 of P. Frankl and A. Kupavskii, Perfect matchings in down-sets, Discrete Math. 346 (2023), no. 5, Paper No. 113323, first posted as arXiv:2201.03865 on 2022-01-11 (library card): if F⊂G⊂2[n]\mathcal F\subset\mathcal G\subset2^{[n]}, G\mathcal G is a down-set, F\mathcal F is intersecting and τ(F)≤2\tau(\mathcal F)\le2, then ∣F∣≤max⁡x∣{G∈G:x∈G}∣|\mathcal F|\le\max_x|\{G\in\mathcal G:x\in G\}|. Here τ(F)\tau(\mathcal F), the covering number, is the least tt such that some tt-set meets every member of F\mathcal F. This is the corrected Statement of Problem 701 for the intersecting subfamilies of covering number at most 22. The proof splits F\mathcal F along a cover {1,2}\{1,2\} into two cross-intersecting traces and applies Theorem 6, that cross-intersecting A,B⊂2[n]\mathcal A,\mathcal B\subset 2^{[n]} satisfy ∣A∣+∣B∣≤max⁡{∣A↓∣,∣B↓∣}|\mathcal A|+|\mathcal B|\le\max\{|\mathcal A^\downarrow|, |\mathcal B^\downarrow|\}. Theorem 6 is a corollary of the paper's main result, Theorem 5: for down-sets A,B\mathcal A,\mathcal B with ∣A∣≤∣B∣|\mathcal A|\le|\mathcal B|, the bipartite graph joining disjoint members has a matching that covers A\mathcal A.

Covers. Intersecting subfamilies of covering number at most 22; the case of covering number 11, a subfamily inside a star, is immediate. The site's remark places the covering condition on the family F\mathcal F of the problem, while the paper places it on the intersecting subfamily. Eifler, Gleixner and Pulaj state the same case, an intersecting family contained in the union of two stars, as their Theorem 5, attributed to a 1972 working paper of Kleitman and Magnanti (claim page).

Acceptance. Refereed: Discrete Math. 346 (2023), no. 5, Paper No. 113323. The site's curator credits the result, but the site labels the problem OPEN, so no review is listed.