2020/09/10 by Kay Bogerd, Bogerd, Kay
Computer Science · Mathematics · #05C69 #05C80 #60C05 #60F #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.2009.04945
openalex publication_date 2020/09/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph G and a constant γ∈ [0,1], let ω(γ)(G) be the largest integer r such that there exists an r-vertex subgraph of G containing at least γ\binomr2 edges. It was recently shown that ω(γ)(G) is highly concentrated when G is an Erdős-Rényi random graph (Balister, Bollobás, Sahasrabudhe, Veremyev, 2019). This paper provides a simple method to extend that result to a setting of inhomogeneous random graphs, showing that ω(γ)(G) remains concentrated on a small range of values even if G is an inhomogeneous random graph. Furthermore, we give an explicit expression for ω(γ)(G) and show that it depends primarily on the largest edge probability of the graph G.