3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ You can e-mail authors, asking for a copy of the paper. They might also help you with your question. $\endgroup$
    – Boris Bukh
    May 30, 2013 at 22:03

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Nice answer! could you suggest a good reading on design theory? $\endgroup$
    – DmitryZ
    May 31, 2013 at 6:41
  • 1
    $\begingroup$ Arguably the most popular textbook is the two volume set by Beth, Jungnickel, and Lenz: amazon.com/Design-Theory-Encyclopedia-Mathematics-Applications/… It covers lots of important classical results. It's a tad dry reading though. The next one is elementary and much more casual amazon.com/Design-Theory-Discrete-Mathematics-Applications/dp/… It's my favorite, but maybe it's too undergraduate-ish. This isn't design theory per se, but here's a really good book on the probabilistic method amazon.com/gp/product/0470170204 $\endgroup$ May 31, 2013 at 7:15
  • $\begingroup$ If you're interested in links to codes and graphs, here is a good one: amazon.com/… And this one is an incredible monograph on "triple systems" amazon.com/… Well, there are so many good books for design theorists, and I can go on and on and on forever. But I think I should stop already... $\endgroup$ May 31, 2013 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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