### GEORGE MASON
UNIVERSITY

DEPARTMENT OF MATHEMATICAL
SCIENCES

COLLOQUIUM

NOVEMBER 20, 2015

**Speaker: **
Jennifer Chubb, University of San Francisco

**Title: ***
Distance functions on computable graphs
*

**Abstract:**
A graph is computable if its edge relation is algorithmically decidable. Given two vertices on a connected computable graph, we can ask, "what is the length of the shortest path between them." Of course for a connected graph we can always algorithmically find a path and determine its length, but the question of finding a shortest path is harder and is not in general computable for infinite graphs.

In considering the question of the computational complexity of the distance function on computable graphs, a number of interesting issues arise. We'll begin by looking at effective properties of the family of functions that, like the distance function, have a computable, decreasing approximation. Next, we'll study the specific example of the distance function of a computable graph. We'll see that functions that are computably approximable from above can be coded, in rather a strong sense, into such a distance function, and so this question is, in a sense, as hard as it could possibly be.

This work is joint will Wesley Calvert and Russell Miller.

**Time:** Friday, November 20, 2015, 3:30-4:20 p.m.

**Place:** Exploratory Hall, room 4106

**Refreshments** will be served at 3:00 p.m.

Department of Mathematical Sciences

George Mason University

4400 University Drive, MS 3F2

Fairfax, VA 22030-4444

http://math.gmu.edu/

Tel. 703-993-1460, Fax. 703-993-1491