Czabarka's conjecture for partially intersecting partition systems

About 19 years old · traced to

Let Pkn\mathcal{P}^n_k be the family of kk-partitions of an nn-set. Two partitions are partially 22-intersecting if some class of one and some class of the other have intersection of size at least 22; a system is partially 22-intersecting if every pair is so related. Let S(n−1,k)S(n-1,k) denote the corresponding extremal quantity used in the source.

Czabarka's conjecture. If n≤2k−1n\leq2k-1 and P⊆Pkn\mathcal{P}\subseteq\mathcal{P}^n_k is a partially 22-intersecting partition system, then

∣P∣≤S(n−1,k).|\mathcal{P}|\leq S(n-1,k).

The conjecture is attributed in the source to Czabarka and is cited to Erdős and Székely. The bound is attained by the system of partitions having a class containing a fixed pair.

References

Primary source

Karen Meagher, “Covering arrays on graphs: qualitative independence graphs and extremal set partition theory”, arXiv:math/0701553 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.