The uniform partially-intersecting partition-system conjecture

From papers

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 tct\leq c and n=ckn=ck. If PUkn\mathcal{P}\subseteq\mathcal{U}^n_k is partially tt-intersecting, then

P(ntct)U(nc,k1).|\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={PUkn:[1,t]Pi for some PiP}.\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.