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 obeys
The 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!