Scholarlink

<p>This paper represents a significant leap forward in the problem of enumerating vertex-transitive graphs. Recent breakthroughs on symmetry of Cayley (di)graphs show that almost all finite Cayley (di)graphs have the smallest possible automorphism group. Extending the scope of these results, we enumerate (di)graphs admitting a fixed semiregular group of automorphisms with <i>m</i> orbits. Moreover, we consider the more intricate inquiry of prohibiting arcs within each orbit, where the special case <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="493_2025_175_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="46" /> </InlineMediaObject> <EquationSource Format="TEX">\(m=2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> is known as the problem of finding Haar graphical representations (HGRs). We significantly advance the understanding of HGRs by proving that the proportion of HGRs among Haar graphs of a finite nonabelian group approaches 1 as the group order grows. As a corollary, we obtain an improved bound on the proportion of DRRs among Cayley digraphs in the solution of Morris and the second author to the Babai-Godsil conjecture.</p>

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

Asymptotic Enumeration of Haar Graphical Representations

  • 期刊论文

  • 发表日期：

    2025年10月2日

查看全文
  • Yunsong Gan,
  • Pablo Spiga,
  • Binzhou Xia

摘要

This paper represents a significant leap forward in the problem of enumerating vertex-transitive graphs. Recent breakthroughs on symmetry of Cayley (di)graphs show that almost all finite Cayley (di)graphs have the smallest possible automorphism group. Extending the scope of these results, we enumerate (di)graphs admitting a fixed semiregular group of automorphisms with m orbits. Moreover, we consider the more intricate inquiry of prohibiting arcs within each orbit, where the special case \(m=2\) m = 2 is known as the problem of finding Haar graphical representations (HGRs). We significantly advance the understanding of HGRs by proving that the proportion of HGRs among Haar graphs of a finite nonabelian group approaches 1 as the group order grows. As a corollary, we obtain an improved bound on the proportion of DRRs among Cayley digraphs in the solution of Morris and the second author to the Babai-Godsil conjecture.