Undergraduate Honors Theses

Thesis Defended

Spring 2018

Document Type

Thesis

Type of Thesis

Departmental Honors

Department

Mathematics

First Advisor

Dr. Sean O'Rourke

Abstract

In this paper, we will discuss new methods for finding planted cliques within Erdős–Rényi random graphs. An Erdős–Rényi random graph is a graph with n vertices, where each vertex is connected to each other vertex with some probability p, independent of all other choices. The planted clique problem asks us to find the most efficient way to find a planted clique in an Erdős–Rényi random graph. A planted clique is a secretly chosen set of vertices in the graph that are purposefully connected with edges added to the graph until all of the selected vertices are connected. There are many other similar problems which have been posed and examined, regarding finding patterns in random graphs or matrices. This paper will begin briefly by discussing previous methods for finding planted cliques in Erdős–Rényi random graphs. It will then present two algorithms for finding planted cliques, one which finds any number of disjoint cliques, and another which finds only one planted clique. Disjoint implies that none of the points can be included in more than one clique. The paper will then prove theorems that state that these algorithms will find such planted cliques, under certain assumptions on some parameters. These theorems are the main results of the paper, and the algorithms can be run in polynomial time. Finally, the paper will discuss the improvements made using these algorithms over previous methods, such as the fact that it is no longer necessary to know the size of a planted clique to find it, and suggest areas of future research.

Share

COinS