{"id":"arxiv/2605.24940","url":"https://arxiv.org/abs/2605.24940","tags":["math.CO"],"score":0,"title":"Decomposition of degree-regular graphs into quasi-random pairs without the Regularity lemma","domain":"math.CO","source":"arxiv","authors":["Béla Csaba"],"reviews":0,"subject":"math.CO","summary":"The Szemerédi Regularity Lemma, in combination with the Blow-up Lemma, form the Regularity Method, a fundamental tool in graph embeddings, albeit restricted to very large and dense graphs. We propose an alternative vertex-partitioning framework that remains effective even as the density tends to zero and without requiring astronomically large vertex sets. This approach, while narrower in scope, extends regularity-type techniques to relatively small graphs previously inaccessible to the Regularity Method. As an application, we use this novel vertex-partitioning method for bipartite packing…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-24","reactions":{}}