2024 Workshop on (Mostly) Matroids

Rigidity and reconstruction in matroids of highly connected graphs

19 Aug 2024, 13:55

25m

S236 (IBS Science Culture Center)

Presentation (25 min)

Speaker

Dániel Garamvölgyi (Alfréd Rényi Institute of Mathematics, Budapest)

Description

A graph matroid family $\mathcal{M}$ is a family of matroids $\mathcal{M}(G)$ defined on the edge set of each finite graph $G$ in a compatible and isomorphism-invariant way. We say that $\mathcal{M}$ has the Whitney property if there is a constant $c$ such that every $c$-connected graph $G$ is uniquely determined by $\mathcal{M}(G)$. Similarly, $\mathcal{M}$ has the Lovász-Yemini property if there is a constant $c$ such that for every $c$-connected graph $G$, $\mathcal{M}(G)$ has maximal rank among graphs on the same number of vertices.

In the talk, I will discuss old and new results about these notions. In particular, we will see that for "most" graph matroid families, the Whitney and the Lovász-Yemini properties are equivalent. I will also talk about how related ideas led to solutions of conjectures of Kriesell and Thomassen on highly connected graphs. (Partly based on joint work with Tibor Jordán, Csaba Király and Soma Villányi.)