IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

An Algebraic Monte-Carlo Algorithm for the Partition Adjacency Matrix Realization Problem

  • Feb. 16, 2018
  • 2:30 p.m.
  • LeConte 312


The graphical realization of a given degree sequence and given partition adjacency matrix simultaneously is a relevant problem in data driven modeling of networks. Here we formulate common generalizations of this problem and the Exact Matching Problem, and solve them with an algebraic Monte-Carlo algorithm that runs in polynomial time if the number of partition classes is bounded. A further instance of the generalization: n men and n woman each has residence in one of the 50 states. Certain pairs can be married, certain pairs cannot. We have 50^2 additional constraints like how many woman from Arizona should marry men from Utah. Is there a perfect matching marrying all of them and satisfying all of the 50^2 conditions? Joint work with Eva Czabarka, Zoltan Toroczkai, and Shanise Walker

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster