Addario-Berry et al.'s antidirected-tree conjecture

About 10 years old · traced to

An oriented graph GG on nn vertices has an edge for each oriented edge of its underlying graph. An antidirected tree is an orientation of a tree in which every vertex has either in-degree 00 or out-degree 00, and the number of edges is its size. Addario-Berry et al.'s conjecture. For any integer k≥1k\geq 1, every oriented graph GG on nn vertices with more than (k−1)n(k-1)n edges contains each antidirected tree with kk edges.

References

Primary source

Andrzej Grzesik and Marek Skrzypczyk, “Antidirected paths in oriented graphs”, arXiv:2506.11866 (2025).

Additional references

5 papers in this index state this conjecture (2016–2025). The statement above is taken from the most recent of them; the others are arXiv:2411.13483, arXiv:2212.09876, arXiv:1912.04004, arXiv:1610.00876.

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.