Erdős problem 74 · problems.science

Let $f(n)\to \infty$ possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?

Sources

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

4 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

74.lean

Retained formal statement1 of 4

Let $f(n)\to \infty$ possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on $n$ vertices can be made bipartite by deleting at most $f(n)$ edges?

FormalConjectures/ErdosProblems/74.leanErdos74.erdos_744 linesExact file

1True ↔2  ∀ (f : ℕ → ℕ),3    Filter.Tendsto f Filter.atTop Filter.atTop →4      ∃ V G, G.chromaticNumber = ⊤ ∧ ∀ (n : ℕ), Erdos74.SimpleGraph.maxSubgraphEdgeDistToBipartite G n ≤ f n

OpenStatement only, no proof

Sources

Search problems.science