Erdős–Pósa constant dependence on |H|
Open Problem (constant c vs. |H|) · arXiv:1807.04969
Status open high confidence
The open problem asks for good bounds on the constant $c = c(H)$ in the Erdős-Pósa bounding function $f(k) = ck\log(k+1)$ for planar minors, and in particular whether $c$ can be made to depend only polynomially on $|H|$. The original paper's proof yields an enormous (possibly non-computable) constant $c$, while Chekuri–Chuzhoy achieve polynomial dependence on $|H|$ at the cost of extra poly-logarithmic factors. No subsequent work resolving this specific quantitative question was found in a thorough search of the literature as of May 2026.
Reviewer notes. No follow-up paper specifically addressing the quantitative dependence of $c$ on $|H|$ was found. The related 2020 paper 'Erdős-Pósa from ball packing' (Cames van Batenburg, Joret, Ulmer; SIDMA) provides an alternative proof framework for edge variants but does not resolve the constant-vs-|H| question. The paper arXiv:2407.09671 ('Obstructions to Erdős-Pósa Dualities for Minors') addresses half-integrality and characterisation of EP-counterexamples, not the quantitative bound on $c$. The open problem remains unresolved with high confidence.
Context
The constant $c = c(H)$ obtained in the proof of Theorem 1.1 is enormous and not even known to be computable, whereas Chekuri and Chuzhoy's earlier result achieves $c$ depending polynomially on $|H|$ (at the cost of a poly-logarithmic factor $\log^d k$). The authors explicitly leave the question of good bounds on $c$ as a function of $|H|$ as an open problem.
Notes. Stated in prose in the introduction without a labelled environment: "Finding good bounds on c as a function of |H| is left as an open problem, in particular it would be interesting to determine whether c could depend polynomially on |H|."
Source paper
A tight Erdős-Pósa function for planar minors
Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond · 2019-10-23
https://arxiv.org/abs/1807.04969
PDF source