DEPARTMENT OF MATHEMATICAL SCIENCES

APPLIED AND COMPUTATIONAL MATHEMATICS SEMINAR

**Speaker:** Ed Scheinerman, Applied Math, Johns Hopkins University

**Title: **
Random threshold graph

**Abstract:**
A \emph{random threshold graph} is a simple graph with vertex set
$\{1,2,\ldots,n\}$ that is generated as follows: Let
$x_1,x_2,\ldots,x_n$ be $n$ values chosen uniformly and independently
from $[0,1]$. Join distinct vertices $u$ and $v$ by an edge if and
only if $x_u + x_v > 1$. We discuss various properties of random
threshold graphs. For example, the probability that a random threshold
graph on $n$ vertices has a Hamiltonian cycle is asymptotically
$1/\sqrt{2\pi n}$. This is joint work with Elizabeth Reilly.

**Time:** Friday, November 14, 2008, 1:30-2:30 p.m.

**Place:** Science and technology I, Room 242

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