Triangle counting with one box-uniform pair and constant opposite degree
ID: triangle-counting-with-one-box-uniform-pair-and-constant-opposite-degree
Let a tripartite graph have nonempty parts , pair edge density of a bipartite graph values on , and . If every has exactly neighbors in , its normalized triangle count obeysThe constant-degree assumption makes the contribution of the constant exactly . For each fixed , apply the bilinear correlation bound for the box norm to the indicator functions of its two vertex neighbourhoods. Their squared norms are and the relative -degree of . Average over and use the Cauchy-Schwarz inequality to bound the mean square root of that degree by .
New to topics? Read the docs here!