Common graph
In graph theory, an area of mathematics, common graphs belong to a branch of extremal graph theory concerning inequalities in homomorphism densities. Roughly speaking,  is a common graph if it "commonly" appears as a subgraph, in a sense that the total number of copies of  in any graph  and its complement  is a large fraction of all possible copies of  on the same vertices. Intuitively, if  contains few copies of , then its complement  must contain lots of copies of  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. Definition 
A graph  is common if the inequality:

holds for any graphon , where  is the number of edges of  and  is the homomorphism density. The inequality is tight because the lower bound is always reached when  is the constant graphon . Interpretations of definition 
For a graph , we have  and  for the associated graphon , since graphon associated to the complement  is . Hence, this formula provides us with the very informal intuition to take a close enough approximation, whatever that means,  to , and see  as roughly the fraction of labeled copies of graph  in "approximate" graph . Then, we can assume the quantity  is roughly  and interpret the latter as the combined number of copies of  in  and . Hence, we see that  holds. This, in turn, means that common graph  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  fraction of all possible copies of  are monochromatic. Note that in a Erdős–Rényi random graph  with each edge drawn with probability , each graph homomorphism from  to  have probability of being monochromatic. So, common graph  is a graph where it attains its minimum number of appearance as a monochromatic subgraph of graph  at the graph  with 

. The above definition using the generalized homomorphism density can be understood in this way. Examples 

 As stated above, all Sidorenko graphs are common graphs. Hence, any known Sidorenko graph is an example of a common graph, and, most notably, cycles of even length are common. However, these are limited examples since all Sidorenko graphs are bipartite graphs while there exist non-bipartite common graphs, as demonstrated below. The triangle graph  is one simple example of non-bipartite common graph. , the graph obtained by removing an edge of the complete graph on 4 vertices , is common. Non-example: It was believed for a time that all graphs are common. However, it turns out that  is not common for . In particular,  is not common even though  is common. Proofs

Sidorenko graphs are common
A graph  is a Sidorenko graph if it satisfies  for all graphons . In that case, . Furthermore, , which follows from the definition of homomorphism density. Combining this with Jensen's inequality for the function :

Thus, the conditions for common graph is met. The triangle graph is common
Expand the integral expression for  and take into account the symmetry between the variables:

Each term in the expression can be written in terms of homomorphism densities of smaller graphs. By the definition of homomorphism densities:

 
 
 

where  denotes the complete bipartite graph on  vertex on one part and  vertices on the other. It follows:

 . can be related to  thanks to the symmetry between the variables  and :

where the last step follows from the integral Cauchy–Schwarz inequality. Finally:

. This proof can be obtained from taking the continuous analog of Theorem 1 in "On Sets Of Acquaintances And Strangers At Any Party"

See also 

 Sidorenko's conjecture

References 

Graph families
Extremal graph theory