{'fraction_non_alphanumeric': 0.041953232462173314, 'fraction_numerical': 0.0068775790921595595, 'mean_word_length': 4.141342756183746, '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}}
Towards a weighted version of the Hajnal-Szemerédi Theorem

Many results in graph theory study the relation between the minimum degree of a given graph and its spanning subgraphs. For example, Dirac’s theorem asserts that a graph on n vertices with minimum degree at least dn2 e contains a Hamilton cycle. Hajnal and Szemerédi [4] proved that every graph on n ∈ rZ vertices with minimum degree at least (1− 1r )n contains a spanning subgraph consisting of n r vertex-disjoint copies of Kr (we call such a subgraph a Kr-factor). In this note we propose investigating this relation in edge-weighted graphs. As a concrete problem, we study the particular case when the spanning subgraph is the graph formed by vertex-disjoint copies of Kr (in other words, we would like to extend the Hajnal-Szemerédi theorem to edge-weighted graphs). Suppose we equip the complete graph Kn with edge weights w : E(Kn) → [0, 1]. For a given weighted graph and vertex v we let degw(v) denote the weighted degree of the vertex v. Let δw(G) be the minimum weighted degree of the graph G. The main question can be formulated as the following: How large must δw(Kn) be to guarantee that there exists a Kr-factor such that every factor has total edge weight at least t ( r 2 ) for some given t ∈ [0, 1]? More formally, for n ∈ rZ let W(r, t, n) be the collection of edge weightings on Kn such that every Kr-factor has a clique with weight strictly smaller than t ( r 2 ) . We then