Strong connectivity comparison conjecture for bridge-addable graph sets
Statement
For a positive integer , let be a non-empty bridge-addable set of graphs on : whenever a graph belongs to , adding an edge between vertices in distinct connected components produces another graph in . Let be uniformly distributed on , and let be uniformly distributed on the set of forests on . Strong bridge-addable connectivity conjecture. For every and every such ,
This is a stronger finite- 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.