Mohr–Pardey–Rautenbach's zero-sum tree-factor conjecture

About 2 years old · traced to

Let KnK_n be the complete graph on nn vertices, and let TT be a tree of order kk. A labeling c:E(Kn)→{−1,1}\mathbf{c}:E(K_n)\to\{-1,1\} is 0-sum if the sum of the labels of all edges of KnK_n is zero; a spanning forest whose components are all isomorphic to TT is a TT-factor, and it is 0-sum if the sum of the labels of its edges is zero.

Mohr–Pardey–Rautenbach's conjecture. Fix integers k,n≥1k,n\geq 1 such that (n2)\binom{n}{2} and (k−1)n/k(k-1)n/k are both even integers. If c:E(Kn)→{−1,1}\mathbf{c}:E(K_n)\to\{-1,1\} is a 0-sum labeling and nn is sufficiently large in terms of kk, then KnK_n has a 0-sum TT-factor.

The conjecture concerns zero-discrepancy decompositions of a balanced complete graph into copies of a fixed tree. The supplied text says that the conjecture is refuted by the preceding construction, so it is not an open conjecture.

References

Primary source

Lawrence Hollom, Lyuben Lichev, Adva Mond and Julien Portier, “Discrepancies of spanning trees in dense graphs”, arXiv:2410.17034 (2024).

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.