Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-126 | 11th September 2013 20:45

Nontrivial t-designs over finite fields exist for all t

RSS-Feed




TR13-126
Authors: Arman Fazeli, Shachar Lovett, Alex Vardy
Publication: 12th September 2013 03:32
Downloads: 3221
Keywords: 


Abstract:

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known to exist only for $t \le 3$. Herein, we prove that simple (meaning, without repeated blocks) nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ exist for all $t$ and $q$, provided that $k > 12t$ and $n$ is sufficiently large. This may be regarded as a $q$-analog of the celebrated Teirlinck theorem for combinatorial designs.



ISSN 1433-8092 | Imprint