Fundamental cycles in grid graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918454927294464 |
|---|---|
| author | Kielak, Bartłomiej Král', Daniel Lamaison, Ander Shu, Xichao |
| author_facet | Kielak, Bartłomiej Král', Daniel Lamaison, Ander Shu, Xichao |
| contents | We show that the average length of a fundamental cycle with respect to any fixed spanning tree of the $n\times n$ square grid is at least $Ω(\log n)$; the bound is asymptotically tight. This result answers in the affirmative a question posed by McCarty in relation to sparse representations of binary matroids. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_17595 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fundamental cycles in grid graphs Kielak, Bartłomiej Král', Daniel Lamaison, Ander Shu, Xichao Combinatorics We show that the average length of a fundamental cycle with respect to any fixed spanning tree of the $n\times n$ square grid is at least $Ω(\log n)$; the bound is asymptotically tight. This result answers in the affirmative a question posed by McCarty in relation to sparse representations of binary matroids. |
| title | Fundamental cycles in grid graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.17595 |