Kiselev–Kozik conjecture on satisfying sequences for rainbow partite matchings

Let s,n,ks,n,k be positive integers, and let a sequence (fi)i=1s(f_i)_{i=1}^s be called satisfying when it has the property that any ss families in [n]k[n]^k whose respective sizes exceed fif_i contain a cross-matching. The sequences

fi=ink1f_i=i n^{k-1}

and

fi=min{i+Cslogs,s1}nk1,i=1,,s,f_i=\min\{i+C\sqrt{s\log s},s-1\}n^{k-1},\qquad i=1,\ldots,s,

are satisfying, where CC is an absolute constant. Kiselev–Kozik's conjecture. The two sequences above are satisfying. The first sequence asserts the sharp asymmetric multipartite analogue of the Aharoni–Howard conjecture, while the second captures the previously observed square-root error term. The Aharoni–Howard conjecture itself was resolved for all s>470s>470, but these stronger assertions about satisfying sequences remain open in the supplied source.

Sources & referencesView supporting material

Primary source

Andrey Kupavskii and Elizaveta Popova, “Satisfying sequences for rainbow partite matchings”, arXiv:2502.03105 (2025).

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.