independent sets and 2-independent sets in random d-regular graphs
by
Hilda Assiyatun
The University of Melbourne
Coauthors: N.C. Wormald

A set I of vertices of a graph G=(V, E) is independent if no two vertices of I are joined by an edge of G. A set S of vertices a graph G=(V, E) is k-independent if it is independent and the distance between any two vertices in it is at least k+1.

In this talk we discuss the application of the small subgraph conditioning method to show the existence asymptotically almost surely (a.a.s) of independent sets and 2-independent sets in random d-regular graphs. This method is originally due to Robinson and Wormald when they proved the almost sure hamiltonicity of random d-regular graphs. The largest size of these sets obtained by this method provide almost sure lower bounds on the size of the maximum independent set and the maximum 2-independent set in such graphs.

Date received: November 9, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-41.