ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a positive integer nn, let A\mathcal{A} be a non-empty bridge-addable set of graphs on {1,…,n}\{1,\ldots,n\}: whenever a graph belongs to A\mathcal{A}, adding an edge between vertices in distinct connected components produces another graph in A\mathcal{A}. Let G\mathbf{G} be uniformly distributed on A\mathcal{A}, and let F\mathbf{F} be uniformly distributed on the set Fn\mathcal{F}_n of forests on {1,…,n}\{1,\ldots,n\}. Strong bridge-addable connectivity conjecture. For every nn and every such A\mathcal{A},

P{G is connected}≥P{F is connected}.\mathbf{P}\{\mathbf{G}\text{ is connected}\}\geq\mathbf{P}\{\mathbf{F}\text{ is connected}\}.

This is a stronger finite-nn formulation of the conjecture that forests are asymptotically the worst bridge-addable classes for connectivity. The original asymptotic conjecture is stated to remain open in the source, and this stronger formulation is proposed without a resolution.

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.