Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Local MINCUTs and the Ising model on Dense Random Graphs 

Reza Gheissari, NYU

Location:  Hill 705
Date & time: Monday, 22 January 2018 at 2:00PM - 3:00PM

Abstract:  Consider a dense Erdos--Renyi random graph G(n,p) with p>0 fixed. Can we partition the graph into two nonempty sets such that every vertex has more neighbors in its own set than in the other? Will a "greedy search" algorithm find such local MINCUTs or will it end up in one of the two trivial partitions ([n],emptyset)? We relate these two questions to the local energy minima of an Ising model on the random graph. While we leave open the question of whether/how many nontrivial local minima exist, one might expect that as in similar disordered systems, there are a rapidly diverging (in n) number of such local minima. We prove, however, that starting from a typical initial configuration, a dynamic search for local minima avoids all such local minima with high probability and quickly ends up in one of the two homogenous ground states (corresponding to the two trivial partitions).

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.