Graphon

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> and <a href="/facts/Statistics/DNPsKGYU">statistics</a>, a graphon (also known as a graph limit) is a <a href="/facts/Symmetric_function/IB8N4T3m">symmetric</a> <a href="/facts/Measurable/yCq7zlI4">measurable</a> function 
  
    
      
        W
        :
        [
        0
        ,
        1
        
          ]
          
            2
          
        
        →
        [
        0
        ,
        1
        ]
      
    
    {\displaystyle W:[0,1]^{2}\to [0,1]}
  
, that is important in the study of <a href="/facts/Dense_graph/xFC7b7s9">dense graphs</a>. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of <a href="/facts/Exchangeable_random_variables/tHvmhbRy">exchangeable</a> random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs <a href="/facts/Almost_surely/fWaxzpBA">almost surely</a>, and, by the <a href="/facts/Szemer%C3%A9di_regularity_lemma/dKt8T8y8">regularity lemma</a>, graphons capture the structure of arbitrary large dense graphs.
</p>

Graphon open-in-new

Graphon