港澳六宝大全

活动主题:Exploring mathematical and algorithmic problems on discrete structures

讲座时间:4月29日15:00-17:00

讲座地点:长安校区网安大楼A-1222

主讲人1：Tony HUYNH

主讲人简介：Tony HUYNH现任韩国基础科学研究院（IBS）离散数学组资深研究员。他于2010年在加拿大滑铁卢大学获得博士学位，师从Jim Geelen。此后长期任职于瑞士洛桑联邦理工学院（EPFL），先后担任博士后、高级研究员及助理教授等职。2020年加入 IBS 后，他专注于图论、组合优化与算法设计的前沿研究，尤其在匹配理论、网络流与图的结构理论方面成果卓著。他在 Combinatorica、JCTB 等顶级期刊发表多篇论文，是该领域极具国际影响力的青年学者之一。

报告题目：Triangulated spheres with holes in triangulated surfaces

讲座内容：Given a triangulation G of a surface, we consider the question of when G contains a spanning subgraph H which is a triangulated sphere with holes. We give a new short proof of a theorem of Nevo and Tarabykin that every triangulation of the torus contains a spanning subgraph which is a triangulated cylinder. For arbitrary surfaces, we prove that every high facewidth triangulation of a surface with h handles contains a spanning subgraph which is a triangulated sphere with 2h holes. We also prove that the number of holes in our theorem is optimal, even for arbitrarily high facewidth triangulations. Our results are motivated by, and have applications for, rigidity questions in the plane. This is joint work with Katie Clinch, Sean Dewar, Niloufar Fuladi, Maximilian Gorsky, Eleftherios Kastis, Atsuhiro Nakamoto, Anthony Nixon and Brigitte Servatius.

主讲人2：Eunjung Kim

主讲人简介：Eunjung KIM，副教授，于2010年获得伦敦大学皇家霍洛威学院博士学位。在法国国家科学研究中心（CNRS）蒙彼利埃计算机、机器人及微电子实验室（LIRMM-CNRS）完成博士后研究后，她于2011年至2023年期间正式任职于法国国家科学研究中心（CNRS）。自2024年起，她加入韩国科学技术院（KAIST）担任副教授。金恩贞的主要研究兴趣在于利用结构图论和宽度参数设计算法，同时她也日益关注逻辑学与图结构及算法之间的相互作用。

报告题目：A Tight Meta-theorem for LOCAL Certification of MSO2 Properties within Bounded Treewidth

讲座内容：Distributed networks are prone to errors so verifying their output is critical. Hence, we develop LOCAL certification protocols for graph properties in which nodes are given certificates that allow them to check whether their network as a whole satisfies some fixed property while only communicating with their local network. Most known LOCAL certification protocols are specifically tailored to the problem they work on and cannot be translated more generally. Thus we target general protocols that can certify any property expressible within a certain logical framework.

主讲人3：Sang-il OUM

主讲人简介：Sang-il OUM是韩国基础科学研究院（IBS）离散数学组（DIMAG）的主任及首席研究员，同时也是韩国科学技术院（KAIST）的数学教授。他于 2005 年在普林斯顿大学获得博士学位，师从著名数学家 Paul Seymour。作为全球知名的图论专家，OUM 教授长期致力于图的结构理论、图子式理论及宽度参数的研究。他最著名的学术贡献在于对秩宽（Rank-width）和分支分解理论的深入探索，这些成果在图算法与逻辑领域具有重要影响。凭借卓越的科研港澳六宝大全力，他不仅推动了 IBS 离散数学组的国际影响力，还积极促进亚洲组合数学界的学术交流与合作。

报告题目：Branch-width of connectivity functions is fixed-parameter tractable

讲座内容：A connectivity function on a finite set $V$ is a symmetric submodular function $f \colon 2^V \to \mathbb{Z}$ with $f(\emptyset)=0$. We prove that finding a branch-decomposition of width at most $k$ for a connectivity function given by an oracle is fixed-parameter tractable, by providing an algorithm of running time $O(\gamma 2^{O(k^2)} n^6 \log n)$, where $\gamma$ is the time to compute $f(X)$ for any set $X$, and $n = |V|$. This improves the previous algorithm by Oum and Seymour [J. Combin. Theory Ser.~B, 2007], which runs in time $O(\gamma n^{8k+O(1)})$. Our algorithm can be applied to rank-width of graphs, branch-width of matroids, branch-width of (hyper)graphs, and carving-width of graphs.

主办单位：信息交叉学部