错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimal abundant packings and choosability with separation

  • Zoltán Füredi,
  • Alexandr Kostochka,
  • Mohit Kumbhat

摘要

A (vkt) 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. P(vkt) stands for the maximum possible b. A packing is called abundant if \(b> v\) b > v . We give new estimates for P(vkt) around the critical range, slightly improving the Johnson bound and asymptotically determine the minimum \(v=v_0(k,t)\) v = v 0 ( k , t ) when abundant packings exist. For a graph G and a positive integer c, let \(\chi _\ell (G,c)\) χ ( 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\) | L ( v ) | = k for all \(v\in V(G)\) v V ( G ) and \(|L(u)\cap L(v)|\le c\) | L ( u ) L ( v ) | c for all \(uv\in E(G)\) u v E ( G ) . Kratochvíl, Tuza and Voigt in 1998 asked to determine \(\lim _{n\rightarrow \infty } \chi _\ell (K_n,c)/\sqrt{cn}\) lim n χ ( K n , c ) / cn (if it exists). Using our bound on \(v_0(k,t)\) v 0 ( k , t ) , we prove that the limit exists and equals 1. Given c, we find the exact value of \(\chi _\ell (K_n,c)\) χ ( K n , c ) for infinitely many n.