Skip to content

Erdős problem 74

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

No current result

No reviewed Result is current in Vela Mathematics Program. Retained source material is shown below.

Retained declaration

FormalConjectures/ErdosProblems/74.lean

Formal Conjectures

FormalConjectures/ErdosProblems/74.leanErdos74.erdos_744 linesExact file
True ↔  ∀ (f : ℕ → ℕ),    Filter.Tendsto f Filter.atTop Filter.atTop →      ∃ V G, G.chromaticNumber = ⊤ ∧ ∀ (n : ℕ), Erdos74.SimpleGraph.maxSubgraphEdgeDistToBipartite G n ≤ f n
OpenStatement only, no proof

Continue

Start a contributionBrowse the source filesOpen the collection entry

Search problems.science

Find a Problem, Result, source, or page