The effect of local majority on global majority in connected graphs

Abstract

Let $\mathcal{G}$ be an infinite family of connected graphs and let $k$ be a positive integer. We say that $k$ is $forcing$ for $\mathcal{G}$ if for all $G\in \mathcal{G}$ but finitely many, the following holds. Any $\{-1,1\}$-weighing of the edges of $G$ for which all connected subgraphs on $k$ edges are positively weighted implies that $G$ is positively weighted. Otherwise, we say that it is $weaklyforcing$ for $\mathcal{G}$ if any such weighing implies that the weight of $G$ is bounded from below by a constant. Otherwise we say that $k$ $collapses$ for $\mathcal{G}$. We classify $k$ for some of the most prominent classes of graphs, such as all connected graphs, all connected graphs with a given maximum degree and all connected graphs with a given average degree.