题目：On spanning tree edge dependences of graphs
报告人：烟台大学 杨玉军教授
时间：2021年11月20号（周六）上午11:00--11:50
报告地点：腾讯会议ID：181 346 639
报告摘要：For a connected graph $G$, let $\tau(G)$ be the number of spanning trees of $G$, and for $e\in E(G)$, let $\tau_G(e)$ be the number of spanning trees of $G$ containing $e$. The quality $d_{G}(e)=\tau_{G}(e)/\tau(G)$ is called the spanning tree edge density of $e$, and $\mbox{dep}(G)=\max\limits_{e\in E(G)}d_{G}(e)$ is called the spanning tree edge dependence of $G$. Given a rational number $p/q\in (0,1)$, if there exists a graph $G$ and an edge $e\in E(G)$ such that $d_{G}(e)=p/q$, then we say the spanning tree edge density $p/q$ is constructible. More specially, if there exists a graph $G$ such that $\mbox{dep}(G)=p/q$, then we say the spanning tree edge dependence $p/q$ is constructible. In 2002, Ferrara, Gould, and Suffel asked which rational spanning tree edge densities are constructible and which rational spanning tree edge dependences are constructible. In 2016, by construction method, Kahl proved that for all $0<p/q<1$, the spanning tree edge density $p/q$ and the spanning tree edge dependence $p/q$ are constructible. Moreover, Kahl proved that all rational spanning tree edge densities are constructible even if $G$ is restricted to bipartite graphs or planar graphs. So he conjectured that all rational spanning tree edge dependences are also constructible if $G$ is restricted to bipartite graphs (Conjecture 1), or planar graphs (Conjecture 2). In this paper, by combinatorial and electric network approach, firstly, we prove that all rational spanning tree edge dependences $p/q$ are constructible via bipartite graphs, which confirms the first conjecture of Kahl. Secondly, we show that all rational spanning tree edge dependences are constructible for planar multigraphs, which confirms Kahl's second conjecture for planar multigraphs. However, for (simple) planar graphs, we show that Conjecture 2 is true for $p/q>\frac{1}{2}$ but fails for $p/q\leq \frac{1}{6}$. More precisely, on one hand, we construct a family of planar graphs to show that all rational spanning tree edge dependences $p/q>\frac{1}{2}$ are constructible via planar graphs, but on the other hand, we show that the spanning tree edge dependence of a planar graph $G$ satisfies $\mbox{dep}(G)> \frac{1}{6}$, implying that all rational spanning tree edge dependences $p/q\leq \frac{1}{6}$ are not constructible.
报告人简介：杨玉军，烟台大学数学与信息科学学院教授、院长。烟台大学数学与信息科学学院教授、院长。山东省优秀青年基金获得者，山东省高等学校青创人才引育计划立项建设团队负责人，山东省高校黄大年式教师团队骨干成员。2009年博士毕业于兰州大学。主要研究领域为图论及其应用，在Combinatorica、European J. Combin.、Proc. Roy. Soc. A、Discrete Math.、Discrete Appl. Math.、Linear Algebra Appl.、J. Phys. A: Math. Theor.等国际权威杂志发表论文40余篇。先后主持国家自然科学基金4项，中国博士后科学基金特别资助和面上项目各1项。2015年获得山东省高校优秀科研成果奖一等奖。受美国Welch基金资助，两次赴美国德州农工大学盖文斯顿分校从事博士后研究。担任中国商业统计学会理事、中国工业与应用数学学会图论组合及其应用专业委员会委员、山东数学会理事、美国《数学评论》评论员。
欢迎广大师生参加，联系人：孙少伟，汪狄建。
