2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Brendan McKay Aug 26 '20 at 9:49
  • $\begingroup$ 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. $\endgroup$ – Thomas Lesgourgues Aug 26 '20 at 10:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Louis D Aug 26 '20 at 15:20
  • $\begingroup$ Thanks @LouisD, I managed to track down the actual result, not trivial, not that difficult. $\endgroup$ – Thomas Lesgourgues Aug 27 '20 at 7:35
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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