The bounded-discrepancy conjecture for spanning forests in zero-sum complete graphs

At least 4 years old · documented by

Let KnK_n be a complete graph, let c:E(Kn)→{−1,1}c:E(K_n)\to\{-1,1\} be a zero-sum labeling satisfying

c(E(Kn))=∑e∈E(Kn)c(e)=0,c(E(K_n))=\sum_{e\in E(K_n)}c(e)=0,

and let FF be a spanning forest of KnK_n. Write Δ(F)\Delta(F) for the maximum degree of FF. The bounded-discrepancy conjecture. There is an isomorphic copy F′F' of FF in KnK_n such that

∣c(E(F′))∣≤Δ(F)−12.|c(E(F'))|\leq\frac{\Delta(F)-1}{2}.

The conjecture would strengthen the general bound ∣c(E(F′))∣≤Δ(F)+1|c(E(F'))|\leq\Delta(F)+1 and is verified in the paper for stars; the theorem proved there also gives the claimed bound for spanning forests with sufficiently large maximum degree. The general case remains open.

References

Primary source

Elena Mohr, Johannes Pardey and Dieter Rautenbach, “Zero-sum copies of spanning forests in zero-sum complete graphs”, arXiv:2101.11233 (2021).

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.