Erdős problem 150 · problems.science

A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let $c(n)$ be the maximum number of minimal cuts a graph on $n$ vertices can have.

Sources

Browse retained paths and inspect the exact material available for this Problem.

5 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

150.lean

Retained formal statement5 of 5

The current best-known bounds on $\alpha$ are $1.4457\leq \alpha \leq \frac{1+\sqrt{5}}{2}\approx 1.618.$ The upper bound is due to Fomin and Villanger [FoVi12] (with a simpler proof in [GaMa18]).

FormalConjectures/ErdosProblems/150.leanErdos150.erdos_150.variants.upper_bound1 lineExact file

1∀ (α : ℝ), Filter.Tendsto (fun n => ↑(Erdos150.maxMinimalCuts n) ^ (1 / ↑n)) Filter.atTop (nhds α) → α ≤ (1 + √5) / 2

SolvedStatement only, no proof

Sources

Search problems.science