Weighted Regularity Lemma with Applications

2009/07/01 by Béla Csaba, Csaba, Béla, András Pluhár +1
Computer Science · Mathematics · #05C99 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C99

paper · pdf · doi:10.48550/arxiv.0907.0245

Added new applications

openalex publication_date 2009/07/01 · arxiv created 2011/02/12 · arxiv updated 2011/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove an extension of the Regularity Lemma with vertex and edge weights which can be applied for a large class of graphs. The applications involve random graphs and a weighted version of the Erdős-Stone theorem. We also provide means to handle the otherwise uncontrolled exceptional set.

Related

• On some extremal problems in graph theory
• Regularity in Weighted Graphs: A Symmetric Function Approach
• On vertex-induced weighted Turán problems
• A characterization and an application of weight-regular partitions of graphs
• The effect of adding randomly weighted edges