Content deleted Content added
Citation bot (talk | contribs) Add: s2cid. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 2217/3732 |
→Random sampling lemma: fix typo in random sampling lemma |
||
Line 66:
===Random sampling lemma===
'''Lemma'''- Let ''H'' be a subgraph of ''G'' formed by including each edge of ''G'' independently with probability ''p'' and let ''F'' be the minimum spanning forest of ''H''. The [[Expected value|expected number]] of '''[[#F-heavy and F-light Edges|F-light]]''' edges in ''G'' is at most ''
To prove the lemma examine the edges of ''G'' as they are being added to ''H''. The number of [[#F-heavy and F-light Edges|F-light]] edges in ''G'' is independent of the order in which the edges of ''H'' are selected since the minimum spanning forest of ''H'' is the same for all selection orders. For the sake of the proof consider selecting edges for ''H'' by taking the edges of ''G'' one at a time in order of edge weight from lightest to heaviest. Let ''e'' be the current edge being considered. If the endpoints of ''e'' are in two disconnected components of ''H'' then ''e'' is the lightest edge connecting those components and if it is added to ''H'' it will be in ''F'' by the [[Minimum_spanning_tree#Cut_property|cut property]]. This also means ''e'' is [[#F-heavy and F-light Edges|F-light]] regardless of whether or not it is added to ''H'' since only heavier edges are subsequently considered. If both endpoints of ''e'' are in the same component of ''H'' then it is (and always will be) F-heavy by the [[Minimum_spanning_tree#Cycle_property|cycle property]]. Edge ''e'' is then added to ''H'' with probability ''p''.
| |||