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



making a random uniform hypergraph linear
**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](https://iti.mff.cuni.cz/series/2013/572.pdf) 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](https://www.researchgate.net/publication/239285245_On_a_Probabilistic_Graph-Theoretical_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](https://link.springer.com/article/10.1007/BF02020444)" 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.


