An algebraic approach to asymptotics of the number of unlabelled bicolored graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910521710608384 |
|---|---|
| author | Salch, A. |
| author_facet | Salch, A. |
| contents | We define and study two structures associated to permutation groups: Dirichlet characters on permutation groups, and the "cycle form," a bilinear form on the group algebras of permutation groups. We use Dirichlet characters and the cycle form to find a new upper bound on the number of unlabelled bicolored graphs with $p$ red vertices and $q$ blue vertices. We use this bound to calculate the asymptotic growth rate of the number of such graphs as $p,q\rightarrow\infty$, answering a 1973 question of Harrison in the case where $q-p$ is fixed. As an application, we show that, in an asymptotic sense, "most" elements of the power set $P(\{ 1, \dots ,p\} \times \{ 1, \dots ,q\})$ are in free $Σ_p\times Σ_q$-orbits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_07870 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An algebraic approach to asymptotics of the number of unlabelled bicolored graphs Salch, A. Combinatorics 05A16, 05C30 We define and study two structures associated to permutation groups: Dirichlet characters on permutation groups, and the "cycle form," a bilinear form on the group algebras of permutation groups. We use Dirichlet characters and the cycle form to find a new upper bound on the number of unlabelled bicolored graphs with $p$ red vertices and $q$ blue vertices. We use this bound to calculate the asymptotic growth rate of the number of such graphs as $p,q\rightarrow\infty$, answering a 1973 question of Harrison in the case where $q-p$ is fixed. As an application, we show that, in an asymptotic sense, "most" elements of the power set $P(\{ 1, \dots ,p\} \times \{ 1, \dots ,q\})$ are in free $Σ_p\times Σ_q$-orbits. |
| title | An algebraic approach to asymptotics of the number of unlabelled bicolored graphs |
| topic | Combinatorics 05A16, 05C30 |
| url | https://arxiv.org/abs/2407.07870 |