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

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))=eE(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 FF' 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.

Sources & referencesView supporting material

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.