Counting two-forests and random cut size via potential theory

2023/08/07 by Richman, Harry, Shokrieh, Farbod, Wu, Chenxi · 1 citation
#05B35 #05C30 #14T15 #31C20 #82B20 #Combinatorics (math.CO) #Differential Geometry (math.DG) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2308.03859

Abstract

We prove a lower bound on the number of spanning two-forests in a graph, in terms of the number of vertices, edges, and spanning trees. This implies an upper bound on the average cut size of a random two-forest. The main tool is an identity relating the number of spanning trees and two-forests to pairwise effective resistances in a graph. Along the way, we make connections to potential theoretic invariants on metric graphs.

Cited by

• The trigonal construction and the second moment of the tropical Prym variety

Related

• Spanning 2-Forests and Resistance Distance in 2-Connected Graphs
• Graphs with at most two trees in a forest building process
• Counting rooted forests in a network
• Uniform spanning forest on the integer lattice with drift in one coordinate
• Forest Cuts in Sparse Graphs