{
  "id": "enwiki-001292431244",
  "slug": "common-graph",
  "title": "Common graph",
  "qid": "",
  "lead": "In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, F is a common graph if it \"commonly\" appears as a subgraph, in a sense that the total number of copies of F in any graph G and its complement \\overline{G} is a large fraction of all possible copies of F on the same vertices. Intuitively, if G contains few copies of F , then its complement \\overline{G} must contain lots of copies of F in order to compensate for it. Common graphs are closely related to other graph notions dealing with homomorphism density inequalities. For example, common graphs are a more general case of Sidorenko graphs.",
  "body": "In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking, F is a common graph if it \"commonly\" appears as a subgraph, in a sense that the total number of copies of F in any graph G and its complement \\overline{G} is a large fraction of all possible copies of F on the same vertices. Intuitively, if G contains few copies of F , then its complement \\overline{G} must contain lots of copies of F in order to compensate for it. Common graphs are closely related to other graph notions dealing with homomorphism density inequalities. For example, common graphs are a more general case of Sidorenko graphs. For a graph G , we have t(F, G) = t(F, W_{G}) and t(F, \\overline{G})=t(F, 1 - W_G) for the associated graphon W_G , since graphon associated to the complement \\overline{G} is W_{\\overline{G}}=1 - W_G . Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means, W to W_G , and see t(F, W) as roughly the fraction of labeled copies of graph F in \"approximate\" graph G . Then, we can assume the quantity t(F, W) + t(F, 1 - W) is roughly t(F, G) + t(F, \\overline{G}) and interpret the latter as the combined number of copies of F in G and \\overline{G} . Hence, we see that t(F, G) + t(F, \\overline{G}) \\gtrsim 2^{-e(F)+1} holds. This, in turn, means that common graph F commonly appears as subgraph. In other words, if we think of edges and non-edges as 2-coloring of edges of complete graph on the same vertices, then at least 2^{-e(F)+1} fraction of all possible copies of F are monochromatic. Note that in a Erdős–Rényi random graph G = G(n, p) with each edge drawn with probability p=1/2 , each graph homomorphism from F to G have probability 2 \\cdot 2^{-e(F)} = 2^ {-e(F) +1} of being monochromatic. So, common graph F is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph G at the graph G=G(n, p) with p=1/2 p=1/2 . The above definition using the generalized homomorphism density can be understood in this way. ===Sidorenko graphs are common=== A graph F is a Sidorenko graph if it satisfies t(F, W) \\ge t(K_2, W)^{e(F)} for all graphons W . In that case, t(F, 1 - W) \\ge t(K_2, 1 - W)^{e(F)} . Furthermore, t(K_2, W) + t(K_2, 1 - W) = 1 , which follows from the definition of homomorphism density. Combining this with Jensen's inequality for the function f(x) = x^{e(F)} : t(F, W) + t(F, 1 - W) \\ge t(K_2, W)^{e(F)} + t(K_2, 1 - W)^{e(F)} \\ge 2 \\bigg( \\frac{t(K_2, W) + t(K_2, 1 - W)}{2} \\bigg)^{e(F)} = 2^{-e(F) + 1} Thus, the conditions for common graph is met. ===The triangle graph is common=== Expand the integral expression for t(K_3, 1 - W) and take into account the symmetry between the variables: \\int_{[0, 1]^3} (1 - W(x, y))(1 - W(y, z))(1 - W(z, x)) dx dy dz \\int{[0, 1]^3} W(x, y) W(x, z) dx dy dz = t(K_{1, 2}, W) \\int_{[0, 1]^3} W(x, y) W(y, z) W(z, x) dx dy dz = t(K_3, W) where K_{1, 2} denotes the complete bipartite graph on 1 vertex on one part and 2 vertices on the other. It follows: t(K_3, W) + t(K_3, 1 - W) = 1 - 3 t(K_2, W) + 3 t(K_{1, 2}, W) . t(K_{1, 2}, W) can be related to t(K_2, W) thanks to the symmetry between the variables y and z : \\begin{alignat}{4} t(K_{1, 2}, W) &= \\int_{[0, 1]^3} W(x, y) W(x, z) dx dy dz && \\\\ &= \\int_{x \\in [0, 1]} \\bigg( \\int_{y \\in [0, 1]} W(x, y) \\bigg) \\bigg( \\int_{z \\in [0, 1]} W(x, z) \\bigg) && \\\\ &= \\int_{x \\in [0, 1]} \\bigg( \\int_{y \\in [0, 1]} W(x, y) \\bigg)^2 && \\\\ &\\ge \\bigg( \\int_{x \\in [0, 1]} \\int_{y \\in [0, 1]} W(x, y) \\bigg)^2 = t(K_2, W)^2 \\end{alignat} where the last step follows from the integral Cauchy–Schwarz inequality. Finally: t(K_3, W) + t(K_3, 1 - W) \\ge 1 - 3 t(K_2, W) + 3 t(K_{2}, W)^2 = 1/4 + 3 \\big( t(K_2, W) - 1/2 \\big)^2 \\ge 1/4 . This proof can be obtained from taking the continuous analog of Theorem 1 in \"On Sets Of Acquaintances And Strangers At Any Party\"",
  "categories": [
    "20384058",
    "23603337",
    "26199120",
    "26220375",
    "48128016"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1292431244",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1748291205.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001292431244",
    "type": "webpage",
    "title": "Common graph",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/common-graph",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001292431244",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1292431244",
    "note": "Immutable snapshot enwiki-001292431244"
  }
}