Matroids and graphs

• Grant number: 15/10323-7
• Support Opportunities: Research Grants - Visiting Researcher Grant - International
• Duration: July 11, 2015 - August 23, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Cristina Gomes Fernandes
• Grantee: Cristina Gomes Fernandes
• Visiting researcher: Jorge Luis Paulo Ramirez Alfonsín
• Visiting researcher institution: Université Montpellier 2, France
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated research grant: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM

Abstract

This project lies in the area of discrete mathematics and combinatorics, and is associated to a two months long visit to the Department of Computer Science of the Institute of Mathematics and Statistics of the University of São Paulo. We are interested in studying problems relating notions of graphs and matroids. Matroid theory is a subject gathering several areas. It helps to explain and to discover the common properties of such areas. Studying problems in this more general setting often provides new insight to different problems and their connections. The theory of matroid can be approached from many different points of view. A matroid can be defined as a simplicial complex of independent sets, a lattice of flats, a closure relation, and in many other different ways. A relatively new point of view is the study of matroid polytopes, which in some sense, are the natural combinatorial setting of matroids in algebraic geometry and optimisation. A better conceptual and mathematical understanding of matroid polytopes is required since this would have significant algorithmic and theoretical consequences. The goal of this project is to develop the study of matroid polytopes and its interactions with other subjects. The project is divided into two connected parts. Firstly, we shall study combinatorial properties of the base matroid graphs, that is, the graphs associated to the 1-skeleton of matroid polytopes. Secondly, we will investigate the major cut set expansion matroid problem. (AU)

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)

FERNANDES, CRISTINA G.; HERNANDEZ-VELEZ, CESAR; DE PINA, JOSE C.; ALFONSIN, JORGE LUIS RAMIREZ. Counting Hamiltonian Cycles in the Matroid Basis Graph. GRAPHS AND COMBINATORICS, v. 35, n. 2, p. 539-550, MAR 2019. (13/03447-6, 12/24597-3, 15/10323-7)

KOLPAKOV, ALEXANDER; ROBINS, SINAI. SPHERICAL TETRAHEDRA WITH RATIONAL VOLUME, AND SPHERICAL PYTHAGOREAN TRIPLES. Mathematics of Computation, v. 89, n. 324, p. 2031-2046, JUL 2020. (15/10323-7)

FERNANDES, CRISTINA G.; DE PINA, JOSE C.; ALFONSIN, JORGE LUIS RAMIREZ; ROBINS, SINAI. Cubic Graphs, Their Ehrhart Quasi-Polynomials, and a Scissors Congruence Phenomenon. DISCRETE & COMPUTATIONAL GEOMETRY, v. 65, n. 1, APR 2020. (15/10323-7, 13/03447-6)