Maximum-density dimer packings (maximum matchings) of non-bipartite site-diluted lattices, such as the triangular and Shastry-Sutherland lattices in $d=2$ dimensions and the stacked-triangular and corner-sharing octahedral lattices in $d=3$, generically exhibit a nonzero density of monomers (unmatched vertices). Following a construction in the recent literature, we use the structure theory of Gallai and Edmonds to decompose the disordered lattice into ``${ \mathcal R}$-type'' regions which host the monomers of any maximum matching, and perfectly matched ``${ \mathcal P}$-type'' regions from which such monomers are excluded. When the density $n_v$ of quenched vacancies lies well within the low-$n_v$ geometrically percolated phase of the disordered lattice, we find that the random geometry of these regions exhibits unusual { \em Gallai-Edmonds percolation} phenomena. In $d=2$, we find two phases separated by a critical point, namely a phase in which all ${ \mathcal R}$-type and ${ \mathcal P}$-type regions are small, and a percolated phase that displays a striking lack of self-averaging in the thermodynamic limit: Each sample has a single percolating region which is of type ${ \mathcal R}$ with probability $f_{ \mathcal R}$ and type ${ \mathcal P}$ with probability $1-f_{ \mathcal R}$, where $f_{ \mathcal R} \approx 0.50(2)$ is independent of $n_v$ (away from the critical region). In this regime, microscopic changes in the vacancy configuration lead to chaotic changes in the large-scale structure of ${ \mathcal R}$-type and ${ \mathcal P}$-type regions. In $d=3$, apart from a phase with small ${ \mathcal R}$-type and ${ \mathcal P}$-type regions, the thermodynamic limit exhibits { \em four} distinct percolated phases separated by critical points at successively lower $n_v$, two of which again display unusual violations of self-averaging. Physical consequences are also discussed.
Categories: cond-mat.dis-nn cond-mat.str-el