Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence (Q2672967)

The binomial random \(r\)-uniform hypergraph \(H_r(n,p)\) is formed by considering a ground set of size \(n\) and including each of the \(\binom{n}{r}\) possible \(r\)-subsets as an edge to \(H\) independently, each with probability \(p\). A hypergraph is linear if no two of its edges intersect in two vertices or more. The article studies the (asymptotic as \(n \rightarrow \infty\), and over suitable choices of \(p = p(n)\)) probability \(\Pr(H_r(n,p) \text{ is linear})\), which is the probability that a random binomial \(r\)-uniform hypergraph is linear. The author utilises the method of cluster expansion, which is a tool from statistical physics which has found numerous applications in enumerative and probabilistic combinatorics. In summary, the probability of interest can be written as \(\Pr(X = 0)\), where \(X = \sum_{v} X_v\) is a certain sum of non-independent indicator random variables. The dependences of \(X_v\) are captured by a dependency graph \(D\). It turns out that \(\log \Pr(X = 0)\) allows a `cluster expansion', which means that it can be written as a formal infinite sum over clusters, which in this case correspond to certain sequences of connected subgraphs (polymers) of \(D\). Then, approximations and truncations of this infinite sum yield approximations to \(\Pr(X = 0)\), as desired. The paper provides a short and nice introduction to the cluster expansion machinery, story, and possible uses; tailored to this specific case. The main result of the paper is a formula for \(\Pr(H_r(n,p) \text{ is linear})\), which is written in terms of a certain explicit dependency graph \(D\), and works in the range where \(p = o(n^{2-r})\). For a fixed value of \(r\), this allows for a calculation of \(\Pr(H_r(n,p) \text{ is linear})\) with more detail, subject to certain explicit calculations which depend on the corresponding dependency graph \(D\). As a proof of concept, the author studies the \(3\)-uniform case \(\Pr(H_3(n,p) \text{ is linear})\) in detail, and under the assumption \(p = o(n^{-7/5})\) provides an asymptotic formula for (the logarithm of) \(\Pr(H_3(n,p) \text{ is linear})\) with four additive terms. This particular calculation refines a result by \textit{B. D. McKay} and \textit{F. Tian} [Adv. Appl. Math. 115, Article ID 102000, 47 p. (2020; Zbl 1433.05159)], which gave a formula with two terms.