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


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}$?


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.

  • $\begingroup$ 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})$. $\endgroup$ – Gabe Conant Jun 23 '19 at 11:59
  • $\begingroup$ Why is a 3-element set of size $O(\sqrt{n})$ for large $n$? $\endgroup$ – LeechLattice Jun 23 '19 at 12:18
  • $\begingroup$ 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})$. $\endgroup$ – Gabe Conant Jun 23 '19 at 12:35
  • $\begingroup$ Thanks for your comment; I have corrected the post. $\endgroup$ – 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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.