Dense Subgraphs in Random Graphs

2018/03/27 by Balister, Paul, Bollobás, Béla, Sahasrabudhe, Julian +1
#05C80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1803.10349

Abstract

For a constant γ∈[0,1] and a graph G, let ω_γ(G) be the largest integer k for which there exists a k-vertex subgraph of G with at least γ\binomk2 edges. We show that if 0

Related

• Quasi-cliques in inhomogeneous random graphs
• On the sizes of large subgraphs of the binomial random graph
• The largest subgraph without a forbidden induced subgraph
• Maximum sparse induced subgraphs of the binomial random graph with given\n number of edges
• Regular induced subgraphs of a random graph