{
  "id": "1711.09422",
  "version": "v1",
  "published": "2017-11-26T17:04:09.000Z",
  "updated": "2017-11-26T17:04:09.000Z",
  "title": "The effect of local majority on global majority in connected graphs",
  "authors": [
    "Yair Caro",
    "Raphael Yuster"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let ${\\mathcal G}$ be an infinite family of connected graphs and let $k$ be a positive integer. We say that $k$ is ${\\it 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 ${\\it weakly~forcing}$ 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$ ${\\it 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-11-26T17:04:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C78"
    ],
    "keywords": [
      "connected graphs",
      "local majority",
      "global majority",
      "maximum degree",
      "prominent classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}