Uniform density in matroids, matrices and graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908803366125568 |
|---|---|
| author | Devriendt, Karel Mulas, Raffaella |
| author_facet | Devriendt, Karel Mulas, Raffaella |
| contents | We give new characterizations for the class of uniformly dense matroids and study applications of these characterizations to graphic and real representable matroids. We show that a matroid is uniformly dense if and only if its base polytope contains a point with constant coordinates. As a main application, we derive new spectral, structural and classification results for uniformly dense graphs. In particular, we show that connected regular uniformly dense graphs are $1$-tough and thus contain a (near-)perfect matching. As a second application, we show that strictly uniformly dense real represented matroids can be represented by projection matrices with a constant diagonal and that they are parametrized by a subvariety of the Grassmannian. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_15267 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Uniform density in matroids, matrices and graphs Devriendt, Karel Mulas, Raffaella Combinatorics Discrete Mathematics Spectral Theory We give new characterizations for the class of uniformly dense matroids and study applications of these characterizations to graphic and real representable matroids. We show that a matroid is uniformly dense if and only if its base polytope contains a point with constant coordinates. As a main application, we derive new spectral, structural and classification results for uniformly dense graphs. In particular, we show that connected regular uniformly dense graphs are $1$-tough and thus contain a (near-)perfect matching. As a second application, we show that strictly uniformly dense real represented matroids can be represented by projection matrices with a constant diagonal and that they are parametrized by a subvariety of the Grassmannian. |
| title | Uniform density in matroids, matrices and graphs |
| topic | Combinatorics Discrete Mathematics Spectral Theory |
| url | https://arxiv.org/abs/2306.15267 |