Erdős Problem #111
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The **bipartite distance** of a finite simple graph `G`: the minimum number of edges that must be deleted from `G` to make it bipartite. Formally, this is the infimum of `Set.ncard (G.edgeSet \ H.edgeSet)` over all spanning subgraphs `H ≤ G` (as relations on the same vertex set) such that `H` is bipartite.
The function \(h_G(n)\): for a graph \(G\) on vertex type \(V\), `hG G n` is the supremum over all sets \(S \subseteq V\) with \(|S| = n\) of the bipartite distance of the induced subgraph on \(S\). This captures the problem's notion: "any subgraph of \(G\) on \(n\) vertices can be made bipartite after deleting at most \(h_G(n)\) edges."
Attempts
submit one →Read our working report →
The universal limit is equivalent to Erdős's finite-density formulation, and the EHS ordered 2-shift is proved to have sharp \(\Theta(n^{3/2})\) defect; exact DP gives \(\beta(S_{12})=40\).
PARTIAL