Perfect matchings in random uniform hypergraphs
Let \(V\) be a set of vertices and \(H\) a collection of subsets (called edges or hyperedges) of \(V\). Then the pair \((V, H)= H^*\) is called a hypergraph. If every edge in \(H\) is of the same size \(R\), then \(H^*\) is called \(R\)-uniform. It is called a complete \(R\)-uniform hypergraph on \(V\) if it contains all subsets of size \(R\) of \(V\). If \(n\) is the number of elements in \(V\), then a random hypergraph \(H^*_R(n, p)\) is a subhypergraph of the complete \(R\)-uniform hypergraph so that each edge belongs independently to the subhypergraph with \(p\) as its probability. A collection of pairwise disjoint edges is called a perfect matching if their union is the entire vertex set. A coupling (joint distribution) on \((G_3(n, p), H^*_3(n, q))\) is a probability space on the set of all pairs of 3-partite graphs and 3-partite 3-uniform hypergraphs on \(3n\) vertices. The main result of this paper is given by: If \(n^{-2/3}\log^{1/3} n\ll p\ll n^{-3/5}\), then there is a coupling on \((G_3(n,17p)\), \(H^{(3)^*}(n,p^3))\) such that \(P\) [all edges in \(H^{(3)^*} (n,p^3)\) are (vertex sets of) triangles in \(G_3(n, 17p)]= 1-0(1)\).
- Almost perfect matchings in random uniform hypergraphs
- Sandwiching random graphs: universality between random graph models
- Distributed algorithms for matching in hypergraphs
- Co-degrees resilience for perfect matchings in random hypergraphs
- Asymptotics for Shamir's problem
- Perfect matchings in random polyomino chain graphs
- Corrádi and Hajnal's theorem for sparse random graphs
- Perfect matchings via uniform sampling in regular bipartite graphs
- Equivalence of a random intersection graph and G (n ,p )
- scientific article; zbMATH DE number 5720905 (Why is no real title available?)
- Combinatorial and computational aspects of graph packing and graph decomposition
- scientific article; zbMATH DE number 949656 (Why is no real title available?)
- Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
- Perfect Matchings in Random r-regular, s-uniform Hypergraphs
- Hitting times for Shamir's problem
- Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
- Tilings in randomly perturbed graphs: Bridging the gap between Hajnal‐Szemerédi and Johansson‐Kahn‐Vu
- Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
- The hitting time of clique factors
- The hitting time of clique factors (extended abstract)
- Clique factors in pseudorandom graphs
- Increasing the flexibility of the herding attack
This page was built for publication: Perfect matchings in random uniform hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4434467)
