Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
McGill University Title: Densities of minor-closed families of graphs Abstract: The density of a sparse family of graphs is defined as the supremum of the ratio of the number of edges to the number of vertices over graphs in the family. For example, the density of forests is one, and the density of planar graphs is three. Eppstein has recently initiated a systematic study of the set of possible densities of minor-closed graph families. We answer one of his questions, showing that all such densities are rational. Based on joint work with Rohan Kapadia. |