Bucić, M; Letzter, S; Sudakov, B; (2019) Directed Ramsey number for trees. Journal of Combinatorial Theory, Series B , 137 pp. 145-177. 10.1016/j.jctb.2018.12.006.

Preview

Text directed-ramsey-number-for-paths.pdf - Accepted Version Download (450kB) | Preview

Abstract

We call a family F of subsets of [n] s-saturated if it contains no s pairwise disjoint sets, and moreover no set can be added to F while preserving this property (here [n] = {1, . . . , n}). More than 40 years ago, Erd˝os and Kleitman conjectured that an s-saturated family of subsets of [n] has size at least (1 − 2 −(s−1))2n. It is easy to show that every s-saturated family has size at least 1 2 · 2 n, but, as was mentioned by Frankl and Tokushige, even obtaining a slightly better bound of (1/2 + ε)2n, for some fixed ε > 0, seems difficult. In this note, we prove such a result, showing that every s-saturated family of subsets of [n] has size at least (1 − 1/s)2n. This lower bound is a consequence of a multipartite version of the problem, in which we seek a lower bound on |F1| + . . . + |Fs| where F1, . . . , Fs are families of subsets of [n], such that there are no s pairwise disjoint sets, one from each family Fi , and furthermore no set can be added to any of the families while preserving this property. We show that |F1| + . . . + |Fs| ≥ (s − 1) · 2 n, which is tight e.g. by taking F1 to be empty, and letting the remaining families be the families of all subsets of [n].

Download activity - last month

Export as JSONXMLCSV

Download activity - last 12 months

Export as JSONXMLCSV

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item