Don Coppersmith, Igor Pak
Probability Theory and Related Fields
We define the subvariance S℘(ℱ) of a family of graphs ℱ with respect to property ℱ to be the infimum of the ratio |H1|/|H2|, where H1 and H2 are any two maximal spanning subgraphs of G with property ℘, and where G is a member of ℱ. It is shown that, for the family of all connected graphs, the subvariance when ℘ is planar, outerplanar, and bipartite planar, is 1/2, 1/2, and 1/2, respectively.
Don Coppersmith, Igor Pak
Probability Theory and Related Fields
Mihir Bellare, Don Coppersmith, et al.
IEEE Trans. Inf. Theory
Avrim Blum, Prasad Chalasani, et al.
STOC 1994
Don Coppersmith, Michael Elkin
SIAM Journal on Discrete Mathematics