Component structure in the evolution of random hypergraphs
From MaRDI portal
The authors generalize studies of Paul Erdős and A. Rényi on probable structure of random graphs with n labeled vertices and given density. They prove some theorems on the size \(C(d^*(n))\) of the greatest connected component in a random hypergraph. If the hypergraph has n vertices, the size of its largest edge is t, (2\(\leq t\leq 0(\ell n n))\) and the average vertex degree is \(d^*(n)\), then with probability tending to 1 when n tends to infinity: \(C(d^*(n))=0(t\quad \log n)\) for \(d<1\); \(C(d^*(n))=0(n^{2/3})\) for \(d\approx 1\); \(C(d^*(n))=0(n/t)\) for \(d>1\). It means here we can also find the well-known double jump which was described in case of random graphs.
Recommendations
Cites work
- A threshold for perfect matchings in random d-pure hypergraphs
- Asymptotical Estimations for the Number of Cliques of Uniform Hypergraphs
- Cliques in random graphs
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3482343 (Why is no real title available?)
- scientific article; zbMATH DE number 3338381 (Why is no real title available?)
- scientific article; zbMATH DE number 3388040 (Why is no real title available?)
- Random hypergraph coloring algorithms and the weak chromatic number
- Sur la cardinalite maximum des couplages d'hypergraphes aléatoires uniformes
- The longest path in a random graph
Cited in
(52)- Probabilistic analysis of strong hypergraph coloring algorithms and the strong chromatic number
- Phase transition phenomena in random discrete structures
- The phase transition in a random hypergraph
- Independence numbers of random sparse hypergraphs
- Charting the replica symmetric phase
- Structure of large random hypergraphs
- Phase transition in the spanning-hyperforest model on complete hypergraphs
- The size of the giant component in random hypergraphs: a short proof
- Operator growth bounds from graph theory
- Loose cores and cycles in random hypergraphs
- Phase transition in cohomology groups of non-uniform random simplicial complexes
- General independence sets in random strongly sparse hypergraphs
- The size of the giant joint component in a binomial random double graph
- Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
- Critical random hypergraphs: the emergence of a giant set of identifiable vertices
- Phase transitions in discrete structures
- The structure of an evolving random bipartite graph
- The order of the giant component of random hypergraphs
- Evolution of high-order connected components in random hypergraphs
- Creation and Growth of Components in a Random Hypergraph Process
- Sharp thresholds of graph properties, and the k-sat problem
- Can you feel the double jump?
- On the security of Goldreich's one-way function
- Essential edges in Poisson random hypergraphs
- Largest components in random hypergraphs
- Counting solutions to random CNF formulas
- Subcritical random hypergraphs, high-order components, and hypertrees
- Longest paths in random hypergraphs
- Efficient algorithms for three‐dimensional axial and planar random assignment problems
- Random triangular groups at density \(1/3\).
- On the second largest component of random hyperbolic graphs
- Counting connected hypergraphs via the probabilistic method
- Local limit theorems for the giant component of random hypergraphs
- The asymptotic number of connected \(d\)-uniform hypergraphs
- Exploring hypergraphs with martingales
- The condensation transition in random hypergraph 2-coloring
- Geometric properties of satisfying assignments of random ε-1-in-kSAT
- scientific article; zbMATH DE number 7651160 (Why is no real title available?)
- Random recursive hypergraphs
- Birth and growth of multicyclic components in random hypergraphs
- Limiting probabilities of first order properties of random sparse graphs and hypergraphs
- What Are Higher-Order Networks?
- Capability accumulation and conglomeratization in the information age
- Connectivity of random hypergraphs with a given hyperedge size distribution
- Sparse random hypergraphs: non-backtracking spectra and community detection
- Counting solutions to random CNF formulas
- Exploring the sharp propagation connectivity threshold in hypergraphs
- Quantum chaos in the sparse SYK model
- Disorder chaos in short-range, diluted, and Lévy spin glasses
- Property FA for random -gonal groups
- Networks beyond pairwise interactions: structure and dynamics
- The average size of giant components between the double-jump
This page was built for publication: Component structure in the evolution of random hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1063043)
