1University of Illinois at Chicago, Department of Mathematics, Statistics, and Computer Science 2Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL, 60607 USA.
The electronic journal of combinatorics, Tome 29 (2022) no. 1
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.
1
University of Illinois at Chicago, Department of Mathematics, Statistics, and Computer Science
2
Department of Mathematics, Statistics, and Computer Science, University of Illinois, Chicago, IL, 60607 USA.
@article{10_37236_10513,
author = {Xizhi Liu and Dhruv Mubayi},
title = {On explicit constructions of designs},
journal = {The electronic journal of combinatorics},
year = {2022},
volume = {29},
number = {1},
doi = {10.37236/10513},
zbl = {1487.05033},
url = {http://geodesic.mathdoc.fr/articles/10.37236/10513/}
}
TY - JOUR
AU - Xizhi Liu
AU - Dhruv Mubayi
TI - On explicit constructions of designs
JO - The electronic journal of combinatorics
PY - 2022
VL - 29
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/10513/
DO - 10.37236/10513
ID - 10_37236_10513
ER -
%0 Journal Article
%A Xizhi Liu
%A Dhruv Mubayi
%T On explicit constructions of designs
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/10513/
%R 10.37236/10513
%F 10_37236_10513
Xizhi Liu; Dhruv Mubayi. On explicit constructions of designs. The electronic journal of combinatorics, Tome 29 (2022) no. 1. doi: 10.37236/10513
