**Speaker**: Xiangqian Zhou (ćšćć), Wright State University

**Date**: Thu, Jul 12, 2018

**Time**: 10:00 - 11:00

**Venue**: Middle Meeting Room

**Title**: Minimally $k$-connected graphs and matroids

**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.

**Slides**:
View slides