Homomorphism density

<p>In the <a href="/facts/Mathematics/pxTouaz4">mathematical</a> field of <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal graph theory</a>, homomorphism density with respect to a graph 
  
    
      
        H
      
    
    {\displaystyle H}
  
 is a parameter 
  
    
      
        t
        (
        H
        ,
        −
        )
      
    
    {\displaystyle t(H,-)}
  
 that is associated to each graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 in the following manner:
</p>

t
        (
        H
        ,
        G
        )
        :=
        
          
            
              |
              
                hom
                ⁡
                (
                H
                ,
                G
                )
              
              |
            
            
              
                |
              
              V
              (
              G
              )
              
                
                  |
                
                
                  
                    |
                  
                  V
                  (
                  H
                  )
                  
                    |
                  
                
              
            
          
        
      
    
    {\displaystyle t(H,G):={\frac {\left|\operatorname {hom} (H,G)\right|}{|V(G)|^{|V(H)|}}}}
  
.
<p>Above, 
  
    
      
        hom
        ⁡
        (
        H
        ,
        G
        )
      
    
    {\displaystyle \operatorname {hom} (H,G)}
  
 is the set of <a href="/facts/Graph_homomorphism/XSljQ25z">graph homomorphisms</a>, or adjacency preserving maps, from 
  
    
      
        H
      
    
    {\displaystyle H}
  
 to 
  
    
      
        G
      
    
    {\displaystyle G}
  
. Density can also be interpreted as the probability that a map from the vertices of 
  
    
      
        H
      
    
    {\displaystyle H}
  
 to the vertices of 
  
    
      
        G
      
    
    {\displaystyle G}
  
 chosen uniformly at random is a graph homomorphism. There is a connection between homomorphism densities and subgraph densities, which is elaborated on below.
</p>

Homomorphism density open-in-new

Homomorphism density