How unproportional must a graph be?

2014/04/04 by Naves, Humberto, Pikhurko, Oleg, Scott, Alex
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1404.1206

Abstract

Let u_k(G,p) be the maximum over all k-vertex graphs F of by how much the number of induced copies of F in G differs from its expectation in the binomial random graph with the same number of vertices as G and with edge probability p. This may be viewed as a measure of how close G is to being p-quasirandom. For a positive integer n and 0

Related

• The Effect of Induced Subgraphs on Quasi-Randomness
• Thresholds and expectation thresholds
• Quasi-randomness is determined by the distribution of copies of a fixed graph in equicardinal large sets
• More on quasi-random graphs, subgraph counts and graph limits
• Quasi-random oriented graphs