The uniform partially-intersecting partition-system conjecture

About 19 years old · traced to

Let Ukn\mathcal{U}^n_k be the family of uniform kk-partitions of an nn-set. Two partitions are partially tt-intersecting if some class from each has intersection of size at least tt.

Uniform partial-intersection conjecture. Let k,c,tk,c,t be positive integers with t≤ct\leq c and n=ckn=ck. If P⊆Ukn\mathcal{P}\subseteq\mathcal{U}^n_k is partially tt-intersecting, then

∣P∣≤(n−tc−t)U(n−c,k−1).|\mathcal{P}|\leq\binom{n-t}{c-t}U(n-c,k-1).

Moreover, equality holds if and only if, up to a permutation of [1,n][1,n],

P={P∈Ukn:[1,t]⊆Pi for some Pi∈P}.\mathcal{P}=\{P\in\mathcal{U}^n_k:[1,t]\subseteq P_i\text{ for some }P_i\in P\}.

The conjecture generalizes the preceding partially 2-intersecting problem from arbitrary partition systems to uniform partition systems.

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.