Common graph

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, an area of mathematics, common graphs belong to a branch of <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal graph theory</a> concerning <a href="/facts/Homomorphism_density/V5cHzcK5">inequalities in homomorphism densities</a>. Roughly speaking, 
  
    
      
        F
      
    
    {\displaystyle F}
  
 is a common <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> if it "commonly" appears as a subgraph, in a sense that the total number of copies of 
  
    
      
        F
      
    
    {\displaystyle F}
  
 in any graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 and its <a href="/facts/Complement_graph/IdHUPFr3">complement</a> 
  
    
      
        
          
            G
            ¯
          
        
      
    
    {\displaystyle {\overline {G}}}
  
 is a large fraction of all possible copies of 
  
    
      
        F
      
    
    {\displaystyle F}
  
 on the same vertices. Intuitively, if 
  
    
      
        G
      
    
    {\displaystyle G}
  
 contains few copies of 
  
    
      
        F
      
    
    {\displaystyle F}
  
, then its complement 
  
    
      
        
          
            G
            ¯
          
        
      
    
    {\displaystyle {\overline {G}}}
  
 must contain lots of copies of 
  
    
      
        F
      
    
    {\displaystyle F}
  
 in order to compensate for it. 
</p><p>Common graphs are closely related to other graph notions dealing with homomorphism density inequalities. For example, common graphs are a more general case of <a href="/facts/Sidorenko%2527s_conjecture/jxzA8ffr">Sidorenko graphs</a>.
</p>

Common graph open-in-new

Common graph