2013/04/30 by Élie de Panafieu, Elie de Panafieu
Computer Science · Mathematics · Physics and Astronomy · #Artificial intelligence #Combinatorics #Complex Network Analysis Techniques #Computer science #Connected component #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Generalization #Graph #Graph theory and applications #Hypergraph #Mathematics #Random graph #Satisfiability #Topological and Geometric Data Analysis #math.CO
paper · pdf · doi:10.1016/j.jda.2015.01.009
published as Journal of Discrete Algorithms (2015), pp. 26-39 · 29 pages, 6 figures
openalex publication_date 2015/02/02 · arxiv created 2015/03/05 · arxiv updated 2015/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 presented in "The first cycles in an evolving graph" [Flajolet, Knuth, Pittel, 1989] and in the "Birth of the giant component" [Janson, Knuth, Łuczak, Pittel, 1993]. 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. Specifically, we investigate random hypergraphs with a large number of vertices n and a complexity, defined as the "excess", proportional to n. We analyze their typical structure before, near and after the birth of the "complex" components, that are the connected components with more than one cycle. Finally, we compute statistics of the model to link number of edges and excess.