{'fraction_non_alphanumeric': 0.05, 'fraction_numerical': 0.010714285714285714, 'mean_word_length': 3.947058823529412, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Perfectly Balanced Partitions of Smoothed Graphs

For a graph G = (V, E) of even order, a partition (V1, V2) of the vertices is said to be perfectly balanced if |V1| = |V2| and the numbers of edges in the subgraphs induced by V1 and V2 are equal. For a base graph H define a random graph G(H, p) by turning every non-edge of H into an edge and every edge of H into a nonedge independently with probability p. We show that for any constant ǫ there is a constant α, such that for any even n and a graph H on n vertices that satisfies �(H)−δ(H) ≤ αn, a graph G distributed according to G(H, p), with ǫ ≤ p ≤ 1− ǫ n , admits a perfectly balanced partition with probability exponentially close to 1. As a direct consequence we get that for every p, a random graph from G(n, p) admits a perfectly balanced partition with probability tending to 1.