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