Unbalanced spanning subgraphs in edge labeled complete graphs (Q2692172)

For a complete graph on \(n\) vertices, an edge labeling is said to be balanced if there are equally many plus-edges and minus-edges, that is edges with label \(+1\) and \(-1\), respectively. The authors are stimulated by the work of \textit{Y. Caro} et al. [``Unavoidable chromatic patterns in 2-colorings of the complete graph'', J. Graph Theory 97, 123--147 (2021; \url{doi.org/10.1002/jgt.22645})] on omnitonal graphs. A graph \(G\) is said to be omnitonal if for every pair \((K,c)\), where the order \(n\) of \(K\) is sufficiently large and there are sufficiently many plus-edges and minus-edges in \(K\), and for every two non-negative integers \(m^+\) and \(m^-\) with \(m(G)=m^++m^-\), there is an isomorphic copy \(G'\) of \(G\) in \(K\) with \(m^+(G^\prime)=m^+\) and \(m-(G^\prime)=m^-\). What is new in this study is that the order of \(K\) is necessarily much bigger than the order of \(G\), that is, the graph \(G\) is far from being a spanning subgraph of \(K\). Noting the fact that the higher the density of a spanning graph \(G\) is, the more every isomorphic copy of \(G\) in \(K\) is forced to reproduce the density of plus- and minus-edges in \((K,c)\) the authors consider graphs of bounded maximum degree as a natural hypothesis excluding dense spanning subgraphs. The authors prove the existence of an isomorphic copy \(G^\prime\) of \(G\) in \(K\) such that the number of edges with label \(+1\) in \(G^\prime\) exceeds the expected value \(d\) times \(m(G)\) when considering a uniformly random copy of \(G\) in \(K\).