Campus Event Calendar
Event Entry
What and Who
On the existence of Hamilton Cycles in Random Intersection Graphs
Charilaos Efthymiou
IMPRS-CS
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 26 February 2007
08:00
540 Minutes
E1 4
024
Saarbrücken
Abstract
Random Intersection Graphs G(n,m,p) is a class of random graphs
in which each of n vertices randomly and independently chooses
some elements from a universal set S, of cardinality
m. Each element is chosen with probability p. Two vertices are joined
by an edge iff their chosen element sets intersect. Given n, m so that
m=n^a, for any real a different than one, we establish here tight lower
bounds p_0(n,m), on the value of p, as a function of n and m, above which
the graph G_{n,m,p} is almost certainly Hamiltonian.
The bounds are tight in the sense that if p is asymptotically
smaller than p_0(n,m) then G(n,m,p) almost certainly has a vertex of
degree less than 2. The proof involves new coupling
techniques that allow us to circumvent the edge dependencies
in the random intersection graph model.
The results strongly support the existence of a threshold for
Hamiltonicity in G(n,m,p).-
in which each of n vertices randomly and independently chooses
some elements from a universal set S, of cardinality
m. Each element is chosen with probability p. Two vertices are joined
by an edge iff their chosen element sets intersect. Given n, m so that
m=n^a, for any real a different than one, we establish here tight lower
bounds p_0(n,m), on the value of p, as a function of n and m, above which
the graph G_{n,m,p} is almost certainly Hamiltonian.
The bounds are tight in the sense that if p is asymptotically
smaller than p_0(n,m) then G(n,m,p) almost certainly has a vertex of
degree less than 2. The proof involves new coupling
techniques that allow us to circumvent the edge dependencies
in the random intersection graph model.
The results strongly support the existence of a threshold for
Hamiltonicity in G(n,m,p).-
Contact
IMPRS
225
--email hidden
passcode not visible
logged in users only
Jennifer Gerling, 02/14/2007 09:41 -- Created document.