Graph theory and applications

• Grant number: 13/23331-2
• Support Opportunities: Scholarships abroad - Research Internship - Post-doctor
• Start date: February 01, 2014
• End date: January 31, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Yoshiko Wakabayashi
• Grantee: Andrea Patricia Jiménez Ramírez
• Supervisor: Robin Thomas
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Institution abroad: Georgia Institute of Technology, United States
• Associated to the scholarship: 11/19978-5 - Embeddings of Graphs on Surfaces and the Ising Model, BP.PD

Abstract

The aim of this project is to investigate several outstanding conjectureson structural graph theory and also to study questions on mathematicalphysics using graph-theoretical tools.The first set of problems of our interest are conjectures by Lovász and, by Norine and Thomas that arise from matching theory. We are interested in studying properties of minimal bricks such as the asymptotic behavior of their number of cubic vertices and the existence of edges with cubic end vertices. Secondly, we plan to investigate two theories that we have developed around the well-known directed cycle double cover conjecture of Jaeger. The aforementioned theories concern the study of a wide variety of topics, such as generation of graphs and connectivity theory. Closely related to double covers of graphs are decompositions of the edge set of graphs into disjoint subgraphs. Indeed, this is the third topic that our project involves. Specifically, we plan to study a famous conjecture of Gallai in the class of planar graphs. Finally, the last problem that we plan to explore, if time allows us, is an application of graph theory to the study of the Ising model. (AU)