【数学与统计及交叉学科前沿论坛------高端学术讲座第120场】

报告题目：Transversals in a collection of stars or generic trees

报告人：李路易 中国科学院数学与系统科学研究院

时间：2024年9月30日（周一）16:00-17:00

地点：4556银河国际在线334讨论室

报告内容：Let $\mathcal{G}=\{G_1,G_2,\ldots,G_m\}$ be a collection of $n$-graphs on the same vertex set $V$ (a graph system), and $F$ be a simple graph with $e(F)\leq m$. If there is an injection $f: E(F)\longrightarrow [m]$ such that $e\in E(G_{f(e)})$ for each $e\in E(F)$, then $F$ is a partial transversal of $\mathcal{G}$. If $e(F)=m$, then it is a transversal of $\mathcal{G}$.

From another perspective, we can see $\mathcal{G}$ as an edge-colored multigraph $\mathcal{\widetilde{G}}$ with $V(\mathcal{\widetilde{G}})=V$ and $E(\mathcal{\widetilde{G}})$ a multiset consisting of $E(G_1),\ldots,E(G_m)$, and the edge $e$ of $\mathcal{\widetilde{G}}$ is colored by $i$ if $e\in E(G_i)$.

Since all edges of $F$ belong to distinct graphs of $\\mathcal{G}$, we also call $F$ a rainbow subgraph of $\mathcal{G}$.

In this talk, we investigated the transversal problem of finding the maximum value of $|\mathcal{G}|$ when $\mathcal{G}$ contains no rainbow elements in $\mathcal{S}$. Specifically, we determine the exact values when $\mathcal{S}$ is a family of stars or a family of trees of the same order $n$ with $n$ dividing $|V|$. Further, all the extremal cases for $\mathcal{G}$ are characterized.

This is joint work with Ethan Y. H. Li, Ping Li, Xueliang Li.

报告人简介：2020年6月于郑州大学获得理学硕士学位，2024年6月于南开大学组合数学中心获得理学博士学位，2023年获得国家留学基金委公派留学项目，前往法国巴黎萨克雷大学进行为期一年的联合培养。硕博期间，在本领域高水平期刊J. Graph Theory, Discrete Mathematics, Theoretical Computer Science等期刊上发表论文13篇，主持天津市研究生科研创新项目一项。目前在中国科学院数学与系统科学研究院从事博士后研究工作。