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 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.

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.

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:

If a regular hypergraph $H$ has size $O(n^3)$, does it have an independent set with size $O(\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 $O(\sqrt{n})$. I would like to find a purely combinatorial analog of Sidon sets, with similar size and constraints. Randomized methods give independent sets with size $O(\sqrt[3]{n})$.

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

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 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.