BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Lilla Tóthmérész contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Using a ribbon structure of the graph, we construct a dissection of the symmetric edge polytope of a graph into unimodular simplices. Our dissection is shellable, and one can interpret the elements of the resulting $h$-vector via graph theory. This gives an elementary method for computing the $h^*$-vector of the symmetric edge polytope.
Chip-firing and rotor-routing are two well-studied examples of abelian networks. We study the complexity of their respective reachability problems. We show that the rotor-routing reachability problem is decidable in polynomial time, and we give a simple characterization of when a chip-and-rotor configuration is reachable from another one. For chip-firing, it has been known that the reachability problem is in P if we have a class of graphs whose period length is polynomial (for example, Eulerian digraphs). Here we show that in the general case, chip-firing reachability is hard in the sense that if the chip-firing reachability problem were in P for general digraphs, then the polynomial hierarchy would collapse to NP. We encode graphs by their adjacency matrix, and we encode ribbon structures "succinctly", only remembering the number of consecutive parallel edges.
Recently O. Bernardi gave a formula for the Tutte polynomial $T(x,y)$ of a graph, based on spanning trees and activities just like the original definition, but using a fixed ribbon structure to order the set of edges in a different way for each tree. The interior polynomial $I$ is a generalization of $T(x,1)$ to hypergraphs. We supply a Bernardi-type description of $I$ using a ribbon structure on the underlying bipartite graph $G$. Our formula works because it is determined by the Ehrhart polynomial of the root polytope of $G$ in the same way as $I$ is. To prove this we interpret the Bernardi process as a way of dissecting the root polytope into simplices, along with a shelling order. We also show that our generalized Bernardi process gives a common extension of bijections (and their inverses) constructed by Baker and Wang between spanning trees and break divisors.
Baker and Norine introduced a graph-theoretic analogue of the Riemann-Roch theory. A central notion in this theory is the rank of a divisor. In this paper we prove that computing the rank of a divisor on a graph is NP-hard. The determination of the rank of a divisor can be translated to a question about a chip-firing game on the same underlying graph. We prove the NP-hardness of this question by relating chip-firing on directed and undirected graphs.
In [5], Holroyd, Levine, Mészáros, Peres, Propp and Wilson characterize recurrent chip-and-rotor configurations for strongly connected digraphs. However, the number of steps needed to recur, and the number of orbits is left open for general digraphs. Recently, these questions were answered by Pham [6], using linear algebraic methods. We give new, purely combinatorial proofs for these formulas. We also relate rotor-router orbits to the chip-firing game: The number of recurrent rotor-router unicycle-orbits equals the order of the Picard group of the graph, defined in the sense of [1], and during a period, the same chip-moves happen, as during firing the period vector in the chip-firing game.
We prove several combinatorial properties of suffix arrays, including a characterization of suffix arrays through a bijection with a certain well-defined class of permutations. Our approach is based on the characterization of Burrows-Wheeler arrays given in [1], that we apply by reducing suffix sorting to cyclic shift sorting through the use of an additional sentinel symbol. We show that the characterization of suffix arrays for a special case of binary alphabet given in [2] easily follows from our characterization. Based on our results, we also provide simple proofs for the enumeration results for suffix arrays, obtained in [3]. Our approach to characterizing suffix arrays is the first that exploits their relationship with Burrows-Wheeler permutations.