Minimal abundant packings and choosability with separation (Q6651912)

A \((v, k, t)\) packing of size \(b\) is a system of \(b\) subsets (blocks) of a \(v\)-element underlying set such that each block has \(k\) elements and every \(t\)-set is contained in at most one block. Let \(P(v, k, t)\) stand for the maximum possible \(b\). A packing is called abundant if \(b > v\). In this paper, the authors give new estimates for \(P(v, k, t)\) around the critical range, slightly improving the Johnson bound and asymptotically determining the minimum \(v = v_0(k, t)\) when abundant packings exist: Let \(t \geq 2\) and suppose that \(k \rightarrow \infty\). Then \(v_0(k, t) = (1 + o(1))k^2/(t-1)\). For a graph \(G\) and a positive integer \(c\), let \(\chi_{\ell}(G, c)\) be the minimum value of \(k\) such that one can properly color the vertices of \(G\) from any assignment of lists \(L\)(v) such that \(|L(v)| = k\) for all \(v \in V(G)\) and \(|L(u) \cap L(v)| \leq c\) for all \(uv \in E(G)\). \textit{J. Kratochvíl} et al. [J. Graph Theory 27, No. 1, 43--49 (1998; Zbl 0894.05016)] asked to determine \( \lim_{n\rightarrow \infty} \chi_{\ell}(K_n, c)/ \sqrt{nc}\) (if it exists). Using the bound on \(v_0(k, t)\), it is proved that the limit exists and equals 1. Given \(c\), the exact value of \(\chi_{\ell}(K_n, c)\) is given for infinitely many \(n\). A conjecture concludes the paper.