Chip-firing based methods in the Riemann–Roch theory of directed graphs

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örner, Lovász 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.     

Divisors on graphs,binomial and monomial ideals,and cellular resolutions

We study various binomial and monomial ideals arising in the theory of divisors, orientations, and matroids on graphs. We use ideas from potential theory on graphs and from the theory of Delaunay decompositions for lattices to describe their minimal polyhedral cellular free resolutions. We show that the resolutions of all these ideals are closely related and that their \({\mathbb {Z}}\)-graded Betti tables coincide. As corollaries, we give conceptual proofs of conjectures and questions posed by Postnikov and Shapiro, by Manjunath and Sturmfels, and by Perkinson, Perlman, and Wilmes. Various other results related to the theory of chip-firing games on graphs also follow from our general techniques and results.     

A Riemann–Roch theorem in tropical geometry

Recently, Baker and Norine have proven a Riemann–Roch theorem for finite graphs. We extend their results to metric graphs and thus establish a Riemann–Roch theorem for divisors on (abstract) tropical curves.     

Chip-firing via open covers

We investigate chip-firing with respect to open covers of discrete graphs and metric graphs. For the case of metric graphs we show that given an open cover and a sink q, stabilization of a divisor D is unique and that there is a distinguished configuration equivalent to D, which we call the critical configuration. Also, we show that given a double cover of the metric graph by stars, which is the continuous analogue of the sandpile model, the critical configurations are in bijection with reduced divisors. Passing to the discrete case, we interpret open covers of a graph as simplicial complexes on the vertex and observe that chip-firing with respect to a simplicial complex is equivalent to the model introduced by Paoletti [G. Paoletti. July 11 2007: Master in Physics at University of Milan, defending thesis “Abelian sandpile models and sampling of trees and forests”; supervisor: Prof. S. Caracciolo. http://pcteserver.mi.infn.it/caraccio/index.html]. We generalize this setup for directed graphs using weighted simplicial complexes on the vertex set and show that the fundamental results extend. In the undirected case we present a generalization of the Cori-Le Borgne algorithm for chip-firing models via open covers, giving an explicit bijection between the critical configurations and the spanning trees of a graph.(http://www.elsevier.com/locate/endm)     

Chip-Firing,Antimatroids, and Polyhedra

Starting from the chip-firing game of Björner and Lovász we consider a generalization to vector addition systems that still admit algebraic structures as sandpile group or sandpile monoid. Every such vector addition language yields an antimatroid. We show that conversely every antimatroid can be represented this way. The inclusion order on the feasible sets of an antimatroid is an upper locally distributive lattice. We characterize polyhedra, which carry an upper locally distributive structure and show that they can be modelled by chip-firing games with gains and losses. At the end we point out a connection to a membership problem discussed by Korte and Lovász.     

Homogeneous games as anti step functions

In this paper the class of homogeneousn-person games “without dummies and steps” is characterized by two algebraic axioms. Each of these games induces a natural vector of lengthn, called incidence vector of the game, and vice versa. A geometrical interpretation of incidence vectors allows to construct all of these games and to enumerate them recursively with respect to the number of persons. In addition an algorithm is defined, which maps each directed game to a minimal representation of a homogeneous game. Moreover both games coincide, if the initial game is homogeneous.     

Graph Invertibility

Extending the work of Godsil and others, we investigate the notion of the inverse of a graph (specifically, of bipartite graphs with a unique perfect matching). We provide a concise necessary and sufficient condition for the invertibility of such graphs and generalize the notion of invertibility to multigraphs. We examine the question of whether there exists a “litmus subgraph” whose bipartiteness determines invertibility. As an application of our invertibility criteria, we quickly describe all invertible unicyclic graphs. Finally, we describe a general combinatorial procedure for iteratively constructing invertible graphs, giving rise to large new families of such graphs.     

Tropical hyperelliptic curves

We study the locus of tropical hyperelliptic curves inside the moduli space of tropical curves of genus g. We define a harmonic morphism of metric graphs and prove that a metric graph is hyperelliptic if and only if it admits a harmonic morphism of degree 2 to a metric tree. This generalizes the work of Baker and Norine on combinatorial graphs to the metric case. We then prove that the locus of 2-edge-connected genus g tropical hyperelliptic curves is a (2g?1)-dimensional stacky polyhedral fan whose maximal cells are in bijection with trees on g?1 vertices with maximum valence 3. Finally, we show that the Berkovich skeleton of a classical hyperelliptic plane curve satisfying a certain tropical smoothness condition is a standard ladder of genus g.     

Generalizations of tournaments: A survey

We survey results concerning various generalizations of tournaments. The reader will see that tournaments are by no means the only class of directed graphs with a very rich structure. We describe, among numerous other topics mostly related to paths and cycles, results on hamiltonian paths and cycles. The reader will see that although these problems are polynomially solvable for all of the classes described, they can be highly nontrivial, even for these “tournament-like” digraphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 171–202, 1998     

Tug-of-War and Infinity Laplace Equation with Vanishing Neumann Boundary Condition

We study a version of the stochastic “tug-of-war” game, played on graphs and smooth domains, with the empty set of terminal states. We prove that, when the running payoff function is shifted by an appropriate constant, the values of the game after n steps converge in the continuous case and the case of finite graphs with loops. Using this we prove the existence of solutions to the infinity Laplace equation with vanishing Neumann boundary condition.     

Graph congruences and what they connote

Abstract

The algebraic notion of a “congruence” seems to be foreign to contemporary graph theory. We propound that it need not be so by developing a theory of congruences of graphs: a congruence on a graph G = (V, E) being a pair (～, ) of which ～ is an equivalence relation on V and is a set of unordered pairs of vertices of G with a special relationship to ～ and E. Kernels and quotient structures are used in this theory to develop homomorphism and isomorphism theorems which remind one of similar results in an algebraic context. We show that this theory can be applied to deliver structural decompositions of graphs into “factor” graphs having very special properties, such as the result that each graph, except one, is a subdirect product of graphs with universal vertices. In a final section, we discuss corresponding concepts and briefly describe a corresponding theory for graphs which have a loop at every vertex and which we call loopy graphs. They are in a sense more “algebraic” than simple graphs, with their meet-semilattices of all congruences becoming complete algebraic lattices.     

Graphes cubiques d'indice trois,graphes cubiques isochromatiques,graphes cubiques d'indice quatre

The process introduced by E. Johnson [Amer. Math. Monthly73 (1966), 52–55] for constructing connected cubic graphs can be modified so as to obtain restricted classes of cubic graphs, in particular, those defined by their chromatic number or their chromatic index. We construct here the graphs of chromatic number three and the graphs whose chromatic number is equal to its chromatic index (isochromatic graphs). We then give results about the construction of the class of graphs of chromatic index four, and in particular, we construct an infinite class of “snarks.”     

Intersection graphs of paths in a tree

The intersection graph for a family of sets is obtained by associating each set with a vertex of the graph and joining two vertices by an edge exactly when their corresponding sets have a nonempty intersection. Intersection graphs arise naturally in many contexts, such as scheduling conflicting events, and have been widely studied.We present a unified framework for studying several classes of intersection graphs arising from families of paths in a tree. Four distinct classes of graphs arise by considering paths to be the sets of vertices or the edges making up the path, and by allowing the underlying tree to be undirected or directed; in the latter case only directed paths are allowed. Two further classes are obtained by requiring the directed tree to be rooted. We introduce other classes of graphs as well. The rooted directed vertex path graphs have been studied by Gavril; the vertex path graphs have been studied by Gavril and Renz; the edge path graphs have been studied by Golumbic and Jamison, Lobb, Syslo, and Tarjan.The main results are a characterization of these graphs in terms of their “clique tree” representations and a unified recognition algorithm. The algorithm repeatedly separates an arbitrary graph by a (maximal) clique separator, checks the form of the resultant nondecomposable “atoms,” and finally checks that each separation step is valid. In all cases, the first two steps can be performed in polynomial time. In all but one case, the final step is based on a certain two-coloring condition and so can be done efficiently; in the other case the recognition problem can be shown to be NP-complete since a certain three-coloring condition is needed.The strength of this unified approach is that it clarifies and unifies virtually all of the important known results for these graphs and provides substantial new results as well. For example, the exact intersecting relationships among these graphs, and between these graphs and chordal and perfect graphs fall out easily as corollaries. A number of other results, such as bounds on the number of (maximal) cliques, related optimization problems on these graphs, etc., are presented along with open problems.     

A constant bound for the periods of parallel chip-firing games with many chips

We prove that any parallel chip-firing game on a graph G with at least 4|E(G)| − |V(G)| chips stabilizes, i.e., such a game has eventual period of length 1. Furthermore, we obtain a polynomial bound on the number of rounds before stabilization. This result is a counterpoint to previous results which showed that the eventual periods of parallel chip-firing games with few chips need not be polynomially bounded.     

New results on planar and directed multicuts

We show that the multicut problem is APX-hard in directed acyclic graphs, even with three source-sink pairs. We also show that it is tractable in planar graphs with a fixed number of terminals, and even FPT if all the terminals lie on the outer face.     

Orthogonal Surfaces and Their CP-Orders

Orthogonal surfaces are nice mathematical objects which have interesting connections to various fields, e.g., integer programming, monomial ideals and order dimension. While orthogonal surfaces in one or two dimensions are rather trivial already the three dimensional case has a rich structure with connections to Schnyder woods, planar graphs and three-polytopes. Our objective is to detect more of the structure of orthogonal surfaces in four and higher dimensions. In particular we are driven by the question which non-generic orthogonal surfaces have a polytopal structure. We review the state of knowledge of the three-dimensional situation. On that basis we introduce terminology for higher dimensional orthogonal surfaces and continue with the study of characteristic points and the cp-orders of orthogonal surfaces, i.e., the dominance orders on the characteristic points. In the generic case these orders are (almost) face lattices of polytopes. Examples show that in general cp-orders can lack key properties of face lattices. We investigate extra requirements which may help to have cp-orders which are face lattices. Finally, we turn the focus and ask for the realizability of polytopes on orthogonal surfaces. There are criteria which prevent large classes of simplicial polytopes from being realizable. On the other hand we identify some families of polytopes which can be realized on orthogonal surfaces.      

Wheels within wheels

A simple means of representing the structure of all strongly connected directed graphs is developed and applied to a certain problem involving the construction of “toll booths”.     

A further note on the nucleoous of the “airport game”

This paper represents a generalization of a previous paper on an “airport cost game” to the case of an “airport profit game”. A fee schedule in the airport profit game is obtained by subtracting the payoff vector from the vector of revenues. It is proved that the fee schedule corresponding to the nucleolus is independent of the revenue vector.     

On directed local chromatic number,shift graphs,and Borsuk‐like graphs

We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of “topologically t‐chromatic” graphs. We show that this minimum for large enough t‐chromatic Schrijver graphs and t‐chromatic generalized Mycielski graphs of appropriate parameters is ?t/4?+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 65‐82, 2010     

Constructing isospectral non‐isomorphic digraphs from hypergraphs

We explore the “oriented line graph” construction associated with a hypergraph, leading to a construction of pairs of strongly connected directed graphs whose adjacency operators have the same spectra. We give conditions on a hypergraph so that a hypergraph and its dual give rise to isospectral, but non‐isomorphic, directed graphs. The proof of isospectrality comes from an argument centered around hypergraph zeta functions as defined by Storm. To prove non‐isomorphism, we establish a Whitney‐type result by showing that the oriented line graphs are isomorphic if and only if the hypergraphs are. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 231–242, 2010