Combinatorics Seminar 2018

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


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