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 cycle in the graph of length at most $k$. Let a $k$-allocation be a collection of disjoint $k$-cycles. For an allocation $A$ and node $v$, let $A(v)$ be the cycle containing $v$, where $A(v) = \varnothing$ if $v$ is not in a cycle. Let $G\setminus e$ be the graph obtained by deleting the edge $e$. Let $M^k(G)$ be the set of maximum-size $k$-allocations.
Consider an Erdos-Renyi random graph $G(m,p(m))$ with $m$ nodes, where between each node an undirected edge exists with probability $p(m)$ (and $p$ is a non-decreasing function). My question concerns the following: suppose we generate a graph $G(m,p(m))$, and then randomly draw a node $v$, edge $e \in G$, and allocations $A \in M^k(G)$ and $A' \in M^k(G\setminus e)$. What is the probability that $A(v) \neq A'(v)$? Denote this probability by $S(m)$. I'm really interested in the following question: Under what conditions does $S(m) \rightarrow 0$ as $m \rightarrow \infty$, and more importantly, what is the rate of convergence?
Yoshida and Zhou (2020) study a similar question, but do not discuss random graphs.
