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

Abstract: Let integer

n g e 3

and integer

r = r (n) g e 3

. Define the binomial random

r

-uniform hypergraph

H_{r} (n, p)

to be the

r

-uniform graph on the vertex set

[n]

such that each

r

-set is an edge independently with probability

p

. A hypergraph is linear if every pair of hyperedges intersects in at most one vertex. We study the probability of linearity of random hypergraphs

H_{r} (n, p)

via cluster expansion and give more precise asymptotics of the probability in question, improving the asymptotic probability of linearity obtained by McKay and Tian, in particular, when

r = 3

and

p = o (n^{- 7 / 5})

.

Review text

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.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Asymptotic linearity of binomial random hypergraphs via cluster expansion under graph-dependence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2672967)