Chip-firing based methods in the Riemann–Roch theory of directed graphs
| Autor: | Lilla Tóthmérész, Bálint Hujter |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Strongly connected component Mathematics::Combinatorics 010102 general mathematics Duality (mathematics) Eulerian path 0102 computer and information sciences Directed graph 01 natural sciences Combinatorics Riemann hypothesis symbols.namesake Indifference graph Mathematics::Algebraic Geometry 010201 computation theory & mathematics Chordal graph FOS: Mathematics symbols Mathematics - Combinatorics Discrete Mathematics and Combinatorics Graph (abstract data type) Combinatorics (math.CO) 0101 mathematics 05C50 05C57 Mathematics |
| Zdroj: | European Journal of Combinatorics. 78:90-104 |
| ISSN: | 0195-6698 |
| DOI: | 10.1016/j.ejc.2019.01.007 |
| Popis: | Baker and Norine proved a Riemann--Roch theorem for divisors on undirected graphs. The notions of graph divisor theory are in duality with the notions of the chip-firing game of Bj\"orner, Lov\'asz and Shor. We use this connection to prove Riemann--Roch-type results on directed graphs. We give a simple proof for a Riemann--Roch inequality on Eulerian directed graphs, improving a result of Amini and Manjunath. We also study possibilities and impossibilities of Riemann--Roch-type equalities in strongly connected digraphs and give examples. We intend to make the connections of this theory to graph theoretic notions more explicit via using the chip-firing framework. Comment: 22 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect