A note on explicit constructions of designs


Abstract in English

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{o}dl and v{S}iv{n}ajov{a} showed that for all fixed integers $r> s ge 2$, there exists an $(n,r,s)$-system with independence number $Oleft(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 $sle r/2$ there exists an explicit construction of an $(n,r,s)$-system with independence number $Oleft(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

Download