Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

A magic square is a square matrix whose entries are nonnegative integers and whose row sums, column sums, and main diagonal sums add up to a common sum called the magic sum. A magic labeling of a graph is an assignment of a nonnegative integer to each edge of the graph such that for each vertex $v$ of the graph the sum of the labels of all edges incident to $v$ is a common sum. In my talk I will describe methods from algebra, combinatorics, and polyhedral geometry, to construct and enumerate magic squares, magic labelings of graphs, and perfect matchings of graphs. The symmetric magic polytope is defined to be the convex hull of all real nonnegative nxn symmetric matrices such that the entries of each row (and therefore column) add to one. I will define the polytopes of magic labelings of graphs with n vertices and show that they are the faces of the symmetric magic polytope. I will give a description of the faces of the Birkhoff polytope as polytopes of magic labelings of digraphs, and also show that copies of the Birkhoff polytope occur as special faces of the symmetric magic polytope.