Spectral discrepancy bound for a biregular graph
ID: spectral-discrepancy-bound-for-a-biregular-graph
Let be the centered biadjacency matrix of an equal-part biregular graph, and put . For subsets of the two parts, their edge discrepancy is . The Cauchy-Schwarz inequality proves the displayed bound. If the part size is , centering the two indicator vectors improves it to . The centered four-cycle identity for a biregular graph shows that implies for .
New to topics? Read the docs here!