Maximum matchings in a class of random graphs
From MaRDI portal
A random graph D(n,m) is obtained by first picking uniformly at random a digraph with vertex set \(\{\) 1,...,n\(\}\) and each outdegree m, and then ignoring orientations of edges. It is not hard to show that D(n,1) almost surely has no perfect matching. Shamir and Upfal proved that D(n,6) almost surely has a perfect matching for n even. The present paper shows that this conclusion holds for D(n,2). The proof is based on a refinement of Tutte's theorem on the existence of perfect matchings, and involves many careful estimations.
Recommendations
- Maximum matchings in general graphs through randomization
- Combinatorial Geometry and Graph Theory
- The number of matchings in random graphs
- A concentration inequality for maximum matching size in random graphs1
- scientific article; zbMATH DE number 1512672
- scientific article; zbMATH DE number 731847
- On maximal matchings of connected graphs
- Small maximal matchings in random graphs.
- Maximum matching in regular and almost regular graphs
- Random matchings in regular graphs
Cites work
- An exact threshold theorem for random graphs and the node-packing problem
- scientific article; zbMATH DE number 3154393 (Why is no real title available?)
- Matchings in random regular bipartite digraphs
- On the connectivity of random m-orientable graphs and digraphs
- On the existence of Hamiltonian cycles in a class of random graphs
- One-factor in random graphs based on vertex choice
- Paths, Trees, and Flowers
- Random near-regular graphs and the node packing problem
- The Factorization of Linear Graphs
Cited in
(37)- Random near-regular graphs and the node packing problem
- An exact threshold theorem for random graphs and the node-packing problem
- Matchings and cycle covers in random digraphs
- Matching theory -- a sampler: From Dénes König to the present
- Random matchings in regular graphs
- Small maximal matchings in random graphs.
- Existence of a perfect matching in a random (\(1+e^{-1}\))-out bipartite graph
- Maximum induced matchings of random cubic graphs
- Maximum matchings of a digraph based on the largest geometric multiplicity
- Edge disjoint spanning trees in random graphs
- Factorially many maximum matchings close to the Erdős-Gallai bound
- Corrigendum to: ``Existence of a perfect matching in a random \((1+e^{-1})\)-out bipartite graph
- Minimum-weight combinatorial structures under random cost-constraints
- Invariant random perfect matchings in Cayley graphs
- Perfect fractional matchings in \(k\)-out hypergraphs
- Perfect matchings in random intersection graphs
- On maximum matchings in König-Egerváry graphs
- On random k-out subgraphs of large graphs
- Karp-Sipser on random graphs with a fixed degree sequence
- scientific article; zbMATH DE number 2127722 (Why is no real title available?)
- scientific article; zbMATH DE number 4029631 (Why is no real title available?)
- scientific article; zbMATH DE number 4073029 (Why is no real title available?)
- scientific article; zbMATH DE number 3777557 (Why is no real title available?)
- scientific article; zbMATH DE number 731847 (Why is no real title available?)
- Maximal matchings in graphs with large neighborhoods of independent vertices
- scientific article; zbMATH DE number 4114698 (Why is no real title available?)
- scientific article; zbMATH DE number 825131 (Why is no real title available?)
- A concentration inequality for maximum matching size in random graphs1
- Rank of the Vertex-Edge Incidence Matrix of r-Out Hypergraphs
- Exact matching of random graphs with constant correlation
- Power of \(k\) choices in the semi-random graph process
- Rainbow Spanning Trees in Randomly Colored \(\boldsymbol{G}_{\boldsymbol{k}-\boldsymbol{out}}\)
- Cliques, chromatic number, and independent sets in the semi-random process
- Streaming edge coloring with asymptotically optimal colors
- Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model
- On maximal matchings of connected graphs
- Maximum matchings in regular graphs of high girth
This page was built for publication: Maximum matchings in a class of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1093654)
