Let $H$ be a $4$-uniform hypergraph on $[1..n]$, i.e. $H$ is a collection of $4$-element subsets of $[1..n]$. The elements of $H$ are called edges. A hypergraph is regular if every element of $[1..n]$ are in the same number of edges.


An **independent set** $I$ of $H$ is a subset of $[1..n]$ such that $I$ does not contain any edge. The **independence number** of $H$ is the maximal cardinality among independent sets of $H$.


**Question:** 


Does there exist two positive numbers $c$, $d$ such that every regular 4-uniform hypergraph on $[1..n]$ with size $<cn^3$ has an independent set with size $d\sqrt{n}$?


**Motivation:** 


Consider the problem of finding a Sidon set in $\mathbb{Z}\_n$. If we relax the problem by allowing 3-term arithmetic progressions, the problem can be encoded into hypergraph independence: $H=\{\{a,b,c,d\}|a,b,c,d\in\mathbb{Z}\_n,b-a=d-c ≠0,a≠c,a≠d\}$. Sidon sets are independent sets of $H$, the largest with size $\sqrt{n}(1+o(1))$. I would like to find a purely combinatorial analog of Sidon sets, with similar size and constraints. Randomized methods give independent sets with size $c\sqrt[3]{n}$.


References about hypergraph independence featuring some group structure (hence not "purely combinatorial") are also welcome. 



Independence number of $4$-uniform regular hypergraph
In general no. Partition the vertices onto $n/k$ subsets (I call them classes) of size $k$, where $k$ grows as $n^{2/3}$. Take into your hypergraph all 4-edges with the vertices in the same class. It has about $(n/k)k^4=nk^3\sim n^3$ edges, but each independent set contains at most $3$ vertices from each class, thus $O(n^{1/3})$ vertices.


Well, your graph is different and the things may go better. 


