Embeddings of Graphs on Surfaces and the Ising Model

• Grant number: 11/19978-5
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: June 01, 2012
• End date: February 28, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiko Wakabayashi
• Grantee: Andrea Patricia Jiménez Ramírez
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated scholarship(s): 13/23331-2 - Graph theory and applications, BE.EP.PD

Abstract

This project has two lines of research: the first one focuses on two fundamental problems in graph theory and the second one focuses on a topic in statistical physics. In the first line, the central objects are graphs, possibly with multiple edges but with no loops. The topic of our interest is the directed cycle double cover conjecture. This conjecture, posed by François Jaeger, is equivalent to the statement that every cubic bridgeless graph has an embedding in a closed Riemann surface with no dual loop. Our plan is to explore Jaeger's conjecture in its geometrical setting: we were able to reformulate it as a question about existence of special perfect matchings in a subclass of braces that we call hexagon graphs. This approach is motivated by the notion of a critical embedding of a graph on a closed Riemann surface, and has shown to be useful to tackle other problems that go beyond the conjecture we address in this project.In the second line, we focus on one of the most studied models of interacting particles in statistical physics: the Ising model. This model and its generalizations are used not only to explain physical phenomena, but also in biology to model neural networks, flocking birds, or beating hearts. Despite of the simplicity of the Ising model approach, its full solution is far from known, except for special cases of planar lattices. Our interest in the Ising model is justified by its strong relationship with discrete mathematics: tools and techniques developed in discrete mathematics have shown to be useful to treat problems on the Ising model and vice versa. Typically, to study the Ising model, particles are located at the vertices of a graph and the type of interaction between them is determined by the existence of (weighted) edges in the graph. In this project, we plan to analyze the Ising model in triangulations of closed Riemann surfaces.

Scientific publications

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

JIMENEZ, ANDREA; WAKABAYASHI, YOSHIKO. On path-cycle decompositions of triangle-free graphs. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, v. 19, n. 3, 2017. (11/19978-5, 13/03447-6)

JIMENEZ, ANDREA; KIWI, MARCOS. Antiferromagnetic Ising model in triangulations with applications to counting perfect matchings. DISCRETE APPLIED MATHEMATICS, v. 172, p. 45-61, JUL 31 2014. (11/19978-5)

JIMENEZ, ANDREA. Non-degenerated Ground States and Low-degenerated Excited States in the Antiferromagnetic Ising Model on Triangulations. Communications in Mathematical Physics, v. 326, n. 1, p. 167-183, FEB 2014. (11/19978-5)