Math department seminar: Dr. Jennifer Chubb, 'Distance functions on computable graphs'

Abstract: An infinite graph---one made of nodes and edges---is computable if there is an algorithm that can decide whether or not a given pair of nodes is connected by an edge. So, for example, the internet is a computable graph which is, for all intents and purposes, infinite. Now, given two nodes on a connected, computable graph, a natural question to ask is, What is the length of the shortest path between them, i.e., the distance between the nodes? Of course, for a connected graph we can always find such a path and determine its length, but the question of finding a shortest path is harder, and is not in general something we can compute for infinite computable graphs. 

In this talk, we will see what it means for something to be non-computable via a classic example called the halting problem. Next we will see that it's possible to encode non-computable information into even very simple computable mathematical objects. Finally, we will see how non-computable information can be encoded into the distance function, the function which outputs the shortest distance between two nodes, of a given graph. So, the answer to "What is the shortest path between two nodes?" Well, we may never know for sure. 

This work is joint with Wesley Calvert and Russell Miller.

Speaker: Dr. Jennifer Chubb, University of San Francisco


Please contact Dr. Johanna Franklin (Mathematics) at for the Zoom meeting information.

Friday, October 30, 2020





Zoom Link
Online, NY 00000


Johanna Franklin

Phone: 516-463-5739

    01 02 03 04 05
06 07 08 09 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
Submit Your Hofstra Event

Hofstra University is pleased to have the public join us for some of our on-campus events, which are held for the benefit of our students. Please be aware, when attending events during the school year, when classes are in session, parking is often limited on South Campus to faculty and students. There is additional parking available on North Campus, approximately a 10-minute walk from Adams Playhouse, through the Student Center and over the unispan. Thank you for your cooperation.
Newest Events