# Independence number of $4$-uniform regular hypergraph

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

• In the question, do you want a lower bound on the size of the independent set also? Otherwise any 3-element set is independent and size $O(\sqrt{n})$. – Gabe Conant Jun 23 '19 at 11:59
• Why is a 3-element set of size $O(\sqrt{n})$ for large $n$? – LeechLattice Jun 23 '19 at 12:18
• Using what I understand to be the definition of "big-O" notation (e.g., here: en.wikipedia.org/wiki/Big_O_notation#Formal_definition), the constant function $3$ is $O(\sqrt{n})$. – Gabe Conant Jun 23 '19 at 12:35
• Thanks for your comment; I have corrected the post. – LeechLattice Jun 23 '19 at 12:42

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.