当前位置:首页 |  学术交流学术交流

美国莱特州立大学周向前教授学术报告

信息来源: 暂无 发布日期: 2017-06-23 浏览次数:

报告人:周向前,Wright  State University, Dayton Ohio USA

报告时间:2017年6月27日14:00-16:00  

报告地点:数计学院4号楼229室

报告题目:Minimally k-connected Graphs and Matroids

报告摘要:A  matroid M is a pair (E, \mathcal{I}) where E is a finite set, called the ground  set of M, and \mathcal{I} is a non-empty collection of subsets of E, called  independent sets of M, such that (1) a subset of an independent set is  independent; and (2) if I and J are independent sets with |I| < |J|, then  exists x \in J-I such that I \cup {x} is independent.  

    A  graph G gives rise to a matroid M(G) where the ground set is E(G) and a subset  of E(G) is independent if it spans a forest. So we may view matroids as a  generalization of graphs.

    A  graph is minimally k-connected if it is k-connected and the deletion of an  arbitrary edge produces a subgraph that is no longer k-connected. Halin showed  that every minimally k-connected graph has a degree-k vertex. Analogous results  for matroids were only proved for some small values of k. We will give a short  survey on these results and show some recent progress on the  problem.