Decomposition of degree-regular graphs into quasi-random pairs without the Regularity lemma
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.24940
curl -X POST /api/v1/records/arxiv/2605.24940/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.24940/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'