ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GnG_n be a sequence of connected graphs, each with nn vertices and O(nα)O(n^{\alpha}) edges, where α<2\alpha<2 is fixed. Here P(G)P(G) denotes the probability that a uniformly chosen subtree of GG is spanning. Chin et al.'s conjecture. Then

lim⁡n→∞P(Gn)=0.\lim_{n \to \infty}P(G_n)=0.

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 ⌊n⌋\lfloor\sqrt n\rfloor 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.