数学与统计学院学术报告[2020] 126号

(高水平大学建设系列报告479号)

报告题目:   The minimum of the number of cycles in tournaments and normalized q-norms

报告人： 马杰 教授  （中国科学技术大学）

报告时间：2020年12月9日14:45—15:45

直播平台及链接： 腾讯会议（会议号： 960226235）　　　　　　　　　　　　　　

报告内容：  

Akin to the Erd\H{o}s-Rademacher problem, Linial and Morgenstern made the following conjecture in tournaments: for any $d\in (0,1]$, among all $n$-vertex tournaments with $d\binom{n}{3}$ many 3-cycles, the number of 4-cycles is asymptotically minimized by a special random blow-up of a transitive tournament. Recently, Chan, Grzesik, Kr\'al' and Noel introduced spectrum analysis of adjacency matrices of tournaments in this study, and confirmed this for $d\geq 1/36$.

In this talk, we investigate the analogous problem of minimizing the number of cycles of a given length. We prove that for integers $\ell\not\equiv 2\mod 4$, there exists some constant $c_\ell>0$ such that if $d\geq 1-c_\ell$, then the number of $\ell$-cycles is also asymptotically minimized by the same family of extremal examples for 4-cycles. In doing so, we answer a question of Linial and Morgenstern about minimizing the $q$-norm of a probabilistic vector with given $p$-norm for integers $q>p>1$. For integers $\ell\equiv 2\mod 4$, however the same phenomena do not hold for $\ell$-cycles, for which we can construct an explicit family of tournaments containing fewer $\ell$-cycles for any given number of $3$-cycles. We conclude by proposing two conjectures on the minimization problem for general cycles in tournaments. Joint with Tianyun Tang.

报告人简历：马杰，现任中国科学技术大学太阳集团官网教授，博士生导师。研究领域为极值组合，图论，概率组合，以及他们在计算机科学和优化问题方面的应用研究。2017年获国家优秀青年科学基金项目资助，2018年开始担任SIAM离散数学杂志编委。

欢迎感兴趣的师生参加！

数学与统计学院

　　　　　　　　　　　　　　　 　　 2020年11月30日