Partition concentration conjecture for powers of paths

From papers

Fix integers k2k\geq2 and mk+1m\geq k+1. Let PP be an mm-path whose vertex set is partitioned as

V(P)=V1Vk+1.V(P)=V_1\cup\dots\cup V_{k+1}.

For a vertex subset VjV_j, write P[Vj]P[V_j] for the induced subgraph, and let f(k,m)f(\ell_{k,m}) be the quantity defined in the paper. Partition concentration conjecture. There exists a positive constant c=c(m)c=c(m) such that some j[k+1]j\in[k+1] satisfies

E(P[Vj])f(k,m)Vjc(m).|E(P[V_j])|\geq f(\ell_{k,m})|V_j|-c(m).

This is proposed as a strengthening of a lemma that would confirm the preceding over-threshold conjecture. Its status is open in the source.

Progress summary

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

Sources & referencesView supporting material

Primary source

Sylwia Antoniuk, Andrzej Dudek and Andrzej Ruciński, “Powers of Hamiltonian cycles in randomly augmented Pósa-Seymour graphs”, arXiv:2512.23886 (2025).

Solutions 0

No solutions have been posted yet.