Chin et al.'s sparse graph conjecture for spanning-subtree probability
Statement
Let be a sequence of connected graphs, each with vertices and edges, where is fixed. Here denotes the probability that a uniformly chosen subtree of is spanning. Chin et al.'s conjecture. Then
This conjecture asserts that subquadratic edge growth forces the spanning-subtree probability to vanish. The paper explicitly states that the conjecture is false: a path with a complete graph of order attached to each end provides a counterexample.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.