A kutatás három egymáshoz kapcsolódó témáról szólt: Ezek a sandpile csoport, a Tutte polinom és a gyökpolitóp.
Egy gráf sandpile csoportja egy Abel-csoport, melyet a chip-firing játékon keresztül lehet definiálni, és melynek rendje a feszítőfák száma. A sandpile csoport kapcsolódik az egyik legalapvetőbb gráf-polinomhoz, a Tutte polinomhoz. A gyökpolitóp egy irányított gráfokhoz rendelt rácspolitóp, melynek Ehrhart-féle h^*-polinomja szintén kapcsolódiok a Tutte polinomhoz.
A vezető kutató számos társszerzővel dolgozott együtt. Néhány eredményük: Chip-firing játékkal kapcsolatos problémák számítási nehézségét bizonyították, igazolták fizikusok egy megfigyelését a párhuzamos chip-firing aktivitásáról véletlen gráfokra, belátták hogy gráfok és matroidok sandpile csoportjának bizonyos csoporthatásai szépen viselkednek élösszehúzásra és éltörlésre nézve. Továbbá aktivitás generátor-függvény jellegű formulákat adtak hipergráfok Tutte polinomjára valamint gyökpolitópok h^*-polinomjára. Az Euler digráfok branching greedoid polinomját előállították mint gyökpolitóp h^*-polinomja. Gráfelméleti formulát adtak a gyökpolitóp h^*-polinomjának fokszámára, és sejtéseket fogalmaztak meg a szimmetrikus élpolitóp minimális térfogatú lapjaival kapcsolatban. Megmutatták hogy ez utóbbi probléma rokona az Euler-gráfok minimálisan sok feszítő fenyőt tartalmazó Euler-irányításának keresése, és néhány speciális esetben megoldották ezt a problémát.
kutatási eredmények (angolul)
The research concerned three related topics: The sandpile group, the Tutte polynomial, and root polytopes.
The sandpile group of a graph is an Abelian group whose cardinality equals the number of spanning trees. It is defined through the chip-firing game, and it has connections to the Tutte polynomial, which is one of the most fundamental graph polynomials. The root polytope is a lattice polytope assigned to a directed graph. The Ehrhart h^*-polynomial of this polytope is also related to the Tutte polynomial.
The PI worked together with several coathors. Some results: They proved computational hardness results about the chip-firing game, confirmed an observation of physicists on the activity of parallel chip-firing games on random graphs, and proved that some actions of the sandpile group of a graph or matroid behave well with respect to deletion or contraction. They proved activity generating function formulas for the Tutte polynomial of hypergraphs and for the h^*-polynomial of root polytopes. They expressed the greedoid polynomial of an Eulerian branching greedoid as an h^*-polynomial of a root polytope. They gave a graph-theoretic formula for the degree of the h^*-polynomial of a root polytope, and they formulated conjectures on facets of the symmetric edge polytope with minimal volume. They showed that the latter problem is related to finding the Eulerian orientation of an Eulerian graph with a minimal number of arborescences, that they solved in some special cases.
Tamás Kálmán, Lilla Tóthmérész: Degrees of interior polynomials and parking function enumerators, accepted for the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2022
Aditya Bandekar, Péter Csikvári, Benjamin Mascuch, Damján Tárkányi, Márton Telekes, Lilla Tóthmérész: Extremal number of arborescences, arXiv:2409.17893, 2024
