← All problems

Picasarri-Arrieta–Rambaud C(k,k)-subdivision question

For each integer k≥2k\ge 2, let C(k,k)C(k,k) be the oriented graph consisting of two internally vertex-disjoint directed paths of length kk with the same initial vertex and the same terminal vertex. Determine the smallest integer gkg_k such that every finite digraph DD satisfying δ+(D)≥2\delta^+(D)\ge 2 and digirth⁡(D)≥gk\operatorname{digirth}(D)\ge g_k contains a subdivision of C(k,k)C(k,k). The claimed answer is gk=k+1g_k=k+1 for every k≥2k\ge 2.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An October 2026 preprint claims to settle the question, but its exact answer has not been independently checked.

The question asks for the smallest digirth forcing every digraph of minimum out-degree at least 22 to contain a subdivision of C(k,k)C(k,k). Picasarri-Arrieta and Rambaud initiated the problem in 2024.

Known results

  • Picasarri-Arrieta and Rambaud (2024): digirth at least 8k−68k-6 forces a subdivision of C(k,k)C(k,k).
  • Picasarri-Arrieta and Rambaud (2024): examples with digirth k−1k-1 and minimum out-degree 22 avoid such a subdivision.
  • Chen, Hou, Ma, Yin, and Zhou (March 14, 2026): improved the forcing bound to 4k+24k+2 and narrowed the threshold to k+1≤g≤4k+2k+1\leq g\leq4k+2.
  • The same 2026 work proved a stronger out-degree variant and constructed examples with digirth at least kk that avoid C(k,k)C(k,k).

October 2026 claimed resolution

A later preprint by Bin Chen, Jianfeng Hou, Xinmin Hou, Siyue Liu, Xinjie Wang, and Xinyu Zhou claims to determine the exact forcing digirth and to sharpen the related out-forest bound. The claim is from an unrefereed preprint and has not been independently assessed.

Current status (as of October 2026): An October 2026 preprint claims the exact threshold is settled, but the resolution remains unverified; the earlier published record only establishes k+1≤g≤4k+2k+1\leq g\leq4k+2.

Sources

Solutions 0

No solutions have been posted yet.