Dense subgraphs in random graphs

DOI10.1016/J.DAM.2019.01.032MaRDI QIDQ1741497zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Julian Sahasrabudhe, Alexander Veremyev, Paul Balister

Publication date 3 May 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.10349

zbMATH Keywords

random graphsbinomial random graphcliquesprobabilistic combinatoricsdense clustersnetworks in sociometryErdős-Renyi random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Abstract: For a constant $gammain[0,1]$ and a graph $G$, let $omeg{a}_{gamma}(G)$ be the largest integer $k$ for which there exists a $k$-vertex subgraph of $G$ with at least $$ edges. We show that if $0<p<gamma<1$ then $omeg{a}_{gamma}(G_{n,p})$ is concentrated on a set of two integers. More precisely, with $alpha(gamma,p)=gammalogfracgammap+(1-gamma)logfrac1-gamma1-p$, we show that $omeg{a}_{gamma}(G_{n,p})$ is one of the two integers closest to $$, with high probability. While this situation parallels that of cliques in random graphs, a new technique is required to handle the more complicated ways in which these "quasi-cliques" may overlap.

Recommendations

• Finding dense subgraphs in \(G(n,1/2)\)
• Dense subgraphs of power-law random graphs
• The densest subgraph problem in sparse random graphs
• Largest sparse subgraphs of random graphs
• Largest sparse subgraphs of random graphs

Cites work

• scientific article; zbMATH DE number 2086259 (Why is no real title available?)
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 1424314 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Cliques in random graphs
• Exact MIP-based approaches for finding maximum quasi-cliques and dense subgraphs
• Largest sparse subgraphs of random graphs
• Micro-review synthesis for multi-entity summarization
• Multivariate algorithmics for finding cohesive subnetworks
• On clique relaxation models in network analysis
• On colouring random graphs
• On the maximum quasi-clique problem
• Paths in graphs
• Reducibility among combinatorial problems
• Some remarks on the theory of graphs
• Statistical analysis of financial networks
• The \(t\)-improper chromatic number of random graphs
• The complexity of detecting fixed-density clusters

Cited in

(15)

• Testing correlation of unlabeled random graphs
• The densest subgraph problem in sparse random graphs
• Dense subgraphs in the H-free process
• Full subgraphs
• Cliques in dense inhomogeneous random graphs
• On a problem of Ahlswede and Katona
• Testing for dense subsets in a graph via the partition function
• Subgraph densities in a surface
• An opposition-based memetic algorithm for the maximum quasi-clique problem
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition
• The landscape of the planted clique problem: dense subgraphs and the overlap gap property
• Dense subgraphs of power-law random graphs
• Superlogarithmic cliques in dense inhomogeneous random graphs
• Asymptotic bounds for clustering problems in random graphs
• Finding dense subgraphs in \(G(n,1/2)\)

Describes a project that uses

Uses Software

• MCODE

This page was built for publication: Dense subgraphs in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1741497)