MathDB
maximum number of mutually independent subsets of a $2^n $-element set

Source: Polish MO second round 1970 p6

August 28, 2024
combinatoricsSubsets

Problem Statement

If A A is a subset of X X , then we take A1=A A^1 = A , A−1=X−A A^{-1} = X - A . The subsets A1,A2,…,Ak A_1, A_2, \ldots, A_k are called mutually independent if the product A1ε1∩A2ε2…Akεk A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \ldots A_k^{\varepsilon_k} is nonempty for every system of numbers ε1,ε2,…,εk \varepsilon_1 , \varepsilon_2, \ldots, \varepsilon_k , such that ∣ε2∣= |\varepsilon_2| = 1 for i=1,2,…,k i = 1, 2, \ldots, k . What is the maximum number of mutually independent subsets of a 2n2^n -element set?
Back to ProblemsView on AoPS