# making a random uniform hypergraph linear

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

• A linear hypergraph cannot have more than $\binom n2/\binom h2$ edges (count pairs of vertices), which is far smaller than $m$ if $p$ is not very small. So usually you can't make it linear by removing $o(m)$ edges. – Brendan McKay Aug 26 '20 at 9:49
• Hi Brendan, I could restrict to $p\sim n^{1-h+1/\ell}$. So a linear hypergraph would have at most $\frac{n(n-1)}{h(h-1)}$ edges while the random hypergraph has $\binom{n}{h}p \sim n^{1+1/\ell}\cdot h^{-h}$ edges (I think), so $p$ should be small enough. – Thomas Lesgourgues Aug 26 '20 at 10:43
• See Theorem 3 and Lemma 4 here. A combinatorial classic - sparse graphs with high chromatic number Note that a 2-cycle is when two hyperedges intersect in at least 2 vertices. So by making the girth greater than $\ell$, this also ensures that the hypergraph is linear. – Louis D Aug 26 '20 at 15:20
• Thanks @LouisD, I managed to track down the actual result, not trivial, not that difficult. – Thomas Lesgourgues Aug 27 '20 at 7:35

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.