Partitioning the power set of \([n]\) into \(C_k\)-free parts (Q2323815): Difference between revisions

Summary: We show that for \(n \geq 3, n\ne 5\), in any partition of \(\mathcal{P}(n)\), the set of all subsets of \([n]=\{1,2,\dots,n\}\), into \(2^{n-2}-1\) parts, some part must contain a triangle -- three different subsets \(A,B,C\subseteq [n]\) such that \(A\cap B,A\cap C,B\cap C\) have distinct representatives. This is sharp, since by placing two complementary pairs of sets into each partition class, we have a partition into \(2^{n-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 \(\mathcal{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 when \(G\) is a cycle, path, or star. Additional bounds are given when \(G\) is a \(4\)-cycle and when \(G\) is a claw.