Jan, 2011
随机几何图的色数
On the chromatic number of random geometric graphs
Colin McDiarmid, Tobias Müller
TL;DR该论文研究了具有共同概率分布的独立随机点构成的随机几何图中色数和团数的关系，并确定了色数相对于团数的渐近比例，同时发现了一个尖锐的阈值。
Abstract
Given independent random points $X_1,...,X_n\in\eR^d$ with common probability
distribution $\nu$, and a positive distance $r=r(n)>0$, we construct a random
geometric graph $G_n$ with vertex set $\{1,...,n\}$ where distinct $i$ and $j$
are adjacent when $\norm{X_i-X_j}\leq r$. Here $\norm{.}$ may be any norm on
$\eR^d$, and $\nu$ may be any probability distri
发现论文，激发创造
关于从随机几何图中估算维度的注记
给定以未知密度 f 为基础的 n 个 i.i.d. 随机向量 Xi 产生的随机几何图 Gn，估计其潜在空间的维度 d 的问题。研究发现，在满足条件 n^(3/2) r_n^d→∞和 r_n=o (1) 的情况下，存在一个估计器，其在概率意义下收敛于 d，对于所有满足∫f^5<∞的密度函数。条件允许极其稀疏的图，当 n^(3/2) r_n^d→0 时，图仅包含孤立边的概率很高。同时证明，在不对密度函数做任何条件的情况下，当 n r_n^d→∞和 r_n=o (1) 时，存在一个一致估计器来估计 d。
Nov, 2023
随机图的 Lovasz 数
研究在随机图 G (n,p) 上的独立数和色数及其相应的松弛值，提出了一种改进的算法来近似计算独立数，同时对于判断 G (n,p) 是否可着色的算法提出了改进方法，并计算了边概率 p 范围内松弛值的渐近值。
Jun, 2003
随机图中的独立集
本研究证明：在随机图中，最大独立集问题的组合结构会在独立集大小 k 超过 k nln (d)/d 这个点时发生相变，形成一个错综复杂的景象，局部搜索算法难以摆脱。这一现象通过 Metropolis 过程，即一个用于采样独立集的马尔可夫链实现了指数下界。
Jul, 2010
边独立随机图的谱
本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质，其中包括对 Erdős-Rényi 图的分析，证明了矩阵与其期望的偏差在一定条件下的上界，并对已有的结果进行了改进。
Apr, 2012
随机几何图
分析具有随机坐标和任意维度几何空间中的图。使用最大聚类的大小数值方法得到关键的连通性。我们推导了一个群集系数的解析表达式，表明即使在无限维度下，这些图形与标准随机图形明显不同，包括与图形双分区相关的见解。
Mar, 2002