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

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,n1k,n\geq 1 such that (n2)\binom{n}{2} and (k1)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.

Sources & referencesView supporting material

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.