Connectivity of the linear uniform hypergraph process

作者：Tian, Fang^*

来源：Discrete Mathematics, 2022, 345(11): 113056.

DOI：10.1016/j.disc.2022.113056

• Asymptotic enumeration
• Graph process
• Linear hypergraph
• Connectivity

For any fixed integer r >= 3, a hypergraph is r-uniform if each edge is a set of r vertices, and is said to be linear if two distinct edges intersect in at most one vertex. The linear r-uniform hypergraph process starts with an empty hypergraph on vertex set [n] at time 0, the ((n)(r)) edges arrive one by one according to a uniformly chosen permutation, and each r edge is added if and only if it does not overlap any of the previously added edges in two or more vertices. In this paper, we show with high probability that the sharp threshold of connectivity in the process is n/r log n and the very edge which links the last isolated vertex with another vertex makes the linear hypergraph connected, which is same as for the general uniform hypergraph process. In fact, we prove the result under the more general condition that distinct edges overlap in less than l vertices, where 2 <= l <= r - 1; i.e., partial Steiner (n, r, l)-systems.