On explicit constructions of designs (Q2121799)

An \((n, r, s)\)-system is a family of \(r\)-subsets of an \(n\)-set, such that the intersection of any two \(r\)-subsets contains less than \(s\) elements. The authors study the existence of explicit constructions of \((n, r, s)\)-systems with a given property, that is, algorithms that run in polynomial time in \(n\) and produce an \((n, r, s)\)-system with the given property. The property considered by the authors is that the independence number of the \((n, r, s)\)-system, that is, the maximum size of a set that contains no \(r\)-subset, is bounded by a given constant. Extending previous results in [\textit{E. Chattopadhyay} and \textit{J. Goodman}, ``Explicit extremal designs and applications to extractors'', Preprint, \url{arXiv:2007.07772}; \textit{E. Chattopadhyay} et al., in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 1184--1197 (2020; Zbl 07298320)], the authors prove the following theorems: Theorem. There exists a constant \(C > 0\) such that for every integer \(r \in \{4, 5, 6\}\) and every integer \(n > r\) there exists an explicit construction of an \((n, r, 2)\)-system with independence number \(\leq Cn^{0.973}\). Theorem. If \(s = 3^{l_1}4^{l_2}5^{l_3}6^{l_4} + 1\), and if \(2s \leq r \leq R(s)\), then there exist constants \(C(l_1,l_2,l_3,l_4)\) and \(\varepsilon(l_1,l_2,l_3,l_4)\) such that for every integer \(n > r\) there exists an explicit construction of an \((n, r, s)\)-system with independence number at most \(Cn^{1-\varepsilon}\). (Herein we omit the expression of \(R(s)\) given in the statement.) Theorem. There exists a constant \(C > 0\) such that for every integer \(n > 5\) there exists an explicit construction of an \((n, 5, 4)\)-systems with independence number at most \(Cn^{\log_3 2} \leq Cn^{0.631}\).