Pseudorandom graph

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a graph is said to be a pseudorandom graph if it obeys certain properties that <a href="/facts/Random_graphs/gfQhq1Sz">random graphs</a> obey <a href="/facts/With_high_probability/eBttFkd4">with high probability</a>. There is no concrete definition of graph <a href="/facts/Pseudorandomness/kfs1wfhY">pseudorandomness</a>, but there are many reasonable characterizations of pseudorandomness one can consider.
Pseudorandom properties were first formally considered by Andrew Thomason in 1987. He defined a condition called "jumbledness": a graph 
 
 
 
 G
 =
 (
 V
 ,
 E
 )
 
 
 {\displaystyle G=(V,E)}
 
 is said to be 
 
 
 
 (
 p
 ,
 α
 )
 
 
 {\displaystyle (p,\alpha )}
 
-jumbled for real 
 
 
 
 p
 
 
 {\displaystyle p}
 
 and 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
 with 
 
 
 
 0

|
          
            e
            (
            U
            )
            −
            p
            
              
                
                  (
                
                
                  
                    
                      |
                    
                    U
                    
                      |
                    
                  
                  2
                
                
                  )
                
              
            
          
          |
        
        ≤
        α
        
          |
        
        U
        
          |
        
      
    
    {\displaystyle \left|e(U)-p{\binom {|U|}{2}}\right|\leq \alpha |U|}

for every subset 
 
 
 
 U
 
 
 {\displaystyle U}
 
 of the vertex set 
 
 
 
 V
 
 
 {\displaystyle V}
 
, where 
 
 
 
 e
 (
 U
 )
 
 
 {\displaystyle e(U)}
 
 is the number of edges among 
 
 
 
 U
 
 
 {\displaystyle U}
 
 (equivalently, the number of edges in the subgraph <a href="/facts/Induced_subgraph/G3EUC0MQ">induced</a> by the vertex set 
 
 
 
 U
 
 
 {\displaystyle U}
 
). It can be shown that the <a href="/facts/Erd%25C5%2591s%25E2%2580%2593R%25C3%25A9nyi_model/F6BQ8gIj">Erdős–Rényi</a> random graph 
 
 
 
 G
 (
 n
 ,
 p
 )
 
 
 {\displaystyle G(n,p)}
 
 is <a href="/facts/Almost_surely/fWaxzpBA">almost surely</a> 
 
 
 
 (
 p
 ,
 O
 (
 
 
 n
 p
 
 
 )
 )
 
 
 {\displaystyle (p,O({\sqrt {np}}))}
 
-jumbled.: 6  However, graphs with less uniformly distributed edges, for example a graph on 
 
 
 
 2
 n
 
 
 {\displaystyle 2n}
 
 vertices consisting of an 
 
 
 
 n
 
 
 {\displaystyle n}
 
-vertex <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> and 
 
 
 
 n
 
 
 {\displaystyle n}
 
 completely independent vertices, are not 
 
 
 
 (
 p
 ,
 α
 )
 
 
 {\displaystyle (p,\alpha )}
 
-jumbled for any small 
 
 
 
 α
 
 
 {\displaystyle \alpha }
 
, making jumbledness a reasonable quantifier for "random-like" properties of a graph's edge distribution.

Pseudorandom graph open-in-new

Pseudorandom graph