报告题目：Enumerating coprime permutations & Enumerating Matroids and Linear Spaces

时间：3月31日(周四) 9:00-11:00

地点：Zoom: 890 901 6918 密码: 202203

邀请人：王光辉 孟宪昌

摘要：

1.       Enumerating coprime permutations

Define a permutation $\sigma$ to be coprime if $\gcd(m,\sigma(m)) = 1$ for $m\in[n]$. In this note, proving a recent conjecture of Pomerance, we prove that the number of coprime permutations on $[n]$ is $n!\cdot (c+o(1))^n$ where

\[c = \prod_{p\text{ prime }}\frac{(p-1)^{2(1-1/p)}}{p\cdot (p-2)^{(1-2/p)}}.\]

The techniques involve entropy maximization for the upper bound, and a mixture of number-theoretic estimates and the absorbing method for the lower bound.

2.       Enumerating Matroids and Linear Spaces

We show that the number of linear spaces on a set of $n$ points and the number of rank-3 matroids on a ground set of size $n$ are both of the form $(cn+o(n))^{n^2/6}$, where $c=e^{\sqrt 3/2-3}(1+\sqrt 3)/2$. This is the final piece of the puzzle for enumerating fixed-rank matroids at this level of accuracy: there are exact formulas for enumeration of rank-1 and rank-2 matroids, and it was recently proved by van der Hofstad, Pendavingh, and van der Pol that for constant $r\ge 4$ there are $(e^{1-r}n+o(n))^{n^{r-1}/r!}$ rank-$r$ matroids on a ground set of size $n$.

主讲人简介：

Ashwin Sah, 美国麻省理工学院数学学院博士生，导师是赵宇飞博士。他的研究兴趣包括组合学、概率论和数论。

Mehtaab Sawhney, 美国麻省理工学院数学学院博士生，导师是赵宇飞博士。他的研究兴趣包括组合与概率。