Partitioning the power set of [n] into Ck-free parts

Blaisdell, Eben and Gyárfás, András and Krueger, Robert A. and Wdowinski, Ronen (2019) Partitioning the power set of [n] into Ck-free parts. THE ELECTRONIC JOURNAL OF COMBINATORICS, 26 (3). pp. 1-12. ISSN 1077-8926

Preview

Text 1812.06448v1.pdf Download (167kB) | Preview

Abstract

We show that for n≥3,n≠5, in any partition of P(n), the set of all subsets of [n]={1,2,…,n}, into 2n−2−1 parts, some part must contain a triangle --- three different subsets A,B,C⊆[n] such that A∩B, A∩C, and B∩C have distinct representatives. This is sharp, since by placing two complementary pairs of sets into each partition class, we have a partition into 2n−2 triangle-free parts. We also address a more general Ramsey-type problem: for a given graph G, find (estimate) f(n,G), the smallest number of colors needed for a coloring of P(n), such that no color class contains a Berge-G subhypergraph. We give an upper bound for f(n,G) for any connected graph G which is asymptotically sharp (for fixed k) when G=Ck,Pk,Sk, a cycle, path, or star with k edges. Additional bounds are given for G=C4 and G=S3.

Actions (login required)

Edit Item