Phase transition of random non-uniform hypergraphs

DOI10.1007/978-3-642-45278-9_12zbMATH Open1325.05122arXiv1304.5932OpenAlexW1986514804MaRDI QIDQ2018538FDOQ2018538

Authors: Elie de Panafieu 

Publication date: 24 March 2015

Published in: Lecture Notes in Computer Science, Journal of Discrete Algorithms (Search for Journal in Brave)

Abstract: 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 $omeg{a}_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, L{}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.

Full work available at URL: https://arxiv.org/abs/1304.5932

Recommendations

• Phase transition of random non-uniform hypergraphs
• The phase transition in a random hypergraph
• Critical random hypergraphs: the emergence of a giant set of identifiable vertices
• The cycle structure of a random nonhomogeneous hypergraph on the subcritical stage of evolution
• Birth and growth of multicyclic components in random hypergraphs

zbMATH Keywords

phase transitionhypergraphanalytic combinatorics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)

Cites Work

• Analytic combinatorics
• Title not available (Why is that?)
• A critical point for random graphs with a given degree sequence
• On convergence rates in the central limit theorems for combinatorial structures
• The number of connected sparsely edged graphs
• Title not available (Why is that?)
• The birth of the giant component
• Title not available (Why is that?)
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• The first cycles in an evolving graph
• Sparse random graphs with clustering
• Component structure in the evolution of random hypergraphs
• The phase transition in a random hypergraph
• Structure of large random hypergraphs
• The number of connected sparsely edged uniform hypergraphs
• Finite size scaling for the core of large random hypergraphs
• Counting connected graphs inside-out
• Hypergraphs and a functional equation of Bouwkamp and de Bruijn
• The asymptotic number of labeled connected graphs with a given number of vertices and edges
• The number of connected sparsely edged graphs. III. Asymptotic results
• Birth and growth of multicyclic components in random hypergraphs
• Counting connected graphs asymptotically
• Airy phenomena and analytic combinatorics of connected graphs
• Decorated hypertrees

Cited In (8)

• Model-based clustering for random hypergraphs
• Chemically inspired Erdős-Rényi hypergraphs
• An average study of hypergraphs and their minimal transversals
• Exact enumeration of satisfiable 2-SAT formulae
• Subcritical Random Hypergraphs, High-Order Components, and Hypertrees
• Phase transition in the spanning-hyperforest model on complete hypergraphs
• The cycle structure of a random nonhomogeneous hypergraph on the subcritical stage of evolution
• The birth of the strong components

This page was built for publication: Phase transition of random non-uniform hypergraphs

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