Abstract
We provide lower bounds on the gonality of a graph in terms of its spectral and edge expansion. As a consequence, we see that the gonality of a random 3-regular graph is asymptotically almost surely greater than one seventh its genus.
Original language | English |
---|---|
Pages (from-to) | 2535-2543 |
Number of pages | 9 |
Journal | Discrete Mathematics |
Volume | 341 |
Issue number | 9 |
DOIs | |
State | Published - Sep 2018 |
Bibliographical note
Funding Information:The first author was supported by a gift from the Eaves family for summer undergraduate research. We thank the Eaves for their generosity. The second author was supported in part by NSF DMS-1601896.
Funding Information:
The first author was supported by a gift from the Eaves family for summer undergraduate research. We thank the Eaves for their generosity. The second author was supported in part by NSF DMS-1601896 .
Publisher Copyright:
© 2018 Elsevier B.V.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics