Return to Answer

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

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

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

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

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

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