论文标题
不均匀随机图
Quasi-cliques in inhomogeneous random graphs
论文作者
论文摘要
给定[0,1] $中的图形$ g $和常数$γ\，令$ω^{（γ）}（g）$是最大的整数$ r $，因此存在$ r $ vertex子级$ g $，其中包含至少$γ\ binom {r} {r} {2} {2} $ edges。最近显示，$ω^{（γ）}（g）$当$ g $是一个erdős-rényi随机图时高度集中（Balister，Bollobás，Sahasrabudhe，Veremyev，Veremyev，2019年）。本文提供了一种简单的方法，将结果扩展到不均匀的随机图设置，表明$ω^{（γ）}（g）$仍然集中在少量值上，即使$ g $是一个不均匀的随机图。此外，我们给出了$ω^{（γ）}（g）$的明确表达式，并证明它主要取决于图$ g $的最大边缘概率。
Given a graph $G$ and a constant $γ\in [0,1]$, let $ω^{(γ)}(G)$ be the largest integer $r$ such that there exists an $r$-vertex subgraph of $G$ containing at least $γ\binom{r}{2}$ 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$.
