A note on explicit constructions of designs

Abstract

An $(n,r,s)$-system is an $r$-uniform hypergraph on $n$ vertices such that every pair of edges has an intersection of size less than $s$. Using probabilistic arguments, Rödl and Šiňajová showed that for all fixed integers $r>s\ge 2$, there exists an $(n,r,s)$-system with independence number $O\left(n^{1-\delta +o(1)}\right)$ for some optimal constant $\delta >0$ only related to $r$ and $s$. We show that for certain pairs $(r,s)$ with $s\le r/2$ there exists an explicit construction of an $(n,r,s)$-system with independence number $O\left(n^{1-\epsilon }\right)$, where $\epsilon >0$ is an absolute constant only related to $r$ and $s$. Previously this was known only for $s>r/2$ by results of Chattopadhyay and Goodman

9 pages

References in corpus (2)

• Progression-free sets in Z_4^n are exponentially small
• On generalized Erdős-Ginzburg-Ziv constants for ${\mathbb{Z}}_2^d$