论文标题
在随机不规则子图上
On random irregular subgraphs
论文作者
论文摘要
令$ g $为$ n $顶点上的$ d $ regratular图。 Frieze，Gould，Karoński和Pfender开始研究以下随机跨度型号$ H = H = H（G）$。在[0,1] $ in [0,1] $中独立分配给每个顶点$ v $ $ g $ a均匀的随机数$ x（v）\ in [0,1] $，而$ g $的边缘$（u，v）$是$ h $的边缘，仅当$ x（u）+x（u）+x（u）+x（v）\ geq 1 $。解决Alon和Wei的问题，我们证明，如果$ d = o（n/（\ log n）^{12}）$，那么对于每个非负整数$ k \ leq d $，则有$（1+o（1+o（1））n/（d+1）n/（d+1）$ h $ h $ h $ h $ h $ h $ h $ h $ h $。
Let $G$ be a $d$-regular graph on $n$ vertices. Frieze, Gould, Karoński and Pfender began the study of the following random spanning subgraph model $H=H(G)$. Assign independently to each vertex $v$ of $G$ a uniform random number $x(v) \in [0,1]$, and an edge $(u,v)$ of $G$ is an edge of $H$ if and only if $x(u)+x(v) \geq 1$. Addressing a problem of Alon and Wei, we prove that if $d = o(n/(\log n)^{12})$, then with high probability, for each nonnegative integer $k \leq d$, there are $(1+o(1))n/(d+1)$ vertices of degree $k$ in $H$.
