论文标题
从随机图中的遗传性属性中的最大子图
Largest subgraph from a hereditary property in a random graph
论文作者
论文摘要
我们证明，对于每个非平凡的遗传图$ {\ cal p} $，对于（0,1）$中的每个固定$ p \，随机图$ g（n，p）$属于$ {\ cal p} $的最大边缘数量，$ g（n，p）$具有很高的可能性\ left（1- \ frac {1} {k-1}+o（1）\ right）p {n \ select 2}，$ $，其中$ k $是不属于$ {\ cal p} $的图形的最小色数。
We prove that for every non-trivial hereditary family of graphs ${\cal P}$ and for every fixed $p \in (0,1)$, the maximum possible number of edges in a subgraph of the random graph $G(n,p)$ which belongs to ${\cal P}$ is, with high probability, $$ \left(1-\frac{1}{k-1}+o(1)\right)p{n \choose 2}, $$ where $k$ is the minimum chromatic number of a graph that does not belong to ${\cal P}$.
