Uniform 4-hypergraph avoiding 2-cycles

Question

There is a paper by Gy\H{o}ry and Lemons "Hypergraphs with No Cycle of a Given Length", which bounds number of hyperedges for hypergraphs avoiding cycles of length $2k$ (unfortunately, I have access only to the abstract: http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=8514699). Particularly, in the case of a uniform 4-hypergraph avoiding 2-cycles it seems to provide $O(n^2)$ bound. I am wondering if it is possible to improve this to $o(n^2)$ or it is sharp? Here 2-cycle simply means two hyperedges $E_1, E_2$ which intersect in $2$ vertices.

Answer 1

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 $\left\lfloor\frac{n}{4}\middle\lfloor\frac{(n-1)}{3}\middle\rfloor\right\rfloor-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, a simple upper bound is $\lfloor\frac{n(n-1)}{12}\rfloor$ (which is $\lfloor\frac{n}{4}\cdot\frac{n-1}{3}\rfloor$). This bound can be slightly strengthened by the Johnson bound to $\left\lfloor\frac{n}{4}\middle\lfloor\frac{(n-1)}{3}\middle\rfloor\right\rfloor$, which is the non-constant term of the number of edges of the hypergraph through design theory mentioned above. Hence, this hypergraph packs all pairs at most once while almost achieving the 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 = \frac{c}{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=\frac{c}{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$.