In the binomial random graph @math , when @math changes from @math (subcritical case) to @math and then to @math (supercritical case) for @math , with high probability the order of the largest component increases smoothly from @math to @math and then to @math . As a natural generalisation of random graphs and connectedness, we consider the binomial random @math -uniform hypergraph @math (where each @math -tuple of vertices is present as a hyperedge with probability @math independently) and the following notion of high-order connectedness. Given an integer @math , two sets of @math vertices are called if there is a walk of hyperedges between them such that any two consecutive hyperedges intersect in at least @math vertices. A @math -connected component is a maximal collection of pairwise @math -connected @math -tuples of vertices. Recently, the threshold for the appearance of the giant @math -connected component in @math and its order were determined. In this article, we take a closer look at the subcritical random hypergraph. We determine the structure, order, and size of the largest @math -connected components, with the help of a certain class of hypertrees' and related objects. In our proofs, we combine various probabilistic and enumerative techniques, such as generating functions and couplings with branching processes. Our study will pave the way to establishing a symmetry between the subcritical random hypergraph and the hypergraph obtained from the supercritical random hypergraph by deleting its giant @math -connected component.
Non-uniform hypergraphs appear in various domains of computer science as in the satisfiability problems and in data analysis. We analyse a general model where the probability for an edge of size t to belong to the hypergraph depends of a parameter ω t of the model. It is a natural generalization of the models of graphs used by Flajolet, Knuth and Pittel 11] and Janson, Knuth, Łuczak and Pittel 16]. The present paper follows the same general approach based on analytic combinatorics. We show that many analytic tools developed for the analysis of graphs can be extended surprisingly well to non-uniform hypergraphs. More specifically, we analyze their typical structure before and near the birth of the complex components, that are the connected components with more than one cycle. We derive the asymptotic number of sparse connected hypergraphs as their complexity, defined as the excess, increases. Although less natural than the number of edges, this parameter allows a precise description of the structure of hypergraphs. Finally, we compute some statistics of the model to link number of edges and excess.