SIR Computer Science Investigation Abstract
CONNECTIVITY IN RANDOM GRAPHS
Presenter:
Sujeeth Bharadwaj, Illinois Mathematics and Science Academy
Advisor:
Dr. Ezra Getzler, Northwestern University
Abstract:
Graphs are representations of relationships between objects. In a graph, objects are represented by vertices and the relationships are represented by edges. A graph is connected if there exists a path between any two vertices a and b in the graph. The ratio of connected graphs to all graphs with n vertices increases with n. Although this problem was explored in the fifties by Erdos and Renyi, we explored how these ratios can be estimated using a computer program. Since computers iterate through all possibilities, this method becomes time-consuming for larger values of n. Therefore, I will also explain how to arrive at an explicit formula to calculate this ratio.