欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Minimally $k$-connected Graphs and Matroids
时间  Datetime
2018-07-12 10:00 — 11:00 
地点  Venue
Middle Lecture Room
报告人  Speaker
Xiangqian Zhou
单位  Affiliation
Wright State University, Dayton Ohio USA
邀请人  Host
张晓东
报告摘要  Abstract

A matroid $M$ is a pair $(E, \mathcal{I})$ where $E$ is a finite set, called the {\em ground set} of $M$, and $\mathcal{I}$ is a non-empty collection of subsets of $E$, called {\em 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 \backslash 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.