Scholarlink

Abstract <p>Consider the set <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal{E}(G,k)\)</EquationSource> <!--DANMath2570020Yarovikov-m1--> </InlineEquation> of all sizes (numbers of edges) of induced subgraphs of size <i>k</i> in a given graph <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(G\)</EquationSource> <!--DANMath2570020Yarovikov-m2--> </InlineEquation> on <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(n\)</EquationSource> <!--DANMath2570020Yarovikov-m3--> </InlineEquation> vertices. For the binomial random graph <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(G = G(n,p)\)</EquationSource> <!--DANMath2570020Yarovikov-m4--> </InlineEquation>, we prove that, for each <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\alpha &gt; 0\)</EquationSource> <!--DANMath2570020Yarovikov-m5--> </InlineEquation> and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\varepsilon \)</EquationSource> <!--DANMath2570020Yarovikov-m6--> </InlineEquation> small enough, the set <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\mathcal{E}(G,k)\)</EquationSource> <!--DANMath2570020Yarovikov-m7--> </InlineEquation> with high probability contains a long interval for all <i>k</i> such that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\({{(\ln n)}^{{1 + \alpha }}} &lt; k &lt; \varepsilon n\)</EquationSource> <!--DANMath2570020Yarovikov-m8--> </InlineEquation>. We also find the asymptotic length of this interval.</p>

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

On the Sizes of k-Subgraphs of the Binomial Random Graph

  • 期刊论文

  • 发表日期：

    2025年6月1日

查看全文
  • Yu. N. Yarovikov

摘要

Abstract

Consider the set \(\mathcal{E}(G,k)\) of all sizes (numbers of edges) of induced subgraphs of size k in a given graph \(G\) on \(n\) vertices. For the binomial random graph \(G = G(n,p)\) , we prove that, for each \(\alpha > 0\) and \(\varepsilon \) small enough, the set \(\mathcal{E}(G,k)\) with high probability contains a long interval for all k such that \({{(\ln n)}^{{1 + \alpha }}} < k < \varepsilon n\) . We also find the asymptotic length of this interval.