Skip to content

Erdős problem 150

A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let c(n)c(n) be the maximum number of minimal cuts a graph on nn 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 statement1 of 5

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

Does c(n)1/nαc(n)^{1/n}\to \alpha for some α<2\alpha <2?

It is unclear in [Er88] whether Erdős knew that the limit existed, which follows from a simple argument first given in the literature (to the best of my knowledge) by Bradač [Br24].

That α<2\alpha<2 was proved by Fomin, Kratsch, Todinca, and Villanger [FKTV08], who proved α1.7087\alpha \leq 1.7087. This was independently studied by Bradač [Br24] (unaware of this earlier work), who proved that α2H(1/3)1.8899\alpha \leq 2^{H(1/3)}\approx 1.8899, where H()H(\cdot) is the binary entropy function.

FormalConjectures/ErdosProblems/150.leanErdos150.erdos_1501 lineExact file
True ↔ ∃ α < 2, Filter.Tendsto (fun n => ↑(Erdos150.maxMinimalCuts n) ^ (1 / ↑n)) Filter.atTop (nhds α)
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page