Min-Max Degree Optimization in Edge-Minimal Hall-Type Key Assignments

This paper studies a key distribution problem on bipartite graphs G = (M, R, E), where M is a set of n members and R is a set of m rooms (m ≤ n). Specifically, we consider a system where any subset of m members must be able to simultaneously access all m rooms with distinct keys. By Hall’s Marriage Theorem, the minimum total number of keys needed to make m-room matchings is m(n − m + 1). We focus on how to distribute these keys fairly among members so that the maximum key holding number is optimized. This parameter is introduced as ∆(m, n). We first prove that every room must hold exactly n − m + 1 keys in any minimal valid assignment. Then, we demonstrate that ∆(m, n) = Ceil(m(n−m+1)/n) for all positive integers m ≤ n. Finally, we propose two future research problems on member regularity and non-abelian finite groups.