Wojda's conjecture on packing digraphs

Less than 1 year old · traced to

Let DD and D′D' be digraphs, and let ∣A(D)∣|A(D)| denote the size of DD, meaning its number of arcs. For every integer nn and every mm satisfying

2≤m≤n2,2\leq m\leq \frac{n}{2},

write μ(n,k)\mu(n,k) for the smallest number such that there exist digraphs DD and D′D' of order nn, with ∣A(D)∣=k|A(D)|=k and ∣A(D′)∣=μ(n,k)|A(D')|=\mu(n,k), that do not pack. Wojda's conjecture. For every mm satisfying 2≤m≤n22\leq m\leq \frac{n}{2},

μ(n,n−m)=2n−⌊nm⌋.\mu(n,n-m)=2n-\left\lfloor\frac{n}{m}\right\rfloor.

Equivalently, the condition that one digraph has size at most n−mn-m and the other has size less than 2n−⌊n/m⌋2n-\lfloor n/m\rfloor guarantees that the two digraphs pack. The paper confirms the conjecture for m≥93m\geq 93 and n≥31mn\geq 31m; the general statement remains open.

References

Primary source

Maciej Cisiński and Andrzej Żak, “Further progress on Wojda's conjecture”, arXiv:2601.13085 (2026).

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.