SEMINARS
Minimally $k$-connected Graphs and Matroids

2018-07-12　10:00 — 11:00

Middle Lecture Room

Xiangqian Zhou

Wright State University, Dayton Ohio USA

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.