All Questions
Tagged with matching-theory random-graphs
8
questions
1
vote
0
answers
18
views
How sensitive are maximum-size matchings to edge deletion in random graphs?
My question concerns the sensitivity of maximum-size matchings (and more generally maximum-size $k$-cycle collections) to deletion of an edge in the graph.
Given a graph $G$, let a $k$-cycle be a ...
- 11
1
vote
0
answers
58
views
Distribution of $k$-matchings in a random graph
Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
4
votes
1
answer
225
views
How many connected components in this random graph?
I was reading this blog post about minimum-weight matchings on two-color point sets in the unit square and it got me thinking.
Suppose you have 3 colors (Red, Blue, Green), and randomly drop $N$ ...
- 3,536
2
votes
1
answer
249
views
Threshold function for the existence of a perfect matching in $G(n,p)$ (from the book of Frieze and Karonski)
I'm reading Introduction to Random Graphs by Frieze and Karonski. Theorem 6.2 determines the threshold for the appearance of a perfect matching in $\mathbf{G}_{n,p}$:
Let $\omega=\omega(n)$, $c>0$...
- 3,407
0
votes
1
answer
71
views
Vertex expander bounded away from zero
Show that for a family of ε-vertex expanders the expansion parameter $h(G_j )$ stays bounded away
from 0. Conversely, let $G_1$, $G_2$, . . . be a sequence of k-regular graphs whose number of vertices ...
- 1,913
0
votes
1
answer
67
views
Vertex expander bounded
Let $G_1$, $G_2$, . . . be a family of ε-vertex expanders on $n_1$, $n_2$, . . . vertices. Show that there is a constant c such that eventually the diameter of $G_j$ is bounded from above by c · log($...
- 1,913
2
votes
1
answer
524
views
Perfect matching in a random bipartite graph with edge probability 1/2
I am trying to prove that, when given a bipartite graph $G=(X \cup Y, E)$ with $|X|=|Y|=n$ and edge probability $\frac{1}{2}$, as $n\rightarrow \infty$ the probability of the graph having a perfect ...
user763105
2
votes
1
answer
356
views
Perfect matching in random bipartite graph - with fixed probability
as a follow up from this question :
Suppose that we have a simpler problem, where the probability $p$ is fixed. Of course we could use the above result to proove that almost every graph in the model ...
- 4,730