



An Algebraic Monte-Carlo Algorithm for the Partition Adjacency Matrix Realization Problem
- Feb. 16, 2018
- 2:30 p.m.
- LeConte 312
Abstract
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