Partition concentration conjecture for powers of paths

About 1 year old · traced to

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

V(P)=V1∪⋯∪Vk+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)∣Vj∣−c(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.

References

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).

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.