The Edge of Graphicality

Many networks may be modelled as a collection of nodes with directed connections between the nodes. From the model, it is easy to observe local information about the nodes, such as the number of connections, but more difficult to observe global information. At the edge of graphicality are those networks where the local information determines the global structure of the network. I present a characterization of networks where only knowledge of how many connections arrive and depart each node is enough to know exactly which connections exist in the network.

Joint work with M. Drew LaMar, Brian Cloteaux, and James Shook.

Speaker Bio: Dr. Elizabeth Moseman got her Ph.D. in mathematics from Dartmouth College under Dr. Peter Winkler. After 3 years of teaching at the United States Military Academy at West Point, she came to NIST as an NRC postdoctoral fellow to study applications of combinatorics, specifically in the area of probabalistic graph algorithms.

Presentation Slides: PDF

Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3668; at least 24 hours in advance.