Unbalanced spanning subgraphs in edge labeled complete graphs

Abstract

Let $K$ be a complete graph of order $n$. For $d\in (0,1)$, let $c$ be a $\pm 1$-edge labeling of $K$ such that there are $d\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges with label $+1$, and let $G$ be a spanning subgraph of $K$ of maximum degree at most $\Delta$. We 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 }$ is at least $\left(c_{d,\Delta }-O\left(\frac{1}{n}\right)\right)m(G)$, where $c_{d,\Delta }=d+\Omega \left(\frac{1}{\Delta }\right)$ for fixed $d$, that is, this number visibly deviates from its expected value when considering a uniformly random copy of $G$ in $K$. For $d=\frac{1}{2}$, and $\Delta \le 2$, we present more detailed results.