Skip to main content
1 of 4
Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43

No. You can't improve it to $o(n^2)$.

Let $\operatorname{ex}_{C_2}(n)$ be the largest possible number of edges of a $4$-uniform hypergraph on $n$ vertices that contains no cycle of length $2$. You can prove that there exists constant $c$ and $n'$ such that for all $n > n'$, $\operatorname{ex}_{C_2}(n) \geq cn^2$.

If you know design theory, you can prove a much stronger theorem. In fact, for any sufficiently large $n$, there exits a $4$-uniform hypergraph on $n$ vertices with $\frac{n(n-1)}{12}-c$ edges that contains no cycle of length $2$, where $c$ is a constant. Because one edge contains ${4}\choose{2}$ pairs out of all distinct ${n}\choose{2}$ pairs, this packs all pairs at most once while almost achieving the trivial upper bound on the number of edges, i.e., almost the best possible way of gathering edges while avoiding a cycle of length $2$. If $n(n-1) \equiv 0 \pmod{12}$, you can do better and can actually gather hyperedges in a way all pairs are used up. This is a simple corollary of one of the main theorems of the following paper:

Y. M. Chee, C. J. Colbourn, A. C. H. Ling, R. M. Wilson, Covering and packing for pairs, J. Combin. Theory Ser. A 120 (2013) 1440–1449.

The arguments used in the paper are definitely overkill for your purpose, though. There are cute and elementary design theoretic techniques to prove a bit weaker theorems that are good enough for your purpose.

But since the paper you linked to is on extremal combinatorics, you might like a simple use of the probabilistic method better. Here's one simple way to prove you can get $c'\cdot n^2$ edges for some constant $c'$:

Let $V$ be a finite set of cardinality $n$. Take uniformly at random $4$-subsets of $V$ (i.e., edges) with probability $p = c\cdot n^2$, where $c$ is a positive constant.

The expected value of the number $f$ of cycles of length $2$ you get is upper bounded by ${{n}\choose{6}}\cdot {{{6}\choose{4}}\choose{2}}p^2$. By Markov's Inequality, the probability that you end up with more than or equal to twice the expected value is smaller than or equal to $\frac{1}{2}$. Hence, you have the probably

$$P\left(f \leq 2{{n}\choose{6}}\cdot {{{6}\choose{4}}\choose{2}}p^2\right) \geq \frac{1}{2}.$$

Let $t$ be the random variable counting the number of edges and $E(t)$ its expected value. Then $E(t) = {{n}\choose{4}}p$. Because $t$ is a binomial random variable, by Chernoff's inequality, for sufficiently large $n$ we have

$P\left(t < \frac{E(t)}{2}\right) < e^{-\frac{E(t)}{8}} < \frac{1}{2}$. Hence, if $n$ is sufficiently large, with positive probability we obtain edge set $\mathcal{E}$ with $\vert\mathcal{E}\vert > {{n}\choose{4}}p$ that contains at most $2{{n}\choose{6}}\cdot {{{6}\choose{4}}\choose{2}}p^2$ cycles of length $2$. Deleting one edge from each forbidden cycle will give you a desired $4$-uniform hypergraph. Hence, you can have at least

$${{n}\choose{4}}p - 2{{n}\choose{6}}\cdot {{{6}\choose{4}}\choose{2}}p^2$$

edges while avoiding cycles of length $2$ with positive probability.

So, all we need to do is choose a good $c$ for the probability $p=c\cdot n^2$ so that the above number is of the form $c'n^2 + O(n)$ for some constant $c'$. This can be done if we pick small enough $c$.

Yuichiro Fujiwara
  • 3.7k
  • 1
  • 25
  • 43