making a random uniform hypergraph linear

Question

Let $\mathcal{H}_{n,p,h}=(V,E)$ be a random $h$-uniform hypergraph on $[n]$, sampled according to the usual binomial distribution. We known that with high probability, the number of edges in $\mathcal{H}_{n,p,h}$ is $$m = (1+o(1))\binom{n}{h}p$$

Let $\ell$ be given. I would like to delete some edges in order to

• have a linear hypergraph (any two edges share at most one vertex)
• remove all cycles of length at most $\ell$

I expect that we should be able to do so by deleting with high probabilities $o(m)$ edges, however simple first moment method are failing me... I try to count the number of Berge-cycle of length of length at most $\ell$, but simply looking at potential cycles for each pair of vertices I over-count way too much.

Is there any known upper bound for the number of cycles ? I found some literature on the probability threshold for the appearance of cycles, but not much on counting the cycles.

Edit: I could restrict to very small $p$. For some constant $c>2$, $$ p = c \cdot n^{1-h+1/\ell}$$

Answer 1

Note: in order to understand the proof, it was key (at least for me) to see that a cycle of length $t$ in a $k$-uniform hypergraph is set of $t$ edges $(e_1,\ldots,e_t)$ such that (viewing each edge as a $k$-set of vertices) $$ \left\vert \bigcup_{i=1}^t e_i \right\vert \leq (k-1)t$$

Following @LouisD comment, I followed a trail of references

• A combinatorial classic - sparse graphs with high chromatic number by Jaroslav Nesetril, where lemma 4 is the hypergraph version ofthe famous theorem stating that we can find a graph with large girth and large chromatic number. The reference for this lemma is the following,
• On a probabilistic graph-theoretic Method, by Nesetril and Rodl, where the lemma page 3 is the same version, without complete proof, referencing the following book,
• P. Erdös and J. Spencer, Probabilistic methods in combinatorics, Akadémiai Kiado, Budapest; North-Holland, Amsterdam; Academic Press, New York, 1974. In there (I have no open source link), chapter 11, exercise 4 asks to prove the lemma, giving a final reference,
• Erdos,Hajnal, "ON CHROMATIC NUMBER OF GRAPHS AND SET-SYSTEMS" in there, page 96, is the proof of the lemma,

To do so, they introduce $z(H)$ which is for a given $k$-uniform hypergraph $H$ and a given $s$, the number of set of vertices of size exactly $(k-1)t$ for some $t\leq s$, forming a $t$-cycle. They then show that for all but $o\binom{\binom{n}{k}}{m}$ hypergraph on $n$ vertices and $m$ edges, $$ z(H)\leq \left(\frac{m}{n}\right)^s \log n$$

From there we can conclude that the number of edges in cycles of length of most $s$ is $$ \binom{(k-1)s}{k}\left(\frac{m}{n}\right)^s \log n$$

Which is the desired property as long as $m< n^{1+1/s}$. However I have one last remark

There is an argument I do not understand in the Erdos-Hajnal article : they consider a subset $V'$ of the $n$ vertices, $V'$ has size $(k-1)t$, and they want to upperbound the number of hypergraph $H$ on $n$ vertices and $m$ edges, with at least $t$ edges in $V'$. They claim (end of page 96) that this is at most $$ \binom{(k-1)t}{t}\binom{\binom{n}{k}}{m-t}$$ I would have expected rather $$ \binom{\binom{(k-1)t}{k}}{t}\binom{\binom{n}{k}}{m-t}$$ because we can select $t$ edges among the $k$-uniform edges in $V'$, and then select $m-t$ other edges in any of the $\binom{n}{k}$ edges (we could even substract by $t$ here, but that's okay for an upper bound).

Note that my result also yield $ z(H)\leq \left(\frac{m}{n}\right)^s \log n$, so it's not that important.