Scholarlink

<p>In this paper, we consider non-sparse random graphs with non-uniform edge probabilities where each vertex is assigned a random positive weight and study the maximum weight of a stable set. We use local weighted domination together with the second moment method to obtain deviation bounds in terms of average edge probability per vertex and then utilize martingale difference methods to establish&#xa0;<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(L^2\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>L</mi> <mn>2</mn> </msup> </math></EquationSource> </InlineEquation>-convergence for the maximum weight, appropriately scaled and centred. We also illustrate our result with an example involving vertex weight distributions satisfying a power law decay.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Maximum Weight of Stable Sets in Non-Sparse and Inhomogeneous Random Graphs

  • 期刊论文

  • 发表日期：

    2025年11月7日

查看全文
  • Ghurumuruhan Ganesan

摘要

In this paper, we consider non-sparse random graphs with non-uniform edge probabilities where each vertex is assigned a random positive weight and study the maximum weight of a stable set. We use local weighted domination together with the second moment method to obtain deviation bounds in terms of average edge probability per vertex and then utilize martingale difference methods to establish  \(L^2\) L 2 -convergence for the maximum weight, appropriately scaled and centred. We also illustrate our result with an example involving vertex weight distributions satisfying a power law decay.