Automated Conjecture Making: Independence in Graphs

Overview

Research in mathematics is largely motivated by conjectures, some of which have been unsolved for tens or even hundreds of years (see: Open Problem Garden, Erdös Problems on Graphs, List of conjectures, Unsolved Problems, The Millennium Prize Problems). Historically, these conjectures have been generated by humans. In recent years, there has been much progress in automated conjecture making, which is the process of having a computer generate conjectures. Since computers can carry out millions of operations per second, computers can generate mathematical questions potentially overlooked by humans.

Graph theory is the study of graphs, which are made up of dots, called vertices, and lines connecting the vertices, called edges. An independent set of a graph is a collection of the vertices, no two of which are connected by an edge. The red vertices in the graphs pictured to the right are independent sets. Independent sets have a wide array of applications, including predicting the stability of chemical compounds, optimizing the configuration of GPS networks, and scheduling theory.

Weisstein, Eric W. "Independent Set." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/IndependentSet.html

We will use SageMath and an automated conjecture making program to research independent sets of graphs. Our goals will be to:

    • explore what is possible in the automation of mathematics,
    • generate conjectures that will advance research on independent sets of graphs, and
    • prove or disprove the conjectures generated.

Desirable Experiences for Applicants

Applicants should have an introduction to proofs course and a familiarity with graph theory (coursework in graph theory is preferred but not necessary). We will spend a considerable amount of time coding in SageMath and Python, so it would be advantageous to have experience in one or both of these. At a minimum, an applicant should be interested in the use of coding and computation. The most important qualifications are a positive attitude, an inquisitive mind, and perseverance.

How to apply

For application information and instructions, please visit the GVSU Summer Mathematics REU home page.