The complete-intersection conjecture for uniform partition systems

About 19 years old · traced to

Let Ukn\mathcal{U}^n_k be the family of uniform kk-partitions of an nn-set, and let a partition system be tt-intersecting when every two partitions have at least tt common classes. For 0≤i≤⌊k−t2⌋0\leq i\leq\left\lfloor\frac{k-t}{2}\right\rfloor, define

Pi(n,k,t)={P∈Ukn:∣P∩{[1,c],[c+1,2c],…,[(t+2i−1)c+1,(t+2i)c]}∣≥t+i}.\mathcal{P}_i(n,k,t)=\left\{P\in\mathcal{U}^n_k:\left|P\cap\{[1,c],[c+1,2c],\ldots,[(t+2i-1)c+1,(t+2i)c]\}\right|\geq t+i\right\}.

Complete-intersection conjecture. For n≥k≥t≥1n\geq k\geq t\geq1, if P⊆Ukn\mathcal{P}\subseteq\mathcal{U}^n_k is tt-intersecting, then

∣P∣≤max⁡0≤i≤(k−t)/2∣Pi(n,k,t)∣.|\mathcal{P}|\leq\max_{0\leq i\leq (k-t)/2}|\mathcal{P}_i(n,k,t)|.

The source presents this as the partition-system analogue of the Ahlswede–Khachatrian theorem. It also conjectures uniqueness up to permutations of the ground set; the fuller candidate statement is recorded here as the principal claim.

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.