The multiple-constraint Erdős–Pósa conjecture

Let t1t\geq 1 be a positive integer, and let

Γ=i=1tΓi,\Gamma=\bigoplus_{i=1}^t\Gamma_i,

where each Γi\Gamma_i is a group. A i=1tΓi\bigoplus_{i=1}^t\Gamma_i-labeled graph is a graph whose edges are labeled by this direct sum, and a cycle is (Γ1,,Γt)(\Gamma_1,\dots,\Gamma_t)-non-zero when it is non-zero in every component.

Multiple-constraint Erdős–Pósa conjecture. The set of all i=1tΓi\bigoplus_{i=1}^t\Gamma_i-labeled graphs has the half-integral Erdős–Pósa property for (Γ1,,Γt)(\Gamma_1,\dots,\Gamma_t)-non-zero cycles. Moreover, the Erdős–Pósa function does not depend on the choice of Γ1,,Γt\Gamma_1,\dots,\Gamma_t.

This would imply the half-integral Erdős–Pósa property for cycles satisfying more than two constraints. The conjecture proposes a uniform Erdős–Pósa function across all choices of the component groups; its resolution is not given in the source.

Sources & referencesView supporting material

Primary source

Tony Huynh, Felix Joos and Paul Wollan, “A unified Erdős-Pósa theorem for constrained cycles”, arXiv:1605.07082 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.