PreprintarXiv licencearXiv
On k-connected Sets in Matroids
Abstract
In 1966, Tutte defined k-connected matroids for each k ≥ 2. Robertson and Seymour built on Tutte's idea to define tangles as a way to identify highly connected parts of a matroid. Motivated by tangles, a set Z in a matroid M has been defined to be $3$-connected if, for each j in {1,2}, there is no j-separation (X,Y) of M such that each of |Z ∩ X| and |Z ∩ Y| is at least j. This paper solves a problem of Whittle for k= 3 by proving that a minor-minimal matroid having Z as a $3$-connected set has at most $3|Z| - 4$ elements. We also identify the matroids for which this bound is attained.
Related
- An inequality for the number of independent sets of matroids with an application to the forest-tree ratio of graphs
- Tiling, spectrality and aperiodicity of connected sets
- Construction of Regular Fat Linear Sets and Non-Representable q-Matroids
- On the minimizer of the barycentric isoperimetric ratio among connected planar sets
- Independent Sets and Balanced Cycle-Linkings in 2-Connected Graphs
BibTeX
@misc{boros2026kconnected,
title = {{On $k$-connected Sets in Matroids}},
author = {Sean Boros and James Oxley},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29979},
eprint = {2610.29979},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29979},
}
RIS
TY - UNPB
TI - On k-connected Sets in Matroids
AU - Sean Boros
AU - James Oxley
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29979
UR - https://arxiv.org/abs/2610.29979
AB - In 1966, Tutte defined k-connected matroids for each k ≥ 2. Robertson and Seymour built on Tutte's idea to define tangles as a way to identify highly connected parts of a matroid. Motivated by tangles, a set Z in a matroid M has been defined to be $3$-connected if, for each j in {1,2}, there is no j-separation (X,Y) of M such that each of |Z ∩ X| and |Z ∩ Y| is at least j. This paper solves a problem of Whittle for k= 3 by proving that a minor-minimal matroid having Z as a $3$-connected set has at most $3|Z| - 4$ elements. We also identify the matroids for which this bound is attained.
ER -