{
  "id": "2406.03355",
  "version": "v1",
  "published": "2024-06-05T15:11:32.000Z",
  "updated": "2024-06-05T15:11:32.000Z",
  "title": "Nordhaus-Gaddum inequalities for the number of cliques in a graph",
  "authors": [
    "Deepak Bal",
    "Jonathan Cutler",
    "Luke Pebody"
  ],
  "comment": "15 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "Nordhaus and Gaddum proved sharp upper and lower bounds on the sum and product of the chromatic number of a graph and its complement. Over the years, similar inequalities have been shown for a plenitude of different graph invariants. In this paper, we consider such inequalities for the number of cliques (complete subgraphs) in a graph $G$, denoted $k(G)$. We note that some such inequalities have been well-studied, e.g., lower bounds on $k(G)+k(\\overline{G})=k(G)+i(G)$, where $i(G)$ is the number of independent subsets of $G$, has been come to be known as the study of Ramsey multiplicity. We give a history of such problems. One could consider fixed sized versions of these problems as well. We also investigate multicolor versions of these problems, meaning we $r$-color the edges of $K_n$ yielding graphs $G_1,G_2,\\ldots,G_r$ and give bounds on $\\sum k(G_i)$ and $\\prod k(G_i)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-05T15:11:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "nordhaus-gaddum inequalities",
      "lower bounds",
      "similar inequalities",
      "graph invariants",
      "multicolor versions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}