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 johanna.n.franklin@hofstra.edu for the Zoom meeting information.

Friday, October 30, 2020

Cost:

free

Categories:

Location:

Zoom
Zoom Link
Online, NY 00000


Contact:

Johanna Franklin

Phone: 516-463-5739

S M T W T F S
    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    
english
Submit Your Hofstra Event
PARKING NOTICE

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
Theme: